Здравствуйте, GSL, Вы писали:

GSL>Здравствуйте, cranky, Вы писали:

C>>Да, теперь вижу, что со вторым проходом я слегка недодумал. Новый вариант решения [...] Позиция первого блока каждого домена вычисляется по смещению узла относительно корня (самый первый узел).
Я тут лучше подумал — не вычисляется она, надо всё же явно хранить с узлом позицию первого блока домена.

GSL>Да красиво, вообщем и целом очень быстро должно получаться...
GSL>Но похоже можно сделать все тоже самое в один проход
Ну да, про второй проход уже речи нет. Хотя можно съэкономить объём памяти под узлы именно путём увеличения числа проходов. Такая идея: знаю статистику распределения первых символов строк доменов, разделить их на классы по числу желаемых проходов и на каждом проходе обрабатывать только те домены, что входят в нужный класс.

GSL>собственно если смещения сразу писать в ноды, ведь как бы дерево не меняловь смещения остануться на месте.
GSL>причем можно даже просто импользовать хешь таблицу для хранения этих данных, а в последней стадии просто объединить временные блоки в единое целое и отсечь все дубликаты
Таки смещений может быть слишком много, где брать память?

GSL>Единственное что меня пока останавливает в реализации такого алгоритма это то, что выбор оптимального размера временного блока, уж очень часто встречаются домйны которые содержат не более 4-5 юзеров. если выбрать очень большой блок можем уперется в размер свободного пространства на диске, если очень маленький то просто оперативки не хватит вообщем пока думаем на данную тему как бужет сводный час сдлаю это с хеш таблицей а то про дерево мне еще надо читать, пока не было надобности такое строить
Но хеш не сортирует строки, хотя позволяет избавиться от дубликатов, наверное это только и нужно Насчёт размера блока. Можно сделать его увеличивающимся в геом. прогрессии: первый блок – 64 байта, второй – 128 и т.д. Получается так, как по мере заполнения выделяется память для вектора из STL. Но в данном случае мне кажется, надо установить верхний предел размера блока. Тогда с узлом придётся хранить немного более расширенную информацию: смещение первого блока, смещение и размер текущего блока, текущее смещение в текущем блоке.

GSL>Но все равно спасибо.
Да пожалуйста, и спасибо за интересную задачу!