11

コメントを使用すると、これが大幅に高速化されるのはなぜですか? ポップ、比較、および長さチェックは O(1) であるべきではありませんか? それは速度に大きな影響を与えますか？

#! /usr/bin/python                                                                
import math                                                                       

pmarbs = []                                                                       
pows = 49                                                                         
pmarbs.append("W")                                                                
inc = 1                                                                           
for i in range(pows):                                                             
    count = 0                                                                     
    j = 0                                                                         
    ran = int(pow(2, i))                                                          
    marker = len(pmarbs) - inc                                                    
    while (j < ran):                                                              
        #potential marble choice                                                  
        pot = pmarbs[marker - j]                                                  
        pot1 = pot + "W"                                                          
        pot2 = pot + "B"                                                          

        if (pot2.count('W') < pot2.count('B')) and (len(pot2) > (i+1)):           
            count += 1                                                            
        else:                                                                     
            pmarbs.append(pot2)                                                   

        pmarbs.append(pot1)                                                       
#        if(len(pmarbs[0]) < i):                                                  
#           pmarbs.pop(0)                                                         
#           marker -= 1                                                           
        j += 1                                                                    


    if (count != 0):                                                              
        print(count)                                                              
        print("length of pmarbs = %s" % len(pmarbs))

更新:コードが大幅に遅いことが私の質問だったので、質問を短くしています。実行時にコードが殺されることはあまり気にしませんでした。

4

2 に答える 2

10

list.pop(index)O(n)リストから値を削除した後、リスト内の他のすべての値のメモリ位置を1つ上にシフトする必要があるため、操作です。pop大きなリストを繰り返し呼び出すことは、計算サイクルを浪費する素晴らしい方法です。大きなリストの先頭から絶対に削除する必要がある場合は、 を何度も使用します。これによりcollections.deque、先頭への挿入と削除がはるかに高速になります。

len()リスト内のすべての値が隣り合わせにメモリに割り当てられているO(1) ことO(n)を確認すると、リストの合計の長さはテールのメモリ位置、つまりヘッドのメモリ位置になるためです。len()および同様の操作のパフォーマンスを気にしない場合は、リンクされたリストを使用して一定時間の挿入と削除を行うことlen()ができます。O(n)pop()O(1)O(n)

私が言ったことpop()はinsert()すべてappend()、通常はO(1).

私は最近、非常に大きなリスト (約 10,000,000 個の整数) から多くの要素を削除する必要がある問題に取り組みましたが、pop()何かを削除する必要があるたびに最初の愚かな実装を使用していましたが、まったく機能しないことが判明しましO(n)た。アルゴリズムの 1 サイクルでも実行しますn。

私の解決策は、すべての「削除された」要素のインデックスを保持するset()呼び出しを作成することでした。ignoreこれらをスキップすることを考える必要がないようにするためのヘルパー関数はほとんどなかったので、私のアルゴリズムはあまり醜くなりませんでした。最終的には、O(n)10,000回の反復ごとに1回のパスを実行して、すべての要素を削除し、ignore無視を再び空にすることでした。これにより、削除のために10,000分の1の作業を行うだけで済みながら、縮小するリストからパフォーマンスを向上させることができました。

また、メモリ エラーが発生するはずです。ハード ドライブよりもはるかに大きいリストを割り当てようとしているためです。

于 2013-10-18T05:03:08.600 に答える