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 之类的东西，这将允许您使用索引组合来在一系列操作中获得良好的性能。其中一个示例与您尝试做的事情有非常相似的感觉。

在尝试使用类似的东西之前，您应该分析您的实际使用情况以确定优化该部分代码是否有任何真正的好处，然后如果它被证明是一个瓶颈，请尝试许多不同的结构组合以查看哪个一个实际上在您的特定用途上表现最好。除非您的数据集非常大，否则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 回答