Оптимизировать пространство большого массива с множеством дубликатов

Question

У меня есть массив, где индекс удваивается как "идентификатор для коллекции элементов", а содержимое массива представляет собой номер группы. Номера групп попадают в конечный диапазон от 0..N, где N << length_of_the_array. Следовательно, каждая запись будет дублироваться большое количество раз. В настоящее время я должен использовать 2 байта для представления номера группы (который может быть> 1000, но < 6500), который из-за дублированного характера в итоге занимает много памяти.

Существуют ли способы оптимизировать пространство в этом массиве, поскольку весь массив может занимать несколько МБ. Цените любые указатели на соответствующий алгоритм / технику оптимизации. К вашему сведению: Я использую язык программирования cpp.

Answer 1

Вы все еще хотите эффективный произвольный доступ к произвольным элементам? Или вы думаете о космически эффективной сериализации индекса-> групповой карты?

Если вы все еще хотите эффективный произвольный доступ, поиск в одном массиве неплох. В худшем случае, промах одного кеша. Ну, на самом деле, в худшем случае ошибка страницы или, скорее всего, ошибка TLB, но это маловероятно, если это всего лишь пара МБ).

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

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

Упакованные 12-битные записи, вероятно, не стоят проблем, если только этого недостаточно, чтобы значительно уменьшить количество кеш-ошибок. Пара команд умножения для генерации правильного адреса и команда сдвига и маски на нагрузке 16b, содержащая желаемое значение, не сильно загружены по сравнению с отсутствием кэша. Доступ на запись в упакованные битовые поля медленнее и не является атомарным, так что это серьезный недостаток. Получение компилятором для упаковки битовых полей с использованием структур может зависеть от компилятора. Может быть, лучше всего использовать массив символов.