Crawler url queue или список хэшей? - PullRequest
Новая
       13

Crawler url queue или список хэшей?

6 голосов
/ 28 июля 2011

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

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

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

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

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

Ответы [ 2 ]

5 голосов
/ 28 июля 2011

IMHO хэши будут лучшим кандидатом для таких списков.

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

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

Для чего-то более полного, вы можете взглянуть на эти OpenSourceбиблиотеки:

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

Обновление:

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

3 голосов
/ 28 июля 2011

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

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

Приятно, что в Trie вы можете выполнять частичное сопоставление, обратный поиск, пропуск поиска и т.д. без каких-либо проблем.Вниз стороны есть;Вы не можете легко иметь повторяющиеся записи, они занимают больше места в наборах данных SMALLER, и в зависимости от вашей реализации переключение с учетом регистра может быть «интересным».

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

...