Способы улучшения эффективности поиска

Question

Мне нужно немного обратной связи. Для одного из моих проектов я создаю шесть степеней википедии. Чтобы он был коротким, я закончил всю очистку данных и вставил ее в таблицу в MSSQL. До сих пор все работает нормально. Я могу найти соединение от начальной точки до конечной точки до третьей степени, тогда она просто слишком долго обрабатывается. Я искал способы изменить свой код для повышения эффективности. Я довольно новичок в этом, и это мой первый раз, поэтому, возможно, не лучший способ (хотя я знаю, что, вероятно, это был худший способ, который я мог бы сделать).

Любая обратная связь будет оценена по достоинству.

# -*- 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

Есть пара вопросов с кодом.

Первой и самой важной проблемой является то, что код не предотвращает повторные обработки элементов, которые уже были посещены. Например, когда вы делаете chicago-> autumn, в вашей рутине нет ничего, чтобы не возвращаться к chicago и делать петлю. Это приводит к тому, что размер вашего поиска растет очень быстро.

Одним из решений является поддержание набора вместо элементов, которые уже посетили:

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) 

... повторить для других подобных петель ...

Вторая проблема состоит в том, что код делает дублировать копии списков элементов и удерживать их дольше, чем необходимо.

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 

Хитрость использовать при выполнении поиска в ширину, как это, чтобы сделать две поисковые запросы - один от начала к концу, а другой от конца к началу, и они встретятся в средний.