|
|
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Добрый вечер! Можно ли запаковать в один Int(4-байта) два числа, первое - не превышает 9999, второе - не превышает 999999? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.01.2016, 00:30 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__, А нижние границы у чисел какие? Если 0, то нельзя. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.01.2016, 00:38 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
miksoft__Avenger__, А нижние границы у чисел какие? Если 0, то нельзя. Да, нижняя граница - 0. Спасибо, хотел лишь убедится, время уже позднее. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.01.2016, 00:42 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__хотел лишь убедится, время уже позднее.у вас 4+6=10 знаков, а 2 32 =4 294 967 296, т.е. всего лишь 9 с половиной знаков, что меньше ,чем 10. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.01.2016, 00:46 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
miksoft, а если попробовать хранить линейную комбинацию по определённым простым числам, пусть значение этой комбинации будет занимать 8 знаков или 8*3.3 = 27 бит. Этой информации будет скорее всего недостаточно. Потому оставшиеся 5 бит можно использовать для того чтобы хранить, например, разницу в количестве цифр двух чисел. Или что-нибудь ещё, что в дальнейшем поможет дешифровать исходные числа. Это всё в первом приближении, но скорее всего алгоритм позволяющий определенным образом зашифровать два этих числа в одно 32 битное существует ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.01.2016, 12:18 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Или такой формат: sq1 sh1 sq2 sh2 Корень подходящего порядка, остаток, корень подходящего порядка, остаток. Думаю 3 порядка хватит для того чтобы всё это уложилось в 32 бита ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.01.2016, 12:26 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
SashaMercuryИли такой формат: sq1 sh1 sq2 sh2 Корень подходящего порядка, остаток, корень подходящего порядка, остаток. Думаю 3 порядка хватит для того чтобы всё это уложилось в 32 бита нет, не подойдёт ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.01.2016, 12:37 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
SashaMercury, 10^10 > 2^32 ничего не выйдет ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.01.2016, 13:55 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__, числа независимы, или возможные значения одного как-то определяются другим? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.01.2016, 14:39 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Для хранения этих чисел нужно 34 бита. Т.е. напрямую нельзя впихнуть в 32 бита. Но если числа упаковываются потому что их много (файл, массив), и нужно экономить память, то можно завести 4 файла и хранить числа в нужном, в зависимости от значения 2-х не вместившихся битов. ЗЫ. Так конечно не надо делать ))) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.01.2016, 18:52 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, Числа независимы и уникальны в своих 10 знаках. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.01.2016, 22:28 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__, тогда это вопрос о хранении 10-значного десятичного числа в 32 битах ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.01.2016, 22:55 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov__Avenger__, тогда это вопрос о хранении 10-значного десятичного числа в 32 битах ) понято, что не о квадратуре круга ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.01.2016, 23:23 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ИзопропилAleksandr Sharahov__Avenger__, тогда это вопрос о хранении 10-значного десятичного числа в 32 битах ) понято, что не о квадратуре круга до 18721171 мне было непонятно, я не телепат ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.01.2016, 23:35 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Добрый вечер! Можно ли запаковать в один Int(4-байта) два числа, первое - не превышает 9999, второе - не превышает 999999? Можно, но паковать их прийдется на CUDA. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2016, 15:59 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
EoltМожно, но паковать их прийдется на CUDA. травой поделись ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2016, 16:18 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ИзопропилEoltМожно, но паковать их прийдется на CUDA. травой поделись Почему тут у всех такое плоское мышление? В 4 байта можно уложить диапазон целых чисел от 0 до 4294967295. В цикле от 1 до 4294967295 подаем счетчик числа на генератор случайных чисел в качестве стартового числа, генерируем пару чисел и проверяем совпали ли они с нужными. В 99% для пары чисел такое стартовое 4 байтовое число будет найдено. Подбор идет долго, распаковка мгновенная. Ответ на вопрос: Можно ли запаковать в один Int(4-байта) два числа да можно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2016, 19:28 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Добрый вечер! Можно ли запаковать в один Int(4-байта) два числа, первое - не превышает 9999, второе - не превышает 999999? Нельзя. int это 2^32 что ~4 млрд, тебе надо 10, т.е. максимум 9999999999, т.е. не лезет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2016, 19:43 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
можно запаковать 3'999 и 999'999 или 9'999 и 399'999, т.е. в итоге максимум будет 3'999'999'999 Если хочешь утрамбовать несколько чисел в двоичный тип, то ограничения бери двоичные, например первое не более 2^12, второе не более 2^20. Так проще и писать и читать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2016, 19:48 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
EoltПочему тут у всех такое плоское мышление? мышление у всех здесь просто адекватное, квадратурой круга и вечным двигателем не занимаемся ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2016, 20:20 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Можно в облаке таблицу используемых значений разместить, а в Int хранить индекс, влезет ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2016, 20:26 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TМожно в облаке таблицу используемых значений разместить, а в Int хранить индекс, влезет а если размер таблицы превысит 2^32? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2016, 20:50 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Изопропила если размер таблицы превысит 2^32? Во-первых статистически маловероятно, во-вторых это шутка была :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2016, 20:51 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TМожно в облаке таблицу используемых значений разместить, а в Int хранить индекс, влезет а если интернет отключат? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2016, 22:18 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Eoltа если интернет отключат? несущественно, ибо 10^10 таки больше чем 2^32 ЗЫ в трудные военные годы синус достигал значения два и даже три ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2016, 22:36 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Добрый вечер! Можно ли запаковать в один Int(4-байта) два числа, первое - не превышает 9999, второе - не превышает 999999? В задаче ничего не сказано про точность поэтому скажу что можно. Вспомните как рабоатют float и double при разрядности 32 и 64 бит они покрывают более широкий диапазон мантиссы чем целые. Хотя гарантируют фиксацию ведущих чисел мантиссы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.01.2016, 01:32 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
запаковать можно, распаковать нельзя ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.01.2016, 09:26 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Добрый вечер! Можно ли запаковать в один Int(4-байта) два числа, первое - не превышает 9999, второе - не превышает 999999? Если ты точно уверен, что не превышает: 1) миллион должен быть всегда (единичка миллиона это по сути разделитель двух чисел) 2) всё от миллиона до 10010000 - это твоё первое число 3) всё что до миллиона это твоё 2е число 4) всё что больше 10010000 - перебор. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.01.2016, 10:38 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
полагаю, речь о положительных числах :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.01.2016, 10:40 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Кто-то по прежнему утверждает, что задача имеет решение? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.01.2016, 11:04 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ИзопропилКто-то по прежнему утверждает, что задача имеет решение? предложите в качестве контраргумента пару чисел в рамках условия задачи, которые нельзя впихнуть и я признаю свою неправоту :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.01.2016, 11:16 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Apoj_sqlИзопропилКто-то по прежнему утверждает, что задача имеет решение? предложите в качестве контраргумента пару чисел в рамках условия задачи, которые нельзя впихнуть и я признаю свою неправоту :) задача в том, что упаковать нужно все возможные пары(0..9999,0..999999), а не какое-то подмножество ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.01.2016, 11:35 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Apoj_sqlпредложите в качестве контраргумента пару чисел в рамках условия задачи, которые нельзя впихнуть и я признаю свою неправоту :) как только ты покажешь свои процедуры Pack и Unpack, так сразу ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.01.2016, 11:39 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Изопропилзадача в том, что упаковать нужно все возможные пары(0..9999,0..999999), а не какое-то подмножество посчитал, действительно я не прав. сорри. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.01.2016, 11:44 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Apoj_sqlполагаю, речь о положительных числах :) Смотрите в корень постановки. В задаче сказано. Можно ли запаковать в один Int(4-байта) два ЧИСЛА , первое - не превышает 9999, второе - не превышает 999999? Обратите внимание. Не целых. Не финансовых. А просто два арифметических числа. Пример чисел: Число Пи, масса электрона и дробь одна третья удовлетворяют условиям. На целое здесь может намекать только формат ограничителей. Но кто скажет что арифметика различает 999999 и 999999.0 ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.01.2016, 11:55 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
maytonОбратите внимание. Не целых. Не финансовых. А просто два арифметических числа. Подозреваю что это просто два ID. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.01.2016, 13:55 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TmaytonОбратите внимание. Не целых. Не финансовых. А просто два арифметических числа. Подозреваю что это просто два ID. Кажется выше уже проверили что количество сочетаний 2х десятичных ID превышает лимит 32х битного целого. Тоесть в целых числах задача не решается. Возможно были завуалированы какие-то доп-ограничения которые мы не услышали. Например число A всегда меньше числа B. Тогда в сочетаниях появится дырка и возможно задача станет решаемой. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.01.2016, 14:00 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Марк, всё-же я думаю что речь шла о целых числах, ибо в первом сообщение тс использовал квалификатор типа Int. SSmiksoft, а если попробовать хранить линейную комбинацию по определённым простым числам, пусть значение этой комбинации будет занимать 8 знаков или 8*3.3 = 27 бит. Этой информации будет скорее всего недостаточно. Потому оставшиеся 5 бит можно использовать для того чтобы хранить, например, разницу в количестве цифр двух чисел. Или что-нибудь ещё, что в дальнейшем поможет дешифровать исходные числа. Это всё в первом приближении, но скорее всего алгоритм позволяющий определенным образом зашифровать два этих числа в одно 32 битное существует Казалось бы что нельзя. Автору требуется (10^10 - e) вариантов, значит при прямой адресации потребует 34 бита. Однако, несмотря на то, что я не нашёл подходящее решение, также не могу найти доказательство того что метод подобный описанному выше не существует. Если решение есть, то одним из возможных путей должен быть следующий алгоритм: 1. 32-k бит используются для того чтобы хранить линейную комбинацию вида: p1*max + p2*min. очевидно будут коллизии 2. k оставшихся бит использовать для устранения этих коллизий. К сожалению я не смог доказать что этот способ должен работать, но и доказать обратного я не смог также. Практически проверить сложно, ибо у меня нет доступа к машине которая может выполнить 10^10 операций достаточно быстро ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 08:49 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Всё было проще чем я думал. Доказал что и такой метод не применим ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 08:58 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Если речь об ID, которые генерятся счетчиками, то задача легко решается. Надо просто пределы обоих пересмотреть, т.е. не 9999 и 999999, а 4096 и 1048576, или 8192 и 524288 и т.д. Если есть комбинация пределов, устраивающая разработчика - задача решаема. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 08:59 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ИзопропилКто-то по прежнему утверждает, что задача имеет решение? Я :) 999999 - можно засунуть в 19 бит. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 11:15 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ЕвгенийВ999999 - можно засунуть в 19 бит. И как? Для справки: 2^19 = 524288 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 12:12 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ЕвгенийВИзопропилКто-то по прежнему утверждает, что задача имеет решение? Я :) 999999 - можно засунуть в 19 бит. это уже не смешно. продемострируй. (естественно все целые от 0 до 999999) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 12:16 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Изопропил это уже не смешно. продемострируй. (естественно все целые от 0 до 999999) Для 9999 Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Имея 2 константы, можно для 0-9999 хранить их в 13 битах. 0-999999 - в качестве упражнения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 12:27 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Впихнуть невпихуемое без дополнительных знаний о источнике и природе исходных данных очевидно нельзя. Путей решения этой задачи всего два: - первый это особое кодирование или индекисрование, предполагающее что в исходных данных встречаются не все комбинации, или хотя бы все они не будут исчерпаны при жизни программы. Примерно на это же полагаются люди выбирающие в качестве ключа обычный integer. - второй путь предполагает возможность хранения дополнительной информации, также как скажем кодировка UTF-8 редко-используемые символы может кодировать большим количеством байтов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 12:30 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Можно представить int32 как 32х битный фильтр Блума. При этом мы теряем возможность обратного преобразования, хотя получаем интерфейс Код: sql 1. Тоесть положили туда два числа сами-знаете-какие и посмотрели что они там лежат. Опять-же зная какие они. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 12:48 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
a7exanderВпихнуть невпихуемое без дополнительных знаний о источнике и природе исходных данных очевидно нельзя. Путей решения этой задачи всего два: - первый это особое кодирование или индекисрование, предполагающее что в исходных данных встречаются не все комбинации, или хотя бы все они не будут исчерпаны при жизни программы. Примерно на это же полагаются люди выбирающие в качестве ключа обычный integer. - второй путь предполагает возможность хранения дополнительной информации, также как скажем кодировка UTF-8 редко-используемые символы может кодировать большим количеством байтов. Ну развивая идею. Давайте вспомним старика Шеннона. И предположим что в задаче на самом деле речь идёт не об обдной паре чисел {a1,b2} а о потоке. И если есть основания говорить что поток обладает энтропией то ... пожалуйста. Можем эти пары кодировать двумя битами, тремя e.t.c как выпадет расклад. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 12:56 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
maytonМожно представить int32 как 32х битный фильтр Блума. При этом мы теряем возможность обратного преобразования, хотя получаем интерфейс Код: sql 1. Тоесть положили туда два числа сами-знаете-какие и посмотрели что они там лежат. Опять-же зная какие они. ВОЗМОЖНО, они там лежат ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 13:16 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ЕвгенийВИзопропилэто уже не смешно. продемострируй. (естественно все целые от 0 до 999999) Для 9999 Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Имея 2 константы, можно для 0-9999 хранить их в 13 битах. 0-999999 - в качестве упражнения. Запустил. Ни одной строчки на экран не вышло. MSVS 2015. PS Вписать 0-9999 в 13 бит (как и 999999 в 19) это заявка на Нобелевскую премию. Даже с константами. Для справки: 2^13 = 8192 PPS Можешь упростить задачу: вписать 10 значений в 3 бита. Думаю тут на бумаге можно понять всю бесперспективность начинания. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 14:04 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ЕвгенийВИмея 2 константы, можно для 0-9999 хранить их в 13 битах. 0-999999 - в качестве упражнения. попытка впихнуть невпихуемое. Париж -столица Франции, 2^13= 8192 тремя битами чисо от 0 до 9 - не закодируешь говнокод даёт коллизию на числах 2,4 и 3,5. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 14:07 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TЗапустил. Ни одной строчки на экран не вышло. MSVS 2015. Это говорит у том, все числа поместились в 13 бит. Поменяй любую из констант и будут тебе выведенные строчки. P.S. Нобелевскую премию по математике не дают. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 14:26 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Это нормально что x3 тут отсутствует? Код: sql 1. Еще у тебя блоки разной длины. После слияния получаются повторы. Например вот 11111111111 Код: sql 1. 2. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 14:53 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TЭто нормально что x3 тут отсутствует? Да. Она получиться из х4 и х5 при востановлении. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 14:56 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ЕвгенийВDima TЭто нормально что x3 тут отсутствует? Да. Она получиться из х4 и х5 при востановлении. Тогда косяк тут Код: sql 1. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 14:59 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Опишите лучше идею формулой чтоли. Или на алгоритмическом языке. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 15:07 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TЭто нормально что x3 тут отсутствует? это нормально косяк в попытке закодировать тремя битами значения от 0 до 9. (пара x4,x5) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 15:18 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
если внимательно посмотреть - 4 бита получается ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 15:20 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
maytonОпишите лучше идею формулой чтоли. Или на алгоритмическом языке. Примерно так на C: Код: sql 1. 2. 3. 4. 5. где %b - вывод в двоичном виде. Там проблема в том что иногда нужные ведущие нолики теряются при склейке. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 15:35 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Изопропил косяк в попытке закодировать тремя битами значения от 0 до 9. (пара x4,x5) Не, при таком раскладе получается что сумма длин строковых представлений х4 и х5 всегда не больше 3 :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 15:40 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TТам проблема в том что иногда нужные ведущие нолики теряются при склейке и остаток и частное от деления (0..9) на 4 - каждое по два бита(что вполне естественно)- итого 4 бита где дам автор алгоритма увидел 3 - в упор не вижу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 15:40 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__, Аффтар! Ты куда пропал? Ты напиши, за каким хреном тебе это понадобилось? С чего это вообще началось? Мысль эта у тебя как возникла? Какую задачу решаешь? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 15:46 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ЕвгенийВНе, при таком раскладе получается что сумма длин строковых представлений х4 и х5 всегда не больше 3 :) но это не решает задачу 010 - как разделять будем? 0 10 или 01 0 ? а это и два и четыре четвёртый битик бы смог помочь ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 15:47 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ЕвгенийВИзопропилкосяк в попытке закодировать тремя битами значения от 0 до 9. (пара x4,x5) Не, при таком раскладе получается что сумма длин строковых представлений х4 и х5 всегда не больше 3 :) 9 у тебя станет 11 (x4 = 1, x5 = 1) 3 тоже 11 (x4 = 0, x5 = 11) теперь покажи фокус как из 11 получить исходное. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 16:10 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ЕвгенийВ, задача сводится к следующей: Есть набор значений 0,1,2,3,4,5,6,7,8,9. Надо его отобразить значениями второго набора 0,1,2,3,4,5,6,7. Причем любое одно значение одного набора должно преобразовываться в одно значение второго и обратно. Как? Ответ: никак. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 16:17 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Кажется задача сводится к переводу из одной системы счисления в другую. Но напрямую влоб входные данные - мощнее по количеству состояний чем получатель. Кажется в дискретной математике этому есть название. Инъекция там... или биекция. Вобщем надо брать автора "за ноздри" и требовать пояснений. Разводит нас... котина. :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 17:45 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima T, По идее они разные. Если бы была возможность отрезать 1 бит (хранить длину). автор0-00 1-01 2-010 3-011 4-10 5-11 6-110 7-111 8-100 9-101 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 17:46 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ЕвгенийВЕсли бы была возможность отрезать 1 бит (хранить длину). если бы у бабушки были яйца - она была бы дедушкой бит, кодирующий длину - и есть тот самый четвёртый ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 17:51 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Или если в постановке слово ЗАПАКОВАТЬ заменить на ХЕШИРОВАТЬ то всё было-бы не так печально. Возможно - злостный перевод с английского? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 18:02 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
mayton, вопрос был простой -"можно ли запаковать" ответ тоже простой -"нельзя" но построители квадратуры круга - не сдаются. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 18:34 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Я не просто так Нобелевскую премию упомянул. Не платят за математику - гугл, эпл, МС и т.п. еще больше заплатят за такой алгоритм. Если есть алгоритм записывающий 20 бит в 19, то это значит любой файл можно сжать до 19 бит: разбиваем на куски по 20, сжимаем, склеиваем обратно куски по 19, режем по 20 и т.д. по кругу, в итоге получаем 19 бит. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 18:55 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Изопропил, да это было понятно после запуска инженерного калькулятора и сравнения чисел. Я грешным делом думаю что как и в задачке с "самолётом на транспортёре" данная - не решается без подсказки. Или афтор всех круто потроллил. Сфоткает и выложит в свой фейсбук. Смотрите грид... как академики копья ломают. Бухаха.. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 18:55 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
maytonда это было понятно после запуска инженерного калькулятора и сравнения чисел. без калькулятора никак? 2^32 - это четыре ярда с хвостиком, а нужно десять. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 19:09 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Изопропилmaytonда это было понятно после запуска инженерного калькулятора и сравнения чисел. без калькулятора никак? 2^32 - это четыре ярда с хвостиком, а нужно десять. Я экспериментировал с открытым интервалом. Поскольку в задаче не было указано от 1 или 0 нуля начинается счёт я брал еще 1 вариант. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 19:21 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Изопропил но построители квадратуры круга - не сдаются. Безумству храбрых поем мы песню! (С) 1. Чисто математически никто не доказал что нельзя, более того существование архиваторов доказывает противоположное. 2. Никто не собирался 34 засунуть в 32. Наверняка существует нечто, многочлен, группа, магические числа и хз еще что зная, что позволит хранить недостающую информацию. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 21:39 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ЕвгенийВ, займись созданием вечного двигателя, математика - не твоё ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.01.2016, 22:47 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ЕвгенийВ1. Чисто математически никто не доказал что нельзя, более того существование архиваторов доказывает противоположное. Есть класс задач для которых нет математичкского доказательства. Пример - шахматные эндшпили. Поэтому я-бы не стал бравировать терминами. Математки засмеют нас. Все мы здесь - работкики It-сегмента и все читали ТЗ которые написаны далеко не мат. языком. И все мы знаем какую свободу мысли дают нам текстовые (гуманитарные) формулировки от бизнеса. Вот и кумекаем... что за смысл был вложен. И учитываю некоторую недоговорённость или неоднозначность толкований (я уже писал про целые-вещественные и смысл упаковки-распаковки) решение данной задачи я-бы отложил до выяснения доп-деталей. Очевидно что автор недоговаривает. Возможно задача решается когда будет известо ограничене на пары {a,b} или на точность кодирования (аппроксимации) чисел. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.01.2016, 00:08 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ЕвгенийВИзопропилно построители квадратуры круга - не сдаются. Безумству храбрых поем мы песню! (С) 1. Чисто математически никто не доказал что нельзя, более того существование архиваторов доказывает противоположное. 2. Никто не собирался 34 засунуть в 32. Наверняка существует нечто, многочлен, группа, магические числа и хз еще что зная, что позволит хранить недостающую информацию. Я уже доказал и успокоился. К сожалению действительно не получится ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.01.2016, 01:45 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
А архиваторы доказывают ровно обратное. При любом шифровании(сжатии) должен быть такой вариант что размер целевого файла с учётом дополнительных расходов памяти или без этого учёта не изменится. Доказать что способа не существует тоже просто. Пусть у нас часть бит x используется для кодирования какой-либо комбинации исходных чисел, группы, многочлена и чего угодно. Сколько вариантов даёт эта часть бит ? 2^x. Пусть оставшуюся часть бит мы используем на коллизии. На каждый вариант из пространства 2^x у нас есть максимум 2^y коллизий которые могут быть успешно разрешены. В таком случае мы имеем максимум 2^(x+y) вариантов всего. Это очень упрощенный вариант, можно доказать строже но суть не изменится. Мы могли бы это сделать, но с потерей точности. Тип float, например, о котором говорил Марк ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.01.2016, 02:16 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ЕвгенийВ1. Чисто математически никто не доказал что нельзя, более того существование архиваторов доказывает противоположное. Архиваторы работают за счет наличия избыточной информации. После первого сжатия избыточность исчезает и последующие сжатия уже пожатого не дают никакого эффекта. ЕвгенийВ2. Никто не собирался 34 засунуть в 32. Наверняка существует нечто, многочлен, группа, магические числа и хз еще что зная, что позволит хранить недостающую информацию. Это только в случае если данные избыточны, т.е. изначально заложен какой-то алгоритм расчета одной части по остальным. Например контрольная сумма и т.п. Тогда эту расчетную часть можно выкинуть и заново рассчитать при восстановлении. Но это должно быть заложено изначально, а не найдено эвристическим образом. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.01.2016, 07:54 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TЕвгенийВ1. Чисто математически никто не доказал что нельзя, более того существование архиваторов доказывает противоположное. Архиваторы работают за счет наличия избыточной информации. После первого сжатия избыточность исчезает и последующие сжатия уже пожатого не дают никакого эффекта. Давно хотел провести эксперимент. Взять хороший генератор шума на базе Secured Random, сформировать файлих хотя-бы на 1Г. И дать возможноть архиваторам (WinRar,7z) его пожать. Меня интересует - поймет ли архиватор на основании полного файла или какой-то выборки что его действия были бесполезны. Или продолжит как ёж-трудяга пыхтеть до победного. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 27.01.2016, 11:34 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Арктур Менгск__Avenger__, Аффтар! Ты куда пропал? Ты напиши, за каким хреном тебе это понадобилось? С чего это вообще началось? Мысль эта у тебя как возникла? Какую задачу решаешь? Хранение данных паспортов. Пока 96`000`000 http://www.fms.gov.ru/upload/expired-passports/list_of_expired_passports.csv.bz2 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 14:01 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
И + минимальный размер файла, потому-что его рассылка идет на удаленные точки по медленным каналам. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 14:03 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Арктур Менгск__Avenger__, Аффтар! Ты куда пропал? Ты напиши, за каким хреном тебе это понадобилось? С чего это вообще началось? Мысль эта у тебя как возникла? Какую задачу решаешь? Хранение данных паспортов. Пока 96`000`000 http://www.fms.gov.ru/upload/expired-passports/list_of_expired_passports.csv.bz2 Вероятно, не все возможные серии используются. Тогда используемые серии хранить в отдельном массиве, а кодировать индекс. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 14:07 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Aleksandr SharahovВероятно, не все возможные серии используются. Первые две цифры серии паспорта соответствуют коду ОКАТО региона, в котором выдан паспорт; третья и четвертая цифры серии паспорта соответствуют последним двум цифрам года выпуска бланка паспорта ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 16:06 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ИзопропилAleksandr SharahovВероятно, не все возможные серии используются. Первые две цифры серии паспорта соответствуют коду ОКАТО региона, в котором выдан паспорт; третья и четвертая цифры серии паспорта соответствуют последним двум цифрам года выпуска бланка паспорта Регионов ~90 Как вариант сначала брать год, но в 2043 году все наестся. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 16:32 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TКак вариант сначала брать год, но в 2043 году все наестся. в базе - DECIMAL(10) и не брать в голову а вот при передаче данных если нужно просто передать список - со сжатием можно хорошо развлечься ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 16:44 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Арктур Менгск__Avenger__, Аффтар! Ты куда пропал? Ты напиши, за каким хреном тебе это понадобилось? С чего это вообще началось? Мысль эта у тебя как возникла? Какую задачу решаешь? Хранение данных паспортов. Пока 96`000`000 http://www.fms.gov.ru/upload/expired-passports/list_of_expired_passports.csv.bz2 Судя по расширению файла csv (не могу пока скачать) данные хранятся в текстовом виде, то есть на xxxx xxxxxx - тратится минимум 10 байт, а то и 20 если в unicode. + перевод строки. Подобные штуки здорово ужмутся в размере, если применить префиксное дерево. http://citforum.ru/database/articles/bst/ ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 16:47 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ЕвгенийВxxxx xxxxxx - тратится минимум 10 байт, а то и 20 если в unicode. + перевод строки. ascii, серия от номера запятой отделена(лидирующие нули присутсвуют), перевод строки - 0A ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 16:59 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ИзопропилЕвгенийВxxxx xxxxxx - тратится минимум 10 байт, а то и 20 если в unicode. + перевод строки. ascii, серия от номера запятой отделена(лидирующие нули присутсвуют), перевод строки - 0A 12 байт на номер, а можно short и int, разделитель - позиция в файле, итого 6 байт. Легким движением уменьшаем в 2 раза. Можно серию в имя файла и тупо список номеров в сам файл (как int), еще сильнее уменьшим. Хотя для номера хватит 5 байт. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 17:08 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Хранение данных паспортов.Тогда, имхо, хранить строкой. А то введут, например, буквы, которые в Int неудобно запихивать. Да и экономия мизерная выходит на фоне всего остального объема паспортных данных. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 17:15 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
miksoft__Avenger__Хранение данных паспортов.Тогда, имхо, хранить строкой. А то введут, например, буквы, которые в Int неудобно запихивать. Да и экономия мизерная выходит на фоне всего остального объема паспортных данных. О как! А я то по названию файла предположил, что там недействительные паспорта и акромя нумеру белее ничего не треба... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 17:23 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Очевидно что для баз данных никакой особо экономии перевод в int не даст. Там - свои накладные расходы на кортежи, блоки и потерянное пространство экстентов (практически во всех DBMS). А с точки зрения memory на app-уровне.. ну можно сэкономить. Только как усложниться при этом доступ? int + short одна статистика. Одни свойства. long int - другая. Другие свойства. Можно и просто в char[] оставить. На мой взгляд вполне себе неплохо. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 17:37 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ЕвгенийВА я то по названию файла предположил, что там недействительные паспорта и акромя нумеру белее ничего не треба...Конкретно в этом файле, может быть, больше ничего и нет. Не смотрел. Но он же не будет существовать один в вакууме. Наверняка будут и другие данные, с которым будет происходить сверка этого списка. А даже банальный JOIN становится куда более сложным (а то и сильно медленнее), если форматы данных не совпадают. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 17:45 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Писать как строку и паковать чем-нибудь хорошо жмущим (7z, rar). Чтобы лучше паковалось - отсортировать. Такой текст должен жаться раз в 10. Т.е. если имеем 12 байт на строку, то после запаковки будет 10 бит на один номер. Набор из 32-битных номеров особо жаться не будет архиватором. Думаю после запаковки будет 25-30 бит на номер. Если проблема в медленных каналах, то как вариант слать только изменения. Не так уж и много паспортов теряют. По сути стандартная репликация. Клиент засылает свое текущее состояние, сервер скидывает ему изменения. Периодически можно засылать полное состояние. PS Кто-нибудь нажимал на ссылку тут 18740263 ? Я ткнул, firefox ушел в аут, начал усиленно отжирать память и молотить процом. За пять минут занял пару гигов оперативки, дальше я задачу снял. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 17:48 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TPS Кто-нибудь нажимал на ссылку тут 18740263 ? Я ткнул, firefox ушел в аут, начал усиленно отжирать память и молотить процом. За пять минут занял пару гигов оперативки, дальше я задачу снял.Там сервер отдает неверный заголовок Content-Type text/plain; charset=utf-8, поэтому браузер пытается скачать его весь и показать его как текстовый файл. Нужно жать ПКМ и "Сохранить объект как..." ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 17:52 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TPS Кто-нибудь нажимал на ссылку тут 18740263 ? да. скачался архив ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 18:16 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Нормально скачался. 1гиг. 96 383 652 номеров. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 18:19 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima T Набор из 32-битных номеров особо жаться не будет архиватором. Думаю после запаковки будет 25-30 бит на номер. Набор случайных не жмется вообще, после сортировки - 43% от начального уровня ужался. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 18:20 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ЕвгенийВDima T Набор из 32-битных номеров особо жаться не будет архиватором. Думаю после запаковки будет 25-30 бит на номер. Набор случайных не жмется вообще, после сортировки - 43% от начального уровня ужался. Осталось затестить тоже самое в тексте: XXXX XXXXXX<enter> Для чистоты эксперимента попробую сейчас тот гиг скачать, как понимаю они там открытым текстом без сжатия. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 18:48 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Скачал, отсортировал. Код: sql 1. правда переводы строк стали двухбайтовыми (0xA 0xD), файл чуть увеличился. Из интересных наблюдений: там все в UTF и лажа из нереальных номеров серии 0000, как понял Советские паспорта тоже естьР_-Р_Р_586151Р_-Р_Р_608275Р_Р_ЕР685239Р_ЕР637039Р_Р_Р'Р_601006РЇР"013332Р_Р_0686885Р'Р"30275311Р"ЕР574471Р_2ЕР73260700000000010000000002......XVР_Р"553080XVР'Р_721378XVР'Р"617824XVР'Р"719576XVЕР590580XVЕР656803XVР_Р_528150XVР>Р_706956XVР>Р_721957XVI-575246XVIРў693061XVII524858XVII645989XX-Р_519379XX-Р_559701XX-Р_646649XX-Р_654615XXР_Р"548495XXР_Р"587957XXР_Р"706757XXР'Р_736496XXР-Р"557014XXР-Р"582132XXР_РR707099XXI-719712XXV-746623 Там одними цифрами все не ограничивается, про перегон в int можно забыть. Жму раром исходный файл и сортированный. Максимальное сжатие. Говорит 50 минут осталось. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 19:21 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TТам одними цифрами все не ограничивается, про перегон в int можно забыть. кентавра можно сделать ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 19:26 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Мне помнится я Базисту предложил задачку об Украинских налоговых номерах. Десяти-значный номер. И есть много интересных закономерностей для уплотнения и хранения. Лучшие задачи проекта ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 19:34 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Допаковалось. Исходный файл был пожат, весил 344 Мб Он же пожатый RAR5 с максимальным сжатием 367 Мб Он же отсортированный и пожатый RAR5 с максимальным сжатием 171 Мб Пошел изучать чудесный bzip2, который жмет лучше RAR`а PS слать обновления будет намного компактней. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 20:06 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TОн же пожатый RAR5 с максимальным сжатием 367 МбЧто-то тут не так. WinRAR 4.20 сжал исходный CSV-файл за 6 минут на некрутом ноутбуке - 354 349 190 байт. Правда, для этого пришлось в опциях сжатия включить принудительное распознавание текста. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 21:40 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Вот чудаки. Преобразуйте этот поток шлака в дельта-код и еще раз закодируйте. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 22:27 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
1. Я его сортирую, потом оставляю только паспорта РФ. Другие не интересуют. Формат сейчас такой: карта по сериям 10000 Int = 80000 байтов + 96 000 000 записей по 4 байта. Итоговый файл занимает 386 мегабайтов. В архиве - WinRar 4.2 - 35 МБ. 7-zip жмет до 50 МБ. 2. Поиск по файлу конкретного паспорта осуществляю методом половинного деления. По серии определяю позиции начала и окончания блока данных в бинарном файле 3. 35 МБ для удаленных офисов - очень большой трафик. Как правило DialUp или GPRS. Поэтому написана утилита которая находит разности между двумя бинарными файлами. На удаленные офисы приходят эти разности. Разность за год по подсчетам должна быть примерно 6 байтов на запись * 40 000 изменений в день * 250 дней = 57 МБ. Сколько это в архиве - не знаю. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 22:41 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Если использовать БД, то все это слишком медленно работает, и слишком много накладных расходов. Размер БД как минимум будет 3 ГБ. Говоря, что медленно работает, имею ввиду перестройку индексов, + вставку удаление и нахождение разностей. Поиск будет мгновенным. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 22:43 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Поэтому написана утилита которая находит разности между двумя бинарными файлами.Имхо, если искать разницу между текстовыми вариантами, ее сортировать и сжимать, то получится экономичнее. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 22:45 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Размер БД как минимум будет 3 ГБ.Если в MySQL использовать InnoDB-таблицу из двух полей SMALLINT и MEDIUMINT (это 2 и 3 байта соответственно), то будет что-то в диапазоне 0,5-1 ГБ. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 22:49 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
miksoft, Это с учетом индекса? Или natural-ом искать буду? Как разности между файлами найти? Это еще два поля - Дата добавления и дата удаления записи. + Еще два индекса. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 22:53 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Это с учетом индекса?Это и есть индекс. Таблицы InnoDB - это фактически и есть первичный ключ таблицы с довеском из остальных полей, если они есть. __Avenger__и дата удаления записиА разве из этого списка могут удаляться записи исходя из его сути? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 22:57 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Как разности между файлами найти?Хотел предложить diff, но, похоже, его нет под Windows. Но есть вот: https://en.wikipedia.org/wiki/WinMerge WinMerge is a free software tool for data comparison and merging of text-like files. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 23:01 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
miksoft, Да, записи могут удаляться. Мало того в 1 день были на 2-й удалили в 3-й добавили опять. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 23:04 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Да там практически - sequence. В отсортированом варианте. Если убрать стрёмные буквенные номера типа XVАГ,????????. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 23:34 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
maytonДа там практически - sequence. В отсортированом варианте.Тогда можно попытаться работать с диапазонами. Это еще увеличит компактность данных. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2016, 23:58 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Я-же говорю. Архиватор не умеет видеть так далеко. Он не сечёт поток целых чисел в виде строк. Дайте ему более явную энтропию. Дайте на вход дельта-код. Может даже RLE в данном случае будет выигрышнее всех других методов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 00:06 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Нашёл googl-овую реализацию Bloom-filter. Заинтересовало какой будет оверхед при вероятности ошибки 0.00001. Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. По отладчику. (Не знал как поднять детали инстанциирования параметров). Очевидная инфа: Нужно аллоцировать память в 2 309 607 327 / 8 = 288 700 915 байт = 275 Мb двести семсят пять метров. При этом неверно детектированые "дохлые" паспорта составят (насколько я понимаю смысл). 96 383 652 * 0.00001 = 963 штуки На скрине с брейпойнтом можно также выкурить еще всяких интересных штук. Типа колчество хеш-функций которые будут задейсвованы а также название алгоритма. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 01:02 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
maytonЕсли убрать стрёмные буквенные номера типа XVАГ,????????. это пущай топикстартер объяснит как оно попало в список. по идее все такие паспорта должны быть невалидны ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 01:55 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Можно ли запаковать в один Int(4-байта) два числа, первое - не превышает 9999, второе - не превышает 999999?Типичная задача, которую решают архиваторы. Но они опираются на контекст всего содержимого данных. В вашем случае возможны только решение для частных случаев. К примеру значение какого-либо имеет ряд дискретных значений или заведомо входящих в некоторый диапазон. В целом /без знания контекста данных/ данная задача не разрешима. См. https://ru.wikipedia.org/wiki/Информационная_энтропия ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 08:45 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__1. Я его сортирую, потом оставляю только паспорта РФ. Другие не интересуют. Формат сейчас такой: карта по сериям 10000 Int = 80000 байтов + 96 000 000 записей по 4 байта. Итоговый файл занимает 386 мегабайтов. В архиве - WinRar 4.2 - 35 МБ. 7-zip жмет до 50 МБ. 2. Поиск по файлу конкретного паспорта осуществляю методом половинного деления. По серии определяю позиции начала и окончания блока данных в бинарном файле 3. 35 МБ для удаленных офисов - очень большой трафик. Как правило DialUp или GPRS. Поэтому написана утилита которая находит разности между двумя бинарными файлами. На удаленные офисы приходят эти разности. Разность за год по подсчетам должна быть примерно 6 байтов на запись * 40 000 изменений в день * 250 дней = 57 МБ. Сколько это в архиве - не знаю. ИМХУ надо разделить задачи: на передачу и использование. Т.е. один формат для передачи, второй для поиска. При получении делать конвертацию из первого во второй. Как понимаю проблемы именно с передачей, как вариант: сделать синхронизацию по типу rsync, т.е. обновление только измененных частей файла. Только надо исключить операцию удаления, например использовать замену на невалидный номер. Тем более что для данной задачи удаление крайне редкая операция. Тогда все операции сведутся к добавлению и изменению. Дальше протокол обмена примерно такой: 1. Клиент разбивает свою копию на блоки, посылает хэш каждого и общий размер. Например если разбить на 64 блока и по каждому посчитать MD5, то запрос будет 16*64 = 1024 байта + немного доп.инфы. 2. Сервер в ответ посылает все что добавилось ( > размера копии клиента), проверяет хэши, если у какого-то блока не совпало, сообщает номер блока клиенту. 3. Клиент дописывает хвост, по измененному блоку разбивает его еще на 64 и отправляет хэши серверу. 4. Сервер проверяет и отправляет клиенту блоки по которым хэш не совпал. и т.д. Можно просто с rsync разобраться и его использовать. Главное чтобы удалений не было. Т.к. удаление редкость, то в 99% случаев все сведется к отправке добавившегося. Полную передачу тоже можно оптимизировать. Тут можно утрамбовать все номера в 20 бит, т.е. 3 байта, если использовать такой формат: Код: sql 1. 2. 3. 4. 5. 6. 7. т.е. если значение >= 1000000 это следующая серия. Максимум будет 1009999, что меньше 1048576 (2^20). Так можно использовать три байта на один паспорт, если со сдвигами пошаманить то 5 байт на две записи. Второй вариант вместо абсолютного номера хранить смещение (дельту от предыдущего номера), как mayton предложил 18742953 Примерно так: Код: sql 1. 2. 3. 4. 5. Тут надо реальное распределение смотреть, думаю можно будет подстроится чтобы уложиться в 1-2 байта на номер. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 09:21 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Владимир2012В вашем случае возможны только решение для частных случаев. К примеру значение какого-либо имеет ряд дискретных значений или заведомо входящих в некоторый диапазон. В целом /без знания контекста данных/ данная задача не разрешима. дык это и есть частный случай - номера российских паспортов ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 09:48 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Можно что-то типа репликации использовать: На сервере все хранить в БД и добавить поле TIMESTAMP или просто счетчик. При каждом добавлении в это поле писать значение счетчика, счетчик увеличивать. Синхронизация примерно так: 1. Клиент присылает значение TIMESTAMP своей копии 2. Сервер обратно отправляет все записи с большим TIMESTAMP и текущее максимальное значение TIMESTAMP. Дополнительно хэши каждой серии. 3. Клиент добавляет к себе новые данные, запоминает значение TIMESTAMP, проверяет хэши, если по какой-то серии не совпало - запрашивает полное обновление этой серии. Так удаление можно использовать и хранить уже отсортированное. PS Серий на сегодня порядка 90*16 = 1440, при 16 байт на хэш будет ~23 Кб ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 10:03 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Думаю в качестве хэша можно вместо MD5 можно что-нибудь покороче взять, например CRC32 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 10:12 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TPS Серий на сегодня порядка 90*16 = 1440, в данных неимоверное количество мусора, ждём разъяснений от топикстартера ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 10:15 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
По удаленным можно отдельную таблицу завести, при удалении переносить туда с установкой TIMESTAMP, и при отправке обновления клиенту из этой таблицы тоже слать список на удаление. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 10:16 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
https://ru.wikipedia.org/wiki/Паспорт_гражданина_Российской_Федерации Серия и номер паспорта записываются в формате XX XX YYYYYY, где XX XX — 4-значная серия паспорта и YYYYYY — 6-значный номер паспорта. Первые две цифры серии паспорта соответствуют коду ОКАТО региона, в котором выдан паспорт; третья и четвертая цифры серии паспорта соответствуют последним двум цифрам года выпуска бланка паспорта (допускается отклонение на 1-3 года). Пример: паспорт серии 45 04 выдан в городе Москва, бланк выпущен в 2004 году, а паспорт серии 37 11 выдан в Курганской области, бланк выпущен в 2011 году. На 2 и 3 страницах паспорта серия и номер паспорта нанесены в паспорте типографским способом. До 2008 года серия и номер были также нанесены типографской краской на последующих страницах. С 2008 года на страницах с 5 по 20, а также на задней обложке серия и номер нанесены методом лазерной перфорации. Третья и четвертые цифры наводят на мысль, что они имеют малое количество значений. И похоже им можно поставить некоторое битовое значение /например 4 бита/ ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 10:26 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ИзопропилDima TPS Серий на сегодня порядка 90*16 = 1440, в данных неимоверное количество мусора, ждём разъяснений от топикстартера Он же написал __Avenger__1. Я его сортирую, потом оставляю только паспорта РФ. Другие не интересуют. т.е. только то что попадает под маску XXXX XXXXXX где X цифра. Посчитал: всего 96`383`652 записей, подходящих 96`373`705, среди них 2806 серий. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 10:38 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ИзопропилDima TPS Серий на сегодня порядка 90*16 = 1440, в данных неимоверное количество мусора, ждём разъяснений от топикстартера Весь мусор в помойку. Остаются только паспорта рф \d{4},\d{6}. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 10:41 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Посмотрел, есть целые диапазоны, т.е. от нескольких номеров подряд до сотен. Их можно хранить так Код: sql 1. для диапазона достаточно одного байта. Чтобы одиночным диапазон=1 не прописывать, можно хранить диапазоны в отдельной секции или файле. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 10:51 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Весь мусор в помойку. Остаются только паспорта рф \d{4},\d{6} 3-4 цифра в серии не вызывает доверия (год печати бланка) в ряде случаев ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 10:52 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TПошел изучать чудесный bzip2, который жмет лучше RAR`аУ "block sorted" ест багофича - на плохо сжимаемых данных получается пятипроцентный оверхед. P.S. imho, лучше изучить LZMA(2) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 16:44 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Прошу прощения. А автору нужно минимизировать репликацию? Или хранение. Или структуру к которой идёт доступ на поиски? Это может быть 3 разных солюшена. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 16:56 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Сделал выгрузки, под спойлерами форматы. По 4 байта на значение Код: sql 1. 2. 3. 4. 5. 6. 7. По 3 байта на значение Код: sql 1. 2. 3. 4. 5. 6. 7. По 3 байта c дельтами 0x0 это байт с нулем Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. Мест где сработало "иначе" всего 36000 оказалось. Результаты: Выгрузка размер пожатый RARПо 4 байта367 Мб 34 MbПо 3 байта275 Мб 33 Mbc дельтами92 Мб 30 Мб Смотрю файл с дельтами - много единичек, т.е. возможно вариант с диапазонами взлетит Код: sql 1. 2. 3. 4. 5. 6. 7. 8. Хотя не думаю что намного ниже 30 Мб будет в архиве. ИМХУ Для передачи лучше копать в сторону репликации, т.к. данные в основном только добавляются. Не надо гонять полное состояние. Достаточно слать на клиента только обновления и немного инфы для контроля целостности его копии. Плюс механизм восстановления при частичном разрушении копии. PS Использовал RAR5 с дефолтными настройками. Выше пробовал максимальное сжатие ставить, как оказалось меньше архив не стал, а время в 10 раз увеличилось. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 17:16 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Диапазоны будут удобны для поиска. Перегнал в такую структуру По три байта с диапазонами Код: sql 1. 2. 3. 4. 5. 6. 7. т.е. номерХ три байта, диапазон 1 байт. номерХ + диапазон = последний номер диапазона Диапазонов оказалось 44,7 млн. из 96, т.е. записей вдвое меньше. Дополню результаты Выгрузка размер пожатый RARПо 4 байта367 Мб 34 MbПо 3 байта 275 Мб 33 Mbc дельтами92 Мб 30 Мбc диапазонами 170 Мб 38 Мб Я бы сравнивал выделенные цифры. Для поиска хранить диапазоны гораздо выгоднее. Вариант с дельтами для поиска не подходит, т.к. там можно искать только перебором. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 19:11 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima T, надо все кодировать длинами диапазонов включений-исключений, начиная с номера 0 например, в некоторой серии есть номера: 2, 7-11, 18 значит, диапазоны такие: 0-1 не входит, 2-2 входит, 3-6 не входит, 7-11 входит, 12-17 не входит, 18-18 входит, 19-999999 не входит, а их длины: 2, 1, 4, 5, 6, 1, 999979 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 22:33 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Если цифры 2, 1, 4, 5, 6, 1, 999979 представить как длины чередующихся чёрно белых отрезков пикселей на картинке - то получим довольно старую известную схему сжатия факсимильных картинок. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 23:51 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
mayton, Именно эта схема кодирования имелась в виду. С учетом переменной длины 1-3 байта на код, сжатие должно быть очень неплохим. Длину кода можно разместить в старшем бите младшего и среднего байта. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2016, 23:58 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, или в двух старших битах младшего байта: 0х = 1, причем x является частью (старшим битом) значения; 10 = 2; 11 = 3; ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 00:10 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Я прошу прощения. Но к чему нам сжатие? Ведь суть этой БД или инфо-системы в том чтобы оперативно извлекать статус по каждому паспорту. По сути нам надо имплементировать интерфейс Код: c# 1. 2. 3. Мы тут сломаем тонну копьев, а всё для чего? Для репликации? Так ли она важна? Может важнее продумать как обеспечить имплементацию для интерфейса что я описал? Если таковой не нужен - ну... пускай автор скажет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 00:11 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
А ну ОК. Половинным делением. Хм... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 00:23 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
mayton, кстати, похоже, при наших данных битовая карта для каждой серии будет и меньше, и быстрее. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 00:31 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
С репликацией тоже не все так однозначно. Пусть есть три файла за разные даты 1, 2, 3. На текущий момент актуальна база номер 3. Что бы перевести 1 файл в 3-тий, надо накатить репликации а) 12 + 23 или б) 13 Что бы перевести 2 файл в 3-тий, надо накатить репликации 23 А вот на второй файл накатить репликацию 13 нельзя! Это приведет к неправильному файлу. Поэтому приходится сейчас выделять некий базовый файл, и относительно его и текущего файла находить разность. Разность будет расти с каждым днем. Этот базовый файл есть на всех удаленных офисах. На него накладывается текущая разность и получаем новый файл с актуальными данными. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 00:35 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
maytonА ну ОК. Половинным делением. Хм... Довольно быстро работает, требуется порядка 10-15 чтений из файла (с буфферным чтением - физически происходит одно чтение в память блока 1МБ). Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 00:40 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__, прелесть битовой карты в том, что требуется одно чтение маленького блока ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 00:47 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov__Avenger__, прелесть битовой карты в том, что требуется одно чтение маленького блока Спасибо, посмотрю на досуге что это такое. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 00:50 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Ну ... поскольку мозговой штурм еще идёт то и я еще подкину дров. С первых страниц топика меня не покидало ощущение что эта задача похожа на MaxMind и базу блоков IP адресов. Характерные особенности - ярко выраженные префиксы (серии паспортов). И диапазоны. Коробочное решение - дерево остатков RadixTree. Оно эффективно на поисках и вставках. К сожалению у меня совершенно нет никакой формулы чтобы оценить расходы на хранение дерева на диске. По этому вопросу надо гуглить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 01:13 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__С репликацией тоже не все так однозначно. Пусть есть три файла за разные даты 1, 2, 3. На текущий момент актуальна база номер 3. Что бы перевести 1 файл в 3-тий, надо накатить репликации а) 12 + 23 или б) 13 Что бы перевести 2 файл в 3-тий, надо накатить репликации 23 А вот на второй файл накатить репликацию 13 нельзя! Это приведет к неправильному файлу. Поэтому приходится сейчас выделять некий базовый файл, и относительно его и текущего файла находить разность. Разность будет расти с каждым днем. Этот базовый файл есть на всех удаленных офисах. На него накладывается текущая разность и получаем новый файл с актуальными данными. Это слишком примитивно. Хотя и этот подход можно использовать, но только добавить хэши файлов. Имя файла обновления: XXXX_<MD5old>_<MD5new>.upd, где XXXX номер обновления, MD5old хэш исходного файла, MD5new хэш после обновления. На клиенте считаешь MD5 текущего состояния, запрашиваешь файл *_<MD5>_*.upd накатываешь, проверяешь что MD5curr = MD5new, если совпало - фиксируешь изменения. Дальше по кругу. Хранить древний базовый файл не надо, надо хранить текущий и все обновления. При появлении свежего файла рассчитываешь обновление от текущего, проверяешь что после наката обновления на текущий получается новый, сохраняешь обновление, заменяешь текущий новым. Тут минусы: при редком обновлении клиенту надо накатить много файлов, если что-то сглючит, то придется качать полное состояние. Надо полноценную репликацию 18744100 18744168 и данные на сервере хранить в СУБД Тогда клиент просто сообщает свое состояние, а сервер отправляет какие надо изменения до текущего состояния. Тут любая частота обновлений сервера. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 09:00 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Формат сейчас такой: карта по сериям 10000 Int = 80000 байтов + 96 000 000 записей по 4 байта. ИМХУ вполне нормальная структура для поиска: 1. Читаем с места серия * 4, получаем расположение блока номеров (тут я бы добавил еще конец блока, т.к. следующей серии может не быть и надо читать пока не попадется следующая присутствующая серия), или сразу получаем что серии нет. 2. Ищем в блоке номеров. Размер блока максимум 4 Мб. Бинарным поиском максимум 20 чтений. Как вариант п.2 заменить на биткарту, тогда на каждую серию надо будет 125000 байт под биткарту с номерами, или весь файл 350 Мб (2806 серий) максимум 1,25 Гб для всех серий. Хоть файл и распухнет, но чтений станет всего два: 4 байта по серии смещение до биткарты + 1 байт биткарты. Еще плюсы: изменение не требует формирования файла с нуля. Для добавления/удаления номера просто установить/сбросить нужный бит. Добавление новой серии: добавить биткарту в конец, в заголовке прописать смещение до биткарты. Сжиматься архиватором наверно будет похуже, но не намного. Расчет разницы двух файлов можно будет делать в один проход, или использовать rsync и забыть про расчеты обновлений. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 09:31 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__С репликацией тоже не все так однозначно. Пусть есть три файла за разные даты 1, 2, 3. Стоп. Нет никаких файлов - есть база данных и её реплики ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 10:18 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
maytonЯ прошу прощения. Но к чему нам сжатие? Ведь суть этой БД или инфо-системы в том чтобы оперативно извлекать статус по каждому паспорту. Согласен. Но обсуждение этого вопроса /на мой взгляд/ имеет смысл продолжить в части способов эффективного и компактного представления данных. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 10:42 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Владимир2012, компактного представления для репликации или поиска? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 10:57 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Изопропилкомпактного представления для репликации или поиска?Общетеоретического. Без контекста обсуждения необходимости использования этого в базах данных. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 11:11 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Владимир2012Общетеоретического. для разных задач - разные алгоритмы иначе - обсуждение сферического коня в вакууме ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 14:17 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Изопропилдля разных задач - разные алгоритмы иначе - обсуждение сферического коня в вакуумеРечь шла об конкретной задаче. И она в какой-то мере типична. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 14:23 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__maytonА ну ОК. Половинным делением. Хм... Довольно быстро работает, требуется порядка 10-15 чтений из файла (с буфферным чтением - физически происходит одно чтение в память блока 1МБ). Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. Поясни, как ты используешь половиное деление если у тебя в текстовом файле существуют записи не выровненные на границу кратную 12 байтам (10 символов + запятая + 0x0A) Пример таких записей я нашёл ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 19:24 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Лучше всего сжимается битовая карта: 26M - сжатая RARом битовая карта, 30M - сжатые RARом дельты, 85M - дельты без сжатия, 333M - битовая карта без сжатия, 1103M - оригинальный csv-файл. Неотлаженный Некрасивый Недоделанный Исходник для справки Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148. 149. 150. 151. 152. 153. 154. 155. 156. 157. 158. 159. 160. 161. 162. 163. 164. 165. 166. 167. 168. 169. 170. 171. 172. 173. 174. 175. 176. 177. 178. 179. 180. 181. 182. 183. 184. 185. 186. 187. 188. 189. 190. 191. 192. 193. 194. 195. 196. 197. 198. 199. 200. 201. 202. 203. 204. 205. 206. 207. 208. 209. 210. 211. 212. 213. 214. 215. 216. 217. 218. 219. 220. 221. 222. 223. 224. 225. 226. 227. 228. 229. 230. 231. 232. 233. 234. 235. 236. 237. 238. 239. 240. 241. 242. 243. 244. 245. 246. 247. 248. 249. 250. 251. 252. 253. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 21:24 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TЭто слишком примитивно. Хотя и этот подход можно использовать, но только добавить хэши файлов. Имя файла обновления: XXXX_<MD5old>_<MD5new>.upd, где XXXX номер обновления, MD5old хэш исходного файла, MD5new хэш после обновления. На клиенте считаешь MD5 текущего состояния, запрашиваешь файл *_<MD5>_*.upd накатываешь, проверяешь что MD5curr = MD5new, если совпало - фиксируешь изменения. Дальше по кругу. Хорошая идея, спасибо. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 23:23 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
maytonПоясни, как ты используешь половиное деление если у тебя в текстовом файле существуют записи не выровненные на границу кратную 12 байтам (10 символов + запятая + 0x0A) Пример таких записей я нашёл Прочитай сообщение 18742992 . Все номера паспортов выровнены на границу 4 байта. Серии хранятся в массиве серий от [0..10000]. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 23:26 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Aleksandr SharahovЛучше всего сжимается битовая карта: 26M - сжатая RARом битовая карта, 30M - сжатые RARом дельты, 85M - дельты без сжатия, 333M - битовая карта без сжатия, 1103M - оригинальный csv-файл. Мощно, какое-то слишком сложное кодирование исходящего буффера. А за сколько у Вас формируется файл с битовой картой? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.01.2016, 23:41 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Прочитай сообщение 18742992 . Все номера паспортов выровнены на границу 4 байта. Серии хранятся в массиве серий от [0..10000]. должно быть и есть - это разные вещи зачем ты нам файл с мусором выдал? номер серии из двух знаков, нецифровые символы в номере, год печати бланка из будущего, советские номера серий Неужели на основании таких данных можно делать адекватные данные о валидности паспорта? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 00:27 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Aleksandr SharahovЛучше всего сжимается битовая карта: 26M - сжатая RARом битовая карта, 30M - сжатые RARом дельты, 85M - дельты без сжатия, 333M - битовая карта без сжатия, 1103M - оригинальный csv-файл. Мощно, какое-то слишком сложное кодирование исходящего буффера. А за сколько у Вас формируется файл с битовой картой? Последовательно по 3 раза вызов каждой процедуры: List loaded OK 45895ms List loaded OK 44882ms List loaded OK 44772ms Map loaded OK 6397ms Map loaded OK 421ms Map loaded OK 421ms Packet loaded OK 2512ms Packet loaded OK 2496ms Packet loaded OK 2496ms Map saved OK 343ms Map saved OK 359ms Map saved OK 343ms Packet saved OK 2293ms Packet saved OK 2293ms Packet saved OK 2294ms ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 00:35 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Изопропил__Avenger__Прочитай сообщение 18742992 . Все номера паспортов выровнены на границу 4 байта. Серии хранятся в массиве серий от [0..10000]. должно быть и есть - это разные вещи зачем ты нам файл с мусором выдал? номер серии из двух знаков, нецифровые символы в номере, год печати бланка из будущего, советские номера серий Неужели на основании таких данных можно делать адекватные данные о валидности паспорта? Этот вопрос не ко мне, а сюда . Сейчас многие обязаны по закону проверять паспорт, согласно перечня ФСФМ или на сайте. Такие у нас законы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 00:40 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Мощно, какое-то слишком сложное кодирование исходящего буффера. Там все элементарно: допустим S это номер первого байта биткарты в файле, N номер паспорта. Дальше читаем из файла байт (S+N/8) работаем с битом N % 8 чтобы не делать деление и получения остатка (это тяжелые операции) можно их заменить: деление на 8 - это битовый сдвиг вправо на 3 бита (>> 3) остаток от деления на 8 - это получение последних трех бит (&7) Смотря на чем пишешь, на С/С++ можно не менять, компилятор за тебя поменяет. Для работы с нужным битом: пусть К номер бита (0-7). Получаем маску M = 1 << K. т.е. битовый сдвиг влево 1 на К разрядов. Математически M = 2^K. Например: при К = 4, M будет 16 или в двоичной 00010000 B - текущее содержимое байта. Проверка текущего значения бита: (B & M) != 0 (true - установлен) Установка бита: B = B | M Сброс бита: B = B & (~M) &, |, ~ побитовые операции И, ИЛИ, НЕ При генерации с нуля, для ускорения, лучше сначала все посчитать в памяти, затем результат сбросить на диск. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 09:57 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Этот вопрос не ко мне, а сюда . Сейчас многие обязаны по закону проверять паспорт, согласно перечня ФСФМ или на сайте. Такие у нас законы. ИМХУ вопрос к тебе, как изучившему предметную область. Например есть там запись 01,591132. Можно трактовать по разному: 0001,591132 и 0100,591132. Очевидно что нужен один из них, но какой? ФСФМ что-нибудь разъясняет по этому поводу? Есть какие-то рекомендации как это трактовать? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 10:08 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TФСФМ что-нибудь разъясняет по этому поводу? http://services.fms.gov.ru/info-service.htm?sid=2000 Данный сервис является информационным, предоставляемая информация не является юридически значимой. no comments ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 10:13 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima T__Avenger__Этот вопрос не ко мне, а сюда . Сейчас многие обязаны по закону проверять паспорт, согласно перечня ФСФМ или на сайте. Такие у нас законы. ИМХУ вопрос к тебе, как изучившему предметную область. Например есть там запись 01,591132. Можно трактовать по разному: 0001,591132 и 0100,591132. Очевидно что нужен один из них, но какой? ФСФМ что-нибудь разъясняет по этому поводу? Есть какие-то рекомендации как это трактовать? Трактовать как ошибочное значение, в чем легко убедиться, если отправить запрос в ФМС на этот URL. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 10:17 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
мусор на входе - мусор на выходе а какие собственно законы требуют применения этого говносервиса? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 10:23 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Aleksandr SharahovТрактовать как ошибочное значение, в чем легко убедиться, если отправить запрос в ФМС на этот URL. Попробовал там вбить. 01 не говорит неверно ввели, 0001 и 0100 говорит отсутствует. Получается надо просто игнорить все серии что не подходят под маску XXXX где X цифра. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 10:47 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Опечатка 01 не говорит неверно ввели ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 10:48 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Изопропил, Ну например, 115-фз и 499-п. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 12:12 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Белка123Изопропил, Ну например, 115-фз и 499-п. как это совместить с "Данный сервис является информационным, предоставляемая информация не является юридически значимой" ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 13:16 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__maytonПоясни, как ты используешь половиное деление если у тебя в текстовом файле существуют записи не выровненные на границу кратную 12 байтам (10 символов + запятая + 0x0A) Пример таких записей я нашёл Прочитай сообщение 18742992 . Все номера паспортов выровнены на границу 4 байта. Серии хранятся в массиве серий от [0..10000]. Спасибо. А сколько времени (мс)у тебя занимает поиск 1 паспорта по этому файлу? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 14:36 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ИзопропилБелка123Изопропил, Ну например, 115-фз и 499-п. как это совместить с "Данный сервис является информационным, предоставляемая информация не является юридически значимой" ЦБ это не волнует. Сказано проверять и все. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 15:06 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
maytonСпасибо. А сколько времени (мс)у тебя занимает поиск 1 паспорта по этому файлу? ИМХУ если правильно бинарный поиск реализовать будет быстрее дерева, медленнее биткарты. По сути это 10-20 чтений с диска по 4 байта. Причем Последние 10 чтений из 1-2 соседних кластеров (если кластер 4 Кб). Т.е. время поиска не больше времени рандомного чтения 10 кластеров. Еще одно интересное наблюдение: 50% номеров содержатся в 150 сериях Код: sql 1. СерияКол-во номеров800457791180035532622503548911800554026432045320284045314084500520041503514190650450714782035069382003491027650348231265024814724004481202500347996557034711301034680719204466153400546248745064598125203458630450745700475034567293054557992203455639400245433432004526509203451882530345183345014498244505448794180344397492054411654003440890450243669645034344284504430080360442784160044229466505422687304421592630342116375004192772202417013460140952540040748746064066014508406575500440406160024004249201399667460539803030339506770339503146033808834023784514604374489800236763845093673613003643623013631394602359497800135799046073558146003355543410335491436023547616005346637760034107410434088657043371893202336596180433186945983315186304320352650030014445102956447504295450750229505118012932902804287123500028443733042834807003281410410227883060012729848042686894600265620220426345314042605129402258314460825697736012525801012517426704251710200424913325042470857042464231504244173920724388120012428577002241843170423965015022319469403228812409922815732012278233062278062501223833501220689400022062511042205612200217349110221146280121091028022096391402205489360520369180220257082022018591702200930970420063156021993744202199278730419290253001927624597190491690218958278041881565402185916680218514952011848833206183673370218294481031816509802180274400717967867021790595701177965100217476371041747103302173899870217385660081728217102172335520516992856031695391800169216701166013 В принципе объяснимо: сроки действия истекли и люди паспорт меняют. ИМХУ надо смешанный формат хранения: биткарта на одну серию 125000 байт или 31250 номеров по 4 байта или 41667 по 3 байта. Т.е. там где номеров больше 31250/41667 меньше места займет биткарта. При 4 байтовом номере экономия 263 Мб, т.е. файл будет ~104 Мб При 3 байтовом номере экономия 178,5 Мб, т.е. файл будет ~97 Мб Некогда писать, на неделе время будет, затестю. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 16:23 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Давайте отложим в сторону юридические моменты. Это не интересно для sql.ru. Лучше обсужить способы storage и оперативный доступ. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 16:24 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TmaytonСпасибо. А сколько времени (мс)у тебя занимает поиск 1 паспорта по этому файлу? ИМХУ если правильно бинарный поиск реализовать будет быстрее дерева, медленнее биткарты. По сути это 10-20 чтений с диска по 4 байта. Причем Последние 10 чтений из 1-2 соседних кластеров (если кластер 4 Кб). Т.е. время поиска не больше времени рандомного чтения 10 кластеров. 2 Дима. ИМХО. 10-20 чтений с диска (random seek, они-же IOPs) это очень много и очень дорого. Если-бы эти 96 млн записей лежали в B+Tree дереве на диске то нам понадобилось-бы 2-3 уровневое дерево или 2-3 операции чтения блоков. Но автор топика уже слышал советы бывалых БД-шников и для себя определил что своя кастомная структура лучше. Ну что-ж. Пускай так. 2 All По поводу биткарт. Я возможно иногда не совсем ясно выражаю свою мысль. Когда я говорю "биткарта Блума" я имею в виду фильтр Блума (ФБ). И это не есть биткарта в общем понимании этого слова. И ее размер не определяется количеством элементов. (Я на всякий случай уточняю). Вообще по последнему пункту я экспериментировал. Я искал некое золотое соотношение качества и количества элементов которо позволяет сериализовать все паспорта и причём без ложно-положительных срабатываний. Это сделать можно но для счётного числа ключей вообще. Для нашей-же задачи фильтр можно наполнить (метафорически это ближе к обучению НС) обучающей выборкой в 96 млн ключей. При этом теоретическая верхняя граница это Десять в десятой это десять миллиардов потенциально возможных числовых ключей. Буквенные я пока для простоты отбросил. Ограниченную кардинальность номеров серий я тоже пока отбросил. Корреляции между сериями и номерами в сериях я тоже отбросил. Исхожу из предположения что номер и серия - соврешенно произвольные. Я решаю (для себя) общую задачу. Исходя из того что обучающая выборка состоит из почти 100 млн ключей а всего возможно 10 млрд необходимо эти 100 млн как-то хранить и быстро доступаться. При этот ответ на проверку паспортов из множества 10 млрд - 100 млн = 9 900 000 000 должен быть отрицательный. Тоесть паспорт должен быть действителен для всех тех номеров которые еще не внесены в обучающую выборку. И в этом есть проблема. ФБ не гарантирует точного ответа. И как захардкодить или как задать "номера исключения" из этого множества я еще не придумал. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 17:32 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Я про обычное бинарное дерево. Почитал про B+Tree, оптимизировано под страничное хранение, согласен что быстрее. В моем смешанном способе хранения проблема снимается: если номеров много: биткарта, т.е. 2 чтения. Если мало: максимум 15 чтений, из которых 10 с одной страницы. Хотя и тут можно добавить в начало списка номеров индекс из 32 диапазонов, тогда будет чтение 3х страниц. Подумаю. Про фильтр Блума: ИМХУ тут он не в тему. Его применение облегчить промахи в выборках, когда сама выборка достаточно тяжелая операция. Тут выборка не тяжелая. Для блума тебе надо какой-то хэш придумать, чтобы равномерно все значения распределил, иначе при 100 млн. бит он просто выродится в биткарту. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 18:14 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TДля блума тебе надо какой-то хэш придумать, чтобы равномерно все значения распределил, иначе при 100 млн. бит он просто выродится в биткарту. С этого предложения я не понял. Имплементации которые я брал уже содержат готовый набор API вместе с хешфункциями и ничего мне придумывать не надо уже. И почему при 100 млн бит он должен во что-то вырождаться? Я не знаю такого ограничения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 18:18 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Если битовая карта (та, которая в общепринятом смысле) целиком лежит в ОП, то плохой номер паспорта определяется мгновенно без обращения к диску вызовом функции вроде MapTest(Map, Serial, No). В этом случае на диске карта может храниться как угодно: или непосредственно, или в виде дельт. Если в ОП находится только карта серий, то форматом хранения данных является непосредственно битовая карта. В этом случае для получения результата необходимо одно чтение с диска одного байта данных. Формат данных, предназначенный для передачи, может быть каким угодно. Удобно передавать ту же карту в сжатом виде из-за небольшого размера (26M). Если нежелательно использовать архиватор, то подойдет файл с дельтами. Небольшое изменение формата позволяет уменьшить его размер до 43M. Как было сказано чуть выше, этот же файл может использоваться и в работе, если вся битовая карта из него будет грузиться в ОП. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 18:29 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
В моём варианте с com.google.common.hash.BloomFilter и fpp (desired false positive probability) = 0.00001 я получил следующие цифры Код: plaintext 1. 2. 3. Формат карты внутри - достаточно плотен. Вот его шапка (на глаз чтоб оценить энтропию). Код: sql 1. 2. 3. 4. 5. Как видно... никаких длинных областей нулей и единиц там не прослеживается. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 19:23 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Сжимать ее вобщем-то бесполезно. Практически 7z с дефолтными настройками ничего не может сделать. Код: sql 1. 2. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 19:25 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
maytonИ почему при 100 млн бит он должен во что-то вырождаться? Я не знаю такого ограничения. Извиняюсь. Перепутал, 10 млрд. бит. Биткарта которая покроет все значения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 19:33 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TmaytonИ почему при 100 млн бит он должен во что-то вырождаться? Я не знаю такого ограничения. Извиняюсь. Перепутал, 10 млрд. бит. Биткарта которая покроет все значения. Простая битовая карта размером в 12 гигабайт? Я-бы такое никому не предложил. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 19:36 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
maytonDima Tпропущено... Извиняюсь. Перепутал, 10 млрд. бит. Биткарта которая покроет все значения. Простая битовая карта размером в 12 гигабайт? Я-бы такое никому не предложил. 1,25 Гб. Всего 4 твоих Блума. PS Сегодня не я один цифры путаю ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 20:13 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima T, а точно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 20:16 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima T1,25 Гб. Всего 4 твоих Блума.Более того, можно вынести третью и четвертую цифры вперед, добавить кольцевой сдвиг (чтобы счет начинался с нуля). Тогда у битовой карты будет использована только первая четверть, а оставшиеся три четверти можно будет просто обрезать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 20:38 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
mayton__Avenger__пропущено... Прочитай сообщение 18742992 . Все номера паспортов выровнены на границу 4 байта. Серии хранятся в массиве серий от [0..10000]. Спасибо. А сколько времени (мс)у тебя занимает поиск 1 паспорта по этому файлу? Если мерить GetTickCount-ом, то получается так: Код: plaintext 1. 2. 3. 4. 5. В среднем 15 ms на паспорт. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 22:28 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima T__Avenger__Мощно, какое-то слишком сложное кодирование исходящего буффера. Там все элементарно: допустим S это номер первого байта биткарты в файле, N номер паспорта. Дальше читаем из файла байт (S+N/8) работаем с битом N % 8 чтобы не делать деление и получения остатка (это тяжелые операции) можно их заменить: деление на 8 - это битовый сдвиг вправо на 3 бита (>> 3) остаток от деления на 8 - это получение последних трех бит (&7) Смотря на чем пишешь, на С/С++ можно не менять, компилятор за тебя поменяет. Для работы с нужным битом: пусть К номер бита (0-7). Получаем маску M = 1 << K. т.е. битовый сдвиг влево 1 на К разрядов. Математически M = 2^K. Например: при К = 4, M будет 16 или в двоичной 00010000 B - текущее содержимое байта. Проверка текущего значения бита: (B & M) != 0 (true - установлен) Установка бита: B = B | M Сброс бита: B = B & (~M) &, |, ~ побитовые операции И, ИЛИ, НЕ При генерации с нуля, для ускорения, лучше сначала все посчитать в памяти, затем результат сбросить на диск. Спасибо, тут все понятно. Непонятно назначение SavePassportPacket и LoadPassportPacket. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 22:43 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Непонятно назначение SavePassportPacket и LoadPassportPacket. Они нужны для сохранения-загрузки всей битовой карты или карты изменений в формате дельта-кодов. В этом формате значительно экономится место на диске. Добавил новые версии "2 в 1" процедур SavePassportPacket2 и LoadPassportPacket2, которые в 2 раза экономнее используют внешнюю память. Удобно для рассылок изменений. свежий исходник {$WARN UNSAFE_CODE OFF} unit ExpiredPassports; interface type TPassportMap= array of array of byte; procedure MapInvert(var Map: TPassportMap; Serial, No: integer); //инвертировать один бит карты procedure MapInclude(var Map: TPassportMap; Serial, No: integer); //установить один бит карты procedure MapExclude(var Map: TPassportMap; Serial, No: integer); //сбросить один бит карты function MapTest(var Map: TPassportMap; Serial, No: integer): boolean; //получить состояние одного бита карты procedure LoadPassportList(var Map: TPassportMap; const FileName: string); //загрузить карту, используя файл ФМС procedure SavePassportMap(var Map: TPassportMap; const FileName: string); //сохранить карту в формате без сжатия procedure LoadPassportMap(var Map: TPassportMap; const FileName: string); //загрузить карту в формате без сжатия procedure SavePassportPacket(var Map: TPassportMap; const FileName: string); //сохранить карту в формате дельта-кодов procedure LoadPassportPacket(var Map: TPassportMap; const FileName: string); //загрузить карту в формате дельта-кодов procedure SavePassportPacket2(var Map: TPassportMap; const FileName: string); //сохранить карту в формате дельта-кодов 2 в 1 procedure LoadPassportPacket2(var Map: TPassportMap; const FileName: string); //загрузить карту в формате дельта-кодов 2 в 1 implementation type TBuffer= array[0..999999] of byte; procedure MapInvert(var Map: TPassportMap; Serial, No: integer); begin; if (Serial<0) or (Serial>9999) or (No<0) or (No>999999) then exit; if Length(Map)=0 then SetLength(Map, 10000); if Length(Map[Serial])=0 then begin; SetLength(Map[Serial], 125000); FillChar(Map[Serial,0], 125000, 0); end; Map[Serial, No shr 3]:=1 shl (No and 7) xor Map[Serial, No shr 3]; end; procedure MapInclude(var Map: TPassportMap; Serial, No: integer); begin; if (Serial<0) or (Serial>9999) or (No<0) or (No>999999) then exit; if Length(Map)=0 then SetLength(Map, 10000); if Length(Map[Serial])=0 then begin; SetLength(Map[Serial], 125000); FillChar(Map[Serial,0], 125000, 0); end; Map[Serial, No shr 3]:=1 shl (No and 7) or Map[Serial, No shr 3]; end; procedure MapExclude(var Map: TPassportMap; Serial, No: integer); begin; if (Serial<0) or (Serial>9999) or (No<0) or (No>999999) then exit; if Length(Map)=0 then exit; if Length(Map[Serial])=0 then exit; Map[Serial, No shr 3]:=(not (1 shl (No and 7))) and Map[Serial, No shr 3]; end; function MapTest(var Map: TPassportMap; Serial, No: integer): boolean; begin; Result:=false; if (Serial<0) or (Serial>9999) or (No<0) or (No>999999) then exit; if Length(Map)=0 then exit; if Length(Map[Serial])=0 then exit; Result:=1 shl (No and 7) and Map[Serial, No shr 3]<>0; end; function SubstrToInt(const s: string; i1, i2: integer): integer; var i, c: integer; begin; Result:=0; for i:=i1 to i2 do begin; c:=ord(s[i])-ord('0'); if cardinal(c)>9 then begin; Result:=-1; exit; end; Result:=Result*10+c; end; end; procedure LoadPassportList(var Map: TPassportMap; const FileName: string); var Fi: Text; s: string; begin; Map:=nil; Assign(Fi, Filename); Reset(Fi); while not EOF(Fi) do begin; ReadLn(Fi, s); if (Length(s)=11) and (s[5]=',') then MapInclude(Map, SubstrToInt(s,1,4), SubstrToInt(s,6,11)); end; CloseFile(Fi); end; procedure SavePassportMap(var Map: TPassportMap; const FileName: string); var Fi: file; Serial: integer; begin; Assign(Fi, Filename); Rewrite(Fi,1); for Serial:=0 to Length(Map)-1 do if Length(Map[Serial])=125000 then begin; BlockWrite(Fi, Serial, 4); BlockWrite(Fi, Map[Serial,0], 125000); end; CloseFile(Fi); end; procedure LoadPassportMap(var Map: TPassportMap; const FileName: string); var Fi: file; Serial, Count: integer; begin; Map:=nil; SetLength(Map, 10000); Assign(Fi, Filename); Reset(Fi,1); while true do begin; BlockRead(Fi, Serial, 4, Count); if Count=0 then break; if (Count<>4) or (Serial<0) or (Serial>9999) then begin; Map:=nil; break; end; SetLength(Map[Serial], 125000); BlockRead(Fi, Map[Serial,0], 125000, Count); if Count<>125000 then begin; Map:=nil; break; end; end; CloseFile(Fi); end; procedure EncodeDelta(var Buf: TBuffer; var BufPos: integer; Delta: integer); begin; if Delta<=$7F then begin; Buf[BufPos]:=Delta; inc(BufPos); end else if Delta<=$3FFF then begin; Buf[BufPos]:=Delta and $3F or $80; Buf[BufPos+1]:=Delta shr 6; inc(BufPos, 2); end else begin; Buf[BufPos]:=Delta and $3F or $C0; Buf[BufPos+1]:=Delta shr 6; Buf[BufPos+2]:=Delta shr 14; inc(BufPos, 3); end; end; function DecodeDelta(var Buf: TBuffer; var BufPos: integer): integer; begin; Result:=Buf[BufPos]; if Result<=$7F then begin; inc(BufPos); end else if Result<=$BF then begin; Result:=integer(Buf[BufPos+1]) shl 6 or Result and $3F; inc(BufPos, 2); end else begin; Result:=integer(Buf[BufPos+2]) shl 14 or integer(Buf[BufPos+1]) shl 6 or Result and $3F; inc(BufPos, 3); end; end; procedure SavePassportPacket(var Map: TPassportMap; const FileName: string); var Fi: file; Serial, No, OldNo, Val, Bit, BufPos, i, j: integer; Buf: TBuffer; begin; Assign(Fi, Filename); Rewrite(Fi,1); for Serial:=0 to Length(Map)-1 do if Length(Map[Serial])=125000 then begin; BlockWrite(Fi, Serial, 4); Bit:=Map[Serial,0] and 1; BlockWrite(Fi, Bit, 1); No:=0; OldNo:=0; BufPos:=0; for i:=0 to 125000-1 do begin; Val:=Map[Serial,i]; if (Val=0) and (Bit=0) or (Val=255) and (Bit<>0) then begin; inc(No, 8); end else for j:=0 to 7 do begin; if Val and 1<>Bit then begin; EncodeDelta(Buf, BufPos, No-OldNo-1); OldNo:=No; Bit:=Bit xor 1; end; inc(No); Val:=Val shr 1; end end; EncodeDelta(Buf, BufPos, No-OldNo-1); BlockWrite(Fi, BufPos, 4); BlockWrite(Fi, Buf[0], BufPos); end; CloseFile(Fi); end; procedure LoadPassportPacket(var Map: TPassportMap; const FileName: string); var Fi: file; Serial, No, OldNo, Bit, BufLen, BufPos: integer; Buf: TBuffer; var Count: integer; begin; Map:=nil; SetLength(Map, 10000); Assign(Fi, Filename); Reset(Fi,1); while true do begin; BlockRead(Fi, Serial, 4, Count); if Count=0 then break; if (Count<>4) or (Serial<0) or (Serial>9999) then begin; Map:=nil; break; end; Bit:=0; BlockRead(Fi, Bit, 1, Count); Bit:=Bit xor 1; if (Count<>1) or (Bit and -2<>0) then begin; Map:=nil; break; end; BlockRead(Fi, BufLen, 4, Count); if (Count<>4) or (BufLen<=0) or (BufLen>SizeOf(Buf)) then begin; Map:=nil; break; end; BlockRead(Fi, Buf[0], BufLen, Count); if Count<>BufLen then begin; Map:=nil; break; end; SetLength(Map[Serial], 125000); No:=0; OldNo:=0; BufPos:=0; while BufPos<BufLen do begin; No:=DecodeDelta(Buf, BufPos)+1+No; Bit:=Bit xor 1; if (BufPos>BufLen) or (No>999999+1) then break; if Bit=0 then while OldNo<No do begin; if (OldNo and 7=0) and (OldNo+7<No) then begin; Map[Serial, OldNo shr 3]:=0; inc(OldNo, 8); end else begin; Map[Serial, OldNo shr 3]:=(not (1 shl (OldNo and 7))) and Map[Serial, OldNo shr 3]; inc(OldNo); end; end else while OldNo<No do begin; if (OldNo and 7=0) and (OldNo+7<No) then begin; Map[Serial,OldNo shr 3]:=$FF; inc(OldNo, 8); end else begin; Map[Serial, OldNo shr 3]:=1 shl (OldNo and 7) or Map[Serial, OldNo shr 3]; inc(OldNo); end; end; end; if (BufPos<>BufLen) or (No<>999999+1) then begin; Map:=nil; break; end; end; CloseFile(Fi); end; procedure EncodeDelta2(var Buf: TBuffer; var BufPos, CodeLen: integer; Delta: integer); begin; if (CodeLen>0) and (Delta<=8) then begin; //пробуем запихнуть маленькую дельту в предыдущий код if Delta=0 then begin; //используем $40 как флаг нулевой дельты if CodeLen=1 then Buf[BufPos-1]:=$40 or Buf[BufPos-1] else Buf[BufPos+1-CodeLen]:=$40 or Buf[BufPos+1-CodeLen]; CodeLen:=0; //чтобы больше не пихать, место занято exit; end else if (CodeLen=1) and (Buf[BufPos-1]<=7) then begin; //если предыдущий код был маленький, то пихаем в него ненулевую дельту Buf[BufPos-1]:=(Delta-1) shl 3 or $80 or Buf[BufPos-1]; CodeLen:=0; //чтобы больше не пихать, место занято exit; end; end; if Delta<=$3F then begin; Buf[BufPos]:=Delta; inc(BufPos); CodeLen:=1; end else if Delta<=$FFF then begin; Buf[BufPos]:=Delta and $3F or $C0; Buf[BufPos+1]:=Delta shr 6; inc(BufPos, 2); CodeLen:=2; end else begin; Buf[BufPos]:=Delta and $3F or $C0; Buf[BufPos+1]:=Delta shr 6 and $3F or $80; Buf[BufPos+2]:=Delta shr 12; inc(BufPos, 3); CodeLen:=3; end; end; function DecodeDelta2(var Buf: TBuffer; var BufPos, NextDelta: integer): integer; begin; if NextDelta>=0 then begin; Result:=NextDelta; NextDelta:=-1; exit; end; Result:=Buf[BufPos]; if Result<=$3F then begin; inc(BufPos); end else if Result<=$7F then begin; NextDelta:=0; Result:=Result and $3F; inc(BufPos); end else if Result<=$BF then begin; NextDelta:=Result shr 3 and $7 + 1; Result:=Result and 7; inc(BufPos); end else begin; if Buf[BufPos+1] and $40<>0 then NextDelta:=0; Result:=integer(Buf[BufPos+1]) and $3F shl 6 or Result and $3F; if Buf[BufPos+1] and $80=0 then inc(BufPos, 2) else begin; Result:=integer(Buf[BufPos+2]) shl 12 or Result; inc(BufPos, 3); end; end; end; procedure SavePassportPacket2(var Map: TPassportMap; const FileName: string); var Fi: file; Serial, No, OldNo, Val, Bit, BufPos, CodeLen, i, j: integer; Buf: TBuffer; begin; Assign(Fi, Filename); Rewrite(Fi,1); for Serial:=0 to Length(Map)-1 do if Length(Map[Serial])=125000 then begin; BlockWrite(Fi, Serial, 4); Bit:=Map[Serial,0] and 1; BlockWrite(Fi, Bit, 1); No:=0; OldNo:=0; BufPos:=0; CodeLen:=0; for i:=0 to 125000-1 do begin; Val:=Map[Serial,i]; if (Val=0) and (Bit=0) or (Val=255) and (Bit<>0) then begin; inc(No, 8); end else for j:=0 to 7 do begin; if Val and 1<>Bit then begin; EncodeDelta2(Buf, BufPos, CodeLen, No-OldNo-1); OldNo:=No; Bit:=Bit xor 1; end; inc(No); Val:=Val shr 1; end end; EncodeDelta2(Buf, BufPos, CodeLen, No-OldNo-1); BlockWrite(Fi, BufPos, 4); BlockWrite(Fi, Buf[0], BufPos); end; CloseFile(Fi); end; procedure LoadPassportPacket2(var Map: TPassportMap; const FileName: string); var Fi: file; Serial, No, OldNo, Bit, BufLen, BufPos, NextDelta: integer; Buf: TBuffer; var Count: integer; begin; Map:=nil; SetLength(Map, 10000); Assign(Fi, Filename); Reset(Fi,1); while true do begin; BlockRead(Fi, Serial, 4, Count); if Count=0 then break; if (Count<>4) or (Serial<0) or (Serial>9999) then begin; Map:=nil; break; end; Bit:=0; BlockRead(Fi, Bit, 1, Count); Bit:=Bit xor 1; if (Count<>1) or (Bit and -2<>0) then begin; Map:=nil; break; end; BlockRead(Fi, BufLen, 4, Count); if (Count<>4) or (BufLen<=0) or (BufLen>SizeOf(Buf)) then begin; Map:=nil; break; end; BlockRead(Fi, Buf[0], BufLen, Count); if Count<>BufLen then begin; Map:=nil; break; end; SetLength(Map[Serial], 125000); No:=0; OldNo:=0; BufPos:=0; NextDelta:=-1; while (BufPos<BufLen) or (NextDelta>=0) do begin; No:=DecodeDelta2(Buf, BufPos, NextDelta)+1+No; Bit:=Bit xor 1; if (BufPos>BufLen) or (No>999999+1) then break; if Bit=0 then while OldNo<No do begin; if (OldNo and 7=0) and (OldNo+7<No) then begin; Map[Serial, OldNo shr 3]:=0; inc(OldNo, 8); end else begin; Map[Serial, OldNo shr 3]:=(not (1 shl (OldNo and 7))) and Map[Serial, OldNo shr 3]; inc(OldNo); end; end else while OldNo<No do begin; if (OldNo and 7=0) and (OldNo+7<No) then begin; Map[Serial,OldNo shr 3]:=$FF; inc(OldNo, 8); end else begin; Map[Serial, OldNo shr 3]:=1 shl (OldNo and 7) or Map[Serial, OldNo shr 3]; inc(OldNo); end; end; end; if (BufPos<>BufLen) or (NextDelta>=0) or (No<>999999+1) then begin; Map:=nil; break; end; end; CloseFile(Fi); end; end. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 23:04 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, эх, жаль, забыл исходнику тег добавить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.01.2016, 23:06 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
maytonДавайте отложим в сторону юридические моменты. Это не интересно для sql.ru. Лучше обсужить способы storage и оперативный доступ. программирование несколько, шире чем кодирование ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2016, 00:02 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Если мерить GetTickCount-ом, то получается так: Код: plaintext 1. 2. 3. 4. 5. В среднем 15 ms на паспорт. Тут что-то неправильно мерялось. Откуда эти нули? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2016, 00:14 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
miksoftDima T1,25 Гб. Всего 4 твоих Блума.Более того, можно вынести третью и четвертую цифры вперед, добавить кольцевой сдвиг (чтобы счет начинался с нуля). Тогда у битовой карты будет использована только первая четверть, а оставшиеся три четверти можно будет просто обрезать. У меня была мысль оценить распределение паспортных пространств во всём универсуме. Для этого визуализировать диапазоны и серии на картинке в виде полосок. Как я это планировал сделать. Например - представить номер паспорта в формате AAAA,BBBBBB как точку с координатами (AAAAB,BBBBB) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2016, 00:19 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
mayton, Да тут особо нечего оценивать. Неравномерностей я вижу всего две: - 3 и 4 цифры, т.к. система работает порядка 25 лет. - старшие цифры номера, т.к. далеко не каждый регион израсходовал весь диапазон номеров в конкретный год. (Кстати, это входит в этот файл или нет?) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2016, 00:33 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Вобщем как-то вот так. Белым пикселам соответствуют использованные паспортнные номера из нашего списка. Грубо 0000,000000 должен соотвествовать пикселу с координатами (0,0). Правому нижнему - 9999,999999 - (511,511). Есть предположение что горизонтальные белые полосы на самом деле не сплошные. В них должны быть дырки. Просто из за уменьшения масштаба эти дырки размером менее 1 пиксела я должен был учитывать в виде антиалиазинга (несколько номеров попадают в 1 пиксел) но алгоритм - грубый и оценочный, и я просто на это забил. Если я где-то ошибся то прошу меня поправить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2016, 01:38 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
1) Немножко переделал. 0000,000000 должен соотвествовать пикселу с координатами (0,0). Да. Координаты - наоборот. Строкам соотвествуют серии. Столбцам - номера. Так более правильно. 2) В картинке появились полу-тона. Просто рендерю в 1024х1024 а потом уменьшаю в два раза чтоб в форуме значить как-то красивее смотрелось. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2016, 02:20 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
mayton, А если 3 и 4 цифры серии вынести вперед, то какая картина получится? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2016, 02:26 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
miksoftmayton, А если 3 и 4 цифры серии вынести вперед, то какая картина получится? Завтра, бро. Меня одолевает древне-греческий бог Гипнос. Осоловело тру глазищи... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2016, 02:40 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Одолел божество. Проснулся. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2016, 13:20 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
__Avenger__Добрый вечер! Можно ли запаковать в один Int(4-байта) два числа, первое - не превышает 9999, второе - не превышает 999999? Читал только 1-ю страницу Охренеть флудерасты ) 9999 - 14 бит 999999 - 20бит всего то надо 34 бита из 64 и ВОСЕМЬ!!! страниц набили программисты ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2016, 13:25 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima T, я вообще в таких случаях делаю клон топика. С пометкой дескыть - в продолжение беседы URL=.... e.t.c. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2016, 13:44 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Отрендерил в 2048х2048. Появились детали. Из характера картинки делаю гипотезы. 1) Данную картинку можно представить как суперпозицию двух других. Или в терминологии ребят, которые работают в Фотошопах - она двуслойна. 2) Один слой содержит ярко-выраженные горизонтальные полосы. Это те что выше коллеги пытались сжать диапазонами. 3) Второй слой - это звёздная пыль из случайных точек (номеров) которые в серии оказались достаточно редкими. Я еще не оценивал их количество. Возникает естественное тех-предложение переделать логику хранения исходя из пунктов (2) (3). А именно - разделить систему хранения на 2 части. Первая часть оперирует диапазонами. А вторая часть - отдельно стоящими номерами. Алгорим, естественым образом должен делать lookup номера в обоих хранилищах последовательно. Полагаю что такой подход позволит еще сильнее сэкономить даже без использования архиваторов, применение которых в данной задаче я считаю ненужным. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2016, 14:00 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Прикладываю картинку коллегам для анализа. Дабы не сердить модератора (и без того дизайн скруля трещит по швам от толстых картинок) я завернул ее в 7zip ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2016, 14:06 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
AWSVladimir__Avenger__Добрый вечер! Можно ли запаковать в один Int(4-байта) два числа, первое - не превышает 9999, второе - не превышает 999999? Читал только 1-ю страницу Охренеть флудерасты ) 9999 - 14 бит 999999 - 20бит всего то надо 34 бита из 64 и ВОСЕМЬ!!! страниц набили программисты 33 бита. расслабься ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.02.2016, 14:42 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
ИзопропилAWSVladimirвсего то надо 34 бита из 64 33 бита. расслабься А пример, что реально можно ужать? Только не надо словестной казуистикой заниматься, что первый бит нулевой. Написано же 34 бита из 64 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.02.2016, 09:01 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Написал парсер списка. Определяюсь с форматом хранения полного состояния. 1. Биткарты Код: sql 1. 2. 3. 4. 5. 2. Биткарты и списки Код: sql 1. 2. 3. 4. 5. 3. Пожатые биткарты Код: sql 1. 2. 3. 4. 5. Результат ФорматРазмерПожатый RARБиткарты349 580 01626 950 857Биткарты+списки (4 байта на адрес)122 389 24427 368 588Биткарты+списки (3 байта на адрес)112 311 93727 307 492Биткарты пожатые26 911 70726 458 169 Плюс у смешанного формата (биткарты+списки) один: размер в непожатом состоянии У биткарт плюсы: поиск в 2 чтения, быстрый расчет обновления (XOR двух биткарт), можно дописывать в существующий файл. У пожатых биткарт частично плюсы биткарт, только для доступа надо сначала ее распаковать, это скорее компромисс между всеми вариантами. Средний размер одной пожатой биткарты 9305 байт. Я почему-то склоняюсь к третьему варианту. PS Если не устану, хочу законченную прогу написать: загрузка из csv, сохранение в своем формате, расчет обновлений, накат обновлений, скачивание обновлений с первоисточника. Исходники потом выложу (C#). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.02.2016, 13:57 |
|
||
|
Два число в одно и обратно
|
|||
|---|---|---|---|
|
#18+
Dima TPS Если не устану, хочу законченную прогу написать: загрузка из csv, сохранение в своем формате, расчет обновлений, накат обновлений, скачивание обновлений с первоисточника. Исходники потом выложу (C#). +1 Это было-бы очень продуктивно. На архиватор я-бы предложил "забить болт". Ну тоесть архивировать можно но решений по поводу эффективности не принимать. Нативный формат в 100 Мб - это само посебе уже отличное решение. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.02.2016, 14:24 |
|
||
|
|
start [/forum/topic.php?all=1&fid=16&tid=1340797]: |
0ms |
get settings: |
8ms |
get forum list: |
12ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
189ms |
get topic data: |
7ms |
get forum data: |
2ms |
get page messages: |
115ms |
get tp. blocked users: |
1ms |
| others: | 260ms |
| total: | 598ms |
| 0 / 0 |
