Längste Kette des letzten Wortes der Zeile/erstes Wort des nächsten

Question

Okay, also versuche ich aus einer Textdatei die längste Kette zu finden, in der das letzte Wort einer Zeile das erste Wort der nächsten ist (funktioniert gut für Gedichte)). Das Python-Skript, das ich bisher gemacht habe, funktioniert gut, dauert aber immer noch sehr lange. Ich bin kein Programmierer und habe wirklich keine Ahnung von Optimierung. Durchlaufe ich mehr Optionen als nötig? Wie kann ich die Zeit reduzieren, die benötigt wird, um einen längeren Text zu durchlaufen?

#!/usr/bin/python 
# -*- coding: utf-8 -*- 
import re 
import sys 

# Opening the source text 
with open("/text.txt") as g: 
    all_lines = g.readlines() 

def last_word(particular_line): 
    if particular_line != "\n": 
     particular_line = re.sub(ur'^\W*|\W*$', "",particular_line) 
     if len(particular_line) > 1: 
      return particular_line.rsplit(None, 1)[-1].lower() 

def first_word(particular_line): 
    if particular_line != "\n": 
     particular_line = re.sub(ur'^\W*|\W*$', "",particular_line) 
     if len(particular_line) > 1: 
      return particular_line.split(None, 1)[0].lower() 

def chain(start, lines, depth): 
    remaining = list(lines) 
    del remaining[remaining.index(start)] 
    possibles = [x for x in remaining if (len(x.split()) > 2) and (first_word(x) == last_word(start))] 
    maxchain = [] 
    for c in possibles: 
     l = chain(c, remaining, depth) 
     sys.stdout.flush() 
     sys.stdout.write(str(depth) + " of " + str(len(all_lines)) + " \r") 
     sys.stdout.flush() 
     if len(l) > len(maxchain): 
      maxchain = l 
      depth = str(depth) + "." + str(len(maxchain)) 
    return [start] + maxchain 

#Start 
final_output = [] 

#Finding the longest chain 

for i in range (0, len(all_lines)): 
    x = chain(all_lines[i], all_lines, i) 
    if len(x) > 2: 
     final_output.append(x) 
final_output.sort(key = len) 

#Output on screen 
print "\n\n--------------------------------------------" 

if len(final_output) > 1: 
    print final_output[-1] 
else: 
    print "Nothing found" 

Answer 1

import itertools 
def matching_lines(line_pair): 
    return line_pair[0].split()[-1].lower() == line_pair[1].split()[0].lower() 

line_pairs = ((line,next_line) for line,next_line in itertools.izip(all_lines,all_lines[1:])) 
grouped_pairs = itertools.groupby(line_pairs,matching_lines) 
print max([len(list(y))+1 for x,y in grouped_pairs if x]) 

obwohl im nicht sicher, wird es schneller (aber ich denke, es wird sein, da es nur ein einziges Mal durchläuft und verwendet hauptsächlich builtins)

Answer 2

Ja, dieser Code hat die Komplexität der $ O (n^2) $. Das heißt, wenn Ihre Datei n Zeilen hat, dann ist die Anzahl der Iterationen, die Ihr Code ausführt, 1 * (n-1) für die erste Zeile, dann 1 * (n-2) für die zweite Zeile usw. mit n solchen Elementen . Für ein großes n ist dies relativ gleich $ n^2 $. Eigentlich gibt es einen Fehler in dem Code in dieser Zeile

del remaining[remaining.index(start)] 

wo Sie wahrscheinlich bedeutet dies auszuführen:

del remaining[:remaining.index(start)] 

(Bekanntmachung der ‚:‘ in den eckigen Klammern), die die Laufzeit (jetzt erweitert Sie haben (n-1) + (n-1) + .. + (n-1) = n * (n-1), was etwas größer ist als (n-1) + (n-2) + (n -3) ..).
Sie können den Code wie folgt optimieren: Beginne mit maxchainlen = 0, curchainlen = 0. Iteriere jetzt durch die Zeilen, vergleiche jedes Mal das erste Wort der aktuellen Zeile mit dem letzten Wort der vorherigen Zeile. Wenn sie übereinstimmen, erhöhen Sie curchainlen um 1. Wenn nicht, prüfen Sie, ob maxchainlen < curchainlen, wenn ja, maxchainlen = curchainlen zuweisen und curchainlen auf 0 setzen. Nachdem Sie die Zeilen durchlaufen haben, führen Sie diese Überprüfung erneut für maxchainlen durch. Beispiel:

lw = last_word(lines[0]) 
curchainlen = 0 
maxchainlen = 0 
for l in lines[2:]: 
    if lw = first_word(l): 
     curchainlen = curchainlen + 1 
    else: 
     maxchainlen = max(maxchainlen, curchainlen) 
     curchainlen = 0 
maxchainlen = max(maxchainlen, curchainlen) 
print(maxchainlen) 

Answer 3

Ich würde Splitting versuchen, diesen Job in zwei Phasen: zunächst finden die Ketten und miteinander vergleichen. Das vereinfacht den Code sehr. Da Ketten eine kleine Teilmenge aller Zeilen in der Datei darstellen, ist es schneller, sie zuerst zu finden und dann zu sortieren, als zu versuchen, das Ganze in einem großen Vorgang zu verarbeiten.

Der erste Teil des Problems ist viel einfacher, wenn Sie das Python yield Schlüsselwort verwenden, das return ähnlich ist, aber eine Funktion nicht beendet. Auf diese Weise können Sie Ihre Inhalte Zeile für Zeile durchlaufen und sie in kleinen Bissen verarbeiten, ohne dass Sie das Ganze jederzeit im Speicher halten müssen.

Hier ist eine grundlegende Möglichkeit, eine Datei eine Zeile nach der anderen zu greifen. Es nutzt yield die Ketten zu ziehen, wie es sie

def get_chains(*lines): 
    # these hold the last token and the 
    # members of this chain 
    previous = None 
    accum = [] 

    # walk through the lines, 
    # seeing if they can be added to the existing chain in `accum` 
    for each_line in lines: 
     # split the line into words, ignoring case & whitespace at the ends 
     pieces = each_line.lower().strip().split(" ") 
     if pieces[0] == previous: 
      # match? add to accum 
      accum.append(each_line) 
     else: 
      # no match? yield our chain 
      # if it is not empty 
      if accum: 
       yield accum 
       accum = [] 
     # update our idea of the last, and try the next line 
     previous = pieces[-1] 

    # at the end of the file we need to kick out anything 
    # still in the accumulator 
    if accum: 
     yield accum 

findet Wenn Sie diese Funktion eine Reihe von Linien füttern, wird es Ketten yield, wenn er sie findet und dann weiter. Wer auch immer ruft die Funktion kann die erarbeiteten Ketten erfassen und Dinge mit ihnen tun.

Sobald Sie die Ketten haben, ist es einfach, sie nach Länge zu sortieren und die längste auszuwählen. Da Python über eine integrierte Sortierung von Listen verfügt, müssen Sie nur eine Liste von Zeilenlängen-> Zeilenpaaren sammeln und sortieren.Die längste Zeile ist der letzte Eintrag: