1

我有一个map<size_t, set<size_t>>，为了获得更好的性能，我实际上将其表示为按字典顺序排序的vector<pair<size_t, vector<size_t>>>。

我需要的是set<T>具有快速插入时间（删除无关紧要），T上面的数据类型在哪里，以便我可以检查重复项（我的程序运行直到不再T生成 unique 。）。

到目前为止，从setto切换unordered_set已经证明是非常有益的（它使我的程序运行速度快了 25% 以上），但即使是现在，插入T似乎仍然是主要瓶颈之一。

给定的最大整数数T约为 1000，每个整数也 <= ~1000，因此数字非常小（但T生成了数千个）。

我已经尝试过的：

  • 使用unsigned short. 它实际上会稍微降低性能。

  • 使用谷歌的btree::btree_map.
    它实际上要慢得多，因为我必须解决迭代器失效问题。
    （我必须复制密钥，我认为这就是它变慢的原因。它至少慢了一倍。）

  • 使用不同的哈希函数。只要我使用合理的东西，我还没有发现任何可衡量的差异，所以这似乎无法改进。

我没有尝试过的：

  • 存储“指纹”/哈希而不是实际集合。
    这听起来像是一个完美的解决方案，除了指纹功能需要快速，而且我需要非常确信不会发生碰撞，否则它们会搞砸我的程序。
    （这是一个需要精确结果的确定性程序；碰撞使其无用。）

  • 以其他紧凑、CPU 友好的方式存储数据。
    我不确定这会有多大好处，因为它可能涉及复制数据，而且到目前为止我获得的大部分性能都是通过（巧妙地）避免在许多情况下复制数据。

如果有的话，我还能做些什么来提高速度？

4

3 回答 3

1

我的印象是你在这里有 3 个不同的问题：

  • 你需要它T本身相对紧凑且易于移动
  • 您需要快速检查 a 是否T可能与现有的重复
  • 您最终需要T在必须检查重复项的任何数据结构中快速插入新的

就T其本身而言，它还没有达到应有的紧凑程度。您可能可以使用单个std::vector<size_t>来表示它：

  • N对
  • N 个索引
  • 每个 I 元素的 N 个“Ids”

所有可以线性化的：

[N, I(0), ..., I(N-1),
    R(0) = Size(Id(0)), Id(0, 0), ... , Id(0, R(0)-1),
    R(1) = ... ]

这样你就有了一块内存。

注意：根据访问模式，您可能需要对其进行调整，特别是如果您需要随机访问任何 ID。

关于重复的可能性，哈希图似乎确实非常合适。您将需要一个好的散列函数，但是对于单个数组size_t（或者unsigned short如果可以，它更小），您可以选择 MurmurHash 或 CityHash 或 SipHash。他们都在飞速发展，尽最大努力产生高质量的哈希（不是加密的，重点是速度）。

现在，问题是检查重复项时何时会变慢。

如果您因为哈希图太大而花费太多时间检查不存在的重复项，您可能需要在它前面投资一个布隆过滤器。

否则，请检查您的散列函数以确保它真的很快并且具有低冲突率，并且您的散列映射实现以确保它只计算一次散列。

关于插入速度。通常，哈希映射，特别是如果平衡良好且预先确定大小，应该是最快的插入之一。确保将数据移入其中，不要复制；如果您无法移动，则可能值得使用 ashared_ptr来限制复制成本。

于 2013-07-21T13:21:30.417 回答
0

不要害怕冲突，使用加密哈希。但是选择一个快速的。256 位冲突的可能性远低于硬件错误。Sun 使用它对 ZFS 中的块进行重复数据删除。ZFS 使用 SHA256。可能您可以使用不太安全的哈希。如果需要 1000000 美元才能找到一个冲突哈希是不安全的，但一个冲突似乎不会降低您的性能。许多碰撞将花费许多$ 1000000。您可以使用（无序）之类的东西multimap<SHA, T>来处理碰撞。顺便说一句，任何哈希表都会发生冲突（或占用太多内存），因此有序映射（gcc 中的 rbtree）或 btree_map 具有更好的保证时间。哈希表也可以通过哈希冲突来处理。可能一种秘盐可以解决这个问题。这是由于表大小远小于可能的哈希数。

于 2013-07-21T09:46:49.080 回答
0

您还可以：1）使用短整数 2）将您的数组重新解释为 uint64_t 之类的数组以进行快速比较（+一些尾随元素），甚至将其重新解释为 128 位值（或 256 位，具体取决于在您的 CPU 上）并通过 SSE 进行比较。这应该会将您的性能推到内存速度限制。根据我的经验，SSE 只能通过对齐的内存访问快速工作。uint64_t 比较可能也需要对齐速度，因此您必须手动分配内存并正确对齐（分配更多并跳过第一个字节）。tcmalloc 是 16 字节对齐的，uint64_t-ready。奇怪的是你必须在 btree 中复制密钥，你可以使用 shared_ptr 来避免它。使用快速比较和慢速哈希 btree 或 std::map 可能会比哈希表更快。我猜任何哈希都比内存慢。

PS 如果你还没有，我强烈建议你使用分析器。请告诉您的程序插入、比较插入和计算哈希所花费的时间百分比。

于 2013-07-22T22:14:27.207 回答