23

我正在尝试使用最小的额外内存开销来实现一个性能与 BST 一样好的跳过列表,目前即使不考虑任何内存限制,我的 SkipList 实现的性能甚至与非常幼稚的平衡 BST 实现相距甚远 -可以这么说,手工制作的 BTS :) -

作为参考,我使用了 William Pugh PUG89的原始论文和我在 Sedgewick -13.5- 的 C 算法中找到的实现。我的代码是递归实现,下面是插入和查找操作的线索:

sl_node* create_node()
{
    short lvl {1};
    while((dist2(en)<p)&&(lvl<max_level))
        ++lvl;
    return new sl_node(lvl);
}

void insert_impl(sl_node* cur_node,
        sl_node* new_node,
        short lvl)
{
    if(cur_node->next_node[lvl]==nullptr || cur_node->next_node[lvl]->value > new_node->value){
        if(lvl<new_node->lvl){
            new_node->next_node[lvl] = cur_node->next_node[lvl];
            cur_node->next_node[lvl] = new_node;
        }
        if(lvl==0) return;
        insert_impl(cur_node,new_node,lvl-1);
        return;
    }
    insert_impl(cur_node->next_node[lvl],new_node,lvl);
}
sl_node* insert(long p_val)
{
    sl_node* new_node = create_node();
    new_node->value = p_val;
    insert_impl(head, new_node,max_level-1);
    return new_node;
}

这是查找操作的代码:

sl_node* find_impl(sl_node* cur_node,
        long p_val,
        int lvl)
{
    if(cur_node==nullptr) return nullptr;
    if(cur_node->value==p_val) return cur_node;
    if(cur_node->next_node[lvl] == nullptr || cur_node->next_node[lvl]->value>p_val){
        if(lvl==0) return nullptr;
        return find_impl(cur_node,p_val,lvl-1);
    }
    return find_impl(cur_node->next_node[lvl],p_val,lvl);
}

sl_node* find(long p_val)
{
    return find_impl(head,p_val,max_level-1);
}

sl_node -skip list node- 看起来像这样:

struct sl_node
{
    long  value;
    short lvl;
    sl_node** next_node;

    sl_node(int l) : lvl(l)
    {
        next_node = new sl_node*[l];
        for(short i{0};i<l;i++)
            next_node[i]=nullptr;
    }
    ~sl_node()
    {
        delete[] next_node;
    }
};

正如你所看到的,与本书的实现相比,这个实现没有什么特别或先进的,我不会分享平衡的 BTS 代码,因为我认为这里不需要,但它是一个非常基本的 BTS,在当新节点高度大于 16*lg(n) 时插入,其中 n 是节点数。

可以这么说,只有当最大高度比最佳理论高度高 16 倍时,我才重新平衡这三个,正如我所说,这个简单的自制 BST 比自制的跳过列表要好得多。

但首先,让我们看一些数据,使用 p=.5 和 n=262144 时,SkipList 中节点的级别具有以下分布:

1:141439, 53.9547%
2:65153, 24.8539%
3:30119, 11.4895%
4:13703, 5.22728%
5:6363, 2.42729%
6:2895, 1.10435%
7:1374, 0.524139%
8:581, 0.221634%
9:283, 0.107956%
10:117, 0.044632%
11:64, 0.0244141%
12:31, 0.0118256%
13:11, 0.00419617%
14:5, 0.00190735%
15:1, 0.00038147%
16:5, 0.00190735%

这几乎完美 - 哦,这是一个大问题! - 符合文章中的理论,即:50% 级别 1,25% 级别 2 等等。输入数据来自我最好的可用伪随机数生成器,即 std::random_device 和 std::default_random_engine 和统一的 int 分布。输入对我来说看起来很随机:)!

