0

ノードを見つけるたびにリストの先頭から開始することを避ける方法を探していたので、ノードにインデックスを割り当て、ランダムな (完全にランダムではない; 以下を参照) ノードへのポインターを保持してから、見つけたいインデックスに最も近いポインタを見つけます。コードで説明させてください：

// 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;        
    }
}

これは頭​​から始めて何度も前に進むよりも効率的ですか?

4

4 に答える 4

4

あなたが発明しようとしているように私には思えますSkip Lists、これは一種のバランスのとれたソートされたツリーです。

おそらく本当に必要なのは、boost::multi_index のようなものを使用することです。これにより、インデックスの組み合わせを使用して、さまざまな操作で優れたパフォーマンスを得ることができます。例の1つは、あなたがやろうとしていることと非常によく似ています。

このようなものを使用する前に、実際の使用状況をプロファイルして、コードのその部分を最適化することで実際にメリットがあるかどうかを判断し、それがボトルネックであることが判明した場合は、さまざまな構造の組み合わせを試して、実際には、特定の用途で最高のパフォーマンスを発揮します。データ セットが非常に大きい場合std::vectorを除き、局所性のため、ほとんどの場合 a が最速です。

于 2009-07-03T22:41:28.720 に答える
2

リストの途中にある要素にアクセスする必要がある場合は、配列を使用することをお勧めします。リストは、さまざまな方法で実装できる抽象データ構造 (ADT) です。基本的に行ったことは、両方の方法のオーバーヘッドを持つ冗長な表現を作成することです。

リンクされたリストの利点は、挿入がリストの先頭で非常に高速になる可能性があることです-配列のO(1)対O(n)。ただし、インデックスを維持する必要があるため、挿入にはとにかく O(N) のオーバーヘッドがあります。

インデックスが必要な場合は、配列を使用してください。より簡単に、より速く。

于 2009-07-03T22:36:50.507 に答える
0

挿入ははるかに高価になるようです。テスト プログラムを作成して、その差を計測してみませんか?

于 2009-07-03T22:36:22.160 に答える
0

疑似ランダム インデックスは、リストの先頭に近い可能性があり (例を示すだけです)、その後リスト内のすべての要素がシフトする可能性があります。これにより、リンクされたリストへの挿入が非常に高価になり、リンクされたリストを持つことが無意味になり、配列を使用するだけで済みます。

于 2009-07-03T22:38:26.307 に答える