Итак есть файл в нем есть мылы. Повторяемость 15%. Надо рассортировать все по доменам и отсечь думбликаты. Ну дубликаты это дело десятое, потому как всего 15%. Порядок адрресов совершенно произвольный. А вот рассортировать по доменам надо как можно более быстро. Количество доменов может измеряться цифрой с 6 нулями
С виду все тривиально и не этюдно.
А вот теперь этюдная загвоздка исходный файл ( или набор файлов ) от 25-50 гигабайт, и не содержит лишней информации кроме адрессов,
Память на машине скажем 512мега, на винте можно брать до 200 гига ( но лучще бы обойтись не более чем 25-50 гигов. )
Какме есть предложения.
Выбор средств не ограничен, можете прост в текстовм редакторе дать последовательность кнопок.
Здравствуйте, 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() подойдет. Повторы можно убить после сортировки за линейное время.
З.Ы. А можно за помощь попросить убрать мои мылы из базы, а?
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, 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, Вы писали:
Я в чём собственно цель глобальная состоит? В какой форме хочется получить файлы рассортированный по доманам?
Казалось бы, берёшь БД и льёшь в неё записи по одной, одно поле -- домен, другое -- юзер. Дальше всё средствами БД имеешь
А что за шпионско-спамерская задачка? В принципе можно и без БД решить, довольно простым способом, но хотелось бы знать зачем такое счастье понадобилось?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, 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>Кстати если надо будет, то можно всех заставить писать куски качественного рассыльщика спама, но никто толком и не поймет что в итоге получиться. потому как разбить задачу грамотно на части и запостить в разных ветках сообщения причем разных людей ничего не стоит
Ну бог с ним со всем.
Если БД не подходит, хотя они именно для этого и делаются в принципе, то можно привинтить самописную.
Винтить предлагаю так:
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 минут
Перекуём баги на фичи!
