Как сохранить миллион в более сжатом виде?

[Don Leno]

Есть база данных, в которой содержатся большие числа. Вопрос: как записать большие значения цифр, к примеру - 1 000 000 в более сжатом виде? Если сохранять как строку, то занимает аж 7 байт.

[ger_kar]

Вообще оно конечно странно хранить числовые значения в строковом виде, для этого же есть специальные типы, то же Long или его эквиваленты для конкретного типа базы данных позволяет хранить числовые значения в диапазоне от -2147483648 до 2147483647

[Don Leno]

А как сохранить эти значения в файл и сколько они будут занимать места?

[Debugger]

А как сохранить эти значения в файл и сколько они будут занимать места?

Если файл будет иметь бинарный формат - то 4 байта. Почти в два раза сжал.

[Mikle]

Сначала нужно определиться, с какой точностью будут числа, будут ли дроби, какие минимальное и максимальное значения.
А Long по сравнению с записью строкой в ASCII даст как раз двукратный выигрыш. Строка "1000000"- это 7 байт плюс разделитель, то есть 8 байт, а Long имеет фиксированный размер и не требует разделителя.
С другой стороны, десятичные цифры пакуются по две на байт, разделитель тоже может быть полубайтным, получаем равенство размера с Long на семизначных числах.

[pronto]

Если числа не будут превышать значения 1000000, то можно обойтись 20-ю битами (2,5 байта). Будет немного сложнее (и дольше) работать с битовым массивом, но даст желанную компактность. Если больше знать о характере данных, то можно ещё придумать способы.

[Don Leno]

Спасибо за ответы, но можно хоть немного теории как реализовать такие алгоритмы, как программить? Особенно понравилось про 2,5 байта))) Числа целые, не дробные. Варьируются от 0 до 1 000 000.

[pronto]

Нумерация бит начинается с ноля. Порядок нумерации справа налево (little endian).
Если биты сгруппировать в байты, то байты нумеруются по тем же правилам.
Биты слева - старшие. Биты справа - младшие.

Код: Выделить всё

31  29  27  25  23  21  19  17  15  13  11   9   7   5   3   1
--==--==--==--==--==--==--==--==--==--==--==--==--==--==--==--==
  30  28  26  24  22  20  18  16  14  12  10   8   6   4   2   0

Код: Выделить всё

      dec        bin
2^0 = 1   = 00000001
2^1 = 2   = 00000010
2^2 = 4   = 00000100
2^3 = 8   = 00001000
2^4 = 16  = 00010000
2^5 = 32  = 00100000
2^6 = 64  = 01000000
2^7 = 128 = 10000000


Степень двойки — порядковый номер бита.
Смещение бит влево на N позиций производится умножением числа на 2^N.
Смещение бит вправо на N позиций производится делением числа на 2^N.

Все числа в примерах в десятичной записи.

Установка бита

Код: Выделить всё

v& = v& or 1 ' установлен бит под номером 0
v& = v& or 64 ' установлен бит под номером 6

Сброс бита

Код: Выделить всё

v& = v& and (not 1) ' сбросить бит 0
v& = v& and (not 64) ' сбросить бит 6

Установка группы бит

Код: Выделить всё

v& = v& or 12 ' установить биты 2 и 3. 12 = 2^2 + 2^3 = 4 + 8
v& = v& or 255 ' установить биты 0-7

Сброс группы бит

Код: Выделить всё

v& = v& and (not 12) ' сбросить биты 2 и 3

Чтение значения битового поля

Код: Выделить всё

bitpart& = (v& and 12) \ 4

Проверка значения бита

Код: Выделить всё

If v& and 64 then ' истина, ести бит 6 установлен

If (v And 32) Then
   If (v And 128) Then
      Debug.Print "Оба бита (5 и 7) установлены"
   End If
End If

If (v And 32) or (v And 128) Then
      Debug.Print "Один из бит установлен"
End If

[Don Leno]

Mikle, если тебе не трудно опиши как сохранить Long в файл?!

[Mikle]

Открой файл For Binary
Сохраняй с помощью Put desc, var

[pronto]

Вариант с 20 битами отпадает, надо полагать? Чуть подробнее про запись в файл в двоичном режиме:

Код: Выделить всё

Put #[дескриптор_файла], [позиция_записи_в_файле], [переменная_или_массив]

[Don Leno]

То есть достаточно открыть в бинарном режиме и записать лонг?! Так просто)))
А считывать как понимаю также через Get. Спасибо!
Pronto, а разве не лучше узнать все варианты? Интересно ведь! Кстати я не совсем понимаю твой алгоритм. Как он работает на реальном примере? Может расскажешь?

[pronto]

