unordered_map について - mayoko’s diary
unordered_map で辛い思いをしたので twitter でわーわー言ってたらいろいろ勉強になったのでメモします。 まとめ 基本的にチェイン法っていうのでやってるっぽい vector< list< T > > みたいのをイメージするとわかりやすい 詳細 まとめで書いたように, 基本的には vector< list< T > > というのが全部説明している気がします。 find() は平均計算量 O(1), 最悪計算量 O(n) find() は, 基本的にはハッシュ値で vector にランダムアクセスするだけで目的のものが見つかるので O(1) だが, ハッシュ値がかぶっているものがあると, vector の要素のリストを線形探索しないといけない。なので最悪 O(n) insert(), delete() も平均計算量 O(1), 最悪計算量 O(n) 結局消す, 入れる場所を探
Fisher-Yates Shuffle - Faith and Brave - C++で遊ぼう
Fisher-Yates Shuffle – An Algorithm Every Developer Should Know てきとうに抜粋して書く。 以下のシャッフルアルゴリズムは間違っていて、 def incorrect_shuffle(items): for i in range(len(items)): randomIndex = random.randint(0, len(items)-1) temp = items[randomIndex] items[randomIndex] = items[i] items[i] = temp return items これには、以下の3つの問題がある： 偏る 偏る 偏る 実は1つだったけど、これは大きな問題だ。 Fisher-Yates Shuffle (Knuth Shuffleとも呼ばれる)の実装は、以下のようになる： def fi
STL風に使えるマップ型コンテナの紹介と性能比較 - Preferred Networks Research & Development
最近スマートフォンに乗り換えました。徳永です。 C++は世に数あるプログラミング言語の中では比較的メモリを食わない方ですが、それでもメモリ使用量が問題となる場合はあります。そのような場合の対処方法はいくつか有りますが、手軽に選択できる方法として、今日はSTLのmapやunordered_mapと同じ感じで使えるデータ構造をいくつか紹介したい思います。 以下、計算量の表記をする際には、要素数をnとします。 Loki::AssocVector LokiはModern C++ Designという本の作者であるAndrei Alexandrescuが開発したライブラリです。AssocVectorはその中の一つとして提供されているクラスで、vector<pair<key, value> >という型のベクターをkeyでソートした状態で持つ事により、二分探索による要素の探索を可能にしたデータ構造です。こ
株式会社エス・スリー・フォー » STLport のハッシュ・コンテナ
STLport のハッシュ・コンテナ 標準C++ライブラリが提供するコンテナは、vector, list, deque, set, multiset, map, multimap の7種です。 これらコンテナから特定の要素を検索するとき、その時間計算量は vector, list, deque では O(N), set, multiset, map, multimap では O(logN) となります。 これ以上に高速な検索が可能なコンテナとしてハッシュ表(hashtable)を利用すれば、適切なハッシュ関数を与えることによって検索に要する時間計算量をコンテナ内の要素数に関わらず O(1) に近づけることができますが、残念ながら標準C++ライブラリにはハッシュ表で実装されたコンテナ(ハッシュ・コンテナ)を提供していません。 SGI(Silicon Graphics社)のSTL実装をベースに
OBB vs AABB - Radium Software Development
This domain may be for sale!
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
std::minmax_element - cppreference.com
