Ich arbeite an Allen Downeys Wie man wie ein Computerwissenschaftler denkt , und ich habe geschrieben, was ich für eine funktional korrekte Lösung zu Aufgabe 10.10 halte. Aber es dauerte etwas mehr als 10 Stunden (!) Zu laufen, also frage ich mich, ob ich eine wirklich offensichtliche und hilfreiche Optimierung vermisse.
Hier ist die Übung:
"Zwei Wörter" interlock ', wenn abwechselnde Buchstaben von jedem ein neues Wort bilden. Zum Beispiel,' schuh 'und' kalt 'verschachteln, um' geschult 'zu bilden. Schreibe ein Programm, das alle Paare von Wörtern findet, die ineinander greifen : Zählen Sie nicht alle Paare auf! "
(Für diese Wortlistenprobleme hat Downey eine Datei mit 113809 Wörtern geliefert. Wir können annehmen, dass diese Wörter in einer Liste sind, ein Wort pro Element in der Liste.)
Hier ist meine Lösung:
%Vor%Die Druckanweisungen sind nicht das Problem; Mein Programm hat nur 652 solcher Paare gefunden. Das Problem sind die verschachtelten Schleifen, oder? Ich meine, obwohl ich Listen durchblättere, die nur Wörter der gleichen Länge enthalten, gibt es (zum Beispiel) 21727 Wörter der Länge 7, was bedeutet, dass mein Programm über 400 Millionen "Stellwerke" prüfen muss, um zu sehen, ob sie " re actual words --- und das ist nur für die Länge-7 Wörter.
Dieser Code brauchte also 10 Stunden, um zu laufen (und fand keine Paare mit Worten der Länge 5 oder größer, falls Sie neugierig waren). Gibt es einen besseren Weg, um dieses Problem zu lösen?
Vielen Dank im Voraus für alle Einsichten. Ich bin mir bewusst, dass "vorzeitige Optimierung die Wurzel allen Übels ist" --- und vielleicht bin ich schon in diese Falle geraten --- aber im Allgemeinen, während ich normalerweise Code schreiben kann, der richtig läuft, habe ich oft Probleme mit dem Schreiben Code, der gut läuft.
Tu es umgekehrt: Durchsuche alle Wörter und teile sie in zwei Wörter auf, indem du die ungeraden und geraden Buchstaben nimmst. Dann schaue diese beiden Wörter im Wörterbuch nach.
Als Seitenknoten müssen die zwei Wörter, die ineinandergreifen, nicht unbedingt die gleiche Länge haben - die Längen können sich auch um 1 unterscheiden.
Einige (nicht getestete) Codes:
%Vor%Eine alternative Version:
%Vor%Auf meinem Rechner läuft das in 0,16 Sekunden und gibt 1254 Wörter zurück.
Bearbeiten: wie @ John Machin in Warum ist dieses Programm in Python schneller als Objective-C? dies kann durch die Lazy Execution weiter verbessert werden (führen Sie nur das zweite Slice durch, wenn das erste in einem gültigen Wort resultiert):
%Vor%Dies reduziert die Ausführungszeit um ein Drittel auf 0,104 Sekunden.
Eine wichtige Sache ist Ihre Funktion index : Es ist die Funktion, die mehr als jede Funktion ausführt. Wenn Sie den Index des gefundenen Wortes nicht benötigen, warum definieren Sie eine Funktion, um diesen Index zu finden?
if word1word2 in lst: ist genug anstelle von if index(lst, word1word2): .
Dasselbe gilt für if index(lst, word2word1): .
OK. Die Bisektion funktioniert wirklich schneller als die in -Syntax. Um die Geschwindigkeit ein wenig zu verbessern, schlage ich vor, die Funktion bisect_left direkt in der Funktion interlockings zu verwenden.
Zum Beispiel statt:
%Vor%Verwenden:
%Vor%Eine sehr leichte Verbesserung der Geschwindigkeit.
Tags und Links python