В моём позопрошлом сообщении нет никакого алгоритма. Там собраны способы работы с отдельными битами в целочисленных типах переменных. Для начала, нужно каждую из операций осмыслить. Чтобы было проще это делать, вот функция по преобразованию из десятичной формы записи в двоичную:

Код: Выделить всё

Function ValueToBin(ByVal value As Long) As String
    Const ConvTable$ = "0000000100100011010001010110011110001001101010111100110111101111"
    '                   ====----====----====----====----====----====----====----====----
    '                      0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15

    Dim i As Long, qbitpart As Long, msb As Boolean

    ValueToBin = String(39, " ")

    If value And &H80000000 Then
        value = value And Not &H80000000: msb = True
    End If

    For i = 7 To 0 Step -1
        qbitpart = value And &HF: value = value \ &H10
        Mid$(ValueToBin, i * 5 + 1, 4) = Mid$(ConvTable, qbitpart * 4 + 1, 4)
    Next i

    If msb Then Mid$(ValueToBin, 1, 1) = "1"

End Function

Пользоваться ею вот так:

Код: Выделить всё

Dim bVal As Byte
Dim iVal As Integer
Dim lVal As Long

bVal = 153   ' = &H99
iVal = 19455 ' = &H4BFF
'lVal = &HBEDECAFE ' переполнение
Debug.Print Hex(bVal), Right(ValueToBin(CLng(bVal)), 9)
Debug.Print Hex(iVal), Right(ValueToBin(CLng(iVal)), 19)

lVal = &H3EDECAFE
Debug.Print Hex(lVal), ValueToBin(lVal)
Debug.Print "80000000", ValueToBin(&H80000000)
lVal = lVal Or &H80000000
Debug.Print Hex(lVal), ValueToBin(lVal)

ЗЫ Функция ValueToBin взята отсюда

[Don Leno]

То есть функция ValueToBin может принимать любое значение Long и переводит его в двоичный код?

[pronto]

Не в двоичный код, а в текстовое представление двоичного кода. На одит бит приходится один символ. Символ — «1» и «0». Символ «1» имеет код 49, а «0» — 48. Например, число 49 в двоичном виде примет вид 0011 0001. При условии, что на один символ отводится один байт.
То есть, текстовое представление числа 49 займёт 9 байт, символьное представление (именно его видно на экране) — 2 байта, а двоичное — 1 байт.

[Don Leno]

Спасибо Pronto. Я пойду разбирать твою функцию чтобы лучше понять как все работает. Особенно благодарен за пояснения)))

[Адская_Капча]

Прошу у всех прощения за долгое отсутствие. Капча закрутилась, закрутилась, времени форумиться совсем не оставалось...

Хотелось бы спросить у TC - а какие числа-то преобладают, большие или маленькие?
Если маленькие - может имеет смысл их хранить по аналогии с UTF-8? Чем меньше число, тем меньше размера оно занимает (вплоть до 1 байта)

[Don Leno]

pronto, я понял! ValueToBin позволяет хранить числа от 0 до 65535 в двух байтах. А если добавить еще полбайта, получится что можно хранить значения аж до 1 000 000 в 2,5 байтах!!! Я проанализировал работу самой функции и смотрел значения что выводятся в дебаггере, но вот не могу я разобрать сам код пока. Может ты прокомментируешь строки кода ValueToBin?
Как я знаю значений в 8 битах всего 256 (от 0 до 255), то есть когда число превышает этот порог, то ValueToBin устанавливает слева в другой восьмерке младший бит в 1. И так по увеличению. И если добавить еще добавлять битов, то он сможет хранить значение еще больше чем 1 000 000)))

[Don Leno]

Мне эта функция напомнила когда я читал по подключениям к ФТП. Там порт нужно было задавать двумя числами (байтами):
например порт: 13012
13012/256=50 остаток 212
в итоге можно число порта записать двумя байтами 50 и 212.
Чтобы вернуть в исходное значение:
50*256=12800 + 212 = 13012!!
То же самое только не с битами а с числами)))

Хм, так кто мешает добавить еще один байт чтобы хранить миллионы? К примеру:
4 120 700

4120700/65536 (или 256^2) = 62 остаток 57 468
57468/256= 224 остаток 124

В итоге число 4 120 700 можно записать 3 байтами: 62, 224 и 124 )))
Обратное преобразование:
62*65536= 4 063 232
224*256= 57 344
4 063 232 + 57 344 + 124 = 4 120 700

В итоге по этому алгоритму можно хранить в 3 байтах значения до 16 842 752 (256^3 + 256^2)!
P.S.
Интересно, код который привел pronto будет работать быстрее чем мой алгоритм?

[pronto]

