Массив сокращенных целых чисел

Question

Просто чтобы не изобретать горячую воду, прошу здесь ...

У меня есть приложение с большим количеством массивов, и ему не хватает памяти.

Таким образом, идея состоит в том, чтобы сжать List<int> до чего-то другого, что бы имело тот же интерфейс (например, IList<T>), но вместо int я мог бы использовать более короткие целые числа.

Например, если мой диапазон значений 0 - 100.000.000, мне нужно только ln2 (1000000) = 20 бит. Таким образом, вместо хранения 32 бит, я могу обрезать излишки и уменьшить требования к памяти на 12/32 = 37,5%.

Вам известна реализация такого массива. С ++ и java тоже подойдут, так как я могу легко конвертировать их в c #.

Дополнительные требования (поскольку все начинают понимать меня):

• целых чисел в списке являются уникальными
• они не имеют специальных свойств, поэтому они не сжимаются никаким другим способом, кроме уменьшения количества бит
• если диапазон значений равен одному миллиону, например, списки будут иметь размер от 2 до 1000 элементов, но их будет много, поэтому BitSets не будет
• новый контейнер данных должен вести себя как массив большого размера (в отношении метода O () - ness)

EDIT:

Пожалуйста, не говорите мне НЕ делать это. Требование для этого хорошо продумано, и это ЕДИНСТВЕННЫЙ оставленный вариант.

Кроме того, 1М диапазона значений и 20 бит для него - ТОЛЬКО ПРИМЕР. У меня есть дела со всеми различными диапазонами и целочисленными размерами.

Кроме того, я мог бы иметь еще более короткие целые числа, например 7-битные целые, тогда упаковка была бы

00000001
11111122
22222333
33334444
444.....

для первых 4 элементов, упакованных в 5 байтов.

---

Почти готов кодирование - скоро будет опубликовано ...

Answer 1

Поскольку вы можете распределять память только в байтовых квантах, вы, по сути, спрашиваете, можете ли вы / как разместить целые числа в 3 байта вместо 4 (но см. № 3 ниже).Это не очень хорошая идея .

1. Поскольку целочисленного типа размером 3 байта нет, вам нужно использовать что-то другое (например, непрозрачный 3-байтовый буфер) вего место.Это потребует, чтобы вы обернули весь доступ к содержимому списка в код, который выполняет преобразование, так что вы все равно можете вставлять «целые» и извлекать «целые».
2. В зависимости как от архитектуры, так и отРаспределитель памяти, запрос 3-байтовых чанков может вообще не повлиять на объем памяти вашей программы (это может просто засорить вашу кучу неиспользуемыми 1-байтовыми «дырами»).
3. Переопределение списка с нуля для работы снепрозрачный байтовый массив в качестве резервного хранилища позволит избежать двух предыдущих проблем (и он также может позволить вам сжать каждый последний бит памяти вместо целых байтов), но это высокий порядок и весьма подвержен ошибкам.

Вместо этого вы можете попробовать что-то вроде:

• Не хранить все эти данные в памяти одновременно.При 4 байтах на целое, вам нужно набрать сотни миллионов целых чисел, прежде чем закончится память.Зачем вам все они нужны одновременно?
• Сжатие набора данных, если возможно, не хранить дубликаты.Их должно быть несколько, если у вас до сотен миллионов.
• Изменение структуры данных таким образом, чтобы она сохраняла различия между последовательными значениями (дельтами), если это возможно.Это может быть не очень трудно достичь, , но , вы можете только реально ожидать чего-то на уровне улучшения 50% (что может быть недостаточно), и это полностью разрушит вашу способность индексировать в список на постоянной основе.время.

Answer 2

Это напоминает мне base64 и аналогичные виды двоично-текстового кодирования .Они занимают 8-битные байты и делают кучу сложностей, чтобы упаковать их в 4-, 5- или 6-битные печатаемые символы.Это также напоминает мне стандартный код обмена информацией Zork (ZSCII), который упаковывает 3 буквы в 2 байта, где каждая буква занимает 5 бит.Похоже, вы хотите взять кучу 10- или 20-битных целых чисел и упаковать их в буфер из 8-битных байтов.

Исходный код доступен для многих библиотек, которые обрабатывают упакованный массив из одногобиты ( a b c d e ).

Возможно, вы могли бы (a) загрузить этот исходный код и изменить исходный код (начиная с некоторого BitArray или другого упакованного кодирования), перекомпилировать для создания новой библиотеки, которая обрабатывает упаковку и распаковку 10- или 20-разрядных целых чисел, а не отдельных битов.(B) может потребоваться меньше времени на программирование и тестирование, чтобы написать библиотеку, которая внешне выглядит как (а), но внутренне она разбивает 20-битные целые числа на 20 отдельных битов, а затем сохраняет их, используя (без изменений) Класс BitArray.

Answer 3

Один вариант, который увеличит ваш размер от 32 до 24 бит, - это создать пользовательскую структуру, которая хранит целое число в 3 байтах:

public struct Entry {
    byte b1; // low
    byte b2; // middle
    byte b3; // high

    public void Set(int x) {
        b1 = (byte)x;
        b2 = (byte)(x >> 8);
        b3 = (byte)(x >> 16);
    }

    public int Get() {
        return (b3 << 16) | (b2 << 8) | b1;
    }
}

Затем вы можете просто создать List<Entry>.

var list = new List<Entry>();
var e = new Entry();
e.Set(12312);
list.Add(e);
Console.WriteLine(list[0].Get()); // outputs 12312

Answer 4

Редактировать : Учитывая, что ваши целые числа уникальны, вы можете сделать следующее: хранить уникальные целые числа до тех пор, пока число сохраняемых вами чисел не станет вдвое меньше максимального числа.Затем переключитесь на хранение целых чисел, которых у вас нет.Это уменьшит объем памяти на 50%.

Может быть стоит изучить другие методы упрощения, прежде чем пытаться использовать 20-битные целые числа.

Как вы относитесь к дублирующимся целым числам? Если имеется много дубликатов, вы можете уменьшить размер хранилища, сохранив целые числа в Dictionary<int, int>, где ключи - это уникальные целые числа, а значения - это соответствующие значения.Заметьте, это предполагает, что вам не важен порядок ваших целых чисел.

Все ли ваши целые числа уникальны? Возможно, вы храните множество уникальных целых чисел в диапазоне от 0 до 100 мил.В этом случае вы можете попытаться сохранить целые числа, которых у вас нет.Затем при определении, есть ли у вас целое число i, просто спросите, нет ли его в вашей коллекции.