Здравствуйте, _FRED_, Вы писали:
_FR>Спасибо. Правильно я понимаю, что в таком разе с каждой дельтой нужно будет ещё и хранить и размер этой дельты или полагаться, что она всегда не болшьше некоторого значения (если мы не говорим о представлении данных в виде строки)? _FR>Например, если абсолютное значение — четырёхбайтовое то дельта двух- или даже одно- байтовая и экономия за счёт этого?
Нужно использовать какую-нибудь схему кодирования с переменной длиной. Простой пример:
Число от 0 до 2^7 — 1 хранится в одном байте со старшим нулевым битом.
Число от 0 до 2^14 — 1 хранится в двух байтах, в первом байте старший бит единица и 7 битов на число, во втором байте старший бит ноль и 7 битов на число. В итоге на число уходит 14 битов и 2 служебных бита.
Число от 0 до 2^21 — 1 хранится в трёх байтах, в первом байте старший бит единица и 7 битов на число, во втором байте старший бит единица и 7 битов на число, в третьем байте старший бит ноль и 7 битов на число. В итоге на число уходит 21 бит и три служебных бита.
Тут идут пересечения по первому диапазону, поэтому можно чуть лучше сделать, это не суть.
Это один из примеров, можно и другие примеры кодировки придумать.
_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
Тут все советуют как хранить, но кто читать эти данные будет?
точно нужна экономия диска, вроде данных то на копейки.
не проще ли выранивать по 2/4 байта, и потом с базы лить блобы ? там же и кеши и оптимизации и все что хочешь. надо ли читать данные в какой-то конкретный день или читается все сразу за неделю?
конечно продажи скорее всего читают линейно и можно вообще уложить год в один массив.
366*32=~10кб
10 лет — 100кб на позицию
1млн позиций 100 гб такое даже в ОЗУ влезет
Здравствуйте, _FRED_, Вы писали: _FR>А что может дать хранение дельты по сравнению с хранением абсолютного значения?
То, что маленькие дельты будут встречаться чаще больших. Это позволит применить схему неравномерного кодирования, и сократить общую длину.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, merge, Вы писали:
M>Надо это хранить в базе занимая как можно меньше места. Период в среднем может быть 30 дней. Получается будет порядка 100 байт в среднем. M>Пока вот первое что в голове есть — через тире.
Можно так и хранить как байты, можно как base64.
Могут быть проблемы с little-big-endian, но вряд ли это актуально.
Здравствуйте, merge, Вы писали:
M>необязательно строка. а, понял мысль. ты предлагаешь одно поле blob сделать и в нем хранить unsigned int16 массив по сути?
Здравствуйте, 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.
Здравствуйте, cppguard, Вы писали:
C>Здравствуйте, merge, Вы писали:
M>>Надо это хранить в базе занимая как можно меньше места. M>>Пока вот первое что в голове есть — через тире. C>
C>Такие задачи очень сильно зависят от последующих режимов чтения. Если не оглядываться на них, то нужно хранить в двоичном формате дельты и сжимать gzip. Получится очень близко к эффективному размеру информации, ниже которого сжимать можно только с потерями.
я про такое слышал, но реализацией не занимался.
можно примером пояснить?
к примеру такие данные есть: 5 — 8 — 4 — 12 в дельте будут как и как потом храним в двоичном виде?
а сжатие оно имеет тут смысл если строка редко будет больше 100 байт? а то мне кажется сжатие\расжатие не очень быстрая операция и есть смысл на больших размерах данных
Обычно в подобных ситуациях — меньше. А так — надо мерять.
_FR>Если бы все числа были бы порядка нескольких тыщ, то я вижу выгоду от хранения небольшой дельты вместо большого абсолюта. А будет ли польза дельты если каждое число, допустим, случайно? Можно пример?
Если каждое число случайно, конечно никакого выигрыша не будет. Это попытка найти некоторую закономерность и сжать данные за счёт этого.
Есть такой массив чисел. кол-во продаж по дням недели за некоторый период.
Надо это хранить в базе занимая как можно меньше места. Период в среднем может быть 30 дней. Получается будет порядка 100 байт в среднем.
Пока вот первое что в голове есть — через тире.
Думал над генерацией хэша еще. У кого какие мысли
Здравствуйте, merge, Вы писали:
M>Надо это хранить в базе занимая как можно меньше места. M>Пока вот первое что в голове есть — через тире.
Такие задачи очень сильно зависят от последующих режимов чтения. Если не оглядываться на них, то нужно хранить в двоичном формате дельты и сжимать gzip. Получится очень близко к эффективному размеру информации, ниже которого сжимать можно только с потерями.
Здравствуйте, Nuzhny, Вы писали:
N>Здравствуйте, merge, Вы писали:
M>>1-4-5-63-2-43-23-31-123-343-312-5646-12-42-4533-1123-552
N>Можно использовать unsigned int16, у тебя явно не больше 32 тысяч продаж. Если этого не хватает, то хранить не абсолютные значения, а дельты.
я плохо объяснил. массив целых чисел надо эффективно хранить в базе. Пока вариант рассматривал только строкой в виде 1-4-5-63-2-43-23-31-123-343-312-5646-12-42-4533-1123-552
на бэке, да, unsigned int16 эффективней int будет.
или я не понял мысль)
Здравствуйте, merge, Вы писали:
M>я плохо объяснил. массив целых чисел надо эффективно хранить в базе. Пока вариант рассматривал только строкой в виде 1-4-5-63-2-43-23-31-123-343-312-5646-12-42-4533-1123-552 M>на бэке, да, unsigned int16 эффективней int будет. M>или я не понял мысль)
В базе — это обязательно строка? Вот твоя строка по байту на символ занимает 56 байт. Если хранить эти 17 значений каждое как uint16, то будет 34 байта. Это же маленькие blob, нет?
Здравствуйте, Nuzhny, Вы писали:
N>Здравствуйте, merge, Вы писали:
M>>я плохо объяснил. массив целых чисел надо эффективно хранить в базе. Пока вариант рассматривал только строкой в виде 1-4-5-63-2-43-23-31-123-343-312-5646-12-42-4533-1123-552 M>>на бэке, да, unsigned int16 эффективней int будет. M>>или я не понял мысль)
N>В базе — это обязательно строка? Вот твоя строка по байту на символ занимает 56 байт. Если хранить эти 17 значений каждое как uint16, то будет 34 байта. Это же маленькие blob, нет?
необязательно строка. а, понял мысль. ты предлагаешь одно поле blob сделать и в нем хранить unsigned int16 массив по сути?
Здравствуйте, merge, Вы писали:
M>Есть такой массив чисел. кол-во продаж по дням недели за некоторый период. M>1-4-5-63-2-43-23-31-123-343-312-5646-12-42-4533-1123-552
В строке выше 17 значений. Как это связано с днями недели? Может имелись в виду дни месяца (для каждого месяца хранить количество продаж за каждый день)?
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, _FRED_, Вы писали:
_FR>Здравствуйте, merge, Вы писали:
M>>Есть такой массив чисел. кол-во продаж по дням недели за некоторый период. M>>1-4-5-63-2-43-23-31-123-343-312-5646-12-42-4533-1123-552
_FR>В строке выше 17 значений. Как это связано с днями недели? Может имелись в виду дни месяца (для каждого месяца хранить количество продаж за каждый день)?
да, ошибься. месяца. есть период в двух других полях и есть 2 поля: в одном храним по дням за весь период, во втором по неделям на этот же период
Здравствуйте, merge, Вы писали:
M>>>Есть такой массив чисел. кол-во продаж по дням недели за некоторый период. M>>>1-4-5-63-2-43-23-31-123-343-312-5646-12-42-4533-1123-552
_FR>>В строке выше 17 значений. Как это связано с днями недели? Может имелись в виду дни месяца (для каждого месяца хранить количество продаж за каждый день)? M>да, ошибься. месяца. есть период в двух других полях и есть 2 поля: в одном храним по дням за весь период, во втором по неделям на этот же период
Известно, на сколько большими могут быть числа? Если нормализация данных (в каждой строке хранить дату и количество продаж) по какой-то причине не подходит и нужно всё в строке, да и место сэкономить, то можно поработать над уменьшением длины строки.
Например, числа записывать не в десятичном формате, а в 52-ричном (английский алфавит с прописными и заглавными буквами) или даже ещё больше, набор символов можно выбрать произвольный.
Блоб, в котором просто массив целых (из подходящего числа битов), кажется (кто его знает, что у вас за база?), будет ещё экономнее (но, возможно, менее удобно). Чтобы как-то оптимизировать дальше размер этого блоба (если требуется) нужно что-то знать дополнительное об этих числах.
Help will always be given at Hogwarts to those who ask for it.
_FR>Известно, на сколько большими могут быть числа? Если нормализация данных (в каждой строке хранить дату и количество продаж) по какой-то причине не подходит и нужно всё в строке, да и место сэкономить, то можно поработать над уменьшением длины строки.
да, уход от нормализации как раз связан с производительностью и объемом. там было порядка 150к строк на вставку и энтити умирал на этой вставке. а просто балком вставить сложно потому, что там винегрет-транзакция из даппера + вставка других данных без балка.
_FR>Например, числа записывать не в десятичном формате, а в 52-ричном (английский алфавит с прописными и заглавными буквами) или даже ещё больше, набор символов можно выбрать произвольный.
а есть готовые алгоритмы или либы для этого?
_FR>Блоб, в котором просто массив целых (из подходящего числа битов), кажется (кто его знает, что у вас за база?), будет ещё экономнее (но, возможно, менее удобно). Чтобы как-то оптимизировать дальше размер этого блоба (если требуется) нужно что-то знать дополнительное об этих числах.
база мсскл — 19. ну получается, что 52 ричный формат или блоб уже особой разницы не играют, всё равно придется конвертер писать на бэке до\перед вставкой?
на бэке работа идёт с линейный списком, то есть 10 дней будет как 10 элементов массива, просто в базе будет 1 строка и продажи будут в одном поле
Число хранится в переменном числе байтов, можно посмотреть в UTF-8 как сделано, в принципе вариантов много.
Сначала хранится абсолютное значение за 1 число, все последующие числа это разность между предыдущим и текущим. Т.е. если продажи 120, 105, 110, то хранятся числа 120, -15, +5.
Альтернативный подход: сначала просто записать числа как есть, можно в 4-байтовом формате, без выпендрёжа, в общем, а потом прогнать через какой-нибудь библиотечный gzip.
Думаю, будет плюс-минус одно и то же.
Ну или готовиться к хардкорному познанию алгоритмов сжатия и адаптации под конкретный случай, но это уже сложно.
Здравствуйте, vsb, Вы писали:
vsb>Сначала хранится абсолютное значение за 1 число, все последующие числа это разность между предыдущим и текущим. Т.е. если продажи 120, 105, 110, то хранятся числа 120, -15, +5.
А что может дать хранение дельты по сравнению с хранением абсолютного значения?
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, _FRED_, Вы писали:
FRE> А что может дать хранение дельты по сравнению с хранением абсолютного значения?
Да ничего, скорее всего, не даст. Тут и так-то размер данных крошечный: даже если отвести 4 байта на количество продаж, то для 31 дня нужно хранить всего 124 байта. Если это сжимать, то точно не gzip т.к. он прибавит минимум 22 байта к сжатым данным. Если заполнить такой массив значениям от 1 до 31 (три байта остаются нулевыми) то deflate с дефолтным уровнем сжатия его сожмет до 54 байт. Отрицательные дельты вполне могут привести к ухудшению сжатия, да еще и усожнят получение значений на конкретный день месяца. Тут, скорее, нужно просто определиться с требуемым количеством байтов, чтобы число продаж уместилось, и не страдать фигней.
Здравствуйте, rudzuk, Вы писали:
R>Здравствуйте, _FRED_, Вы писали:
FRE>> А что может дать хранение дельты по сравнению с хранением абсолютного значения?
R>Да ничего, скорее всего, не даст. Тут и так-то размер данных крошечный: даже если отвести 4 байта на количество продаж, то для 31 дня нужно хранить всего 124 байта. Если это сжимать, то точно не gzip т.к. он прибавит минимум 22 байта к сжатым данным. Если заполнить такой массив значениям от 1 до 31 (три байта остаются нулевыми) то deflate с дефолтным уровнем сжатия его сожмет до 54 байт. Отрицательные дельты вполне могут привести к ухудшению сжатия, да еще и усожнят получение значений на конкретный день месяца. Тут, скорее, нужно просто определиться с требуемым количеством байтов, чтобы число продаж уместилось, и не страдать фигней.
оказалось, что может быть и годовые продажи, нечасто, но может. Квартал достаточно часто. так что получается 150 * 4 = 600 байт. это меняет что-то?
Здравствуйте, merge, Вы писали:
m> оказалось, что может быть и годовые продажи, нечасто, но может. Квартал достаточно часто. так что получается 150 * 4 = 600 байт. это меняет что-то?
Массив чытерыхбайтовых целых заполненный значениями от 1 до 150 deflate сжимает до 238 байт.
Здравствуйте, merge, Вы писали:
M>оказалось, что может быть и годовые продажи, нечасто, но может. Квартал достаточно часто. так что получается 150 * 4 = 600 байт. это меняет что-то?
А вам эти данные, внутренности, нужно когда-либо обновлять? Например, в строке данных за месяц исправить несколько каких-то значений?
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, _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, Вы писали:
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.
Для хранения — blob protobuf содержащий в обьект с repeated(на случай если захочется запихнуть еще что-нибудь)
Дополнительно для оптимизации хранить не абсолютное значение, а разницу с предидущим днем для всех кроме первого.
тут может выйти и хуже и лучше — и не факт что стоит возни
Здравствуйте, merge, Вы писали:
M>Есть такой массив чисел. кол-во продаж по дням недели за некоторый период. M>Надо это хранить в базе занимая как можно меньше места.
Здравствуйте, merge, Вы писали:
M>к примеру такие данные есть: 5 — 8 — 4 — 12 в дельте будут как и как потом храним в двоичном виде?
Реализации могут быть разные. Можно дельты сделать того же размера, что и опорное значение, тогда выгода будет только вместе с использованеим сжатия. Можно дельту сделать размером в 1 байт, но тогда значения, очевидно, должны попадать в 0..255. Ещё вместо разницы можно считать xor, тогда алгоритм будет работать и с вещественными числами. Одним словом — простор для фантазии.
M>а сжатие оно имеет тут смысл если строка редко будет больше 100 байт? а то мне кажется сжатие\расжатие не очень быстрая операция и есть смысл на больших размерах данных
Если строка меньше 100 байт, зачем вообще что-то сжимать?
Здравствуйте, 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 байта.