在我的机器上搜索“所有”SkipList 中的“所有”262144 个元素所需的时间(以随机顺序)为 315 毫秒,而对于幼稚 BTS 上的相同搜索操作,所需时间为 134 毫秒,因此 BTS 几乎比跳过列表。这并不是我对“跳过列表算法与平衡树具有相同的渐近预期时间界限并且简单、快速且使用更少空间” PUG89 所期望的

SkipList 节点“插入”所需的时间为 387 毫秒,BTS 为 143 毫秒,同样,简单的 BST 性能更好。

如果不是使用输入数字的随机序列,而是使用排序序列,事情会变得更有趣,这里我可怜的自制 BST 变得很慢,并且插入 262144 个排序的 int 需要 2866 毫秒,而 SkipList 只需要 168 毫秒。

但是,到了搜索时间,BST 还是更快!对于排序后的输入,我们有 234 毫秒和 77 毫秒,这个 BST 快 3 倍。

使用不同的 p 因子值,我得到的性能结果略有不同:

在此处输入图像描述

在此处输入图像描述

最后但并非最不重要的一点是内存使用图,正如您所料,它确认如果我们增加每个节点的级别数量,我们会显着影响内存指纹。内存使用量计算为存储所有节点的附加指针所需空间的总和。

在此处输入图像描述

毕竟,你们中的任何人都可以向我提供关于如何实现与 BTS 一样好的 SkipList 的评论 - 不计算额外的内存开销 - 吗?

我知道 DrDobbs LINK关于 SkipList 的文章,我浏览了所有论文,搜索和插入操作的代码与PUG89的原始实现完全匹配,所以应该和我的一样好,并且文章没有提供任何性能无论如何分析,我没有找到任何其他来源。你能帮助我吗?

任何评论都非常感谢!

谢谢!:)

4

2 回答 2

26

历史

自从 William Pugh 写下他的原始论文以来,时代已经发生了一些变化。我们在他的论文中没有提到 CPU 和操作系统的内存层次结构,这已成为当今如此普遍的焦点(现在通常与算法复杂性同等重要)。

他的基准测试输入案例只有区区 2^16 个元素,而当时的硬件通常最多只有 32 位扩展内存寻址可用。这使得指针的大小比我们今天在 64 位机器上使用的大小减少一半或更小。同时,例如,一个字符串字段可能同样大,这使得存储在跳过列表中的元素与跳过节点所需的指针之间的比率可能要小得多,特别是考虑到我们通常需要每个跳过节点的多个指针.

那时,C 编译器在寄存器分配和指令选择等方面的优化并不那么激进。即使是普通的手写汇编通常也可以在性能方面提供显着优势。在那些时候,编译器的提示就像register并且inline实际上做了一件大事。虽然这似乎有点没有意义,因为平衡的 BST 和跳过列表实现在这里都是平等的,但即使是基本循环的优化也是一个更加手动的过程。当优化是一个越来越手动的过程时,更容易实现的东西通常更容易优化。跳过列表通常被认为比平衡树更容易实现。

因此,所有这些因素都可能在当时 Pugh 的结论中发挥了作用。然而时代已经变了:硬件变了,操作系统变了,编译器变了,对这些主题进行了更多的研究,等等。

执行

除此之外,让我们玩得开心并实现一个基本的跳过列表。出于懒惰,我最终调整了这里可用的实现。这是一种普通的实现,与当今大量易于访问的示例性跳过列表实现几乎没有什么不同。

我们将比较我们的实现的性能与std::set几乎总是作为红黑树实现的性能*。

* 有些人可能想知道为什么我使用0而不是nullptr和那种东西。这是一种习惯。在我的工作场所,我们仍然必须编写针对各种编译器的开放库,包括仅支持 C++03 的编译器,所以我仍然习惯于以这种方式编写低/中级实现代码,有时甚至在C,所以请原谅我写这段代码的旧风格。

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <cassert>
#include <cstring>
#include <set>

using namespace std;

static const int max_level = 32;
static const float probability = 0.5;

