Итак есть файл в нем есть мылы. Повторяемость 15%. Надо рассортировать все по доменам и отсечь думбликаты. Ну дубликаты это дело десятое, потому как всего 15%. Порядок адрресов совершенно произвольный. А вот рассортировать по доменам надо как можно более быстро. Количество доменов может измеряться цифрой с 6 нулями
С виду все тривиально и не этюдно.
А вот теперь этюдная загвоздка исходный файл ( или набор файлов ) от 25-50 гигабайт, и не содержит лишней информации кроме адрессов,
Память на машине скажем 512мега, на винте можно брать до 200 гига ( но лучще бы обойтись не более чем 25-50 гигов. )
Какме есть предложения.
Выбор средств не ограничен, можете прост в текстовм редакторе дать последовательность кнопок.
Re: Требуеться этюдное решение.
От:
Аноним
Дата:
06.07.05 05:49
Оценка:
Здравствуйте, GSL, Вы писали:
GSL>Задачка реальная и с виду простая.
GSL>Итак есть файл в нем есть мылы. Повторяемость 15%. Надо рассортировать все по доменам и отсечь думбликаты. Ну дубликаты это дело десятое, потому как всего 15%. Порядок адрресов совершенно произвольный. А вот рассортировать по доменам надо как можно более быстро. Количество доменов может измеряться цифрой с 6 нулями
GSL>С виду все тривиально и не этюдно. GSL>А вот теперь этюдная загвоздка исходный файл ( или набор файлов ) от 25-50 гигабайт, и не содержит лишней информации кроме адрессов,
GSL>Память на машине скажем 512мега, на винте можно брать до 200 гига ( но лучще бы обойтись не более чем 25-50 гигов. )
GSL>Какме есть предложения. GSL>Выбор средств не ограничен, можете прост в текстовм редакторе дать последовательность кнопок.
Для начала можно отсортировать по алфавиту, то есть раскидать по 26 файлам — далее каждый файлик сортировать отделньо, там уже скорее всего и qsort() подойдет. Повторы можно убить после сортировки за линейное время.
З.Ы. А можно за помощь попросить убрать мои мылы из базы, а?
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, GSL, Вы писали: E>Я в чём собственно цель глобальная состоит? В какой форме хочется получить файлы рассортированный по доманам? E>Казалось бы, берёшь БД и льёшь в неё записи по одной, одно поле -- домен, другое -- юзер. Дальше всё средствами БД имеешь
E>А что за шпионско-спамерская задачка? В принципе можно и без БД решить, довольно простым способом, но хотелось бы знать зачем такое счастье понадобилось?
Значиться так....
1. БД не очень годиться по нескольким причинам, это не разовая поделушка, это должен быть tools. Причем желательно совершенно ни от чего не зависящий.
2. Это имеет отношение к спаму, но очень косвенное.
3. Это по сути анализатор логов системы, там критериев значительно больше, надо просто собрать события одного порядка и раскидать по разным таскам для анализа. Одно из событий таки получение мыла, каждое событие имеет нечто типа
usersub_module:{0,255}):module:domain
Ну вообщем как-то так.или примерно так...просто все значительно более запущено и стращно
4. Анализатор запускается раз в сутки, Во врем One night process.
Формат в котором это будет выдано не важен, например туча файлов, имена которых разбито на критерии, или просто 1 файл типа INI, или просто файл в которм события 1 группы идут подряд... воообщем не важно...
Для тех кто не любит спамеров. Спам победить не удасться, спам надо просто принять как должное и организовывать грамотные фильтры, при наличии примерно 17 почтовых ящиков, получаю не более 4 сообщений в сутки со спамом. Провайдеры стараютсю, мои фильтры отсеивают еще 3 мессаги гарантировано, при этом спам читаю, очень пользительно перед сном знать на чем народ хочет денег делать. Это по детству такой максимализм по отношению к спаму.
Готов выдать все свои ящики кроме 2 в открытое пользование, даже если провайдеры будут поставлять 200-300 сообщений на каждый ящик ко мне на глаза попадет не более 100 месаг, остальное ляжет в папку для спама, скажу сразу оменно благодаря грамотному построению правил и такому колличеству ящиков спама у меня и нет
Кстати если надо будет, то можно всех заставить писать куски качественного рассыльщика спама, но никто толком и не поймет что в итоге получиться. потому как разбить задачу грамотно на части и запостить в разных ветках сообщения причем разных людей ничего не стоит
Ну а тема закрыта, ни одного толкового решения не было предложено... ну разве что БД но оно не очень годиться..
Здравствуйте, GSL, Вы писали:
GSL>Задачка реальная и с виду простая.
GSL>Итак есть файл в нем есть мылы. Повторяемость 15%. Надо рассортировать все по доменам и отсечь думбликаты. Ну дубликаты это дело десятое, потому как всего 15%. Порядок адрресов совершенно произвольный. А вот рассортировать по доменам надо как можно более быстро. Количество доменов может измеряться цифрой с 6 нулями
GSL>С виду все тривиально и не этюдно. GSL>А вот теперь этюдная загвоздка исходный файл ( или набор файлов ) от 25-50 гигабайт, и не содержит лишней информации кроме адрессов,
GSL>Память на машине скажем 512мега, на винте можно брать до 200 гига ( но лучще бы обойтись не более чем 25-50 гигов. )
GSL>Какме есть предложения. GSL>Выбор средств не ограничен, можете прост в текстовм редакторе дать последовательность кнопок.
сортировка слиянием не подойдет ? Хотя вроде есть виды сортировок специально для строк вроде как с линейным временем но подойдут ли они в случае такого объема? Вообщем чти Седжвика или Кнута.
Здравствуйте, GSL, Вы писали:
GSL>Задачка реальная и с виду простая.
GSL>Итак есть файл в нем есть мылы. Повторяемость 15%. Надо рассортировать все по доменам и отсечь думбликаты. Ну дубликаты это дело десятое, потому как всего 15%. Порядок адрресов совершенно произвольный. А вот рассортировать по доменам надо как можно более быстро. Количество доменов может измеряться цифрой с 6 нулями
GSL>С виду все тривиально и не этюдно. GSL>А вот теперь этюдная загвоздка исходный файл ( или набор файлов ) от 25-50 гигабайт, и не содержит лишней информации кроме адрессов,
GSL>Память на машине скажем 512мега, на винте можно брать до 200 гига ( но лучще бы обойтись не более чем 25-50 гигов. )
GSL>Какме есть предложения. GSL>Выбор средств не ограничен, можете прост в текстовм редакторе дать последовательность кнопок.
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, GSL, Вы писали:
GSL>>Задачка реальная и с виду простая.
GSL>>Итак есть файл в нем есть мылы. Повторяемость 15%. Надо рассортировать все по доменам и отсечь думбликаты. Ну дубликаты это дело десятое, потому как всего 15%. Порядок адрресов совершенно произвольный. А вот рассортировать по доменам надо как можно более быстро. Количество доменов может измеряться цифрой с 6 нулями
GSL>>С виду все тривиально и не этюдно. GSL>>А вот теперь этюдная загвоздка исходный файл ( или набор файлов ) от 25-50 гигабайт, и не содержит лишней информации кроме адрессов,
GSL>>Память на машине скажем 512мега, на винте можно брать до 200 гига ( но лучще бы обойтись не более чем 25-50 гигов. )
GSL>>Какме есть предложения. GSL>>Выбор средств не ограничен, можете прост в текстовм редакторе дать последовательность кнопок.
А>Для начала можно отсортировать по алфавиту, то есть раскидать по 26 файлам — далее каждый файлик сортировать отделньо, там уже скорее всего и qsort() подойдет. Повторы можно убить после сортировки за линейное время.
Так не получиться, придеться разбивать на много файлов.
А>З.Ы. А можно за помощь попросить убрать мои мылы из базы, а?
Можно конечно как только такой файл будет, только там их нет
там корпоративные мылы достаточно узкого направления.
Здравствуйте, GarryIV, Вы писали:
GSL>>Какме есть предложения. GSL>>Выбор средств не ограничен, можете прост в текстовм редакторе дать последовательность кнопок.
GIV>Это подойдет? http://www.getinfo.ru/article543_1.html#c13
За русский хеш спасиб, но оно все равно в памяти не поместиться. надо алгоритмы порциальной обработки данных.
Здравствуйте, GSL, Вы писали:
Я в чём собственно цель глобальная состоит? В какой форме хочется получить файлы рассортированный по доманам?
Казалось бы, берёшь БД и льёшь в неё записи по одной, одно поле -- домен, другое -- юзер. Дальше всё средствами БД имеешь
А что за шпионско-спамерская задачка? В принципе можно и без БД решить, довольно простым способом, но хотелось бы знать зачем такое счастье понадобилось?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, GSL, Вы писали:
GSL>Кстати если надо будет, то можно всех заставить писать куски качественного рассыльщика спама, но никто толком и не поймет что в итоге получиться. потому как разбить задачу грамотно на части и запостить в разных ветках сообщения причем разных людей ничего не стоит
Ну бог с ним со всем.
Если БД не подходит, хотя они именно для этого и делаются в принципе, то можно привинтить самописную.
Винтить предлагаю так:
1) Организовать подсчёт хэш-ключа по домену.
2) Поднастроить длину ключа, так чтобы разных ключей получалось не слишком много, а информации на один ключ приходилось тоже не черезмерно. Я так понимаю, что длина бит в 12 — 13 как раз для твоей задачи.
3) Потом читаешь свой мега-файл, и раскидываешь записи по файлам поменьше, выбирая их имена по хэш-функции.
Получаешь каталог с примерно 4000 файлов вида F9A.tmp
4) Сортируешь каждый из файлов уже в памяти, ну и потом делаешь что придумаешь -- например чливаешь всё это обратно в один большой пребольшой, или ещё как-нибудь офолрмляешь результат
Вот такой вот предлагаю алгоритм.
Вроде должно сработать
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, GSL, Вы писали:
GSL>>Кстати если надо будет, то можно всех заставить писать куски качественного рассыльщика спама, но никто толком и не поймет что в итоге получиться. потому как разбить задачу грамотно на части и запостить в разных ветках сообщения причем разных людей ничего не стоит
E>Ну бог с ним со всем. E>Если БД не подходит, хотя они именно для этого и делаются в принципе, то можно привинтить самописную.
E>Винтить предлагаю так:
E>1) Организовать подсчёт хэш-ключа по домену. E>2) Поднастроить длину ключа, так чтобы разных ключей получалось не слишком много, а информации на один ключ приходилось тоже не черезмерно. Я так понимаю, что длина бит в 12 — 13 как раз для твоей задачи.
E>3) Потом читаешь свой мега-файл, и раскидываешь записи по файлам поменьше, выбирая их имена по хэш-функции. E>Получаешь каталог с примерно 4000 файлов вида F9A.tmp
E>4) Сортируешь каждый из файлов уже в памяти, ну и потом делаешь что придумаешь -- например чливаешь всё это обратно в один большой пребольшой, или ещё как-нибудь офолрмляешь результат
E>Вот такой вот предлагаю алгоритм.
E>Вроде должно сработать
Собственно оно так примерно и работает, только польщует по стандартную реализацию хеш таблицы.
Читает пока более или менее есть память, потом пишет уже осортированное и немного ужа тое в файл,
очистка памяти и все по новой, потом вторая тулса читает уже эти файлы и лепит им подобные но уже на основе того что исходные отсортированы. в итоге имеем отсортированный файл.
Если интересно то в рабочем состоянии система за сутки генрит лог не более чем 50 мегабайт, просто ловим уже 2 недели необъяснимый баг. пришлось включить слив расширенного лога из более чем 60 различных независимых модулей, а с самого начала не было предусмотрено писать логи в свои файлы, а пишется через общий тунелинг.. ( вообщем нажили себе гимор )
Но предложенный метод натолкнул на интереснейшую идею... кроме того что он сам по себе быстрее, так мы его тут чичас еще раз в 10 разгоним по скорости....будет просто улетно.. хотя будет теперь 2 разных анализатора...
Здравствуйте, GSL, Вы писали:
GSL>Задачка реальная и с виду простая. GSL>Итак есть файл в нем есть мылы. Повторяемость 15%. Надо рассортировать все по доменам и отсечь думбликаты. Ну дубликаты это дело десятое, потому как всего 15%. Порядок адрресов совершенно произвольный. А вот рассортировать по доменам надо как можно более быстро. Количество доменов может измеряться цифрой с 6 нулями GSL>А вот теперь этюдная загвоздка исходный файл ( или набор файлов ) от 25-50 гигабайт, и не содержит лишней информации кроме адрессов, GSL>Память на машине скажем 512мега, на винте можно брать до 200 гига ( но лучще бы обойтись не более чем 25-50 гигов. )
Можно построить PATRICIA trie по строкам доменов. В этом случае дерево строится в оперативке и на каждый узел приходится 16 байт (2 пойнтера + skip + птр на строку). В то же время строки (уже только уникальные!) хранятся либо в отображаемом в память файле, либо в ОЗУ (если хватает). В принципе, скорость доступа к строкам не так критична, как к узлам. На каждую уникальную строку домена приходится один узел. Итак, требования к памяти минимальны. Добавление и поиск нодов в цифровом дереве происходит за время O(logN). Затем построенную патрицию можно использовать для сортировки по доменам во втором проходе по мега-файлу, ибо в дереве уже все строки упорядочены. Подробности устройства алгоритма см. Кнут, Искусство программирования, т.3
Здравствуйте, GSL, Вы писали:
GSL>Задачка реальная и с виду простая.
Вот тебе бредовый вариант:
1) Открываешь файл с адресами и создаёшь его отображение в память (filemapping)
2) Читаешь очередной адрес
3) Создаёшь файл с таким именем
4) Если ещё остались адреса в файле, goto п. 2
5) Закрываешь отображение и файл с адресами
Далее перебираешь созданные файлы (для ускорения используешь NtQueryDirectoryFile вместо FindFirst/FindNext):
7) Читаешь имя файла. Оно должно быть вида [логин]@[домен]
8) Создаёшь или открываешь файл с именем [домен]
9) Дописываешь туда [логин]@[домен]
10) Закрываешь файл с именем [домен]
11) Удаляешь файл с именем [логин]@[домен]
12) Если ещё остались файлы, goto п. 7
Здесь файловая система работает как std::set, на который не расходуется драгоценная память.
Здравствуйте, GSL, Вы писали:
GSL>Выбор средств не ограничен, можете прост в текстовм редакторе дать последовательность кнопок.
1) для каждой записи вида Name@Domain открываем файл .../temp/Domain и дописываем туда строку Name
2) сортируем список файлов temp/* и склеиваем их содержимое в один файл
На шелле (даже на бат-файлах) можно написать, правда, рожать будет очень долго...
Здравствуйте, Olegator, Вы писали:
O>Здравствуйте, GSL, Вы писали:
GSL>>Задачка реальная и с виду простая.
O>Вот тебе бредовый вариант:
O>1) Открываешь файл с адресами и создаёшь его отображение в память (filemapping) O>2) Читаешь очередной адрес O>3) Создаёшь файл с таким именем O>4) Если ещё остались адреса в файле, goto п. 2 O>5) Закрываешь отображение и файл с адресами
O>Далее перебираешь созданные файлы (для ускорения используешь NtQueryDirectoryFile вместо FindFirst/FindNext):
O>7) Читаешь имя файла. Оно должно быть вида [логин]@[домен] O>8) Создаёшь или открываешь файл с именем [домен] O>9) Дописываешь туда [логин]@[домен] O>10) Закрываешь файл с именем [домен] O>11) Удаляешь файл с именем [логин]@[домен] O>12) Если ещё остались файлы, goto п. 7
O>Здесь файловая система работает как std::set, на который не расходуется драгоценная память.
не совсем понял, но пробовали делать по другому, просто читали файл пока есть память и дописывали в файлы domain или создавали его. Но работало это жутко медленно особенно по достижении 10 000 доменов.
Здравствуйте, 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 этапе работы, Второй этап достаточно медленный но зато совсем не ест память
С деревом я почитаю но, что-то мне говорить что во втором этапе у нас будут проблемы, потому как список отсортированных доменов не дает нам ничего при втором проходе для постоения окончательного списка..потому как т.е. я не вижу как можно используя память только для хранения любого дерева остортирровать по сути дела поток. потому как мега файл по сути своей не что иное как предсказуемый поток данных.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, GSL, Вы писали:
GSL>>Выбор средств не ограничен, можете прост в текстовм редакторе дать последовательность кнопок.
К>1) для каждой записи вида Name@Domain открываем файл .../temp/Domain и дописываем туда строку Name К>2) сортируем список файлов temp/* и склеиваем их содержимое в один файл К>На шелле (даже на бат-файлах) можно написать, правда, рожать будет очень долго...
Это первое решение которое пришло в голову, количество файлов может начать измеряться сотнями тысяч или более да и медленно это оказалось, открытие и закрытие файлов это очень медленно... именно эти 2 операции...так 100 000 файлов по одной строке записать в файл занимает на PC кажеться 10 минут
Здравствуйте, 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 проходов ленточной сортировки мы их объединим в единый сортированный блок.
... << RSDN@Work 1.1.3 stable >>
Ennio Morricone — Chi Mai
Standarts are great, everyone should have one!
Re[2]: Требуеться этюдное решение.
От:
Аноним
Дата:
12.07.05 09:28
Оценка:
DK>ИМХО, одним из быстрых вариантов будет простая реализация сортировки Фон-Неймана (aka ленточной) с предварительным проходом по исходным данным. Сперва из исходного файла (F1) читаем сколько влезет в память, сортируем чем-нибудь достаточно быстрым в памяти, кидаем результат в промежуточный файл (F2), и так до конца F1. Теперь у нас в исходном файле где-то 50-100 посортированных блоков, и за 7 проходов ленточной сортировки мы их объединим в единый сортированный блок.
А при таком количестве блоков лучше просто запихать их все в разные файлы, а далее слить их все сразу, тоже ИМХО
ленточной сортировки мы их объединим в единый сортированный блок.
А>А при таком количестве блоков лучше просто запихать их все в разные файлы, а далее слить их все сразу, тоже ИМХО
1) Я не знаю какая именно там файловая система.
2) Писать слияние одновременно 100 файлов — весьма непростая задача. Тут и очередь с приоритетами, и много всяких ньюансов....
3) ИМХО Есди операция разовая — оверхед (временнной, не синтаксический ) не столь критичен, если операция частая — скорее всего изменения будут добавляться сперва в конец файла, вряд ли их будет больше 500МБ за раз — при повторе операции после предварительной сортировки у нас будет всего 2-3-4 монотонных последовательности, так что нам потребуется 1-2 прохода для достижения полного порядка.
... << RSDN@Work 1.1.3 stable >>
Altan — Mazurka
Standarts are great, everyone should have one!
Здравствуйте, Аноним, Вы писали:
А>А чем дело то закончилось ?
Дело закончилось очень просто...
Написал примерно то что тут назвали ленточной сортировкой...
отсеили логи нашли баг, закрыли тему
тут меня еще обвиняли в спамерстве, вообщем эта задача была не спамерскакая, хотя спамерские задачки тоже есть но меня тут сразу закроют, а жаль иногда бывает очень забавно и интересно...
Re[6]: Требуеться этюдное решение.
От:
Аноним
Дата:
16.05.06 12:18
Оценка:
Здравствуйте, GSL, Вы писали:
GSL>тут меня еще обвиняли в спамерстве, вообщем эта задача была не спамерскакая, хотя спамерские задачки тоже есть но меня тут сразу закроют, а жаль иногда бывает очень забавно и интересно...
sub_module:{0,255}):module:domain 
Перекуём баги на фичи!
