高速なハッシュテーブルを設計する | POSTD
(訳注：2016/9/28、頂きましたフィードバックを元に記事を修正いたしました。) はじめに 本稿では、高速で汎用的なハッシュテーブルを作るために行う、設計についての多くの意思決定事項を紹介します。最終的に、私の emilib::HashSet とC++11の std::unordered_set の間のベンチマークが出来上がりました。もし、ハッシュテーブルに興味があって、自分で設計したいなら（どのプログラミング言語かに関わらず）、本稿がヒントになるかもしれません。 ハッシュテーブル は、素晴らしい発明です。 ならし計算量O(1) ( O(√N)時間 )で、挿入、削除、検索を行うことができます。ならし計算量とは、ハッシュテーブルの計算に平均でO(1)の計算量がかかることを意味しますが、時々、これよりも多くの時間がかかる場合があります。具体的には、ハッシュテーブルに空きがない場合で、挿入の
Big Sky :: C++ の数式パーサ Lepton で遊んでみた。
Lepton という数式パーサを見つけたので遊んでみた。 Simtk.org: Lepton Mathematical Expression Parser: Overview Purpose/Synopsis: A small C++ library for parsing, evaluating, differentiating, and analyzing mathem... https://simtk.org/home/lepton 一般的な数式パーサは expression を token に分解するのみだが、この lepton はもう1歩踏み込んだ処理が行える。 通常の数式は以下の様にパースし実行出来る。 #include <iostream> #include <string> #include <map> #include <Lepton.h> int main(int ar
find関数で見るC++の変化 - C++と色々
STLアルゴリズムはそのアルゴリズムを適用する範囲の先頭と末尾のイテレータのペアを引数に取ります。実際には範囲全体にアルゴリズムを適用させるケースが多く、イテレータのペアを書くのが冗長に感じることがあります。そこでBoost.Rangeには、範囲を引数に渡すことでその範囲全体にSTLアルゴリズムを適用する関数たちがあります。Boost.Rangeのfind関数の実装例を見てC++03/C++11/C++14の比較をしたいと思います。 C++03 まず、範囲なら何でも、コンテナでも組み込み配列でもアルゴリズムに適用できるように、begin関数、end関数を定義します。 namespace ns { //コンテナ版begin/end関数 //非const、constでオーバーロード template <typename Container> typename Container::iterat
MSのあまりにもひどいマクロ - ここは匣
2013-10-10 MSのあまりにもひどいマクロ maxとかminとかが使えないと思ったらminwindef.hとかいうところでマクロとして定義されていてキレそうっていうかこれは完全にブチギレ— 秋弦めい (@maytheplic) October 10, 2013 http://stackoverflow.com/questions/5004858/stdmin-gives-error StackOverflowにも同じような事言ってる人が居たので引用。 どうやら以下のようなコードがエラーになるらしいです #include <algorithm> #include <Windows.h> int main() { int k = std::min(3, 4); return 0; } error C2589: '(' : illegal token on right side of
Boost.Geometry 四角形の内外判定 - Faith and Brave - C++で遊ぼう
Boost.Geometryには、2次元上の点を表現するpoint_xyコンセプトと、左上の点と右下の点のペアとして表現されるboxコンセプトがあり、この2つをwithinアルゴリズムに適用することで、四角形の内外判定が簡単にできます。 #include <iostream> #include <boost/geometry/geometry.hpp> namespace bg = boost::geometry; typedef bg::model::d2::point_xy<double> point_type; typedef bg::model::box<point_type> box_type; int main() { const point_type top_left(0, 0); const point_type bottom_right(3, 3); const box_
dag_vector: ランダムアクセス可能な圧縮配列 - Preferred Networks Research & Development
こんにちは、この夏はシルキードライで乗り切りたい岡野原です。 今日は最近公開したC++のオープンソースであるdag vectorについて紹介します。 github: dag_vector ライセンスは修正BSDライセンスです。 dag vector (direct accessible gamma code vector) は値を圧縮して格納したまま任意の場所の値を高速に参照可能な配列ライブラリです。しかもデータ末尾への追記が可能です。 dag vectorはstd::vectorのように利用できます。下にいくつか例を見ていきましょう。 dag_vectorの例 #include "dag_vector.hpp" // dag_vectorは0以上の正整数の配列を扱う配列。 dag_vector dv; // 値はいつでも追加可能。追加された値は圧縮して格納される // 正整数xは2lg(
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
マルチコア時代のLock-free入門