Эффективно хранить набор чисел

Question

Я ищу наиболее эффективный способ хранения коллекции целых чисел.Прямо сейчас они хранятся в HashSet<T>, но профилирование показало, что эти коллекции сильно влияют на некоторый критичный к производительности код, и я подозреваю, что есть лучший вариант.

Некоторые дополнительные сведения:

• Случайные поиски должны быть O (1) или близки к нему.
• Коллекции могут вырасти большими, поэтому желательна эффективность использования пространства.
• Значения равномерно распределены в 64-битное пространство.
• Изменчивость не требуется.
• Нет четкой верхней границы для размера, но десятки миллионов элементов не редкость.

НаиболееУжасное выступление хита сейчас создает их.Похоже, что это связано с распределением - очистка и повторное использование HashSet s очень помогает в тестах, но, к сожалению, это неосуществимо в коде приложения.

(добавлено) Реализация структуры данных, адаптированной кЗадача в порядке.Хеш-таблица все еще способ пойти?На первый взгляд, это тоже кажется возможным, но у меня нет с ними практического опыта.

Answer 1

Я решил попытаться реализовать специальный набор классов на основе хеш-функции, который использует линейное зондирование для обработки коллизий:

• Резервное хранилище представляет собой простой массив long s
• Размер массива больше ожидаемого количества элементов, которые будут сохранены.
• Для хэш-кода значения используйте наименее значащий 31 бит.

Поиск позиции значения в резервном хранилище выполняется с использованием базового линейного зонда, например:

int FindIndex(long value)
{
    var index = ((int)(value & 0x7FFFFFFF) % _storage.Length;
    var slotValue = _storage[index];

    if(slotValue == 0x0 || slotValue == value) return index;

    for(++index; ; index++)
    {
        if (index == _storage.Length) index = 0;
        slotValue = _storage[index];
        if(slotValue == 0x0 || slotValue == value) return index;
    }
}

(Я смог определить, что сохраняемые данные никогда не будут содержать 0, поэтому это число безопасно использовать для пустых слотов.)

Массив должен быть больше, чем количество хранимых элементов. (Коэффициент загрузки меньше 1.) Если набор когда-либо будет полностью заполнен, то FindIndex() перейдет в бесконечный цикл, если будет использоваться для поиска значения, которого еще нет в наборе. На самом деле, он захочет иметь достаточно много пустого пространства, иначе поиск и извлечение могут пострадать, когда данные начнут образовывать большие скопления.

Я уверен, что еще есть место для оптимизации, и я могу застрять, используя какой-то BigArray<T> или шард для бэк-магазина на больших наборах. Но первые результаты многообещающие. Он работает в два раза быстрее HashSet<T> при коэффициенте нагрузки 0,5, почти в два раза быстрее при коэффициенте нагрузки 0,8, и даже при 0,9 он все еще работает на 40% быстрее в моих тестах.

Накладные расходы составляют 1 / load factor, поэтому, если эти показатели производительности сохранятся в реальном мире, то я считаю, что это также будет более эффективным с точки зрения памяти, чем HashSet<T>. Я не проводил формальный анализ, но, судя по внутренней структуре HashSet<T>, я почти уверен, что его накладные расходы значительно превышают 10%.

-

Так что я очень доволен этим решением, но мне все еще интересно, есть ли другие возможности. Может быть, какая-то трия?

-

Эпилог: Наконец-то дошло время провести несколько конкурентных тестов по сравнению с HashSet<T> на живых данных. (До того, как я использовал синтетические тестовые наборы.) Это даже превзошло мои оптимистические ожидания от предыдущих. Реальная производительность оказывается в 6 раз выше, чем HashSet<T>, в зависимости от размера коллекции.

Answer 2

HashSet обычно является лучшей коллекцией общего назначения в этом случае.

Если у вас есть какая-либо конкретная информация о вашей коллекции, возможно, у вас есть лучшие варианты.

Если у вас фиксированная верхняя граница, которая невелика, вы можете использовать битовый вектор подходящего размера.

Если у вас очень плотная коллекция, вы можете хранить пропущенные значения.

Если у вас очень маленькие коллекции, <= 4 элемента или около того, вы можете хранить их в обычном массиве. Полное сканирование такого небольшого массива может быть быстрее, чем хеширование, необходимое для использования хэш-набора. </p>

Если у вас нет более специфических характеристик ваших данных, чем «большие коллекции int», то HashSet - путь.

Answer 3

Если размер значений ограничен, вы можете использовать битовый набор. Он хранит один бит на целое число. В общей сложности использование памяти будет состоять из n битов, причем n является наибольшим целым числом.

Другим вариантом является фильтр Блума. Фильтры Блума очень компактны, но вы должны быть готовы к случайным ошибкам при поиске. Вы можете найти больше о них в Википедии.

Третий вариант - использование отсортированного массива. Поиски - это log n, где n равно числу целых чисел. Это может быть достаточно быстро.

Answer 4

Самым болезненным ударом по производительности сейчас является их создание ...

Как вы, очевидно, заметили, HashSet<T> не имеет конструктора, который принимает аргумент capacityчтобы инициализировать его емкость.

Один трюк, который, я считаю, сработает, заключается в следующем:

int capacity = ... some appropriate number;
int[] items = new int[capacity];
HashSet<int> hashSet = new HashSet<int>(items);
hashSet.Clear();
...

Если посмотреть на реализацию с отражателем, это инициализирует емкость до размера items массив, игнорируя тот факт, что этот массив содержит дубликаты.Однако на самом деле это только добавит одно значение (ноль), поэтому я предполагаю, что инициализация и очистка должны быть достаточно эффективными.

Я не проверял это, так что вам пришлось бы его тестировать.И будьте готовы рискнуть зависеть от недокументированной внутренней детали реализации.

Было бы интересно узнать, почему Microsoft не предоставила конструктору аргумент capacity, как они делают для других типов коллекций.

Answer 5

Что я хотел бы сделать, это просто создать массив целых чисел с достаточным размером, чтобы обрабатывать сколько угодно целых чисел Есть ли какая-то причина держаться подальше от общего List<T>? http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx