最後の行の最後の単語/次の最初の単語の最長チェーン

Question

テキストファイルから、1行の最後の単語が次の最初の単語である最長の鎖を見つけることを試みています）。私が遠くまで持っていなければならないPythonスクリプトは、うまく動作しますが、依然として非常に長い時間がかかります。私はコーディングのエキスパートでなく、実際には最適化のアイデアはありません。必要以上に多くのオプションを実行していますか？ 長いテキストを実行するのにかかる時間を短縮するにはどうすればよいですか？

#!/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]) 

それが速くなります（しかし、私はそれが一度だけ反復し、それ以降も、ほとんどの組み込みコマンドを使用します考える）イムわからないが

Answer 2

はい、このコードは、の複雑さを持っています$ O（n^2）$。つまり、ファイルにn行がある場合、コードで実行される反復の量は、最初の行では1 *（n-1）、2番目の行では1 *（n-2） 。大きなnについては、これは$ n^2 $に比較的等しい。

del remaining[:remaining.index(start)] 

（気づく「：」角括弧内）のランタイムを拡張（今実際に、あなたはおそらくこれを実行することを意図し、このライン

del remaining[remaining.index(start)] 

のコードにバグがあります（n-1）+（n-1）+（n-1）= n *（n-1） -3）..）。
あなたは次のようにコードを最適化できます：maxchainlen = 0、curchainlen = 0.で始まります。現在の行の最初の単語と前の行の最後の単語を比較するたびに、繰り返します。一致する場合はcurchainlenを1増やしてください。一致しない場合はmaxchainlenが0であるかどうかを確認してください。maxchainlenの場合はmaxchainlen = curchainlen、init curchainlenを0に設定してください。例：

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

私は2つのフェーズにこの仕事を分割試してみた：最初のはチェーンを発見し、それらを比較します。これにより、コードが大幅に単純化されます。チェーンはファイル内のすべての行の小さなサブセットになるので、最初に見つけて並べ替えることは、全体を1つの大きなステップで処理しようとするよりも速くなります。

returnに似ていますが、機能を終了しないpython yieldキーワードを使用すると、問題の最初の部分がずっと簡単になります。これにより、一度に1つの行にコンテンツをループさせ、すべてのものを常にメモリに保持することなく、小さなビットで処理することができます。

ここでは、一度に1行ずつファイルを取得するための基本的な方法を示します。それはあなたがこの関数に行の文字列を供給するとき、それはそれらを見つけた場合はチェーンをyieldしてから続行します彼らに

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 

を見つけるとチェーンを引き出すためにyieldを使用しています。 は、とコールされます。この関数は、生成されたチェーンを捕捉し、そのチェーンで物事を行うことができます。

チェーンを取得したら、長さで並べ替えて最も長いものを簡単に選択できます。 Pythonにはリストソートが組み込まれているので、line-length - > lineのリストを集めてソートするだけです。最長行は最後の項目になります。

def longest_chain(filename): 

    with open (filename, 'rt') as file_handle: 
     # if you loop over an open file, you'll get 
     # back the lines in the file one at a time 
     incoming_chains = get_chains(*file_handle) 

     # collect the results into a list, keyed by lengths 
     all_chains = [(len(chain), chain) for chain in incoming_chains] 
     if all_chains: 
      all_chains.sort() 
      length, lines = all_chains[-1] 
      # found the longest chain 
      return "\n".join(lines) 
     else: 
      # for some reason there are no chains of connected lines 
      return []