Здравствуйте, cranky, Вы писали:
C>Да, теперь вижу, что со вторым проходом я слегка недодумал. Новый вариант решения: по мере чтения мылов входного файла образуем патрицию по строкам доменов, как и ранее, но структура данных, на которую будет ссылаться каждый нод должна включать кроме строки ещё и указатель позиции в промежуточном файле. Этот файл состоит из блоков одинакового фиксированного размера (напр. 4К), каждый из которых содержит имена юзеров, разделённые '\0' и принадлежащие одному домену и в конце блока позицию следующего блока этого же домена. Тогда при добавлении нового уникального домена в цифродерево мы просто присоединяем ещё один блок к промежуточному файлу, если же домен уже существует — просто записываем в сохранённую позицию новое имя юзверя. Если имя не помещается в блок, присоединяем к файлу новый блок и записываем его позицию в конец старого. В конце всей процедуры имеем промежуточный файл, отсортированный по доменам (при условии сохранения дерева). Позиция первого блока каждого домена вычисляется по смещению узла относительно корня (самый первый узел). Кстати, узлы дерева можно тоже вынести в отображаемый файл, ибо теперь доступ к ним необходим исключительно последовательный (в глубину, путём сохранения парентов в стеке), без повторного захода в узел. Дальнейшая сортировка по юзерам уже не составляет особой проблемы, но если очень хочется, то можно опять же воспользоваться исключительно красивым алгоритмом PATRICIA 
Да красиво, вообщем и целом очень быстро должно получаться...
Но похоже можно сделать все тоже самое в один проход
собственно если смещения сразу писать в ноды, ведь как бы дерево не меняловь смещения остануться на месте.
причем можно даже просто импользовать хешь таблицу для хранения этих данных, а в последней стадии просто объединить временные блоки в единое целое и отсечь все дубликаты
Единственное что меня пока останавливает в реализации такого алгоритма это то, что выбор оптимального размера временного блока, уж очень часто встречаются домйны которые содержат не более 4-5 юзеров. если выбрать очень большой блок можем уперется в размер свободного пространства на диске, если очень маленький то просто оперативки не хватит
вообщем пока думаем на данную тему
как бужет сводный час сдлаю это с хеш таблицей а то про дерево мне еще надо читать, пока не было надобности такое строить
Но все равно спасибо.
