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

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

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

GSL>>>Задачка реальная и с виду простая.
[...]

C>>Можно построить PATRICIA trie по строкам доменов.
[...]

GSL>Тут есть некоторые загвоздки, 512 мега памяти дано просто что бы было нас самом деле давайте сделаем вид что у на 1 мега и решение не работает. надо решать быстро и универсально...
GSL>Такие деревью перестают себя оправдывать при использовнии большего объемв памяти чем есть в налии совбодной физической памяти ) потому как по узлам придеться бегать все время а виртуальная память не самая быстрая...
Это да... Но если кол-во доменов в районе 1е6, то и ОЗУ нужно 16М, что немного.

GSL>Мы просто поделили процесс на 2 стадии первый это перегонка в кучу файлов формата отсортированных по domain

GSL>domain : user1 user2 user3....

GSL>т.е. читаем и сортируем пока есть память, потом пишем на винт.чистим память и новый файл...

GSL>Объем данных сократился примерно на 50-70%

GSL>далее пакетная обработка совмещения пакетов, по 32 файла уже без анализа строк с минимальным объемом используемой памяти ( можно буферизировать но скорее всего ничего не даст ) В итоге после нескольких повторов второй стадии имеем остсортированный файл...потому-что после первой стадии файлы уже осортированы.

GSL>Теперь почему мне этот вариант понравился больше... потому, что он есть память только на 1 этапе работы, Второй этап достаточно медленный но зато совсем не ест память

GSL>С деревом я почитаю но, что-то мне говорить что во втором этапе у нас будут проблемы, потому как список отсортированных доменов не дает нам ничего при втором проходе для постоения окончательного списка..потому как т.е. я не вижу как можно используя память только для хранения любого дерева остортирровать по сути дела поток. потому как мега файл по сути своей не что иное как предсказуемый поток данных.

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