операции с постоянным временем

Question

Существуют ли алгоритмы постоянного времени для пересечения и объединения двоичных множеств?

Я представляю себе использование растровых изображений с указателями на элементы в памяти и использование ИЛИ для объединения и И для пересечения.

Есть ли у кого-нибудь сейчас решение?

Answer 1

Это постоянное время до 32 элементов с классом BitArray.Вы можете написать собственный, чтобы получить до 64 элементов, используя базовый ulong [].Неуправляемый код делает возможным 128 элементов с помощью встроенных функций _mm_or_si128 и _mm_and_si128.Трудно использовать из-за требований к выравниванию памяти, не может получить это из кучи мусора.

Это не практичные суммы в большинстве случаев, когда вы хотите оптимизировать этот вид кода.По сути, это алгоритм O (n) с очень маленьким Oh.Можно также использовать BitArray.