Упаковка повторящихся указателей

[Igors]

Добрый день

Имею массивы данных A и B. Каждый элемент массива B хранит переменное число указателей на данные массива А. Для всех элементов массива А существует хотя бы один указатель на него, хранимый в элементе массива В. Однако реально намного больше указателей (в разных элементах B) указывают на одни и те же данные А.
Пример

976,144 элементов в массиве А
9,761,502 указателей сохранено во всех элементах массива В

(1) 289               // 289 элементов массива В хранят 1 указатель
(2) 5768             // 5768 элементов массива В хранят 2 указателя
(3) 14624           // и.т.д
(4) 23738
(5) 23962
(6) 45696
(7) 50171
(8 ) 65778
(9) 60586
(10) 73359
(11) 53775
(12) 60424
(13) 23796
(14) 13969
(15) 3025
(16) 1295
(17) 530
(18) 2254
(19) 4689
(20) 29658
(21) 18392
(22) 13850
(23) 11127
(24) 10720
(25) 8902
(26) 5942
(27) 3557
(28) 2586
(29) 5726
(30) 1074
(31) 2631
(32) 29211
(33) 42531
(34) 691
(37) 10
(64) 712
(65) 59
(128) 1

Вопрос - как бы мне "упаковать" хранимые указатели чтобы они жрали меньше памяти? При этом, конечно, должна быть возможность перебирать все указатели хранящиеся в элементе B "почти" так же быстро как и сейчас

Спасибо

[lit-uriy]

ты случаем не СУБД пишешь?

[spectre71]

Отношение многое ко многому.
В общем случае при достаточно случайном распределении - никак.

[Igors]

ты случаем не СУБД пишешь?

Нет, бог миловал.

[Igors]

Отношение многое ко многому.
В общем случае при достаточно случайном распределении - никак.

У меня тоже аж ни одной мысли  Не коррелированы они никак, частотный словарь даст 5-10% - не стоит возиться. Обидно подымать лапки в верх как оте STL-вские зайчики 

[spectre71]

Отношение многое ко многому.
В общем случае при достаточно случайном распределении - никак.

У меня тоже аж ни одной мысли  Не коррелированы они никак, частотный словарь даст 5-10% - не стоит возиться. Обидно подымать лапки в верх как оте STL-вские зайчики 

10'000'000 индексов не так и много, если в данной задаче пиковое кол-во не будет существенно больше, то даже не стоит заморачиваться.

[Igors]

10'000'000 индексов не так и много, если в данной задаче пиковое кол-во не будет существенно больше, то даже не стоит заморачиваться.

Так это всего для миллиона элементов массива A, а их может быть и 10-20 млн

[spectre71]

10'000'000 индексов не так и много, если в данной задаче пиковое кол-во не будет существенно больше, то даже не стоит заморачиваться.

Так это всего для миллиона элементов массива A, а их может быть и 10-20 млн

Если объем превысит некоторое установленное(или расчитанное) значение можно сохранять данные в файле и использавать "file mapping".
Например:

uchar * QFile::map ( qint64 offset, qint64 size, MemoryMapFlags flags = NoOptions )
bool QFile::unmap ( uchar * address )

[Igors]

Я тут подумал, кое-что вырисовывается. Рассмотрим очень упрощенный вариант: мы хотим упаковать всего 31 наиболее часто встречающихся указателя (ну или 63 в 64 битах). Тогда выходит так:

- отбираем 31 наиболее часто встречающихся указателя и помещаем их в отдельный массив С

- для каждого элемента массива В смотрим имеет ли он 2 или более указателя находящихся в С. Если да - имеет смысл его паковать 

- пакуем массив указателей: выкидываем из него все элементы которые есть в C, при этом взводим бит в маске.

- переписываем  массив - сначала записываем маску, потом все неупакованные указатели

- использование (когда нужно перебрать все указатели в В): проверяем является ли первый указатель маской. Младший бит взведен (нечетный адрес), значит это маска, выбираем указатели из С используя биты маски. Пример: маска 0x00A3, надо взять 0-й, 4-й и 6-й указатели из C

Пока неясно как завести более длинный "словарь С"


 

[spectre71]

Я тут подумал, кое-что вырисовывается. Рассмотрим очень упрощенный вариант: мы хотим упаковать всего 31 наиболее часто встречающихся указателя (ну или 63 в 64 битах). Тогда выходит так:

- отбираем 31 наиболее часто встречающихся указателя и помещаем их в отдельный массив С

- для каждого элемента массива В смотрим имеет ли он 2 или более указателя находящихся в С. Если да - имеет смысл его паковать  

- пакуем массив указателей: выкидываем из него все элементы которые есть в C, при этом взводим бит в маске.

- переписываем  массив - сначала записываем маску, потом все неупакованные указатели

- использование (когда нужно перебрать все указатели в В): проверяем является ли первый указатель маской. Младший бит взведен (нечетный адрес), значит это маска, выбираем указатели из С используя биты маски. Пример: маска 0x00A3, надо взять 0-й, 4-й и 6-й указатели из C

Пока неясно как завести более длинный "словарь С"

Это имеет смысл если есть достаточное кол-во повторяющихся поднаборов индексов.
В этом случае словарей(C) можно сделать и больше.
1bit - указывает на тип индекса: 0 - прямой, 1-набор из словаря
если 0 - то индекс берем как есть
если 1 - то индекс берем из словаря
(Если тип индекса int32, то простая проверка на > или < 0)

Для словарного индекса, например:
15bit - номер словаря (32768 - словарей)
16bit - маска

[spectre71]

Также не обязательно использовать всегда 15bit для номера словаря.
Для некоторых словарей может быть и другой расклад, например:
10bit - номер словаря
21bit - маска