static double sys_time()
{
    return static_cast<double>(clock()) / CLOCKS_PER_SEC;
}

static int random_level() 
{
    int lvl = 1;
    while ((static_cast<float>(rand()) / RAND_MAX) < probability && lvl < max_level)
        ++lvl;
    return lvl;
}

template <class T>
class SkipSet
{
public:
    SkipSet(): head(0)
    {
        head = create_node(max_level, T());
        level = 0;
    }
    
    ~SkipSet()
    {
        while (head)
        {
            Node* to_destroy = head;
            head = head->next[0];
            destroy_node(to_destroy);
        }
    }

    bool contains(const T& value) const
    {
        const Node* node = head;
        for (int i=level; i >= 0; --i)
        {
            while (node->next[i] && node->next[i]->value < value)
                node = node->next[i];
        }
        node = node->next[0];
        return node && node->value == value;
    }

    void insert(const T& value)
    {
        Node* node = head;  
        Node* update[max_level + 1];
        memset(update, 0, sizeof(Node*)*(max_level + 1));

        for (int i = level; i >= 0; i--) 
        {
            while (node->next[i] && node->next[i]->value < value)
                node = node->next[i];
            update[i] = node; 
        }
        node = node->next[0];

        if (!node || node->value != value)
        {
            int lvl = random_level();
            assert(lvl >= 0);
            if (lvl > level) 
            {
                for (int i = level + 1; i <= lvl; i++) {
                    update[i] = head;
                }
                level = lvl;
            }
            node = create_node(lvl, value);
            for (int i = 0; i <= lvl; i++) {
                node->next[i] = update[i]->next[i];
                update[i]->next[i] = node;
            }            
        }
    }

    bool erase(const T& value)
    {
        Node* node = head;  
        Node* update[max_level + 1];
        memset(update, 0, sizeof(Node*)*(max_level + 1));

        for (int i = level; i >= 0; i--) 
        {
            while (node->next[i] && node->next[i]->value < value)
                node = node->next[i];
            update[i] = node; 
        }
        node = node->next[0];

        if (node->value == value)
        {
            for (int i = 0; i <= level; i++) {
                if (update[i]->next[i] != node)
                    break;
                update[i]->next[i] = node->next[i];
            }
            destroy_node(node);
            while (level > 0 && !head->next[level])
                --level;
            return true;
        }
        return false;
    }

private:
    struct Node
    {
        T value;
        struct Node** next;
    };

    Node* create_node(int level, const T& new_value)
    {
        void* node_mem = malloc(sizeof(Node));
        Node* new_node = static_cast<Node*>(node_mem);
        new (&new_node->value) T(new_value);

        void* next_mem = calloc(level+1, sizeof(Node*));
        new_node->next = static_cast<Node**>(next_mem);
        return new_node;
    }

    void destroy_node(Node* node)
    {
        node->value.~T();
        free(node->next);
        free(node);
    }

    Node* head;
    int level;
};

template <class T>
bool contains(const std::set<T>& cont, const T& val)
{
    return cont.find(val) != cont.end();
}

template <class T>
bool contains(const SkipSet<T>& cont, const T& val)
{
    return cont.contains(val);
}

template <class Set, class T>
void benchmark(int num, const T* elements, const T* search_elements)
{
    const double start_insert = sys_time();
    Set element_set;
    for (int j=0; j < num; ++j)
        element_set.insert(elements[j]);
    cout << "-- Inserted " << num << " elements in " << (sys_time() - start_insert) << " secs" << endl;

    const double start_search = sys_time();
    int num_found = 0;
    for (int j=0; j < num; ++j)
    {
        if (contains(element_set, search_elements[j]))
            ++num_found;
    }
    cout << "-- Found " << num_found << " elements in " << (sys_time() - start_search) << " secs" << endl;

    const double start_erase = sys_time();
    int num_erased = 0;
    for (int j=0; j < num; ++j)
    {
        if (element_set.erase(search_elements[j]))
            ++num_erased;
    }
    cout << "-- Erased " << num_found << " elements in " << (sys_time() - start_erase) << " secs" << endl;
}

