Реализация разреженного массива в C # / быстрый способ сопоставить целое число с конкретным номером корзины / диапазона

Question

Моя первоначальная проблема заключается в том, что мне нужно реализовать очень быстрый, разреженный массив в C #.Первоначальная идея состояла в том, чтобы использовать обычный Dictionary<uint, TValue> и обернуть его в моем собственном классе, чтобы раскрыть только параметр типа TValue.Оказывается, это довольно медленно.

Так что моей следующей идеей было сопоставить каждое целое число в необходимом диапазоне (UInt32.MinValue до UInt32.MaxValue) с ведром, некоторого размера и использовать его.Поэтому я ищу хороший способ сопоставить целое число без знака X с сегментом Y, например:

Отображение чисел от 0-1023 до 8 различных сегментов, содержащих по 128 чисел в каждом, 0-127, 128-255.

Но если у кого-то есть лучший способ реализации быстрого разреженного массива в C #, это также будет очень полезно.

Answer 1

Я тоже заметил, что Dictionary<K,V> медленный, когда ключ является целым числом.Я не знаю точно, почему это так, но я написал более быструю реализацию хеш-таблицы для ключей uint и ulong:

• Efficient32bitHashTable и Efficient64bitHashTable

Предостережения / недостатки:

• 64-битный (ключ ulong) является общим, но другой (ключ uint) принимает значения int, потому что это все, что мне было нужно в то время;Я уверен, что вы можете легко сделать это универсальное.

• В настоящее время емкость определяет размер хеш-таблицы навсегда (то есть она не увеличивается).

Answer 2

Существует 101 способ реализации разреженных массивов в зависимости от таких факторов, как:

• Сколько элементов будет в массиве
• Как элементы объединяются в кластеры
• Пространство / скорость торговли
• и т. Д.

В большинстве учебников есть раздел, посвященный разреженным массивам, просто в Google получается множество попаданий.Затем вам нужно будет перевести код на C # или просто использовать код, написанный кем-то другим, я нашел два без особых усилий (я не знаю, насколько они хороши)

• Используйте специальные массивы для ускорения вашего кода
• SparseArray для C #