링크 된 목록 :이 솔루션이 좋습니까?

Question

나는 노드를 찾고 싶을 때마다 목록의 머리부터 시작하는 것을 피할 방법을 찾고 있었기 때문에 노드에 인덱스를 할당하고 무작위 (정확히 무작위는 아니며 아래 참조) 노드에 포인터를 유지할 것을 고려했다. 찾을 인덱스에 가장 가까운 포인터를 찾습니다. 코드로 설명하도록 허용 :

// head and last are pointers to the first and last items of a doubly-linked list 
// current is a pointer that will change over time. It's used as a temporary pointer 
template <class T>a 
Node<T>* List<T>::get_closest(Node<T> node, int& difference) { 
    int curr_to_i = current->index - node->index; 
    int last_to_i = last->index - node->index; 
    Node* closest = node->index < abs(curr_to_i) ? head : current; 
    closest = closest->index < abs(last_to_i) ? closest : last; 
    difference = closest->index - node->index; 
    return closest; 
} 

/* 
* This functions adds a node with the given value to the given index. The node at that 
* index and all the following are moved, and the new node is inserted before them. 
*/ 
template <class T> 
bool List<T>::add(T value, int index) { 
    if (index < 0) { //Invalid index 
     return false; 
    } else if (index == last->index +1) { 
     push(value); 
     return true; 
    } else if (index > 0) { 
     Node* new_n = new Node; 
     new_n->value = value; 
     new_n->index = index; 
     int difference; 
     Node* closest = get_closest(new_n, difference); 
     if (difference < 0) { 
      for (int i = 0; i < abs(difference); i++) { 
       current = current->previous; 
      } 
     } else if (difference > 0) { 
       for (int i = 0; i < abs(difference); i++) { 
       current = current->next; 
      } 
     } /* current now points to the node we want to move */ 
     new_n->previous = current->previous; 
     new_n->next = current; 
     current->previous->next = new_n; 
     current->previous = new_n; 
     if (index == 0) { 
      root = new_n; 
     } 
     new_n = new_n->next; 
     while (new_n != null) { 
      new_n->index++; 
      new_n = new_n->next; 
     } 
     return true;   
    } 
} 

머리에서 시작하여 앞으로 몇 번 앞으로 나아가는 것보다 효율적입니까?

Answer 1

목록의 중간에있는 요소에 액세스해야하는 경우 배열을 사용하는 것이 좋습니다. 목록은 다양한 방식으로 구현 될 수있는 추상 데이터 구조 (ADT)입니다. 기본적으로 수행 한 작업은 두 가지 방법의 오버 헤드가있는 중복 표현을 만드는 것입니다.

링크 된 목록의 장점은 배열의 O (1) 대 O (n) 목록의 머리글에서 매우 빠르게 삽입 할 수 있다는 것입니다. 그러나 인덱스를 유지 관리해야하므로 삽입을 위해 O (N) 오버 헤드가 있습니다.

색인 생성이 필요하면 배열을 사용하십시오. 더 빠르고 간단합니다.

Answer 2

삽입이 훨씬 비쌉니다. 왜 테스트 프로그램을 작성하고 시간을 다르게하지 않습니까?

Answer 3

의사 랜덤 인덱스는 잠재적으로 목록의 시작 부분에 가깝게 나타날 수 있습니다 (설명의 편의상). 이후 목록의 모든 요소가 변경됩니다. 이렇게하면 링크 된 목록에 삽입하는 작업이 매우 비싸서 링크 된 목록을 갖는 것이 무의미 해 지므로 배열을 사용할 수 있습니다.

Answer 4

균등 정렬 트리의 일종 인 Skip Lists을 발명하려고하는 것처럼 들립니다.

아마 당신이 원하는 것은 boost :: multi_index와 같은 것을 사용하는 것입니다. 이것은 인덱스의 조합을 사용하여 다양한 작업에서 좋은 성능을 얻을 수있게 해줍니다. examples 중 하나는 사용자가하려는 것과 매우 유사한 느낌을줍니다.

이와 같은 것을 사용하기 전에 코드의 해당 부분을 최적화하는 실질적인 이점이 있는지를 확인하기 위해 실제 사용 환경을 프로파일 링해야하며 병목 현상이 발생하면 많은 다양한 조합을 시도하십시오. 구조를 사용하여 특정 용도에서 실제로 어느 것이 가장 잘 수행되는지 확인하십시오. 데이터 세트가 매우 큰 경우가 아니면 std::vector은 지역성 때문에 거의 항상 가장 빠릅니다.