どちらがより速いです - 少数の要素を並べ替えるか、掛け合わせますか？

Question

読み通し Cactus Kevのポーカーハンド評価者, 、次の記述に気づきました。

最初は、評価者に渡す前に、最初に手を並べ替えることができると思っていました。しかし、ソートには時間がかかり、CPUサイクルのソーティングを無駄にしたくありませんでした。 5枚のカードが与えられた順序を気にしない方法が必要でした。
...
多くのことを考えた後、私は素数を使用するためにブレーンストーミングをしました。 13枚のカードランクのそれぞれにプライムナンバー値を割り当てます...このシステムの美しさは、手の各カードのランクのプライム値を掛けると、注文に関係なくユニークな製品を取得することです。 5枚のカードの。
...
乗算は、コンピューターが行うことができる最速の計算の1つであるため、評価前に各手を整理することを余儀なくされていた時間から数百ミリ秒を削りました。

私はこれを信じるのに苦労しています。

Cactus Kevは各カードを4バイトの整数として表し、呼び出して手を評価します eval_5cards( int c1, int c2, int c3, int c4, int c5 ). 。カードを1つのバイトとして、5バイトの配列としてポーカーハンドを表すことができます。この5バイト配列をソートしてユニークな手を取得することは、かなり速くなければなりません。彼のアプローチよりも速いですか？

彼の表現（カードは4バイトの整数として）を保持した場合はどうなりますか？ 5つの整数の配列を並べ替えると、乗算するよりも速くなりますか？そうでない場合、少数の要素をより速く並べ替えるために、どのような低レベルの最適化を行うことができますか？

ありがとう！

みなさん、良い答え。ハードパフォーマンス統計を取得するために、ソートと乗算のパフォーマンスのベンチマークに取り組んでいます。

Answer 1

並べ替えは、数字を掛けることよりも本質的に難しくありません。紙の上では、それらはほぼ同じであり、大きな種類で大きな乗算を競合するために洗練された乗算アルゴリズムも必要です。さらに、提案された乗算アルゴリズムが実行可能である場合、バケットソートを使用することもできます。これは漸近的に高速です。

ただし、ポーカーハンドは漸近問題ではありません。それはたった5枚のカードであり、彼はカードの13の数値の1つだけを気にしています。原則として乗算が複雑であっても、実際にはマイクロコードで実装されており、非常に高速です。彼がしていることは機能します。

現在、理論的な質問に興味がある場合は、乗算ではなく追加を使用するソリューションもあります。 1つの値のカードは4枚しかないので、値1,5,25、...、5^12を割り当てて追加することもできます。それはまだ32ビットの算術に適合します。他の数学的特性を備えた他の追加ベースのソリューションもあります。しかし、マイクロコード化された算術は、コンピューターが行っている他の何よりもはるかに高速であるため、実際には問題ではありません。

Answer 2

もちろん、それはコンピューターのCPUに大きく依存しますが、典型的なIntel CPU（Core 2 Duoなど）は、3 CPUクロックサイクル内で2つの32ビット数値を掛けることができます。それを打ち負かすソートアルゴリズムの場合、アルゴリズムは3 * 4 = 12 CPUサイクルよりも速くなる必要があります。これは非常に厳しい制約です。確かに12サイクル未満でそれを行うことはできません。単独で2つの数値を比較すると、1つのCPUサイクルが必要になります。結果の条件付きブランチも1つのCPUサイクルを取ります。したがって、勝利を増やします。

もちろん、これはレイテンシを考慮して、1番目または2番目のレベルのキャッシュ、あるいはメモリからカード値を取得することではありません。ただし、このレイテンシは、いずれかの場合、乗算および並べ替えに適用されます。

Answer 3

テストなしで、私は彼の議論に同情的です。ソートと比較して、4つの乗算でそれを行うことができます。 n log n. 。具体的には、最適です ソートネットワーク 9つの比較が必要です。評価者は、少なくとも別の5つの操作であるソートされた配列のすべての要素を見る必要があります。

Answer 4

5つの要素は、最適化された決定ツリーを使用してソートすることができます。これは、汎用ソートアルゴリズムを使用するよりもはるかに高速です。

ただし、ソートは多くの枝を意味するという事実は残っています（後に必要な比較もそうです）。枝はそうです 本当 現代のパイプライン化されたCPUアーキテクチャ、特に同様の可能性がある（したがって、ブランチ予測ロジックを打ち負かす）。それは、増殖と比較の理論的コストよりもはるかに多く、乗算が速くなります。

しかし、並べ替えを行うためにカスタムハードウェアを構築できれば、 そうかもしれない より速くなります。

Answer 5

それは本当に関連するものではありませんが、彼は正しいです。並べ替えは乗算よりもはるかに時間がかかります。

本当の問題は、彼が結果のプライムナンバーで何をしたか、そしてそれがどのように役立つかということです（それを考慮してから、並べ替えよりも時間がかかると予想されます。

Answer 6

同じ数字のセットを掛けるよりも速いソート操作を考えるのは困難です。プロセッサレベルでは、乗算は正当です load, load, multiply, load, multiply, ..., 、おそらくアキュムレータが投げ込まれた操作があるかもしれません。それは線形で、簡単にパイプライン化されており、関連するブランチの誤認定コストとの比較はありません。値ごとに平均約2命令を掛けする必要があります。複数の命令が痛々しいほど遅い場合を除き、より速い種類を想像するのは本当に難しいです。

Answer 7

言及する価値のあることの1つは、CPUの乗算命令がゆっくりと死んでいても（または存在しない...）、ルックアップテーブルを使用して物事をさらに高速化できるということです。

Answer 8

多くのことを考えた後、私は素数を使用するためにブレーンストーミングをしました。 13枚のカードランクのそれぞれにプライムナンバー値を割り当てます...このシステムの美しさは、手の各カードのランクのプライム値を掛けると、注文に関係なくユニークな製品を取得することです。 5枚のカードの。

これは、非陽性番号システムの例です。

理論へのリンクが見つかりません。私は、適用された代数の一部として、オイラーのティエントと暗号化の周りのどこかでそれを研究しました。 （私は私の母国語でそれをすべて研究したので、私は用語に間違っている可能性があります。）

彼の表現（カードは4バイトの整数として）を保持した場合はどうなりますか？ 5つの整数の配列を並べ替えると、乗算するよりも速くなりますか？

RAMは外部リソースであり、一般にCPUに比べて遅くなります。 5の5の並べ替えは、スワップ操作のために常にRAMに移動する必要があります。ソート機能自体のオーバーヘッドをここに追加すると、乗算はすべて悪く見えるようになります。

現代のCPUでは、整理よりもはるかに速く、整理よりもはるかに高速であると思います。これは、CPUをRAMに接続するバスは1つだけであるのは、異なるアルスで複数の乗算を同時に実行できるからです。

そうでない場合、少数の要素をより速く並べ替えるために、どのような低レベルの最適化を行うことができますか？

5つの整数を使用して非常に迅速にソートできます バブルソート: ：QSORTはより多くのメモリを（再帰に）使用しますが、適切に最適化されたバブルソートはD-Cacheから完全に機能します。

Answer 9

他の人が指摘したように、ソートだけで5つの値を掛けるよりも速くはありません。しかし、これは彼の解決策の残りを無視します。 5要素の種類を軽視した後、彼は4888の値の配列でバイナリ検索を行います - 少なくとも12の比較は、これまでに必要な種類を超えています！

ソートを伴うより良い解決策があると言っているわけではないことに注意してください。個人的には十分な考えを与えていません。

彼はまた、素数を使用する必要はありませんでした。彼が単に各カードの値を4ビットでエンコードした場合、彼は手を表すために20ビットが必要であり、0〜2^20 = 1048576の範囲を与え、プライムを使用して生産された範囲の約1/100、そして十分に小さい（まだキャッシュコヒーレンシーの問題に苦しんでいますが）ルックアップテーブルを作成します。

もちろん、さらに興味深いバリアントは、テキサスホールデムのようなゲームで見つかったような7枚のカードを撮影し、それらから作ることができる最高の5カードハンドを見つけることです。

Answer 10

乗算はより速いです。

特定の配列の乗算は、アレイの並べ替えよりも常に高速になり、乗算が意味のある結果になると仮定すると、コードがポーカーハンドを評価するように設計されているため、ルックアップテーブルは無関係です。とにかくソートされたセット。

Answer 11

既製のテキサスHold'em 7および5カード評価者の例を見つけることができます ここ ドキュメントとさらに説明しました ここ. 。すべてのフィードバックは、そこにある電子メールアドレスで歓迎されます。

並べ替える必要はありません。通常（時間の約97％）、7カードを評価するときにわずか6個の追加とビットシフトで逃げることができます。アルゴは、約9MBのRAMを占める生成されたルックアップテーブルを使用し、近接剤で生成されます。安いです。これらはすべて32ビット内で行われ、7カード評価者を「インライン化」することは、ラップトップで毎秒約50mのランダムに生成された手を評価するのに適しています。

ああ、そして乗算はソートよりも速いです。