ValueToBin не позволяет хранить числа. Она преобразует один вид записи в другой и не имеет отношения к поставленной задаче. Я её привёл для того, чтобы можно было нагляднее изучать действия с отдельными битами.
Например, есть число 5616. В двоичном виде примет вид "1 0101 1111 0000". Этот вид и есть результат работы функции ValueToBin.
Вот так выглядил бы вызов функции в коде программы:

Код: Выделить всё

Dim BinaryRepresentation As String ' объявление текстовой переменной
BinaryRepresentation = ValueToBin(5616)

Переходим к сдвигу бит влево/вправо. Ещё раз.
Чтобы сдвинуть биты вправо на N позиций, то нужно число разделить на 2^N.
Чтобы сдвинуть биты влево на N позиций, то нужно число умножить на 2^N.

Например, хочу сдвинуть биты в числе 5616 на 4 позиции вправо.
2^4 (2 в степени 4) = 16
5616 / 16 = 351

Опять обращаюсь к функции ValueToBin, чтобы убедиться, что биты действительно переместились
BinaryRepresentation = ValueToBin(351)
BinaryRepresentation будет содержать результат преобразования числа 351 — "1 0101 1111"

Теперь всё вместе.

Код: Выделить всё

5616 = 1 0101 1111 0000
351  = 0 0001 0101 1111 (обычно, если все старшие биты, которые слева, равны нулю, то они не пишутся)


Чтобы понять работу функции нужно взять любое число в пределах [0; 4294967295] и повторить весь алгоритм (со всеми итерациями) на листочке. Если возникнут конкретные вопросы, то спрашивай.

ЗЫ. Не рассматривай байты в отдельности. Если число объявлено 4-мя байтами, то все манипуляции с ним происходят в 32-разрядных регистрах процессора. Кстати, твои расчёты относительно числа 16 842 752 неверны, так как 2^24 (24 = количество бит в трёх байтах) = 16 777 215

[Don Leno]

Pronto спасибо за подробный коммент!
Буду тестить на листочке))) Позже отпишусь о результатах

ЗЫ Про байты. Но суть мне же их файл сохранить надо. То есть мне надо знать сколько мое число будет занимать в файле. Чтобы правильно организовать базу данных.
А расчеты неверны эт точно, я на калькуляторе считал неправильно))))

[pronto]

На всякий случай прокомментирую функцию ValueToBin

Код: Выделить всё

Function ValueToBin(ByVal value As Long) As String
    Const ConvTable$ = "0000000100100011010001010110011110001001101010111100110111101111"
    '                   ====----====----====----====----====----====----====----====----
    '                      0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15

    Dim i As Long, qbitpart As Long, msb As Boolean

   ' Резервирование места под результат
   ' строка заполняется пробелами
   ' 39 = 32 (кол-во бит) + 7 (пробелы между четырмя битами)
    ValueToBin = String(39, " ")

   ' Проверка 31-го бита (самого старшего в переменной value)
    If value And &H80000000 Then
       
        ' Сброс верхнего бита в переменной. Это нужно для последующих сдвигов.
        ' такая ситуация вытекает из особенностей интерпритации целого числа со знаком.
        value = value And Not &H80000000
       
        ' так как бит сброшен, то в переменной msb запоминается этот факт
        msb = True
    End If

   ' 32 (кол-во бит) / 4 = 8
   
   ' цикл от 7 до 0, всего 8 итераций
    For i = 7 To 0 Step -1
      ' вычисление номера кубита (четырёх бит) в ConvTable

      ' Если в маске бит = 1, то в результате он остаётся.
      ' Это вытекает из таблицы истинности оператора AND (Конъюнкция)
      ' V     M   R  (V - переменная, M - маска, R - результат)
      ' 0 AND 0 = 0
      ' 0 AND 1 = 0
      ' 1 AND 0 = 0
      ' 1 AND 1 = 1
     
      ' для числа 5616
      ' V = 5616     = 0000 0000 0000 0000 0001 0101 1111 0000
      ' M = 15 = &HF = 0000 0000 0000 0000 0000 0000 0000 1111
      ' R =            0000 0000 0000 0000 0000 0000 0000 0000
     
        qbitpart = value And &HF
       
      ' qbitpart = 0
     
      ' сдвиг бит на 4 позиции вправо
      ' используется целочисленное деление "\"
        value = value \ &H10
     
      ' value = 0000 0000 0000 0000 0000 0001 0101 1111
      ' для следующей итерации qbitpart примет значение 15
     
      ' копирование в результирующую переменную текстового представления
      ' младших четырёх бит заданного числа в аргументе функции
      ' i = 7, выражение i * 5 + 1 примет значение 7 * 5 + 1 = 35 + 1 = 36
      ' это получилась позиция вставки в результирующую строку
      '
      ' qbitpart = 0, выражение qbitpart * 4 + 1 примет значение 0 * 4 + 1 = 0 + 1 = 0
      ' это получилась позиция копирования из ConvTable
      ' по этой позиции возьмётся текст "0000"
        Mid$(ValueToBin, i * 5 + 1, 4) = Mid$(ConvTable, qbitpart * 4 + 1, 4)
    Next i

   ' если в исходном числе был снят старший бит, то в результате
   ' нужно первый символ установить в "1"
    If msb Then Mid$(ValueToBin, 1, 1) = "1"

