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

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

GSL>>Задачка реальная и с виду простая.
GSL>>Итак есть файл в нем есть мылы. Повторяемость 15%. Надо рассортировать все по доменам и отсечь думбликаты. Ну дубликаты это дело десятое, потому как всего 15%. Порядок адрресов совершенно произвольный. А вот рассортировать по доменам надо как можно более быстро. Количество доменов может измеряться цифрой с 6 нулями
GSL>>А вот теперь этюдная загвоздка исходный файл ( или набор файлов ) от 25-50 гигабайт, и не содержит лишней информации кроме адрессов,
GSL>>Память на машине скажем 512мега, на винте можно брать до 200 гига ( но лучще бы обойтись не более чем 25-50 гигов. )

C>Можно построить PATRICIA trie по строкам доменов. В этом случае дерево строится в оперативке и на каждый узел приходится 16 байт (2 пойнтера + skip + птр на строку). В то же время строки (уже только уникальные!) хранятся либо в отображаемом в память файле, либо в ОЗУ (если хватает). В принципе, скорость доступа к строкам не так критична, как к узлам. На каждую уникальную строку домена приходится один узел. Итак, требования к памяти минимальны. Добавление и поиск нодов в цифровом дереве происходит за время O(logN). Затем построенную патрицию можно использовать для сортировки по доменам во втором проходе по мега-файлу, ибо в дереве уже все строки упорядочены. Подробности устройства алгоритма см. Кнут, Искусство программирования, т.3

Тут есть некоторые загвоздки, 512 мега памяти дано просто что бы было нас самом деле давайте сделаем вид что у на 1 мега и решение не работает. надо решать быстро и универсально...
Такие деревью перестают себя оправдывать при использовнии большего объемв памяти чем есть в налии совбодной физической памяти ) потому как по узлам придеться бегать все время а виртуальная память не самая быстрая...

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

domain : user1 user2 user3....

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

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

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

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

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