如何对一组有序的唯一 ID 实现 O(1) 位置查找？

Question

我认为我的情况并不少见，但我一直无法想出一种方法来使我的代码在处理大型数据集时高效。

我的数据集是一个唯一 ID 的列表（如果重要，则为 32 位无符号整数），其中列表的顺序很重要（即调用代码希望 ID 按照插入的顺序保留）。

调用代码可以将新的（唯一的）ID 插入列表中的任何位置和/或从列表中删除 ID。 该列表可能会变得非常大（例如数万个 ID 长）

因为列表用于填充 QTableView，所以我需要在给定的唯一 ID 及其在列表中的当前位置之间进行快速（理想情况下为 O(1)）查找，反之亦然。

我当前的代码将列表存储为

std::vector<uint32_t>

，因此在第 n 位置查找 ID 只需要对向量进行索引即可。 （参见下面示例代码中的

int32_t getIDAtRow(size_t rowIdx) const

）

对于反向查找，我的代码生成一个

std::unordered_map<uint32_t, size_t>

，以便给定唯一 ID 作为键，它可以快速返回该唯一 ID 当前所在的行索引。 （请参阅下面示例代码中的

ssize_t getRowIndexForID(uint32_t id) const

）。

如果数据是静态的，这一切都可以很好地工作；但是，如果调用代码开始在列表开头附近进行大量插入或删除，则每次插入/删除都会使反向查找表中的大多数项目无效，因此必须重新生成它们，这可能会变得非常慢。 我尝试了各种策略来缓解性能问题（例如延迟重新生成或仅进行部分重新生成），但没有一个是完全令人满意的——我仍然总能找到一些调用模式，由于过度的调用而导致性能缓慢再生。

所以我的问题是：我是否可以在这里使用其他一些数据结构来获得更好的双向

ID<->RowIndex

查找性能，即使 ID 列表很大并且被插入和/或从很多中删除？ 即是否有一些东西在插入或删除后不需要 O(N) 反向表重新生成？

可编译的玩具示例代码如下，以防它有助于更好地解释问题。

#include <set>
#include <algorithm>
#include <random>
#include <vector>
#include <unordered_map>
#include <cstdio>
#include <cstdint>

class IDToRowMap
{  
public:
   IDToRowMap() {/* empty */}

   // append a new unique ID to the end of our ordered IDs list
   void appendID(uint32_t id) 
   {
      if (getRowIndexForID(id) >= 0) 
      {
         printf("Error, ID %u is already in the table!\n", id);
      }
      else
      {
         idsInRowOrder.push_back(id);
         idToRowIndex[id] = idsInRowOrder.size()-1;
      }
   }
   
   // insert a new unique ID into the middle of our ordered IDs list
   void insertIDAtRow(uint32_t id, size_t rowIdx)
   {
      if (getRowIndexForID(id) >= 0) 
      {
         printf("Error, ID %u is already in the table!\n", id);
      }
      else if (rowIdx < idsInRowOrder.size())
      {
         idsInRowOrder.insert(idsInRowOrder.begin()+rowIdx, id);
         regenerate_reverse_index_starting_at(rowIdx);
      }
      else 
      {
         appendID(id);
      }  
   }        
            
   // remove the specified ID from our list
   void removeID(uint32_t id)
   {           
      const ssize_t rowIdx = getRowIndexForID(id);
      if (rowIdx >= 0)
      {
         idsInRowOrder.erase(idsInRowOrder.begin()+rowIdx);
         idToRowIndex.erase(id);
               
         regenerate_reverse_index_starting_at(rowIdx);
      }        
      else 
      {
         printf("Error, ID %u is not in the table!\n", id);
      }
   }        

   // clear the list
   void clear()
   {           
      idsInRowOrder.clear();
      idToRowIndex.clear();
   }        
            
   // Returns the row index that (id) is at, or -1 if (id) isn't in the set
   ssize_t getRowIndexForID(uint32_t id) const
   {           
      auto search = idToRowIndex.find(id);
      if (search == idToRowIndex.end()) return -1;
      return search->second;
   }