int main()
{
    const int num_elements = 200000;
    vector<int> elements(num_elements);
    for (int j=0; j < num_elements; ++j)
        elements[j] = j;
    random_shuffle(elements.begin(), elements.end());

    vector<int> search_elements = elements;
    random_shuffle(search_elements.begin(), search_elements.end());

    typedef std::set<int> Set1;
    typedef SkipSet<int> Set2;

    for (int j=0; j < 3; ++j)
    {
        cout << "std::set" << endl;
        benchmark<Set1>(num_elements, &elements[0], &search_elements[0]);
        cout << endl;

        cout << "SkipSet" << endl;
        benchmark<Set2>(num_elements, &elements[0], &search_elements[0]);
        cout << endl;
    }
}

在 GCC 5.2,-O2 上,我得到这个:

std::set
-- Inserted 200000 elements in 0.104869 secs
-- Found 200000 elements in 0.078351 secs
-- Erased 200000 elements in 0.098208 secs

SkipSet
-- Inserted 200000 elements in 0.188765 secs
-- Found 200000 elements in 0.160895 secs
-- Erased 200000 elements in 0.162444 secs

......这太可怕了。我们的速度是全线的两倍左右。

优化

然而,我们可以进行明显的优化。如果我们查看Node,它的当前字段如下所示:

struct Node
{
    T value;
    struct Node** next;
};

这意味着 Node 字段的内存及其下一个指针列表是两个独立的块,它们之间的步幅可能很远,如下所示:

    [Node fields]-------------------->[next0,next1,...,null]

这对于参考的位置很差。如果我们想在这里改进一些东西,我们应该将这些内存块合并成一个连续的结构,如下所示:

    [Node fields,next0,next1,...,null]

我们可以通过 C 中常见的变长 struct 习惯用法来实现这一点。在不直接支持它的 C++ 中实现有点尴尬,但我们可以模拟如下效果:

struct Node
{
    T value;
    struct Node* next[1];
};

Node* create_node(int level, const T& new_value)
{
    void* node_mem = malloc(sizeof(Node) + level * sizeof(Node*));
    Node* new_node = static_cast<Node*>(node_mem);
    new (&new_node->value) T(new_value);
    for (int j=0; j < level+1; ++j)
        new_node->next[j] = 0;
    return new_node;
}

void destroy_node(Node* node)
{
    node->value.~T();
    free(node);
}

通过这个适度的调整,我们现在有了这些时间:

SkipSet (Before)
-- Inserted 200000 elements in 0.188765 secs
-- Found 200000 elements in 0.160895 secs
-- Erased 200000 elements in 0.162444 secs

SkipSet (After)
-- Inserted 200000 elements in 0.132322 secs
-- Found 200000 elements in 0.127989 secs
-- Erased 200000 elements in 0.130889 secs

...这使我们更接近于与std::set.

随机数发生器

真正有效的跳过列表实现通常需要非常快的 RNG。尽管如此,我在一次快速分析会议中发现,只有很少一部分时间用于生成随机级别/高度,这不足以将其视为热点。它也只会影响插入时间,除非它提供更均匀的分布,所以我决定跳过这个优化。

内存分配器

在这一点上,我想说我们对跳过列表实现与 BST 的预期有一个相当合理的概述:

Insertion
-- std::set: 0.104869 secs
-- SkipList: 0.132322 secs

Search:
-- std::set: 0.078351 secs
-- SkipList: 0.127989 secs

Removal:
-- std::set: 0.098208 secs
-- SkipList: 0.130889 secs

但是,如果我们想更进一步,我们可以使用固定分配器。在这一点上,我们有点作弊,因为std::set它旨在与任何符合标准分配器接口要求的通用分配器一起工作。但是让我们看看使用固定分配器:

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <cassert>
#include <set>

