python - O（n ^ 2）を回避するために既存のリストを更新する

Question

（時間）の代わりにneighbor_trial(atomlist,trialatom)実行される新しい関数、を作成したいと思います。これは、前回の実行の結果を更新するだけで実現できます。は移動される原子であり、内の他のすべての原子は移動されません。O(n)neighbor(atomlist)O(n^2)neighbor(atomlist)trialatomatomlist

バックグラウンド：

atomlistAtomクラスのインスタンスのリストです。Atomオブジェクトには、がの最近傍であるatom1.is_neighbor(atom2)かどうかをチェックする関数があります。そうである場合は、リストに追加されます。アトムは最大12個の一意の最近傍のみを持つことができ、それ自体を含めることはできません。atom2atom1atom2atom1.nrst

問題：

neighboratom全員のリストを正しく更新しますnrstが、時間がかかります（何度も再実行する必要があります）。ただし、neighbor_trial正しく更新されません。すべてatomのnrstネイバーをチェックして、trialatom現在ネイバーであるかどうかを確認し、リストがワイプされたのnrstリストを再作成する必要があります。atomnrst

def neighbor(atomlist): 
    cdef int i, j
    for atom in atomlist:  
        atom.nrst=[]   #Unnecessarily deletes every atom's nrst! 
    for i in range(len(atomlist)):
        for j in range(i+1,len(atomlist)):
            if atomlist[i].is_neighbour(atomlist[j]):
                atomlist[i].nrst.append(atomlist[j])
                atomlist[j].nrst.append(atomlist[i])

def neighbor_trial(atomlist,trialatom):
    cdef int i, j
    redoo_list=[]
    for atom in trialatom.nrst:
        atom.nrst=[]            #Only trialatom and its neighbours' nrst list are wiped!
        redoo_list.append(atom)
    trialatom.nrst = []
    redoo_list.append(trialatom)
    for i in range(len(atomlist)):
        for j in range(len(redoo_list)):
            if atomlist[i] != redoo_list[j]:
                if atomlist[i].is_neighbour(redoo_list[j]):
                    redoo_list[j].nrst.append(atomlist[i])