   // Returns the ID at the given row, or -1 if (rowIdx) isn't a valid row index
   int32_t getIDAtRow(size_t rowIdx) const
   {        
      return (rowIdx < idsInRowOrder.size()) ? idsInRowOrder[rowIdx] : -1;
   }        
         
   void print() const
   {
      for (size_t row=0; row<idsInRowOrder.size(); row++)
      {
         const uint32_t id = idsInRowOrder[row];
         const ssize_t checkRowIndex = getRowIndexForID(id);
         const int32_t checkRowID    = getIDAtRow(checkRowIndex);

         printf("row=%zu id=%u checkRowIndex=%zi checkRowID=%i", row, id, checkRowIndex, checkRowID);
         if (checkRowIndex != row) printf(" ERROR:(checkRowIndex doesn't match row)");
         if (checkRowID    != id)  printf(" ERROR:(checkRowID doesn't match id)");
         printf("\n");
      }
   }

private:
   // Here's where it gets inefficient -- if I have to insert or remove IDs near the front
   // of the list I end up regenerating the reverse index a lot and if the list is long, it gets slow
   void regenerate_reverse_index_starting_at(size_t startIdx)
   {
      printf("Regenerating reverse index from row %zu to row %zu\n", startIdx, idsInRowOrder.size());
      for (size_t i=startIdx; i<idsInRowOrder.size(); i++) idToRowIndex[idsInRowOrder[i]] = i;
   }

   std::vector<uint32_t> idsInRowOrder;
   std::unordered_map<uint32_t, size_t> idToRowIndex;  // reverse-lookup
};

int main(int, char **)
{
   std::vector<uint32_t> someIDs;
   {
      while(someIDs.size()<50) someIDs.push_back(someIDs.size());

      std::random_device rd;  // Seed generator
      std::mt19937 gen(rd()); // Mersenne Twister engine

      std::shuffle(someIDs.begin(), someIDs.end(), gen);  // put them in some random order
   }

   IDToRowMap map;
   for (auto a : someIDs) map.appendID(a);

   printf("Enter one of the following:\n");
   printf("   a 12345 - append ID 12345\n");
   printf("   i 12345 - insert ID 12345 at row #3\n");
   printf("   r 12345 - remove ID 12345\n");
   printf("   c       - clear the table\n");
   printf("   p       - print the table\n");
   printf("\n");

   while(1)
   {
      char buf[128];
      if (fgets(buf, sizeof(buf), stdin))
      {
         switch(buf[0])
         {
            case 'a':
            {
               const uint32_t id = atol(&buf[2]);
               printf("Appending id %u\n", id);
               map.appendID(id);
            }
            break;

            case 'i':
            {
               const uint32_t id = atol(&buf[2]);
               printf("Inserting id %u at row #3\n", id);
               map.insertIDAtRow(id, 3);
            }
            break;

            case 'r':
            {
               const uint32_t id = atol(&buf[2]);
               printf("Removing id %u\n", id);
               map.removeID(id);
            }
            break;

            case 'c':
               map.clear();
               printf("Cleared!\n");
            break;

            case 'p':
               map.print();
            break;

            default:
               printf("Unknown command [%s]\n", buf);
            break;
         }
      }
   }

   return 0;
}

编辑：

LinkedHashSet

类型的类（我确实有C++版本的，并且我发现它在其他上下文中非常有用）并不能解决这个问题，因为查找a的nth项链表是 O(N) 操作，因此在处理大型数据集时效率较低。

Answer 1

正如评论中提到的，似乎无法获得

O(1)

性能，但

O(log(N))

性能是可以获得的。

此类实现的候选者将使用“绳索数据结构”。 绳索数据结构旨在尽可能高效地处理非常长的字符串，并且通常在文本编辑器中用于在长文档中高效插入/删除/查找。 在这种情况下，它将管理一串 uint32_t 而不是一串

char

，但数据处理逻辑在其他方面是相同的。