c# - 恒定时间集合操作

Question

二元集交集和并集是否有恒定时间算法？

我想象使用带有指向内存中元素的指针的位图，并使用 OR 表示联合，使用 AND 表示交集。

现在有人有解决方案吗？

Answer 1

使用 BitArray 类，它是最多 32 个元素的恒定时间。您可以使用底层的 ulong[] 编写自定义元素以获取多达 64 个元素。使用 _mm_or_si128 和 _mm_and_si128 内在函数，非托管代码可以实现 128 个元素。由于它们的内存对齐要求而难以使用，无法从垃圾收集堆中获取。

在您想要优化此类代码的大多数情况下，这些都不是实际数量。它基本上是一个 O(n) 算法，具有非常小的 Oh。还不如使用 BitArray。