Сообщение Re: Хранение массива целых чисел от 22.04.2024 18:12
Изменено 22.04.2024 18:15 swame
Re: Хранение массива целых чисел
Здравствуйте, merge, Вы писали:
M>Есть такой массив чисел. кол-во продаж по дням недели за некоторый период.
M>Надо это хранить в базе занимая как можно меньше места. Период в среднем может быть 30 дней. Получается будет порядка 100 байт в среднем.
M>Пока вот первое что в голове есть — через тире.
M>Думал над генерацией хэша еще. У кого какие мысли
M>1-4-5-63-2-43-23-31-123-343-312-5646-12-42-4533-1123-552
Я занимался компактным сохранением последовательность чисел в строку.
Есть разница между несортированными и сортированными массивами.
В твоем случае несортированный.
И для тех и для других использовал дельту между соседними значениями.
И алгоритмы VLQ (используется например в git ) и GVE (используется в protobuf).
VLQ использует минимум 1 байт на хранимое значение, а GVE 6 байт на 4 значения.
По теме
https://habr.com/ru/companies/badoo/articles/451938/
https://habr.com/ru/articles/511646/
https://www.programmersought.com/article/28225953711/
http://roaringbitmap.org/software/
В результате кодирования массив целых преобразуется в массив 32-битных целых, но меньшего объема памяти, храню их в строке.
Хранимая последовательность у меня выглядит так:
"groupeddata": "4F4F6C39 394F4F85 31974F85 394F8539 4F394F39 6439394F 876C3964 85316464 87648531 64266C4F 31648564 4F853997 85858585 854F856C 31313164 39854F4F 396C8539 85858539 8585394F 394F3985 3939644F 85398585 85858539 64398585 976C4F64 3939854F 8531396C 85858585 39393939 39393939 4F4F4F4F 4F4F4F4F 85856C4F 6C646485 4F39396C 31974F4F 39393985 4F979739 4F6C854F 8597974F 39393939 39646439 6C973985 854F3985 3997974F 85399785 64979785 974F9797 976C6C39 64856497 26266464 85853985 64393939 646C3964 9787976C
....
26262626 26262626 26262626 26262626 85262626 1B262685 2828281B 28281B28 28281B28 54541B28 28282854 1B282828 28282828 28282828 28282828 281B2854 64641B1B 31316464 64313131 31316464 64646431 31312626 64643131 31316464 31312626 85853939 64642626 64313164 4B643164 31856439 85313164 85858585 39313185 64646439 2685854F 31646426 85262631 4F973985 3131316C 31316431 26313131 64646426 64646464 64313164 26313164 85858526 8531314B 26262626 64643131 85363685 64646485 6464644B 31312626 31643131 64643164 26263131 26263131 28286854 1B1B2828 28535453 681B541B 54286828 28885428 2843541B 5468681B 1B888188 1B1B881B 28881B81 00438168",
Сортированный массив я анализировал на плотность встречающихся значений и разбивал на чейны 2 видов:
1. Range — идущие подряд n чисел начиная с M
2. Битмап — числа начиная с M кодируются битами, плотность 1 бит на число.
3. Разреженные массивы (дельта кодируется алгоритмами VLQ или GVE).
Все множество кодируется последовательностью таких чейнов, минимальный размер чейна 4 байта.
M>Есть такой массив чисел. кол-во продаж по дням недели за некоторый период.
M>Надо это хранить в базе занимая как можно меньше места. Период в среднем может быть 30 дней. Получается будет порядка 100 байт в среднем.
M>Пока вот первое что в голове есть — через тире.
M>Думал над генерацией хэша еще. У кого какие мысли
M>1-4-5-63-2-43-23-31-123-343-312-5646-12-42-4533-1123-552
Я занимался компактным сохранением последовательность чисел в строку.
Есть разница между несортированными и сортированными массивами.
В твоем случае несортированный.
И для тех и для других использовал дельту между соседними значениями.
И алгоритмы VLQ (используется например в git ) и GVE (используется в protobuf).
VLQ использует минимум 1 байт на хранимое значение, а GVE 6 байт на 4 значения.
По теме
https://habr.com/ru/companies/badoo/articles/451938/
https://habr.com/ru/articles/511646/
https://www.programmersought.com/article/28225953711/
http://roaringbitmap.org/software/
В результате кодирования массив целых преобразуется в массив 32-битных целых, но меньшего объема памяти, храню их в строке.
Хранимая последовательность у меня выглядит так:
"groupeddata": "4F4F6C39 394F4F85 31974F85 394F8539 4F394F39 6439394F 876C3964 85316464 87648531 64266C4F 31648564 4F853997 85858585 854F856C 31313164 39854F4F 396C8539 85858539 8585394F 394F3985 3939644F 85398585 85858539 64398585 976C4F64 3939854F 8531396C 85858585 39393939 39393939 4F4F4F4F 4F4F4F4F 85856C4F 6C646485 4F39396C 31974F4F 39393985 4F979739 4F6C854F 8597974F 39393939 39646439 6C973985 854F3985 3997974F 85399785 64979785 974F9797 976C6C39 64856497 26266464 85853985 64393939 646C3964 9787976C
....
26262626 26262626 26262626 26262626 85262626 1B262685 2828281B 28281B28 28281B28 54541B28 28282854 1B282828 28282828 28282828 28282828 281B2854 64641B1B 31316464 64313131 31316464 64646431 31312626 64643131 31316464 31312626 85853939 64642626 64313164 4B643164 31856439 85313164 85858585 39313185 64646439 2685854F 31646426 85262631 4F973985 3131316C 31316431 26313131 64646426 64646464 64313164 26313164 85858526 8531314B 26262626 64643131 85363685 64646485 6464644B 31312626 31643131 64643164 26263131 26263131 28286854 1B1B2828 28535453 681B541B 54286828 28885428 2843541B 5468681B 1B888188 1B1B881B 28881B81 00438168",
Сортированный массив я анализировал на плотность встречающихся значений и разбивал на чейны 2 видов:
1. Range — идущие подряд n чисел начиная с M
2. Битмап — числа начиная с M кодируются битами, плотность 1 бит на число.
3. Разреженные массивы (дельта кодируется алгоритмами VLQ или GVE).
Все множество кодируется последовательностью таких чейнов, минимальный размер чейна 4 байта.
Re: Хранение массива целых чисел
Здравствуйте, merge, Вы писали:
M>Есть такой массив чисел. кол-во продаж по дням недели за некоторый период.
M>Надо это хранить в базе занимая как можно меньше места. Период в среднем может быть 30 дней. Получается будет порядка 100 байт в среднем.
M>Пока вот первое что в голове есть — через тире.
M>Думал над генерацией хэша еще. У кого какие мысли
M>1-4-5-63-2-43-23-31-123-343-312-5646-12-42-4533-1123-552
Я занимался компактным сохранением последовательность чисел в строку.
Есть разница между несортированными и сортированными массивами.
В твоем случае несортированный.
И для тех и для других использовал дельту между соседними значениями.
И алгоритмы VLQ (используется например в git ) и GVE (используется в protobuf).
VLQ использует минимум 1 байт на хранимое значение, а GVE 6 байт на 4 значения.
Но GVE более комфортный для процессора.
По теме
https://habr.com/ru/companies/badoo/articles/451938/
https://habr.com/ru/articles/511646/
https://www.programmersought.com/article/28225953711/
http://roaringbitmap.org/software/
В результате кодирования массив целых преобразуется в массив 32-битных целых, но меньшего объема памяти, храню их в строке.
Хранимая последовательность у меня выглядит так:
"groupeddata": "4F4F6C39 394F4F85 31974F85 394F8539 4F394F39 6439394F 876C3964 85316464 87648531 64266C4F 31648564 4F853997 85858585 854F856C 31313164 39854F4F 396C8539 85858539 8585394F 394F3985 3939644F 85398585 85858539 64398585 976C4F64 3939854F 8531396C 85858585 39393939 39393939 4F4F4F4F 4F4F4F4F 85856C4F 6C646485 4F39396C 31974F4F 39393985 4F979739 4F6C854F 8597974F 39393939 39646439 6C973985 854F3985 3997974F 85399785 64979785 974F9797 976C6C39 64856497 26266464 85853985 64393939 646C3964 9787976C
....
26262626 26262626 26262626 26262626 85262626 1B262685 2828281B 28281B28 28281B28 54541B28 28282854 1B282828 28282828 28282828 28282828 281B2854 64641B1B 31316464 64313131 31316464 64646431 31312626 64643131 31316464 31312626 85853939 64642626 64313164 4B643164 31856439 85313164 85858585 39313185 64646439 2685854F 31646426 85262631 4F973985 3131316C 31316431 26313131 64646426 64646464 64313164 26313164 85858526 8531314B 26262626 64643131 85363685 64646485 6464644B 31312626 31643131 64643164 26263131 26263131 28286854 1B1B2828 28535453 681B541B 54286828 28885428 2843541B 5468681B 1B888188 1B1B881B 28881B81 00438168",
Сортированный массив я анализировал на плотность встречающихся значений и разбивал на чейны 2 видов:
1. Range — идущие подряд n чисел начиная с M
2. Битмап — числа начиная с M кодируются битами, плотность 1 бит на число.
3. Разреженные массивы (дельта кодируется алгоритмами VLQ или GVE).
Все множество кодируется последовательностью таких чейнов, минимальный размер чейна 4 байта.
M>Есть такой массив чисел. кол-во продаж по дням недели за некоторый период.
M>Надо это хранить в базе занимая как можно меньше места. Период в среднем может быть 30 дней. Получается будет порядка 100 байт в среднем.
M>Пока вот первое что в голове есть — через тире.
M>Думал над генерацией хэша еще. У кого какие мысли
M>1-4-5-63-2-43-23-31-123-343-312-5646-12-42-4533-1123-552
Я занимался компактным сохранением последовательность чисел в строку.
Есть разница между несортированными и сортированными массивами.
В твоем случае несортированный.
И для тех и для других использовал дельту между соседними значениями.
И алгоритмы VLQ (используется например в git ) и GVE (используется в protobuf).
VLQ использует минимум 1 байт на хранимое значение, а GVE 6 байт на 4 значения.
Но GVE более комфортный для процессора.
По теме
https://habr.com/ru/companies/badoo/articles/451938/
https://habr.com/ru/articles/511646/
https://www.programmersought.com/article/28225953711/
http://roaringbitmap.org/software/
В результате кодирования массив целых преобразуется в массив 32-битных целых, но меньшего объема памяти, храню их в строке.
Хранимая последовательность у меня выглядит так:
"groupeddata": "4F4F6C39 394F4F85 31974F85 394F8539 4F394F39 6439394F 876C3964 85316464 87648531 64266C4F 31648564 4F853997 85858585 854F856C 31313164 39854F4F 396C8539 85858539 8585394F 394F3985 3939644F 85398585 85858539 64398585 976C4F64 3939854F 8531396C 85858585 39393939 39393939 4F4F4F4F 4F4F4F4F 85856C4F 6C646485 4F39396C 31974F4F 39393985 4F979739 4F6C854F 8597974F 39393939 39646439 6C973985 854F3985 3997974F 85399785 64979785 974F9797 976C6C39 64856497 26266464 85853985 64393939 646C3964 9787976C
....
26262626 26262626 26262626 26262626 85262626 1B262685 2828281B 28281B28 28281B28 54541B28 28282854 1B282828 28282828 28282828 28282828 281B2854 64641B1B 31316464 64313131 31316464 64646431 31312626 64643131 31316464 31312626 85853939 64642626 64313164 4B643164 31856439 85313164 85858585 39313185 64646439 2685854F 31646426 85262631 4F973985 3131316C 31316431 26313131 64646426 64646464 64313164 26313164 85858526 8531314B 26262626 64643131 85363685 64646485 6464644B 31312626 31643131 64643164 26263131 26263131 28286854 1B1B2828 28535453 681B541B 54286828 28885428 2843541B 5468681B 1B888188 1B1B881B 28881B81 00438168",
Сортированный массив я анализировал на плотность встречающихся значений и разбивал на чейны 2 видов:
1. Range — идущие подряд n чисел начиная с M
2. Битмап — числа начиная с M кодируются битами, плотность 1 бит на число.
3. Разреженные массивы (дельта кодируется алгоритмами VLQ или GVE).
Все множество кодируется последовательностью таких чейнов, минимальный размер чейна 4 байта.