Здравствуйте, 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

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

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

Да красиво, вообщем и целом очень быстро должно получаться...
Но похоже можно сделать все тоже самое в один проход

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

Единственное что меня пока останавливает в реализации такого алгоритма это то, что выбор оптимального размера временного блока, уж очень часто встречаются домйны которые содержат не более 4-5 юзеров. если выбрать очень большой блок можем уперется в размер свободного пространства на диске, если очень маленький то просто оперативки не хватит вообщем пока думаем на данную тему как бужет сводный час сдлаю это с хеш таблицей а то про дерево мне еще надо читать, пока не было надобности такое строить

Но все равно спасибо.

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

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

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

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

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

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

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

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

К>>1) для каждой записи вида Name@Domain открываем файл .../temp/Domain и дописываем туда строку Name
К>>2) сортируем список файлов temp/* и склеиваем их содержимое в один файл
К>>На шелле (даже на бат-файлах) можно написать, правда, рожать будет очень долго...

GSL>Это первое решение которое пришло в голову, количество файлов может начать измеряться сотнями тысяч или более да и медленно это оказалось, открытие и закрытие файлов это очень медленно... именно эти 2 операции...так 100 000 файлов по одной строке записать в файл занимает на PC кажеться 10 минут

А если по буквам сортировать? Тогда файлы можно будет открытыми держать.

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

GSL>Память на машине скажем 512мега, на винте можно брать до 200 гига ( но лучще бы обойтись не более чем 25-50 гигов. )

ИМХО, одним из быстрых вариантов будет простая реализация сортировки Фон-Неймана (aka ленточной) с предварительным проходом по исходным данным. Сперва из исходного файла (F1) читаем сколько влезет в память, сортируем чем-нибудь достаточно быстрым в памяти, кидаем результат в промежуточный файл (F2), и так до конца F1. Теперь у нас в исходном файле где-то 50-100 посортированных блоков, и за 7 проходов ленточной сортировки мы их объединим в единый сортированный блок.

DK>ИМХО, одним из быстрых вариантов будет простая реализация сортировки Фон-Неймана (aka ленточной) с предварительным проходом по исходным данным. Сперва из исходного файла (F1) читаем сколько влезет в память, сортируем чем-нибудь достаточно быстрым в памяти, кидаем результат в промежуточный файл (F2), и так до конца F1. Теперь у нас в исходном файле где-то 50-100 посортированных блоков, и за 7 проходов ленточной сортировки мы их объединим в единый сортированный блок.

А при таком количестве блоков лучше просто запихать их все в разные файлы, а далее слить их все сразу, тоже ИМХО

Здравствуйте, <Аноним>, Вы писали:

ленточной сортировки мы их объединим в единый сортированный блок.

А>А при таком количестве блоков лучше просто запихать их все в разные файлы, а далее слить их все сразу, тоже ИМХО

1) Я не знаю какая именно там файловая система.
2) Писать слияние одновременно 100 файлов — весьма непростая задача. Тут и очередь с приоритетами, и много всяких ньюансов....
3) ИМХО Есди операция разовая — оверхед (временнной, не синтаксический ) не столь критичен, если операция частая — скорее всего изменения будут добавляться сперва в конец файла, вряд ли их будет больше 500МБ за раз — при повторе операции после предварительной сортировки у нас будет всего 2-3-4 монотонных последовательности, так что нам потребуется 1-2 прохода для достижения полного порядка.

А чем дело то закончилось ?

Здравствуйте, Аноним, Вы писали:

А>А чем дело то закончилось ?

Дело закончилось очень просто...
Написал примерно то что тут назвали ленточной сортировкой...
отсеили логи нашли баг, закрыли тему

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

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

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

Продай базу сортированную