検索効率を改善する方法

Question

私は少しのフィードバックが必要です。私のプロジェクトの1つとして、私はウィキペディアの6度を作成しています。それを短く保つために、私はすべてのデータのクリーニングを終え、それをMSSQLのテーブルに挿入しました。この時点まではすべてが正常に機能します。開始点から終了点までの接続を3度まで検索することができます。その後、処理に時間がかかります。コードを変更して効率を上げる方法を模索していました。私はこれにかなり新しいです、そして、それは私の最初の時間なので、最良の方法ではないかもしれません（私はおそらく私がそれをやったことができた最悪の方法を知っている）。

フィードバックは高く評価されます。

# -*- coding: utf-8 -*- 
""" 
Spyder Editor 

This is a temporary script file. 
""" 

import pyodbc 
import time 
#import re 

#rex = re.compile('(\(\'[a-zA-Z0-9]+\', \')(\w\\))') 
start_time = time.time() 


listinit = [] 
listseconditeration = [] 
listthirditeration = [] 
listfourthiteration = [] 
listfifthiteration = [] 
listsixthiteration = [] 

start = input ("Select start location :") 
finish = input ("Select finish location :") 
cnxn = pyodbc.connect('DRIVER={SQL Server};SERVER=johndoe-PC\SQLEXPRESS;DATABASE=master;UID=-----;PWD=------;Trusted_Connection=yes') 
cursor = cnxn.cursor() 
cursor.execute("select * from join_table where link1 like '%s'" % (start)) 

rows = cursor.fetchall() 
for row in rows: 
    listinit.append(row) 

for element in listinit: 
    var1 = str(element) 
    var1 = var1.replace("'","") 
    var1 = var1.replace("(","") 
    var1 = var1.replace(")","") 
    var1 = var1.replace(",","") 
    var1 = var1.replace(" ","") 
    var1 = var1.replace(start,"") 
    listseconditeration.append(var1) 


if (finish) in (listseconditeration): 
    print("one degree away") 
    print("%s minutes" % (time.time() - start_time)) 


for element in listseconditeration: 
    var2 = str(element) 

    cursor.execute("select * from join_table where link1 like '%s'" % (var2)) 
    rows1 = cursor.fetchall() 

    for row in rows1: 

     listthirditeration.append(row) 

     for element in listthirditeration: 
      var3 = str(element) 
      var3 = var3.replace("'","") 
      var3 = var3.replace("(","") 
      var3 = var3.replace(")","") 
      var3 = var3.replace(",","") 
      var3 = var3.replace(" ","") 
      var3 = var3.replace(var2, "") 
      listfourthiteration.append(var3) 



if (finish) in (listfourthiteration): 
    print("two degree away") 
    print("%s minutes" % (time.time() - start_time)) 



for element in listfourthiteration: 
    var4 = str(element) 

    cursor.execute("select * from join_table where link1 like '%s'" % (var4)) 
    rows2 = cursor.fetchall() 

    for row in rows2: 

     listfifthiteration.append(row) 

     for element in listfifthiteration: 
      var5 = str(element) 
      var5 = var5.replace("'","") 
      var5 = var5.replace("(","") 
      var5 = var5.replace(")","") 
      var5 = var5.replace(",","") 
      var5 = var5.replace(" ","") 
      var5 = var5.replace(var4, "") 
      listsixthiteration.append(var5) 
     print(row) 


if (finish) in (listsixthiteration): 
    print("three degree away") 

Answer 1

コードにいくつか問題があります。

最初の最も重要な問題は、コードが既に訪問された要素の再処理を妨げないことです。たとえば、シカゴ→秋をするとき、シカゴに戻ってループを起こすのを防ぐためのルーチンには何もありません。これにより、検索のサイズが非常に速くなります。

第二の問題は、コードが行うということです... ...

seen = set() 

... 

    for element in listthirditeration: 
     var3 = str(element) 
     var3 = var3.replace("'","") 
     var3 = var3.replace("(","") 
     var3 = var3.replace(")","") 
     var3 = var3.replace(",","") 
     var3 = var3.replace(" ","") 
     var3 = var3.replace(var2, "") 

     if var3 not in visited: 
      visited.add(var3) 
      listfourthiteration.append(var3) 

を他の類似したforループを繰り返す：

一つの解決策は、既に訪問されている代わりに、要素のセットを維持することです要素のリストのコピーを複製し、必要以上に長く保持します。最初に向かって端から端に向かって開始から1及び別、およびそれらをに会う持っている - そのような幅優先探索を行うときに使用する

cursor.execute("select * from join_table where link1 like '%s'" % (var2)) 

rows1 = cursor.fetchall()   # <<== fetchall() returns a list of results 

for row in rows1: 

    listthirditeration.append(row) # <<== this makes a second copy of the results 

トリックは、2回の検索を行うことです中間。