using namespace std;

static const int max_level = 32;

class FixedAlloc
{
public:
    FixedAlloc(): root_block(0), free_element(0), type_size(0), block_size(0), block_num(0)
    {
    }

    FixedAlloc(int itype_size, int iblock_size): root_block(0), free_element(0), type_size(0), block_size(0), block_num(0)
    {
        init(itype_size, iblock_size);
    }

    ~FixedAlloc()
    {
        purge();
    }

    void init(int new_type_size, int new_block_size)
    {
        purge();
        block_size = max(new_block_size, type_size);
        type_size = max(new_type_size, static_cast<int>(sizeof(FreeElement)));
        block_num = block_size / type_size;
    }

    void purge()
    {
        while (root_block)
        {
            Block* block = root_block;
            root_block = root_block->next;
            free(block);
        }
        free_element = 0;
    }

    void* allocate()
    {
        assert(type_size > 0);
        if (free_element)
        {
            void* mem = free_element;
            free_element = free_element->next_element;
            return mem;
        }

        // Create new block.
        void* new_block_mem = malloc(sizeof(Block) - 1 + type_size * block_num);
        Block* new_block = static_cast<Block*>(new_block_mem);
        new_block->next = root_block;
        root_block = new_block;

        // Push all but one of the new block's elements to the free pool.
        char* mem = new_block->mem;
        for (int j=1; j < block_num; ++j)
        {
            FreeElement* element = reinterpret_cast<FreeElement*>(mem + j * type_size);
            element->next_element = free_element;
            free_element = element;
        }
        return mem;
    }

    void deallocate(void* mem)
    {
        FreeElement* element = static_cast<FreeElement*>(mem);
        element->next_element = free_element;
        free_element = element;
    }

    void swap(FixedAlloc& other)
    {
        std::swap(free_element, other.free_element);
        std::swap(root_block, other.root_block);
        std::swap(type_size, other.type_size);
        std::swap(block_size, other.block_size);
        std::swap(block_num, other.block_num);
    }

private:
    struct Block
    {
        Block* next;
        char mem[1];
    };
    struct FreeElement
    {
        struct FreeElement* next_element;
    };

    // Disable copying.
    FixedAlloc(const FixedAlloc&);
    FixedAlloc& operator=(const FixedAlloc&);

    struct Block* root_block;
    struct FreeElement* free_element;
    int type_size;
    int block_size;
    int block_num;
};

static double sys_time()
{
    return static_cast<double>(clock()) / CLOCKS_PER_SEC;
}

static int random_level()
{
    int lvl = 1;
    while (rand()%2 == 0 && lvl < max_level)
        ++lvl;
    return lvl;
}

template <class T>
class SkipSet
{
public:
    SkipSet(): head(0)
    {
        for (int j=0; j < max_level; ++j)
            allocs[j].init(sizeof(Node) + (j+1)*sizeof(Node*), 4096);
        head = create_node(max_level, T());
        level = 0;
    }

    ~SkipSet()
    {
        while (head)
        {
            Node* to_destroy = head;
            head = head->next[0];
            destroy_node(to_destroy);
        }
    }

    bool contains(const T& value) const
    {
        const Node* node = head;
        for (int i=level; i >= 0; --i) 
        {
            while (node->next[i] && node->next[i]->value < value)
                node = node->next[i];
        }
        node = node->next[0];
        return node && node->value == value;
    }

    void insert(const T& value)
    {
        Node* node = head;  
        Node* update[max_level + 1] = {0};
        for (int i=level; i >= 0; --i) 
        {
            while (node->next[i] && node->next[i]->value < value)
                node = node->next[i];
            update[i] = node; 
        }
        node = node->next[0];

        if (!node || node->value != value)
        {
            const int lvl = random_level();
            assert(lvl >= 0);
            if (lvl > level) 
            {
                for (int i = level + 1; i <= lvl; ++i)
                    update[i] = head;
                level = lvl;
            }
            node = create_node(lvl, value);
            for (int i = 0; i <= lvl; ++i) 
            {
                node->next[i] = update[i]->next[i];
                update[i]->next[i] = node;
            }            
        }
    }

