「なぜsetを使っちゃいけないの？」CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。
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でソートした状態で持つ事により、二分探索による要素の探索を可能にしたデータ構造です。こ
d.y.d. 2倍だけじゃない
10:01 10/07/20 それでも２倍だ 先日のvectorの伸長度合いの記事に関して 本当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ： 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります（途中計算略）。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります
Oracle の B*Tree インデックスの内部構造についてお勉強中（その１）
お仕事のデータベース一式のリース切れ間近ということで、リース延長で耐えることができるのか、それともシステム更改が必要なのかを見極めるため、最近はデータベース周りのチューニングばかりやってます。 当初設計時に、５年間持つ設計をしたのですが、流石に５年目にもなると予定とはそれなりに乖離が発生するものです。テーブル＆インデックス設計をユーザ向けの処理をとにかく高速に処理できるように設計したので、ユーザ向けの処理は速度的に全然大丈夫なのですが、データの肥大化によるバッチ処理のパフォーマンス劣化が顕著です。単純にストレージと CPU パワーが足りていないのでしょう。 しかしながらチューニングの余地はまだまだ十分にありそうです。バッチ向けの最適化を図ることにしました。うまくいけば来年度どころか、後数年はリース延長で延命できるかもしれません。 今回実施したチューニングの１つのポイントとして、バッチ処理向
第35回 キーを使って値を参照するMap型
プログラムを書いていると，キーと値を組にしてデータを保持する辞書（dictionary，連想コンテナ：associative containerとも言います）のデータ構造を使いたくなることがあります。Haskellではこのようなとき，containersパッケージのData.Mapモジュールに用意されているMap型などの「木を使ったデータ型」をよく使います。今回はMap型を紹介します。 辞書を実現する様々な方法 Haskellで辞書を実現する方法はいくつか考えられます。それらの方法で実装した辞書が，実際の使用に耐えられるかどうかを検証していきましょう。 辞書を実現する最も簡単な方法は，キーと値の対を直接保持する連想リストを作成することです。連想リストでは対の1番目の要素がキー，2番目の要素が値になります。 作成した連想リストから，キーにより値を取り出すには，lookup関数を使います。 l
ソースでわかる！ハッシング
これまでの2回で、増減するデータを格納して検索するための方法を2つ紹介しました。1つはリスト構造（linked list）、もう1つは二分探索木（binary search tree）です。 この2つは、配列に対する線形探索（linear search）と二分探索（binary search）と同様の探索性能があることを示しました。アルゴリズム性能を表すオーダーＯで表すと、それぞれＯ(n)とＯ(log2(n))です。 今回は、Ｏ(1)である方法を紹介します。今回もプログラムを使いながら見てみましょう。プログラムはこちら（http://www.thinkit.co.jp/images/article/159/3/15931.zip）からダウンロードできます（15931.zip/2 KB）。 アルゴリズム性能がＯ(1)であるとは、「いつでも一定の時間でアルゴリズムが停止する」ということです。探
図解！二分探索のプログラミング
二分木（Binary Tree） 「第1回：サーチのアルゴリズムを学ぶ」は、動的に増減する要素をリンクトリストで管理する方法を紹介しました。 リンクトリストでは要素を探索する場合、リンク（ポインタ）を順にたどるしかないため、線形探索と等しい時間がかかってしまいます。今回は、リストと同様にポインタでつながった構造でありながら、探索時間は二分探索と同じ性能の構造である二分木（Binary Tree）を紹介します。これはB-Tree や Balanced Tree（バランス木）と言葉も機能も似ていますが、少し違います。今回は、探索目的に使う二分木である二分探索木（Binary Search Tree）と呼ぶものを扱います。 図1-1に二分探索木を示します。 全体を木だと思ってください。丸をノード（node；節）と呼びます。また、ノードから出ている線は木の枝（branch）に相当します。各ノードか
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Google Code Archive - Long-term storage for Google Code Project Hosting.