問題タブ [std-bitset]

質問する

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

99 問題
Newest
Active
Bountied
318
Unanswered
0 投票する
1 に答える
147 参照

c++ - ふるいに使用するのに最適なデータ構造は何ですか?

エラトステネスのふるいを実装しています。最初のステップ、つまり使用するデータ構造の決定に行き詰まっています。簡単に言えば、エラトステネスのふるいは連続した数字のリストから始まります (例: 2、3、4、5、...99、100)。次に、特定の数字が取り消し線で消され、二度と考慮されなくなります。使用するのに最適なデータ構造は何ですか? 制限 (例では 100) は実行時までわかりませんが、常に開始数は 2 です。

私はいくつかの異なる解決策を見てきました。制限nはタイプですmpz_class

  • bool primes[n]
  • bool* primes
  • std::vector<bool> primes
  • std::bitset<n> primes
  • vectorパラメータを使用するintかunsigned char、より効率的であるためbool
  • ベクトルおよび配列ベースのソリューションの場合、n+1要素を割り当てます（ここで見られるnように）これは、の値が最後の要素になり、ループ内で必要な減算が少なくなるためだと思います。

この情報の一部は、このコード レビューの質問から得られます。@Jamal は、「実際には std::vector に特に問題がある」と述べていますが、詳しくは述べていません。また、より良い選択をするよりもunsigned char、サイズが等しいか小さいことが保証されている場所を赤くします。 bool


12345678910