セクシーな素数、「スローパイソン」、または私が誤解の壁と戦った方法

多くの開発者、特にシステムの設計に積極的に関与している開発者は、おそらく同様の状況に直面しているでしょう：同僚（開発者、プロジェクトデザイナー、セールスマンは関係ありません）は別の修正案を思いつきます：java、scalaなどですべてを書き直しましょう。 （お気に入りの代替）。



だから、私はもう一度、このような大きなプロジェクトのレガシーなアイデアに「失望」しました。 完全に書き換えるわけではなく、完全に書き換えるわけではありません（長期的には）。 一般に、python（およびモジュール式のティックルもあります）からscalaに切り替えます。 まだ新しいモジュールとサービスの開発、つまり 最下位の中間レベルおよび最近隣APIから始めます。 将来理解するように、それはまったく可能です。



人は開発プロジェクトではありません。たとえば、スタートアッププロジェクトと小さな営業担当者（特定のクライアント用）はすべて1つにまとめられています。



私は反対ではありません。 私は岩を尊重し、私自身の方法でそれを愛しています。 通常、私は一般的に新しいものすべてに開かれています。 したがって、たとえば、tickleとpython以外の場所では、他の言語のサービスまたはモジュールがあります。 そのため、たとえば、cvsからsvnに移動してからgitに移動しました（以前には、ずっと前にMS-VSSが一般的でした）。 本当にたくさんの例がありますが、一つはそれらを結び付けることです-それは開発者自身がそれをどのように決定したか、少なくとも承認したかです（それが集合体であるか、イニシエーターのグループがあったかは関係ありません）。 そして、ポイントは、一般的に、賛否両論です。



問題は、時折、合理的な議論のために、「開発者vs. 後者の「誰でも」は「問題」の知識のレベルに達しません。または、思考を伝えることは単に信じられないほど困難です-つまり、 異なる言語での会話のように。 それに、ソフトウェアアーキテクトのような人なら。 たとえば、顧客の突然の「需要」を発表した純粋な「セールスマン」などと「会話」がある場合はさらに悪い。



なぜ、誰もが、例えば、瓦職人に処方しないのか-どんな種類のヘラを使うべきなのか（例えば、10 mmの歯でもっと接着剤が必要になる、とにかく5 mmだとしましょう。そして、誰も湾曲した床や壁を気にしません 理論的には、ネジをハンマーで「ねじ込む」こともできますが、このためのドライバーがあり、後にドライバーが発明されました。 もちろん誇張しますが、時にはそのような不条理を本当に思い出させます。



これは、理想的には、ツールは開発者自身が選択するか、少なくともこの中に最後の言葉を入れるべきだということです-彼はこのツールで作業するか苦しむべきです。



しかし、何か気が散った。 私の具体的な議論の歴史では、スカラにとって、いつものように、人はほとんど何も持っていません。

開発者の可用性、既成の開発、洗練されデバッグされたシステムなど、私は長い間話をすることができました。 など しかし、彼の「Pythonは非常に遅い」と思った。 例として、彼はC、Clojure、Python、Ruby、Scalaなどのベンチマークの解釈-Stack Overflowへのリンクを投げました。これは最後まで読んでいませんでした（ほとんどプレーンテキストがあるため、すべてがpythonでそれほど悪いわけではありません） 。



これはまさにその意味でした（時間は秒単位で示されます）：

Sexy primes up to: 10k 20k 30k 100k --------------------------------------------------------- Python2.7 1.49 5.20 11.00 119 Scala2.9.2 0.93 1.41 2.73 20.84 Scala2.9.2 (optimized) 0.32 0.79 1.46 12.01
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

純粋に技術的な側面について彼と話してください。少しでも欲求はありません。 つまり メモリ割り当て/オブジェクトプール、GC（RPythonや独自のJit、MemMgr、GCを備えたRpyやpypyのようなクリーンなCPythonはありません）、ベンチマークを書いた人が行き過ぎた砂糖などについて



私の答えは、「このためにPythonで開発するのは好きではありません」と「少なくともスピード重視のコードはそういう風には書かない」というものでした。 私は少しcで、このベンチマークの例が人工的なものであることを自然に理解しています。 それは単に速度を測定することを意味します。 しかし、そのようなテストでCPythonに飛び込む痛みも私にはわかっています。

したがって、私はこの特定の例で、なぜこのテストが推奨されないのか、なぜ非常に客観的ではないのかなどを示しようとしました。



まず、このテストと、PyMNg（アセンブリ）、pypy2、pypy3、python3（同じ明白な理由で遅い）での実行結果（星印）を見せることから始めました。 鉄はもちろん異なりますが、順序はほぼ同じだと思います。

  Sexy primes up to: 10k 20k 30k 100k --------------------------------------------------------- PyMNg * 0.10 - - 2.46 pypy2 * 0.13 - - 5.44 pypy3 * 0.12 - - 5.69 --------------------------------------------------------- scala 2.10.4 (warmed up) * - - 6.57 scala 2.10.4 (cold) * - - 7.11 --------------------------------------------------------- Python3.4 * 1.41 - - 117.69 --------------------------------------------------------- Python2.7 1.49 5.20 11.00 119.00 Scala2.9.2 0.93 1.41 2.73 20.84 Scala2.9.2 (optimized) 0.32 0.79 1.46 12.01
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

原則として、人は自分のどこが間違っているのか、「Hello、world」などのベンチマークでは言語の選択が評価されなかったということを説明したかっただけなので、これ以上続行できません



したがって、タスクは、Pythonで「セクシーな」素数のペアを探すことです。 たくさんの高速。



デブリーフィングに興味がない人のために、githubのスクリプトへのリンクを試してみてください。



スポイラーの下での各オプションのパフォーマンス。

すべてのオプションで100K 。





max



オプションで始まる10M （このような配列では残りは遅い）





siev1



から始まる100M （同じ理由で）。





ところで、CPythonとPyPyの間のこのような分散は、人々がPyPyに切り替え、独自のロケーター、メモリマネージャー、GC、スタックレスなどのサードパーティモジュール（NumPyなど）を使用し、独自のアセンブリを作成する理由の1つであることがよくあります。 たとえば、実行速度が重要であり、ここにあるように、オブジェクトプールや複数の呼び出しなどを「積極的に」使用する場合などです。 また、私たちの場合、純粋なpythonから移行したのはかなり前のことです。 さらに多くのことがあり、ブレーキを掛けることで多面的操作や再カウントなどを行いました。 しかし、この動き自体はチーム全体の意図的な決定であり、上から「下がった」癖ではありませんでした。 興味があり、時間を見つけたら、これについての記事を埋め込むことを試みることができます。



この特定の「タスク」については、独自のCバインディングを記述したり、numpyなどのモジュールを使用したりできます。 私は、Pythonが内部でどのようにカチカチ音をたてているかを知っていれば、実際に「アルゴリズム的に」短時間で膝の上で解決できると同僚に納得させようとしました。



そのため、人に、人為的なテストではなく、手元のタスクが解決された場合にPythonが迅速に「実行」できることを証明し始めます。



オリジナルのスクリプトは、3番目のpythonの可読性とサポートのために私によってわずかに変更されました。私のサンプルスクリプトのこのオプションはorg



と呼ばれます。 _{（ただ、ここでは「xrange vs range」については必要ありません-違いは何であるかを完全に想像できます。ここでは特に3番目のpythonでは特に問題ではなく、反復は一種の「完了」です）}

 def is_prime(n): return all((n % i > 0) for i in range(2, n)) # def sexy_primes_below(n): # return [[j-6, j] for j in range(9, n+1) if is_prime(j) and is_prime(j-6)] def sexy_primes_below(n): l = [] for j in range(9, n+1): if is_prime(j-6) and is_prime(j): l.append([j-6, j]) return l
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

なぜなら 10Mでも100Kのセクシーペアしかありません。元のprimes_below



を直接のサイクルで自分のバージョンに変更しても、実行時間に大きな影響はありません。後続のバージョン（たとえば、ふるい）の変更の視覚的です。 少なくとも今のis_prime



、 is_prime



の実装におけるis_prime



全体。



1.最初に、元の（特にPyPy、まあ、または私たちのPyMNgのような「アセンブリ」）のような「砂糖」の使用は推奨されません。少なくともこの場合、速度の低下という形で戻ります。 これをmod1



バリアントとして書き直します

 def is_prime(n): i = 2 while True: if not n % i: return False i += 1 if i >= n: return True return True
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

少なくともPyPyではすでに高速です。 しかし、それはポイントではありません...



2.コードはすぐに明確になり、偶数（2つを除いて元々素数ではない）をチェックしない場合、 mod2



半分の速度で書き直せることがmod2



ます。

 def is_prime(n): if not n % 2: return False i = 3 while True: if n % i == 0: return False i += 2 if i >= n: return True return True
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

オリジナルで修正しましょうorg2



はorg2



と同じmod2



が、1行で "sugar"を使用しています。

 def is_prime(n): return n % 2 and all(n % i for i in range(3, n, 2))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

3.平方根の値の除数をチェックすると（丸めた値は正しいが、簡単になります-これは単なるテストです）、すべてをより速く行うことができ、 max



オプションを取得します。

 def is_prime(n): if not n & 1: return 0 i = 3 while 1: if not n % i: return 0 if i * i > n: return 1 i += 2 return 1
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

はるかに速く、本当に。



繰り返しますが、これを元のorgm



で編集します。

 def is_prime(n): #return ((n & 1) and all(n % i for i in range(3, int(math.sqrt(n))+1, 2))) return ((n & 1) and all(n % i for i in range(3, int(n**0.5)+1, 2)))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、少なくともPyPyでは再び遅くなります（ただし、部分的には、範囲内にある「ルート」の直接計算による可能性があります）。



