И дальше буду его оптимизировать, несколько месяцев.
Вон Judy Array, ближайший конкурент, конторка Hawlet Packard целых два года лабала
средствами целой комманды задротов-очкариков. 20 тысяч строк кода в имплементации !
Но они мне в три раза слили на 32х битных ключах, хехе :)

А на 16 байтных ключах, хештаблицы, мне сливают гдето на 30% пока что.
Но опять же, хештаблицы не сортируют данные, а я сортирую, чтобы по индексу иметь
возможность делать выборки по диапазону.

ДохтаРmaytonДохтаР, я тоже думал о дереве остатков.

Еще дополнение. Три цифры ### - это порядковый номер зарегистрированного
человека в этот день. Учитывая статистику рождаемости/регистрации
налогоплательщиков вряд-ли это будет достигать 999.

Цифра будет гораздо более скромная.

999 сжимается в полтора байта - 12 бит ( пол байта на цифру), в 16ричном редакторе читать удобно :)
и даже в 10 бит =1024, если не облом со сдвигами возиться.

Твоя имплементация будет иметь минимум 4 колена дерева. 3 колена год/месяч/число и остаток 4е колено.
А это весьма неудачная реализация. Сольет Стебельку в раз десять ..................
...............

maytonBAZlST, ну... я о принципе говорю. Есть такие DBMS (не помню щас названий)
которые настолько интенсивно юзают указатели (всякие там колончатые DBMS,
графовые) что для них сериализация представляет собой целую проблему.
Даже не сериализация а принципиальное отсутствие ключа вида "ID".
Надеюсь у тебя такой проблемы не будет и твои 16G не будут
пол-дня сохраняться.

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

maytonДохтаР999 сжимается в полтора байта - 12 бит ( пол байта на цифру), в 16ричном редакторе читать удобно :)
и даже в 10 бит =1024, если не облом со сдвигами возиться.
Да не будет там даже 500 регистраций. Я сейчас ищу статистику рождаемости
по сайтам Держстат но там всё только в разрезе страны и за кварталы.
А мне нужно аппроксимировать за 16 лет назад и взять за 1 день чтобы
знать сколько будут регаться в 1 день сегодня 16 летние.

зачем столько геморроя изза простой задачи ?
тебе какая производительность нужна ?

ДохтаРBAZlSTпропущено...


Твоя имплементация будет иметь минимум 4 колена дерева. 3 колена год/месяч/число и остаток 4е колено.
А это весьма неудачная реализация. Сольет Стебельку в раз десять ..................
...............

Та мне пофик на стебелек, один ИНН хранить не разумно ,
там обязательно появиться еще что то типа ФИО,
ключей к договорам, номера паспорта, телефона и еще кучи фигни
для которой уже можно заводить оракел или на крайняк сиквелалйт .

и чо ?

Все это реализовывается в два счета на noSQL.

ДохтаРТа я не против, реализуй
Мне реализация учета на SQL более по душе.

SQL здесь и действительно лучше. Справочная маленькая табличка персонов,
чо там оптимизировать и главное ЗАЧЕМ - не понятно =)
Непонятна сама постановка задачи.

maytonМне вообще не нужна производительность. Я спросил про РАЗМЕР
той структуры данных которая нужна для хранения этого набора ключей.
Зачем? Хм... может решил в браузере в JavaScript-е эти проверки делать.
Кто-то ставит постановки на скорость. Я - на объём. А что. Имею право.

размер у тебя 34*46/8 = 195 мб + служебная инфо.
И стоит ради такого обьема информации чесать яйтса ?

maytonИли на мобильнике таскать. А мобильники они знаешь какие. А?
Не у всех по 8 гигов стоит. У меня - вообще по 256К на один аппликейшн.
Вот так-то.

46млн персонов ты несожмешь в 256 килобайт.
О чем твоя задача ? О мобильнике Нокия 6610 ?

Короче решаем вотету задачу 13716181 , а я домой

maytonBAZlSTразмер у тебя 34*46/8 = 195 мб + служебная инфо.
И стоит ради такого обьема информации чесать яйтса ?
Может быть и нет. Но моя задача имела материальную составляющую.

А синтетику в виде сколько байтов совпадут - решать не интересно.
Тем более что твои задачи прекрасно решены в основах тв.и.мс.

Купи на Петровке книжку - Гмурман - Теория вероятностей и мат-статистика.
Задачник с решениями. Бомбовская вещь. После неё и таких
постановок у тебя не будет.

У тебя тест с числовым рядом еще более синтетический
чем я тестировал. Я то брал нормальное такое случайное распределение из заархивированых файлов,
а у тебя отличная синтетическая закономерность из дат вначале ИНН.
Потому утверждение, скорость вставок 20млн неверное. Верно 30-40 млн.
Но это тебе не нужно, потому что задача твоя вообще ниочем.
На диске файлик займет 500 мб места в хучшем случае, зачем ты приплел мобильные устройства с 256к памяти
совсем непонятно.

maytonBAZlSTКороче решаем вотету задачу 13716181 , а я домой
Уже решено. Эти задачи с битами байтами и эмуляцией минимумов максимумов
решил Генри Уоррен. Там-же и он коснулся моей любимой темы. Генераторов
числовых последовательностей. Все базовые целочисленные алгоритмы - там-же.

Почитай эту книгу.

http://www.kodges.ru/15309-algoritmicheskie-trjuki-dlja-programmistov.html

Мне вообщето код нужно на Си, а не "почитай эту книгу".

maytonБаз. Я тебя не узнаю! То вроде был силён в теории. А то вдруг - дайте Си. Зачем тебе Си?
Там ничего нового уже не будет. Все изъезжено вдоль и поперек. Теория брадт.
Это сила. Я бы мат. периодику читал да мозгов не хватает. Завидую парням
которые жонглируют кольцами, полями, множествами.

А ты не завидуешь?

Вот ты мне скажи, ты что уподобился дедалу или аленю ?
Есть задача. Допустим тебя спросили такую задачу на собеседовании.
Ты что человеку который тебя собеседует на смекалку скажешь - почитайте книгу.
Она нахрен не имеет никакого отношения к задаче.
Или предложите решение, или вообще нахрен ничего не отписывайте в тему и не позорьтесь.
Шо доктор включил дурачка "реши сдвигами" шо майтон включил дурачка "читай книжку".

Если есть красивый алгоритм - пишите. Нет - ну так окончательно не показывайте свою тупосць.
Ну емае.