跳过清单，他们真的表现得和Pugh纸张一样好吗？

2 回答

• 3

  历史

  自威廉·普格撰写他的原始论文以来，时代已经发生了一些变化我们在他的论文中没有提到CPU和操作系统的内存层次结构，它已成为当今流行的焦点（现在通常与算法复杂性同样重要） .

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

  C编译器在寄存器分配和指令选择等方面的优化并不那么激进 . 即使是普通的手写组装也可以提供显着的性能优势 . 像 register 和 inline 这样的编译器提示在这些时候实际上做了很多 . 虽然这似乎没什么问题，因为 balancer 的BST和跳过列表实现在这里是平等的，甚至基本循环的优化也是一个更加手动的过程 . 当优化是一个越来越多的手动过程时更容易实现更容易优化 . 跳过列表通常被认为比 balancer 树更容易实现 .

  因此，所有这些因素可能都与Pugh当时的结论有关 . 时代已经改变：硬件已经改变，操作系统发生了变化，编译器发生了变化，对这些主题进行了更多的研究，等等 .

  实施

  除此之外，让我们有一些乐趣并实现一个基本的跳过列表 . 我最终调整了懒惰的实现here . 这是一种普通的实现方式，与当今众多易于访问的示例性跳过列表实现几乎没有什么不同 .

  我们将把我们实现的性能与 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中常见的可变长度结构习惯来实现这一点 . 在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 . 尽管如此，我在快速分析 Session 期间发现，只花了很少的时间来产生随机水平/高度，几乎不足以将其视为热点 . 它也只会影响插入时间，除非它提供更均匀的分布，所以我决定跳过这个优化 .

  内存分配器

  在这一点上，我要说我们对跳过列表实现与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 更快的删除（插入时间在我的机器上有点波动，我会说它们大致相同） .

  当然，我们欺骗了应用这最后一步 . 使用自定义分配器可以倾斜对我们有利的事物，并且还会改变容器的特性，使其在清除，销毁或压缩之前无法释放其内存 . 它可以将内存标记为未使用，并在后续插入时回收它，但它不能使其使用的内存可用于跳过列表之外的那些内存 . 我也没有理会注意所有可能类型的 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的供应商实现等而异 .

  自Pugh于1989年撰写的论文以来，时代已经发生了很大的变化 .

  今天，参考局部性的好处使得事物占主导地位，甚至线性复杂度算法也可以胜过线性复杂性算法，只要前者具有更多的缓存或页面友好性 . 密切关注系统从内存层次结构的上层（例如：第二阶段）获取内存块的方式，内存较慢但内存较大，一直到小的L1缓存行和少量注册，这是一个比以往更大的交易，并且如果你问我哪些好处可以与算法改进相媲美，就不再是“微观”了 .

  鉴于节点的大小相当大，并且同样重要的是节点的可变大小（这使得它们难以非常有效地分配），跳过列表可能在这里被削弱 .

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

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

  但要记住：

  A technique is only as good as it can be applied in the hands of the implementor.

  回复于 2024-04-19T06:23:52+08:00
• 23

  我怀疑跳过列表是比AVL树更好的选择，即使在1989年 . 在1989年或1990年作为一名学生我实施了两者：它不是跳过列表的一个很好的实现，我必须承认，我是一个新手在这段时间 .

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

  插入操作较少的优点，我从未见过 . AVL树，如果我记得正确，平均不超过2-3次操作 . 因此，昂贵的重新 balancer 不经常发生 .

  我认为这更像是炒作 .

  回复于 2024-04-19T06:23:52+08:00