0

スニペット

if (a<=lim){
    if(std::find(prims.begin(), prims.end(), a)==prims.end()){
        prims.push_back(a);
        count+=lim/a;
    }         
}

したがって、基本的には、コードにこの部分があり、変数がまだ存在しない場合はaこれに変数を追加してから、その場でカウンターを更新します。vector

しかし、これは実行時間の点で最適ではないかと思います。もっと速くできることはありますか？

4

3 に答える 3

5

std::set一意の値のみを保持する場合に一般的に使用されるコンテナーです。値は赤黒木として内部的に保存されるため、ほとんどの演算は対数の複雑さになります。

これは、実装よりも高速であり、提案された二分探索の実装とほぼ同じ速さです。

new (c++11) を使用してさらに改善することができstd::unordered_setます。これはハッシュ テーブルとして格納され、平均一定時間操作でさらに高速になります。

次のように使用setします

std::set<TYPE> prims;
....
if (a<=lim){
    if(prims.insert(a).second){
        count+=lim/a;
    }         
}

ここで、TYPE はベクトルに格納されている値の型です

于 2012-12-04T04:55:07.980 に答える
0

setやmapなど、一意性が組み込まれた他のSTLコンテナを使用したい。http://www.cplusplus.com/reference/map/map/。たとえば、マップでモデル化されたハッシュテーブルは、ユースケースに適合します。

<map>
using namespace std;

int insert_and_update(int key_val,map<int,int> hash_map) {
map<int,int>::iterator it;
it = hash_map.find(key_val);
  if( it != hash_map::end() ) {
     it->second += 1; //contains the associated value.
     return 1;
  }
 hash_map(key_val) = 1; //else insert new key into map
 return 0;      
}
于 2012-12-04T05:03:40.343 に答える
0

を使用しstd::unordered_setて重複をチェックできます。これにより、O(1) 償却されたルックアップが得られます。

の最大サイズがある程度わかっていてa、それがかなり小さい場合は、bool配列を使用して要素かどうかを格納するxと、真のO(n)ルックアップが得られます。

于 2012-12-04T04:55:31.543 に答える