    bool erase(const T& value)
    {
        Node* node = head;  
        Node* update[max_level + 1] = {0};
        for (int i=level; i >= 0; --i) 
        {
            while (node->next[i] && node->next[i]->value < value)
                node = node->next[i];
            update[i] = node; 
        }
        node = node->next[0];

        if (node->value == value)
        {
            for (int i=0; i <= level; ++i) {
                if (update[i]->next[i] != node)
                    break;
                update[i]->next[i] = node->next[i];
            }
            destroy_node(node);
            while (level > 0 && !head->next[level])
                --level;
            return true;
        }
        return false;
    }

    void swap(SkipSet<T>& other)
    {
        for (int j=0; j < max_level; ++j)
            allocs[j].swap(other.allocs[j]);
        std::swap(head, other.head);
        std::swap(level, other.level);
    }

private:
    struct Node
    {
        T value;
        int num;
        struct Node* next[1];
    };

    Node* create_node(int level, const T& new_value)
    {
        void* node_mem = allocs[level-1].allocate();
        Node* new_node = static_cast<Node*>(node_mem);
        new (&new_node->value) T(new_value);
        new_node->num = level;
        for (int j=0; j < level+1; ++j)
            new_node->next[j] = 0;
        return new_node;
    }

    void destroy_node(Node* node)
    {
        node->value.~T();
        allocs[node->num-1].deallocate(node);
    }

    FixedAlloc allocs[max_level];
    Node* head;
    int level;
};

template <class T>
bool contains(const std::set<T>& cont, const T& val)
{
    return cont.find(val) != cont.end();
}

template <class T>
bool contains(const SkipSet<T>& cont, const T& val)
{
    return cont.contains(val);
}

template <class Set, class T>
void benchmark(int num, const T* elements, const T* search_elements)
{
    const double start_insert = sys_time();
    Set element_set;
    for (int j=0; j < num; ++j)
        element_set.insert(elements[j]);
    cout << "-- Inserted " << num << " elements in " << (sys_time() - start_insert) << " secs" << endl;

    const double start_search = sys_time();
    int num_found = 0;
    for (int j=0; j < num; ++j)
    {
        if (contains(element_set, search_elements[j]))
            ++num_found;
    }
    cout << "-- Found " << num_found << " elements in " << (sys_time() - start_search) << " secs" << endl;

    const double start_erase = sys_time();
    int num_erased = 0;
    for (int j=0; j < num; ++j)
    {
        if (element_set.erase(search_elements[j]))
            ++num_erased;
    }
    cout << "-- Erased " << num_found << " elements in " << (sys_time() - start_erase) << " secs" << endl;
}

int main()
{
    const int num_elements = 200000;
    vector<int> elements(num_elements);
    for (int j=0; j < num_elements; ++j)
        elements[j] = j;
    random_shuffle(elements.begin(), elements.end());

    vector<int> search_elements = elements;
    random_shuffle(search_elements.begin(), search_elements.end());

    typedef std::set<int> Set1;
    typedef SkipSet<int> Set2;

    cout << fixed << setprecision(3);
    for (int j=0; j < 2; ++j)
    {
        cout << "std::set" << endl;
        benchmark<Set1>(num_elements, &elements[0], &search_elements[0]);
        cout << endl;

        cout << "SkipSet" << endl;
        benchmark<Set2>(num_elements, &elements[0], &search_elements[0]);
        cout << endl;
    }
}

* 在发现这似乎工作得很好之后,我还做了一个小调整,random_level让它简单地假设概率为 50%。

