Очередь URL-адресов сканера или список хэшей?

Я переписываю часть приложения для картографирования сайтов Delphi 6, которое я написал ранее. Приложение сканирует один сайт.

Мне нужно управлять двумя аспектами этого:

  1. Очередь URL-адресов для сканирования в порядке поступления.
  2. Отсканированный список URL-адресов, чтобы ссылки с новой страницы не добавлялись в очередь, если они уже были посещены. Этот список нужно будет поискать.

Раньше это делалось с помощью TList и StringList соответственно. Очевидно, что их производительность снижается на сайтах с тысячами ссылок.

Мой вопрос: что следует использовать для этих очередей/списков, чтобы обеспечить наилучшую производительность? У меня мало опыта работы с хэшами.


queue web-crawler delphi hash
person MikeD    schedule 28.07.2011    source источник
comment
Один сайт с тысячами страниц? Это большой сайт! Вы переписываете в Delphi 6 или в более поздней версии Delphi? Если это более поздняя версия, вы можете попробовать TDictionary для # 2, который, я считаю, быстрее. Другие, более информированные, несомненно, разъяснят.   -  person RobertFrank    schedule 28.07.2011
comment
Тысячи строк в TStringlist звучат не очень - отсортирован ли список строк (iirc помогает сократить время поиска)?   -  person mjn    schedule 28.07.2011
comment
О, и, возможно, вам следует использовать потоки для параллельного перехода по нескольким ссылкам. Тогда список фильтров посещенных страниц должен быть только одним экземпляром (очевидно).   -  person mjn    schedule 28.07.2011
comment
Действительно ли это должна быть очередь FIFO для URL-адресов? Потому что это сильно ограничивает варианты или вам приходится прилагать дополнительные усилия, чтобы следить за их порядком.   -  person ain    schedule 28.07.2011
comment
Очередь, вероятно, не должна быть FIFO. Новый код будет использовать потоки, безопасно обращаясь к единому списку URL-адресов в очереди и посещенных URL-адресов. Некоторые из сайтов, которые люди пытаются составить карту сайта, имеют 40 000 страниц (продукты и тому подобное). Да, заморочено, чтобы сайтмап это, но хотят. ржу не могу   -  person MikeD    schedule 28.07.2011
comment
Я предлагаю вам изучить внутренности TMemIniFile для THashedStringList   -  person Premature Optimization    schedule 30.07.2011

Ответы (2)


arrow_upward
5
arrow_downward

ИМХО хеши будут лучшим кандидатом для таких списков.

В Delphi 6 вы можете использовать класс THashedStringList, доступный в модуле IniFiles. Это будет быстрее, чем TStringList.

Обратите внимание, что если вы используете отсортированный TStringList, вы можете использовать гораздо более быстрый бинарный поиск, достаточно быстрый для вашей цели.

Чтобы получить более полную информацию, вы можете взглянуть на эти библиотеки OpenSource:

  • TSynBigTableMetaData для хранения любых данных о количестве ( в вашем случае HTML-страницы), связанные с полями метаданных - у вас есть индексы для полей метаданных, поэтому добавление и поиск будут быстрыми;
  • Динамический массив с именем, использующим хэш, можно использовать в Delphi 6 с TDynArrayHashed.

Обновление:

Просто трюк для сортировки URI, если вы используете отсортированный TStringList: вам лучше использовать функцию обратной сортировки, т.е. сравнивать текст URI, начиная с конца строки, а не с начала, поскольку в URI изменение происходит в суффиксе а не в префиксе. Вы ускорите сортировку/бинарный поиск.

person Arnaud Bouchez    schedule 28.07.2011
comment
TSynBigTableMetaData выглядит довольно интересно, но я нигде не смог найти никакой документации, только случайные примеры кода на форуме. - person MikeD; 28.07.2011
comment
@Jambog Устройство самодокументировано. Все классы и методы имеют точное описание в интерфейсной части. Взгляните на эти описания, и вы найдете выход. Вы можете использовать наш инструмент SynProject для создания документации в формате pdf из комментариев, если вам это нужно. - person Arnaud Bouchez; 28.07.2011
comment
Арно, Synopse Big Table выглядит действительно классным фрагментом кода, однако я думаю, что вы разочарованы, если думаете, что он самодокументируемый. В качестве только одного примера, это функция поиска, но образцы кода на форумах показывают зацикливание, и даже они загадочны с такими вещами, как for i := n-200 to n-1 do. - person MikeD; 29.07.2011
comment
Конечно, общая документация должна быть написана. О методах поиска и примере исходного кода взгляните на функции и методы эталонного тестирования и регрессионного тестирования, доступные в модуле, в функции эталонного тестирования TestBigTable и классе регрессии TTestBigTable. Стоит взглянуть. n-200 to n-1 - это просто цикл для многократного тестирования любой проблемы регрессии. - person Arnaud Bouchez; 29.07.2011
comment
@Jambog, не забудьте принять ответы, которые вам как-то помогли. Here is как это сделать;) - person TLama; 24.01.2012

arrow_upward
3
arrow_downward

Работа Trie отлично подходит для хранения больших (уникальных) текстовых блоков и сохранения высокой скорости поиска. Некоторое время назад я написал о них быструю и грязную статью для Pascal Gamer: http://www.pascalgamer.com/issue_details.php?i=1, который, возможно, стоит прочитать.

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

Хорошая вещь в Trie, вы можете выполнять частичное сопоставление, обратный поиск, пропускать поиск и т. д. без каких-либо проблем. Нижние стороны; вы не можете легко дублировать записи, они занимают больше места в МЕНЬШИХ наборах данных, и в зависимости от вашей реализации переключение с учетом регистра может быть «интересным».

Используйте эту концепцию изо дня в день для миллионов записей без проблем и с высокой скоростью сохранения.

person jdarling    schedule 28.07.2011
comment
хэши обычно быстрее, чем попытки, потому что они O (1) по дизайну, если хэш-функция хорошо определена - person Arnaud Bouchez; 28.07.2011
comment
В зависимости от вашей цели и вашей хэш-функции они могут быть быстрее. Конечно, вам все еще нужно учитывать накладные расходы на хэш. Преимущество, которое я вижу в Trie над Hash, связано с тем, что я сказал выше; Частичные совпадения, обратный поиск, пропуск поиска и т. д. IE, где вы хотите сделать больше, чем просто сопоставить 1: 1 (обычно для сопоставления URL) - person jdarling; 29.07.2011
comment
Вы совершенно правы. Но, как вы сказали, вопрос ОП был о совпадении 1: 1. В этом случае хэши быстрее, чем попытки. Что касается самой хеш-функции, я нашел strchr.com/hash_functions достойным прочтения. И использовал оптимизированную конвейерную crc32 в качестве хеш-функции в моих библиотеках при хэшировании некоторого текста. - person Arnaud Bouchez; 29.07.2011
comment
Спасибо за ссылку, ее у меня еще не было в моем Diigo :). Моим главным справочником по Хэшу по-прежнему является книга Джулиана Бакнелла «Томы Дельфи: Алгоритмы и структуры данных», которую можно всегда иметь под рукой даже сегодня. - person jdarling; 29.07.2011
comment
Книгу Джулиана действительно нужно читать и понимать. О функции хэширования было представлено лишь несколько. - person Arnaud Bouchez; 30.07.2011