End Function

Про байты. Приведи пример, как будут сохраняться 3 байта? А 2,5?

[Don Leno]

Вот сохранение в 3 байта. Написал на скорую руку, так что строго не судить)))

[Don Leno]

Про 2,5 байта расскажу в теории:

0000 0000 0000 0000 0000
____..............-----..-----
0,5 б -- 2-й б --- 1-й байт--

В первом байте хранятся значения от 0-255 (256 значений). Когда значение превышает это число, то ко второму байту устанавливается младший бит в 1. То есть значение 256 будет выглядеть так:

0000 0000 0001 0000 0000 = 256
0000 0000 0011 0000 0000 = 512
0000 0000 0111 0000 0000 = 1024
...
0000 1111 1111 1111 1111 = 65536
0001 1111 1111 1111 1111 = 131072
и т.д.

В таком случае в двух байтах храниться числа от 0 до 65536. А остальные в том числе и до миллиона в последних 0,5 байтах)))

Чтобы сохранить это значение достаточно, эти биты сконвертить в байты. Как я помню есть такие функции можно найти в нете BinatyToDecimal и обратно.

[pronto]

Don Leno просил строго не судить его алгоритм сохранения числа в трёх байтах (но очень хочется)... Отмечу лишь то, что ты так и не усвоил операции над отдельными битами(установка/снятие). И самое страшное — ты меняешь порядок следования байт в числе. Первым байтом у тебя считается 3-й байт, со вторым всё нормально по чистой случайности, третьим — первый (самый младший байт). Такого недосмотра за порядком байт могло бы и не быть, если бы была сделана обратная операция — чтение. Вообще, сохранение без возможности восстановления не имеет смысла...
По алгоритму. Маленькая подсказка. Поищи по форуму что-то вроде "LSet". Надо отметить, что этот метод использует возможности языка, а не чистой математики... Когда-нибудь доберёмся и до 2,5 байт

[goldexer]

Вообще, конечно, если числа как раз до миллиона хранятся в базе в урезанном до 20 бит числовом формате, а не в строках, то дальше уже некуда, дальше только посекционная архивация с предсказательным деархивированием и кешированием и другие методы, сильно урезающие быстродействие.

Подозреваю, что есть простор для пересмотра оптимизации и реструктуризации базы данных. Если просто хранить в ней таблицу с даже четырех-байтными «миллионами», так это же ё-мое, чтоб она стала хоть сколько нибудь большой (большой не в нашем понимании, а в понимании жесткого диска) это нужно каждому жителю земли сдать по четыре байта в аренду.

[pronto]

Не знаю как Don Leno относится к этой задаче... А я не пытаюсь достичь максимума компактности (для долгосрочного хранения — архиватор в помощь), я пытаюсь донести понимание, как это сделать быстро и несильно проиграть по скорости. Если бы оно было (понимание работы логических операций, разницы между двоичным и десятичным числом, что ничего никуда преобразовывать не надо), то задача становится элементарной, решение которой заняло бы (максимум) 30 мин.

[Don Leno]

pronto, вернулся к твоему первому сообщению по работе с битами.
К примеру, у меня есть числа от 0 до 255, возьму 0 и 255:

dec bin
0 00000000
255 11111111

Про установку и сбос битов есть такой вопрос. Могу ли я у числа 0 установить 8 бит в 1, а у числа 255 сбросить 4 бит в 0?
то есть получиться уже другое число в бинарном виде:

dec bin
? 00000001
? 11101111

Верно?!

[pronto]

Да, можешь. Только опять обращаю твоё внимание, что биты нумеруются справа налево и их счёт начинается с ноля.
Установка 8-го (на самом деле 7-го) бита будет выглядить вот так:

Код: Выделить всё

Dim Variable As Long
Variable = Variable Or 2^7

Результат Variable = 128(dec) = 1000 0000(bin)
2^7 можно сразу записать любым другим доступным способом.
Сброс 4-го (3-го) бита:

Код: Выделить всё

Dim Variable As Long
Dim Mask as Long
Variable = 255
Mask = 2^3
Mask = Not Mask
Variable = Variable And Mask

Обычно, используют более краткую запиь: Variable = Variable And (Not 2^3)
Результат Variable = 247(dec) = 1111 0111(bin)

[Don Leno]

спасибо, pronto.
Прочитал всю тему заново.
Про сброс и установку битов я теперь понял)))