通过使用固定分配器,我们可以使用非常简单的恒定时间策略快速分配和释放元素,更重要的是,分配节点的方式使得具有相同高度(最常一起访问)的节点被分配得更连续相互尊重(尽管不是按照理想的顺序)。这将时间改进为:

Insertion
-- std::set: 0.104869 secs
-- SkipList: 0.103632 secs

Search:
-- std::set: 0.078351 secs
-- SkipList: 0.089910 secs

Removal:
-- std::set: 0.098208 secs
-- SkipList: 0.089224 secs

... 这对于大约 40 分钟的工作来说还不错,std::set整个行业的专家都对此进行了戳、戳和调整。我们的移除速度也比std::set(我的机器上的插入时间略有波动,我会说它们大致相当)。

当然,我们作弊应用了这最后一步。使用自定义分配器使事情对我们有利,并且还改变了容器的特性,使其内存在被清除、销毁或压缩之前无法释放。它可以将内存标记为未使用并在后续插入时回收它,但它不能使其使用的内存可供跳过列表之外的人使用。我也没有费心去注意所有可能类型的正确对齐,T这对于真正概括它是必要的。

排序输入

让我们尝试对排序的输入使用它。为此,只需注释掉这两个random_shuffle语句。就我而言,我现在得到了这些时间:

std::set
-- Inserted 200000 elements in 0.044 secs
-- Found 200000 elements in 0.023 secs
-- Erased 200000 elements in 0.019 secs

SkipSet
-- Inserted 200000 elements in 0.027 secs
-- Found 200000 elements in 0.023 secs
-- Erased 200000 elements in 0.016 secs

...现在我们在所有领域都SkipSet表现std::set出色,尽管只是针对这种特殊情况。

结论

所以我不知道这对跳过列表到底是什么意思。几乎没有任何时间和精力,我们已经非常接近与std::set*. 然而我们没有打败它,我们不得不用内存分配器作弊才能真正接近。

* 请注意,里程可能因机器、供应商实施std::set等而异。

自 1989 年 Pugh 撰写论文以来,时代已经发生了很大变化。

今天,引用局部性的好处占据了主导地位,即使线性复杂度算法也可以胜过线性算法,前提是前者对缓存或页面友好得多。密切关注系统从内存层次结构的上层(例如:二级)抓取内存块的方式,内存较慢但更大,一直到 L1 缓存线和极小的寄存器,这比以往任何时候都更重要,并且如果你问我什么时候好处可以与算法改进相媲美,不再是“微”。

考虑到节点的大小相当大,并且同样重要的是节点的可变大小(这使得它们难以非常有效地分配),跳过列表在这里可能会被削弱。

我们没有看到的一件事是跳过列表在插入时更新的本地化性质。与平衡树通过旋转父节点重新平衡所需的区域相比,这往往会影响更少的区域。因此,跳过列表可以提供潜在的更有效的并发集合或映射实现。

跳过列表的另一个有希望的特性是它只是一个最低级别的链表。结果,它提供了非常简单的线性时间顺序遍历,而不必沿着具有线性复杂度的树的分支下降,因此如果我们想要对包含的所有元素进行大量线性时间迭代,它可能非常好.

但永远记住:

一种技术只有在实施者手中能被应用时才好。

于 2015-11-30T16:42:26.683 回答
3

即使在 1989 年,我也怀疑跳过列表是否比例如 AVL 树更好。在 1989 年或 1990 年,作为学生,我实现了两者:我必须承认,这不是跳过列表的好实现,我是新手在这段时间。

然而,AVL 树不再难以实现。相比之下,我在模 2 中实现的列表中跳过的可变长度前向指针遇到了困难,我最初使用最多 16 个下一个指针解决了这个问题。

插入操作少的好处,我没见过。如果我没记错的话,AVL 树平均只有 2-3 次操作。因此,昂贵的再平衡并不经常发生。

我认为这更像是一种炒作。

于 2015-11-30T17:05:59.753 回答