4.ここで同僚の目が明るくなり、彼はその漫画（私の意見では「貪欲な金持ち」）のように、毛皮と7つの帽子について言います：「もっと速くできますか？」 なぜなら メモリの制限はありません（埋め込まれていないなど）。「半分」のふるい-半分のふるいを使用してすぐにやり直すことにしました。 さらに、Pythonでは、1つまたは2つのふるいを整理します。

まあ、すぐにsexy_primes_below



を変更して、ふるいを生成しますis_prime



を編集is_prime



ず、ループで呼び出さないように、すぐにsieve



を要求します。

siev1



オプションをsiev1



ます。

 def primes_sieve(n): """ temporary "half" mask sieve for primes < n (using bool) """ sieve = [True] * (n//2) for i in range(3, int(n**0.5)+1, 2): if sieve[i//2]: sieve[i*i//2::i] = [False] * ((ni*i-1)//(2*i)+1) return sieve def sexy_primes_below(n): l = [] sieve = primes_sieve(n+1) #is_prime = lambda j: (j & 1) and sieve[int(j/2)] for j in range(9, n+1): i = j-6 #if (i & 1) and is_prime(i) and is_prime(j): if (i & 1) and sieve[int(i/2)] and sieve[int(j/2)]: l.append([i, j]) return l
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このオプションは非常に高速であるため、たとえばPyPyでは、100Kでのオリジナルとほぼ同じ時間で100Mで出力されます。 つまり 2000倍以上の数をチェックし、性的に単純なカップルの数桁大きいリストを生成します。



すぐにsiev2



バリアントに書き直しましたsiev2



「ダム」なブール処理を思い出したからです。 つまり ブールフラグを0/1に置き換えます。 この例では、元の100Kの2倍の速さで100Mを実行しています！



5.バリアントosiev1



とosiev2



書いたので、将来、すべての数字のふるいを多くの短い数字に置き換えることができるようになりました。つまり、 ペアをインクリメンタルまたはブロック単位で検索できるようにします。



これを行うために、私はオフセットふるいをフラグではなく値自体を保存する直接ふるいに変更しました：

 sieve = [1, 1, 1, 0, 1, 1 ...]; #  3, 5, 7, 9, 11, 13 ... osieve = [3, 5, 7, 0, 11, 13, ...]; #  3, 5, 7, 9, 11, 13 ...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

オプションosiev1

 def primes_sieve(n): """ temporary odd direct sieve for primes < n """ sieve = list(range(3, n, 2)) l = len(sieve) for i in sieve: if i: f = (i*i-3) // 2 if f >= l: break sieve[f::i] = [0] * -((fl) // i) return sieve def sexy_primes_below(n): l = [] sieve = primes_sieve(n+1) #is_prime = lambda j: (j & 1) and sieve[int((j-2)/2)] for j in range(9, n+1): i = j-6 #if (i & 1) and is_prime(i) and is_prime(j): if (i & 1) and sieve[int((i-2)/2)] and sieve[int((j-2)/2)]: l.append([i, j]) return l
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

osiev2



の2番目のバージョンは、「少し」高速です。 ふるいをはるかに最適に開始します。

 def primes_sieve(n): """ temporary odd direct sieve for primes < n """ #sieve = list(range(3, n, 2)) l = ((n-3)//2) sieve = [-1] * l for k in range(3, n, 2): o = (k-3)//2 i = sieve[o] if i == -1: i = sieve[(k-3)//2] = k if i: f = (i*i-3) // 2 if f >= l: break sieve[f::i] = [0] * -((fl) // i) return sieve
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これらの2つの方法は、反復ふるいに変換できます（たとえば、10Kまたは100Kのブロックでペアを検索します）。 これにより、カウント時にメモリが大幅に節約されます。 たとえば、1Gまたは10Gの両方のosieveバージョンを試してみると、すぐにMemoryError例外が発生することがほぼ保証されています（まあ、またはあなたは豊富なPinocchioであり、多くのメモリと64ビットpythonがあります）。



私はブロックメソッドを終了しませんでした（スクリプトの例ではありません。突然誰かがしたい場合は「宿題」のようにしましょう）。 私の同僚はすでに悔い改め、賞賛に屈しており、少なくとも私の頭（およびチーム）がそのようなナンセンスで悩まないことを願っています。



元の100Kでは、後者の実行時間を計算できなくなりました-0.00ミル（実行時間の反復回数を10に増やすことでのみカウントしました）。



私がほとんど確信しているのは、scalaだけでなく、純粋なCでも速度をもう1桁上げることは不可能だということです。



スクリプト自体、実験する場合は、たとえば次のように助けを求めることができます。

 sexy-primes-test.py --help
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

どちらかと言えば、素数についてはwikihowで非常に詳細で非常に詳細です 。



労働者の要請で調査を追加しました...