Вопрос по эффективности сортировки по питону - PullRequest
1 голос
/ 17 июня 2009

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

Использование будет что-то вроде

./find.py  LinkThatStartsWithB

Таким образом, он будет переходить на веб-страницу, связанную с буквой B. Мои вопросы: какой самый эффективный / самый умный способ использовать ввод пользователя и перейти на веб-страницу?

Сначала я думал о том, чтобы использовать список и затем получить первую букву слова и использовать числовой идентификатор, чтобы указать, куда идти в индексе списка.

(A = 1, B = 2 ...) Пример кода:

#Use base url as starting point then add extension on end.
Base_URL = "http://www.website.com/"

#Use list index as representation of letter
Alphabetic_Urls = [
       "/extensionA.html",
       "/extensionB.html",
       "/extensionC.html",
       ]

Или лучше сделать словарь?

Спасибо

Ответы [ 5 ]

3 голосов
/ 17 июня 2009

Как вы получаете этот список URL-адресов?

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

for link in mysite.getallLinks():
    if link[0] == firstletter:
        print link

Если вы собираетесь выполнять несколько поисков (а не только один параметр командной строки), , тогда , возможно, стоит создать словарь, используя что-то вроде:

import collections
d=collections.defaultdict(list)
for link in mysite.getallLinks():
    d[link[0]].append(link)             # Dict of first letter -> list of links

# Print all links starting with firstletter
for link in d[firstletter]:
    print link

Хотя с учетом того, что есть только 26 ведер, это не будет иметь большого значения.

1 голос
/ 17 июня 2009

Самый разумный способ - сделать код более простым для чтения. Когда у вас есть только 26 элементов в списке, кого волнует, какой алгоритм он использует для просмотра? Вы должны использовать что-то действительно, действительно глупое, чтобы это повлияло на производительность.

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

Если ваш пример действительно точен, разве вы не можете просто взять первую букву входной строки и предсказать URL из этого? ("/extension" + letter + ".html")

0 голосов
/ 18 июня 2009

Поскольку кажется, что вы говорите всего о 26 предметах, вам, вероятно, не нужно слишком беспокоиться об эффективности. Все, что вы придумали, должно быть достаточно быстрым.

В общем, я рекомендую использовать структуру данных, которая является наилучшим приближением вашей проблемной области. Например, похоже, что вы пытаетесь сопоставить буквы URL-адресам. Например, это URL-адрес "A" и URL-адрес "B". В этом случае структура данных отображения, подобная dict, звучит уместно:

html_files = {
    'a': '/extensionA.html',
    'b': '/extensionB.html',
    'c': '/extensionC.html',
}

Хотя в этом конкретном примере вы могли бы обмануть его и вообще пропустить структуру данных - '/extension%s.html' % letter.upper():)

0 голосов
/ 17 июня 2009

Словарь будет хорошим выбором, если у вас есть (и всегда будет) небольшое количество предметов. Если в будущем список URL-адресов будет расширяться, вы, вероятно, захотите отсортировать URL-адреса по их буквам, а затем сопоставить ввод с этим, а не жестко кодировать словарь для каждого.

0 голосов
/ 17 июня 2009

словарь! O (1)

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...