Eine Frage über die Python-Sortierung Effizienz

Question

In Ordnung, so mache ich eine Befehlszeile basierte Implementierung einer Website-Suchfunktion. Die Website enthält eine Liste aller benötigten Links in alphabetischer Reihenfolge.

Verwendung wäre so etwas wie

./find.py LinkThatStartsWithB 

So wäre es auf der Webseite mit dem Buchstaben B. zugeordnet navigieren Meine Fragen ist, was ist die effizienteste/klügste Weg, um die Eingabe durch den Benutzer zu bedienen und navigieren zur Webseite?

Was ich zuerst dachte, war etwas in der Art einer Liste zu verwenden und dann den ersten Buchstaben des Wortes zu bekommen und den numerischen Identifizierer zu verwenden, um zu sagen, wo im Listenindex zu gehen ist.

(A = 1, B = 2, ...) Beispielcode:

#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", 
     ] 

Oder wäre Wörterbuch eine bessere Wette sein?

Danke

Answer 1

Wie erhalten Sie diese Liste von URLs?

Wenn Ihre Befehlszeilen-App die Website nach Links durchsucht und Sie nur nach einem einzelnen Element suchen, ist der Aufbau eines Wörterbuchs sinnlos. Es wird mindestens genauso lange dauern, um das Diktat zu erstellen, als es nur zu überprüfen, wie Sie gehen! zB nur die Suche wie:

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

Wenn Sie mehrere Such gehen zu tun (und nicht nur einen einzigen Kommandozeilenparameter), dann könnte es sich lohnen, den Aufbau eines Wörterbuchs mit so etwas wie:

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 

Obwohl es nur 26 Eimer gibt, wird es keinen großen Unterschied machen.

Answer 2

Wörterbuch! O (1)

Answer 3

Der klügste Weg hier wird sein, was den Code am einfachsten zu lesen macht. Wenn Sie nur 26 Elemente in einer Liste haben, wen interessiert es dann, welchen Algorithmus es verwendet, um durchzusehen? Sie müssten wirklich etwas verwenden, wirklich dumm, um es auf die Leistung auswirken.

Wenn Sie wirklich an der Leistung interessiert sind, müssten Sie verschiedene Optionen benchmarken. Wenn man nur die Komplexität betrachtet, wird nicht die ganze Geschichte erzählt, weil sie die beteiligten Faktoren verbirgt. Zum Beispiel beinhaltet eine Wörterbuchsuche das Berechnen des Hashs des Schlüssels, das Nachschlagen in Tabellen und dann das Überprüfen der Gleichheit. Bei kurzen Listen kann eine einfache lineare Suche manchmal effizienter sein, je nachdem, wie kostspielig der Hash-Algorithmus ist.

Wenn Ihr Beispiel jedoch sehr genau ist, können Sie nicht einfach den ersten Buchstaben der Eingabezeichenfolge verwenden und die URL daraus vorhersagen? ("/extension" + letter + ".html")

Answer 4

Wörterbuch wäre eine gute Wahl, wenn Sie eine kleine Anzahl von Gegenständen haben (und immer haben werden). Wenn die Liste der URLs in der Zukunft erweitert wird, werden Sie wahrscheinlich die URLs nach ihrem Buchstaben sortieren und dann die Eingabe mit dem vergleichen müssen, anstatt das Wörterbuch für jedes einzelne hart zu codieren.

Answer 5

Da es sich anhört, als würden Sie nur über 26 Artikel sprechen, müssen Sie sich wahrscheinlich nicht allzu viel Gedanken über Effizienz machen. Alles, was dir einfällt, sollte schnell genug sein.

Im Allgemeinen empfehle ich, die Datenstruktur zu verwenden, die die beste Annäherung an Ihre Problemdomäne darstellt. Zum Beispiel klingt es so, als würden Sie Buchstaben URLs zuordnen. Z. B. ist dies die "A" -URL und dies ist die "B" -URL. In diesem Fall ertönt eine Abbildungsdatenstruktur wie ein dict angebracht:

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

Obwohl in genau diesem Beispiel Sie es tatsächlich betrüge könnten und die Datenstruktur vollständig überspringen - '/extension%s.html' % letter.upper() :)