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

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

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