Здравствуйте, _FRED_, Вы писали:
_FR>Здравствуйте, merge, Вы писали:
M>>оказалось, что может быть и годовые продажи, нечасто, но может. Квартал достаточно часто. так что получается 150 * 4 = 600 байт. это меняет что-то?
_FR>А вам эти данные, внутренности, нужно когда-либо обновлять? Например, в строке данных за месяц исправить несколько каких-то значений?
нет. они один раз расчитываются и дальше только на чтение. Единственное, что нужно будет в линейный массив потом разложить это при считывании в энтити по дням
Здравствуйте, rudzuk, Вы писали:
r> m> оказалось, что может быть и годовые продажи, нечасто, но может. Квартал достаточно часто. так что получается 150 * 4 = 600 байт. это меняет что-то?
r> Массив чытерыхбайтовых целых заполненный значениями от 1 до 150 deflate сжимает до 238 байт.
Попробовал еще вариант с формированием строки чисел с разделителем. Рандомно сгенерировал числа от 10 до 2000. Сжимается лучше чем сырой массив (размер сырого массива/сжатого массива/сжатой строки с разделителями): 124/97/48, 600/376/217. В таком варианте кодирование с дельтами может еще сократить размер.
Здравствуйте, rudzuk, Вы писали:
r> Попробовал еще вариант с формированием строки чисел с разделителем. Рандомно сгенерировал числа от 10 до 2000. Сжимается лучше чем сырой массив (размер сырого массива/сжатого массива/сжатой строки с разделителями): 124/97/48, 600/376/217. В таком варианте кодирование с дельтами может еще сократить размер.
Блин, лажанулся с цифрами. На самом деле они хуже. Вообще, часто получается, что длина строки выходит меньше чем сжатый сырой масссив, а сжатие строки не всегда приводит к уменьшению размера (на месячном диапазоне строка всегда получается короче, но это на равномерно распределенном рандоме). В общем, нужно на реальных данных экспериментировать.
Здравствуйте, _FRED_, Вы писали:
vsb>>Сначала хранится абсолютное значение за 1 число, все последующие числа это разность между предыдущим и текущим. Т.е. если продажи 120, 105, 110, то хранятся числа 120, -15, +5.
_FR>А что может дать хранение дельты по сравнению с хранением абсолютного значения?
Если мы кодируем числа в кодировке с переменным числом битов, то чем меньше число, тем меньше битов нужно для его кодирования.
Здравствуйте, vsb, Вы писали:
vsb>>>Сначала хранится абсолютное значение за 1 число, все последующие числа это разность между предыдущим и текущим. Т.е. если продажи 120, 105, 110, то хранятся числа 120, -15, +5. _FR>>А что может дать хранение дельты по сравнению с хранением абсолютного значения?
vsb>Если мы кодируем числа в кодировке с переменным числом битов, то чем меньше число, тем меньше битов нужно для его кодирования.
А почему число будет меньше? В семпловой строке в стартовом сообщении разброс очень даже приличный:
Если бы все числа были бы порядка нескольких тыщ, то я вижу выгоду от хранения небольшой дельты вместо большого абсолюта. А будет ли польза дельты если каждое число, допустим, случайно? Можно пример?
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, merge, Вы писали:
_FR>>Например, числа записывать не в десятичном формате, а в 52-ричном (английский алфавит с прописными и заглавными буквами) или даже ещё больше, набор символов можно выбрать произвольный. M>а есть готовые алгоритмы или либы для этого?
Да это школьная задачка:
internal static class NumberFormatter
{
// 64-base alphabet: 10 digits, lower and upper letters (2x26), and @, and #private const string Characters = "0123456789@ABCDEFGHIJKLMNOPQRSTUVWXYZ#abcdefghijklmnopqrstuvwxyz";
private static readonly int Base = Characters.Length;
private static readonly double LogBase = Math.Log(Base);
private static readonly Encoding ThisEncoding = Encoding.ASCII;
private static readonly byte[] ByteArray = ThisEncoding.GetBytes(Characters);
private static readonly string[] StringsArray = Array.ConvertAll(Characters.ToArray(), ch => ch.ToString());
private const int StackAllocLimit = 22; // 22 symbols in enough to represent UInt128.MaxValue with base 64public static string ToString<T>(T number) where T : IBinaryInteger<T>, IMinMaxValue<T> {
var typedBase = T.CreateChecked(Base);
if(number < typedBase) {
var index = Int32.CreateChecked(number);
return StringsArray[index];
}//ifvar bufferArray = default(byte[]); // For huge numbers ;o)var length = GetResultLength(number);
var buffer = length <= StackAllocLimit ? stackalloc byte[length] : (bufferArray = ArrayPool<byte>.Shared.Rent(length));
try {
var index = length - 1; // Populating the buffer from the last symbol to the firstwhile(number > T.Zero) {
(number, var modulo) = T.DivRem(number, typedBase);
var characterIndex = Int32.CreateChecked(modulo);
Debug.Assert(index >= 0, $"index {{{index}}} < 0");
buffer[index] = ByteArray[characterIndex];
index--;
}//whilereturn ThisEncoding.GetString(buffer);
} finally {
if(bufferArray is not null) {
ArrayPool<byte>.Shared.Return(bufferArray, clearArray: true/* To be sure :o) Can be omitted in a trusted environment */);
}//if
}//trystatic int GetResultLength(T number) {
var value = number < T.MaxValue ? number + T.One : number;
var doubleValue = Double.CreateChecked(value);
return (int)Math.Ceiling(Math.Log(doubleValue) / LogBase);
}
}
}
Help will always be given at Hogwarts to those who ask for it.
Обычно в подобных ситуациях — меньше. А так — надо мерять.
_FR>Если бы все числа были бы порядка нескольких тыщ, то я вижу выгоду от хранения небольшой дельты вместо большого абсолюта. А будет ли польза дельты если каждое число, допустим, случайно? Можно пример?
Если каждое число случайно, конечно никакого выигрыша не будет. Это попытка найти некоторую закономерность и сжать данные за счёт этого.
Здравствуйте, merge, Вы писали:
M>>>оказалось, что может быть и годовые продажи, нечасто, но может. Квартал достаточно часто. так что получается 150 * 4 = 600 байт. это меняет что-то? _FR>>А вам эти данные, внутренности, нужно когда-либо обновлять? Например, в строке данных за месяц исправить несколько каких-то значений?
M>нет. они один раз расчитываются и дальше только на чтение. Единственное, что нужно будет в линейный массив потом разложить это при считывании в энтити по дням
Если на эти данные никому не нужно смотреть "глазами" прям в БД, я б хранил просто два-три-четыре (смотря какое максимальное значение ожидается) байта на каждый номер последовательно. Если считать, что числа эти случайные, то сжатие не сильно поможет. Кодированипе-декодирование будет не сложным и быстрым.
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, vsb, Вы писали:
_FR>>А почему число будет меньше? В семпловой строке в стартовом сообщении разброс очень даже приличный: _FR>>Может я не понимаю чего-то? vsb>Обычно в подобных ситуациях — меньше. А так — надо мерять.
_FR>>Если бы все числа были бы порядка нескольких тыщ, то я вижу выгоду от хранения небольшой дельты вместо большого абсолюта. А будет ли польза дельты если каждое число, допустим, случайно? Можно пример? vsb>Если каждое число случайно, конечно никакого выигрыша не будет. Это попытка найти некоторую закономерность и сжать данные за счёт этого.
Спасибо. Правильно я понимаю, что в таком разе с каждой дельтой нужно будет ещё и хранить и размер этой дельты или полагаться, что она всегда не болшьше некоторого значения (если мы не говорим о представлении данных в виде строки)?
Например, если абсолютное значение — четырёхбайтовое то дельта двух- или даже одно- байтовая и экономия за счёт этого?
Просто всё ещё кажется, что просто хранить данные в бинарном виде фиксированного размера "одно за другим" будет значительно экономнее.
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, _FRED_, Вы писали:
_FR>Спасибо. Правильно я понимаю, что в таком разе с каждой дельтой нужно будет ещё и хранить и размер этой дельты или полагаться, что она всегда не болшьше некоторого значения (если мы не говорим о представлении данных в виде строки)? _FR>Например, если абсолютное значение — четырёхбайтовое то дельта двух- или даже одно- байтовая и экономия за счёт этого?
Нужно использовать какую-нибудь схему кодирования с переменной длиной. Простой пример:
Число от 0 до 2^7 — 1 хранится в одном байте со старшим нулевым битом.
Число от 0 до 2^14 — 1 хранится в двух байтах, в первом байте старший бит единица и 7 битов на число, во втором байте старший бит ноль и 7 битов на число. В итоге на число уходит 14 битов и 2 служебных бита.
Число от 0 до 2^21 — 1 хранится в трёх байтах, в первом байте старший бит единица и 7 битов на число, во втором байте старший бит единица и 7 битов на число, в третьем байте старший бит ноль и 7 битов на число. В итоге на число уходит 21 бит и три служебных бита.
Тут идут пересечения по первому диапазону, поэтому можно чуть лучше сделать, это не суть.
Это один из примеров, можно и другие примеры кодировки придумать.
_FR>Просто всё ещё кажется, что просто хранить данные в бинарном виде фиксированного размера "одно за другим" будет значительно экономнее.
Надо считать на конкретных данных. Большого проигрыша тут быть не должно.
Для хранения — blob protobuf содержащий в обьект с repeated(на случай если захочется запихнуть еще что-нибудь)
Дополнительно для оптимизации хранить не абсолютное значение, а разницу с предидущим днем для всех кроме первого.
тут может выйти и хуже и лучше — и не факт что стоит возни
Здравствуйте, merge, Вы писали:
M>Есть такой массив чисел. кол-во продаж по дням недели за некоторый период. M>Надо это хранить в базе занимая как можно меньше места.
Здравствуйте, 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
Тут все советуют как хранить, но кто читать эти данные будет?
точно нужна экономия диска, вроде данных то на копейки.
не проще ли выранивать по 2/4 байта, и потом с базы лить блобы ? там же и кеши и оптимизации и все что хочешь. надо ли читать данные в какой-то конкретный день или читается все сразу за неделю?
конечно продажи скорее всего читают линейно и можно вообще уложить год в один массив.
366*32=~10кб
10 лет — 100кб на позицию
1млн позиций 100 гб такое даже в ОЗУ влезет
Здравствуйте, merge, Вы писали:
M>к примеру такие данные есть: 5 — 8 — 4 — 12 в дельте будут как и как потом храним в двоичном виде?
Реализации могут быть разные. Можно дельты сделать того же размера, что и опорное значение, тогда выгода будет только вместе с использованеим сжатия. Можно дельту сделать размером в 1 байт, но тогда значения, очевидно, должны попадать в 0..255. Ещё вместо разницы можно считать xor, тогда алгоритм будет работать и с вещественными числами. Одним словом — простор для фантазии.
M>а сжатие оно имеет тут смысл если строка редко будет больше 100 байт? а то мне кажется сжатие\расжатие не очень быстрая операция и есть смысл на больших размерах данных
Если строка меньше 100 байт, зачем вообще что-то сжимать?
Здравствуйте, _FRED_, Вы писали: _FR>А что может дать хранение дельты по сравнению с хранением абсолютного значения?
То, что маленькие дельты будут встречаться чаще больших. Это позволит применить схему неравномерного кодирования, и сократить общую длину.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, 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 более комфортный для процессора.
В результате кодирования массив целых преобразуется в массив 32-битных целых, но меньшего объема памяти, храню их в строке.
Хранимая последовательность у меня выглядит так:
Сортированный массив я анализировал на плотность встречающихся значений и разбивал на чейны 3 видов:
1. Range — идущие подряд n чисел начиная с M
2. Битмап — числа начиная с M кодируются битами, плотность 1 бит на число.
3. Разреженные массивы (дельта кодируется алгоритмами VLQ или GVE).
Все множество кодируется последовательностью таких чейнов, минимальный размер чейна 4 байта.