Pythonループをスピードアップするには

Question

私はいくつかのサイトでいくつかの対立を見ていて、どれも解決策を教えてくれませんでした。 コードのこの作品は、実行に5秒以上かかります：

for i in xrange(100000000): 
    pass 

私は、整数最適化問題に取り組んでいると私はO（nはn個のログ）アルゴリズム編集を使用する必要があります：Oを（ここで、nはすべての行列の項目を表します。つまり、次のコードでは、n * m = 10000です。10000要素の100 * 100の行列の場合、25000000回程度の反復が行われます。。 そのコードは次のようにまとめることができます。

m = 100 
n = 100 
for i in xrange(m): 
    for j in xrange(n): 
    for i2 in xrange(i + 1, m): 
     for j2 in xrange(j + 1, n): 
     if myarray[i][j] == myarray[i2][j2] and myarray[i2][j] == myarray[i][j2]: 
      return [i, j], [i2, j2] 

は、私は、PythonであきらめるとJavaやCに戻るべきでしょうか？

私はPython 2.7で動作し、Psycoは利用できません。 PyPyはTkinterをサポートしていないのでTkinterを使っています。

だから、彼らはループの速度を改善するだろうか？他にも解決策はありますか？

Answer 1

申し訳ありませんが、最適化の問題ではありません。どちらの言語または実装を選択しても、このアルゴリズムは最悪および平均のケースではO(n*log n)ではありません。 how the Big-O notation worksを読んで、より良いアルゴリズムを開発したいと思うかもしれません。

Answer 2

Cythonプロジェクトを使用して、Pythonの表記法を使用し、速度をCにすることはできます。 最初のステップは、Cループにループを変換するために、次のようになります。それは、自動的にループで使用されるすべての変数を入力することによって行われます：

cdef int m = 100 
cdef int n = 100 
cdef int i, j, i2, j2 
for i in xrange(m): 
    for j in xrange(n): 
    for i2 in xrange(i + 1, m): 
     for j2 in xrange(j + 1, n): 

次の部分についてはそのmyarrayのは純粋になるならば、それも良いだろうCの配列、そして豊富なPythonのコンパイラも配列のアクセスもありません。あなたのpythonの配列では、あなたは（あなたがあなたの配列にダブルを持っている場合）ネイティブcomparaisonを行うことによって、豊かなcomparaisonを削除することができます

 cdef double a, b, c, d 
     a = myarray[i][j] 
     b = myarray[i2][j2] 
     c = myarray[i2][j] 
     d = myarray[i][j2] 

     if a == b and c == d: 
      return [i, j], [i2, j2] 

その後、yourfile.htmlが生成開く、最適化がcython -a yourfile.pyxを実行することによって起こっているかを見ることができます。 Cythonがあなたのコードをどのように最適化したかを見て、Pythonのオーバーヘッドを取り除きました。

Answer 3

極端なコーディングスタイルではありませんが、絶望的なコーディングが求められます。

try: 
    i,j,i2,j2 = ((i,j,i2,j2) 
     for i in xrange(m) 
      for j in xrange(n) 
      for i2 in xrange(i + 1, m) 
       for j2 in xrange(j + 1, n) 
       if myarray[i][j] == myarray[i2][j2] and 
        myarray[i2][j] == myarray[i][j2]).next() 
    return [i,j],[i2,j2] 
except StopIteration: 
    return None 

Answer 4

発電exprが動作しませんでした申し訳ありません：一つの大きなジェネレータ式にあなたのネストされたネストされたループを回してみてください。ここではまず、すべてのような値を集計して、長方形のグループを探し異なる方式である：

from collections import defaultdict 
from itertools import permutations 
def f3(myarray): 
    tally = defaultdict(list) 
    for i,row in enumerate(myarray): 
     for j,n in enumerate(row): 
      tally[n].append((i,j)) 

    # look for rectangular quads in each list 
    for k,v in tally.items(): 
     for quad in permutations(v,4): 
      # sort quad so that we can get rectangle corners 
      quad = sorted(quad) 
      (i1,j1),(i2,j2) = quad[0], quad[-1] 

      # slice out opposite corners to see if we have a rectangle 
      others = quad[1:3] 

      if [(i1,j2),(i2,j1)] == others: 
       return [i1,j1],[i2,j2] 

Answer 5

私はあなたのコード全体で数回見て、私は右のそれを得れば、あなたは、2つの異なるコーナーマーカーを使用して四角形をマーク。私の答えが本当にあなたの立場を明確にするためのコメントであれば申し訳ありません。

Answer-Part：： 適切なアルゴリズムをお探しの場合は、スキャンラインアルゴリズムを検討してください。私は "最大長方形ソリューション"の例としてhere @SOを見つけました。

私の質問はあなたが本当に探していますか？

1. forループジレンマ
2. あなたのアルゴリズム
3. 速いアルゴリズムのための最高の言語はパウロのこと が

が

私も指摘しなければならない長方形、およびソリューションの農産物を見つけるために、解決するための最良の方法Paulsはコーナーが同じ値でマークされていると仮定し、コーナーは2つの異なる値でマークされていると仮定しているため、異なる結果が得られます。

Iは醜いC & Pスクリプトでそれを説明するための時間と自由を取った： それは、2Dフィールドを作成することによって、両方のアルゴリズムを比較し にstring.lowercaseの文字とそれを充填し、文字を大文字にコーナーを回します。

from random import choice 
from string import lowercase 
from collections import defaultdict 
from itertools import permutations 
from copy import deepcopy 

m,n = 20, 20 
myarray = [[choice(lowercase) for x in xrange(m)] for y in xrange(n)] 

def markcorners(i,j,i2,j2): 
    myarray[i][j] = myarray[i][j].upper() 
    myarray[i2][j] = myarray[i2][j].upper() 
    myarray[i2][j2] = myarray[i2][j2].upper() 
    myarray[i][j2] = myarray[i][j2].upper() 

def printrect(): 
    for row in myarray: 
     print ''.join(row) 
    print '*'*m 

def paul_algo(): 
    tally = defaultdict(list) 
    for i,row in enumerate(myarray): 
     for j,n in enumerate(row): 
      tally[n].append((i,j)) 

    # look for rectangular quads in each list 
    for k,v in tally.items(): 
     for quad in permutations(v,4): 
      # sort quad so that we can get rectangle corners 
      quad = sorted(quad) 
      (i1,j1),(i2,j2) = quad[0], quad[-1] 

      # slice out opposite corners to see if we have a rectangle 
      others = quad[1:3] 

      if [(i1,j2),(i2,j1)] == others: 
       markcorners(i1,j1,i2,j2) 

def xavier_algo(): 
    for i in xrange(m): 
     for j in xrange(n): 
      for i2 in xrange(i + 1, m): 
       for j2 in xrange(j + 1, n): 
        if myarray[i][j] == myarray[i2][j2] and myarray[i2][j] == myarray[i][j2]: 
         markcorners(i,j,i2,j2) 

savearray = deepcopy(myarray) 
printrect() 

xavier_algo() 
printrect() 

myarray = deepcopy(savearray) 
paul_algo() 
printrect()