설명상의 특기항

큐의 개념으로서, 「꺼내는 장소를 순서의 최초」 「추가하는 장소를 순서의 마지막」이라고 나타내는 경우가 많지만, 물리적인 위치의 도시를 하는 관계상
・처음:왼쪽
・마지막:우측
로 간주한다.

Javascript의 배열형은 왼쪽에서 추가(unshift)·삭제(shift)가 느린

(왼쪽에서 추가하는 횟수를 2배로 하면, 2배를 확실히 넘는 처리 시간이 되어 버린다)

이로 인해 발생하는 문제

Javascript에서 폭 우선 탐색(01BFS)의 문제 해결에 있어서, 처리 시간이 넥이 된다.
폭 우선 탐색의 기본 구현은 큐에 준한다. 그래서 하고 싶은 조작은 「큐의 좌단으로부터 꺼내는 것, 우단에 추가하는 것」이다.

・사용하는 데이터 구조는 배열형
・배열형이 서포트하고 있는 shift 메소드, push 메소드를 사용한다
된다고 생각된다.

기본 코드는 다음과 같습니다. 정점 0을 시점으로 한 폭 우선 탐색으로 한다.

normal.js

//頂点と隣接リスト群。コード例すべてで共通。
var node = [
  {
    depth : -1,
    edges : [1, 3, 5]
  },
  {
    depth : -1,
    edges : [2, 4]
  },
  ....
];

var queue = [0];

while(queue.length > 0){
  var now = queue.shift();
  var edges = node[now].edges;
  for(var i = 0; i < edges.length; i++){
    var next = edges[i];
    if(node[next].depth == -1){
       node[next].depth = node[now].depth + 1;
       queue.push(next);
    }
  }
}

처리 시간은 나중에.

빠른 대기열 만들기

우선 큐를 만들기 위한 발상이 나올 때부터
큐의 출입 방법은 「척척법」과 같은 생각을 가질 수 있다.

큐에 대한 정보로서, 「다음에 꺼내는 위치」를 정의한다.
・꺼내면 1개 오른쪽으로 진행한다.
· "꺼내는 위치"와 "queue의 크기"가 일치했을 때 (= 꺼낼 곳에 아무 것도 없다), 처리를 종료한다.

꺼내기 위치를 결정함으로써 척취충
・꺼내기 위치:뒷발
・추가시의 배열의 크기:앞발
가 결정되었다고 말할 수 있다.



insectMoth.js

var queue = [0];
var pollIndex = 0;//取り出し位置

while(pollIndex < queue.length){
  var now = queue[pollIndex];
  pollIndex++;//取り出し位置更新
  var edges = node[now].edges;
  for(var i = 0; i < edges.length; i++){
    var next = edges[i];
    if(node[next].depth == -1){
       node[next].depth = node[now].depth + 1;
       queue.push(next);
    }
  }
}

//私の提出コード漁ったら「追加する位置」も定義してるものがあるが必要なし

처리 시간은 나중에.

대기열은 가능했지만 양단 대기열이 아니기 때문에 만듭니다.

01BFS는 「좌측에 추가」가 상정되므로, 위치의 지정이 마이너스가 될 가능성이 있다.
그러나 배열 형은 마이너스 위치를 지정하거나 그 위치에 값을 둘 수 없습니다.

🤔?


···사용할 수 없기 때문에 배열형으로부터 오브젝트형으로 변경한다.

이번에는 좌우 각각에서 「다음에 추가하는 위치」를 정의한다. (검은 화살표)
「꺼내는 위치」는 자동으로 정해진다(흰색 화살표)



그대로는 사용할 수 없으므로 보정을 실시한다.

・요소수가 0개→1개로 변화할 때
어느 방향에서 추가했는지에 관계없이 추가했을 때의 장소가 "X"일 때,
다음에 추가하는 위치는
왼쪽: X-1
오른쪽: X+1

・요소수가 1개→0개로 변화할 때
어느 쪽에서 삭제했는지에 관계없이, 다음에 추가하는 위치는 좌우 모두 동일해진다.

왼쪽에서 삭제: 오른쪽 추가 위치를 왼쪽으로 1개 이동
오른쪽에서 삭제: 왼쪽 추가 위치를 오른쪽으로 1개 이동



ArrayDeque.js

var queue = {
  firstIndex : 0,
  lastIndex : 0,
  map : {},
  shift : function(){
    if(this.nullCheck()){
      return null;
    }
    var retVal = this.map[this.firstIndex + 1];
    this.firstIndex++;
    if(Math.abs(this.firstIndex - this.lastIndex) == 1){
      this.lastIndex--;
    }
    return retVal;
  },
  unshift : function(V){
    this.map[this.firstIndex] = V;
    if(this.nullCheck()){
      this.lastIndex++;
    }
    this.firstIndex--;
  },
  pop : function(){
    if(this.nullCheck()){
      return null;
    }
    var retVal = this.map[this.lastIndex - 1];
    this.lastIndex--;
    if(Math.abs(this.firstIndex - this.lastIndex) == 1){
      this.firstIndex++;
    }
    return retVal;
  },
  push : function(V){
    this.map[this.lastIndex] = V;
    if(this.nullCheck()){
      this.firstIndex--;
    }
    this.lastIndex++;
  },
  nullCheck : function(){
    return this.firstIndex == this.lastIndex;
  }
}

queue.push(0);
while(!queue.nullCheck()){
  var now = queue.shift();
  var edges = nodes[now];
  for(var i = 0; i < edges.length; i++){
    var next = edges[i];
    if(node[next].depth == -1){
      node[next].depth = node[now].depth + 1;
      queue.push(next);
    }
  }
}

처리 시간

정점수 10만, 변수 20만 정도로 시험한다.

· 첫 번째: 652ms
・다음: 154ms
・마지막:129ms

범용성의 의미에서도 양단 큐를 상정한 오브젝트로 하면 무 문제.

부산물

Java의 ArrayDeque와 달리, 큐내의 임의의 위치의 값을 보거나 재기록하거나 할 수가 있다.
핀 포인트이지만, 이 문제의 정답에 공헌했다.

가능한 불편함

검색시 값의 물리적 삭제는 수행되지 않습니다. 따라서 낭비가 남는다. 이것이 원인의 불편은 미확인이기 때문에, 지금의 곳 스루 하고 있다.

끝에

눈치 채면 만들 수 있었다.
처리 비용이 높은 문제와 그 해결 방법에 대해서, 유제의 기사가 별로 발견되지 않기 때문에 사례 소개로 투고했다.

・스택 2개로 큐를 실현