Changing std::sort at Google’s Scale and Beyond
TL;DR; We are changing std::sort in LLVM’s libcxx. That’s a long story of what it took us to get there and all possible consequences, bugs you might encounter with examples from open source. We provide some benchmarks, perspective, why we did this in the first place and what it cost us with exciting ideas from Hyrum’s Law to reinforcement learning. All changes went into open source and thus I can
はじめに - アルゴリズムとデータ構造大全
はじめに このドキュメントは，主に競技プログラミングで出題される問題を解く際に利用できるアルゴリズムやデータ構造をまとめたものです．特定の問題にはあまりフォーカスしないため，問題を解く際の考察の仕方等の内容はありません．詳しく，正確に，分かりやすく書いていこうと思っています． このドキュメントは執筆途中です． 想定する読者 C++を用いたプログラミングに慣れている方を読者として想定しており，C++言語の仕様や，文法にはあまり触れません．また，計算量という用語についても説明しません．ただし，償却計算量など，計算量の見積もりが複雑なものについては必要に応じて説明します． コードについて このドキュメントで登場するコードは，可読性向上のため，以下のようなコードがファイルの先頭に記述してあることを前提としています．また，適切な問題を用いてコードの検証がなされている場合は，コード周辺にのように，検証
絶対にバグらない二分探索の実装パターンと、それがバグらない5つの理由 - Qiita
概要 絶対にバグらない二分探索の実装パターンと、それがバグらない5つの理由を紹介します。 めぐる式二分探索と比べると、コーナーケースに強いです（具体的には「解が存在する値」「解が存在しない値」の存在を前提しないので強いです）。 #二分探索 二分探索とは、判定関数 $f(x): T \rightarrow bool\ (x \in [s, t))$ が広義単調増加であるときに、 $f(x) = true$ となる最小の$x$を$O(\log (t-s))$で求めるアルゴリズムです。 …が、二分探索は、$T = int$の時、必ずバグることで有名です。何をやってもバグります。 この記事では、以下のC++のコードが、任意の広義単調増加な$f$についてあらゆるコーナーケースに常に正しく動くことを納得させます。 お気持ち 初期値のngには、絶対に$f(x)$がfalseであるような$x$を入れておき
Union-Find with deletions - 誤読
謎のデータ構造を見つけてしまった。実装したくなかったが、してしまった。後悔しかしていない。 UnionFindといえば競プロerであればほとんどの人が知ってると思われるが、あれはUniteとFindはあってもある要素をフリーにするという操作ができない。 UF木の葉以外を削除しようとすると計算量が増えてしまうのは想像がつくと思う。 そこでUnion-Find with Deletionsというのがあって、これを使うとUniteをO(A(n)),FindをO(A(n)),DeleteをO(1)でできるようになっておいしい。 （追記）論文でUniteがO(1)なのは集合をしていしてUniteする実装だからで、要素を指定してそれらの属するグループを併合するっていうのはFindを挟む必要があるのでO(A(n))になっているだけです。 主なアイデア 1.要素の部分と木構造の部分を切り離して木のノードが
I Wrote The Fastest Hashtable
I had to get there eventually. I had a blog post called “I Wrote a Fast Hashtable” and another blog post called “I Wrote a Faster Hashtable.” Now I finally wrote the fastest hashtable. And by that I mean that I have the fastest lookups of any hashtable I could find, while my inserts and erases are also really fast. (but not the fastest) The trick is to use Robin Hood hashing with an upper limit on
LOIS
Papers and technical documentation LOIS: technical documentation. PDF (Feb 1, 2016) Abstract: LOIS is a C++ library allowing iterating through certain infinite sets, in finite time. The resulting language has an intuitive semantics, corresponding to execution of infinitely many threads in parallel. This allows to merge the power of abstract mathematical constructions into imperative programming. I
UpCoder coding blog
Another custom container post for my Vectors and Vector Based Containers series. In this post I'll look at an alternative implementation of the humble bit vector, designed specifically for optimising zero fill operations. It's not a new technique, and not particularly complicated to implement, but it's not completely obvious, and it's something that gave us some noticeable speedups when applied to
Boost.GraphでJR全線乗り尽くしプランを立てる - プログラミング生放送+CLR/H+Sapporo.cpp 勉強会＠札幌 （2014.7.12）
Boost.GraphでJR全線乗り尽くしプランを立てる - プログラミング生放送+CLR/H+Sapporo.cpp 勉強会＠札幌 （2014.7.12）
Programming and DIY Projects: Advanced Tools and Techniques
By choosing the right language for the job, developers can optimize productivity and project outcomes. 3. Linux and Open Source for Developers Linux remains a developer’s paradise with its flexibility, tools, and open-source support. Top Tools for Developers in Linux tmux: Terminal multiplexer for managing multiple sessions. htop: A process viewer for real-time resource monitoring. Docker: For con
冗長性が低く重要度の高いパターンの抽出(1) - sfchaos's blog
パターンマイニングはデータマイニングを代表する手法の一つで，特にアソシエーションルールを適用した「ビールとおむつ」などの例が有名です． 最近は，Rなどのデータ分析ツールでもAprioriやEclat(頻出パターンマイニング), CSPADE(系列パターンマイニング)等のアルゴリズムを実行するライブラリが提供されており，パターンマイニングを実行することの障壁は比較的低くなっています． パターンマイニングでは，一般的に膨大な数のパターンが抽出されます．この事象はアイテムの組み合わせや順列の数が膨大になることに起因しており，少量のトランザクションから大量のパターンが抽出されることも決して珍しくありません*1．このような背景の下，パターンマイニングで抽出されたパターンから重要なパターンを抽出することは，大きな技術的課題の一つだと言えるでしょう． 抽出したパターンは膨大な数に 以上で説明したことを実
非復元抽出の高速かつ実装が簡単な方法を考える - シリコンの谷のゾンビ
※ @tomerun さんに書いてもらったコードとその検証結果を記事の最後に追記しました．(2013-07-21 2:00) ふとしたきっかけで非復元抽出 (random sampling without replacement) を実装するときに気になったのでどんな実装がよいのか考えてみた．なお非復元抽出はビンゴのように，N個の要素の中からk個の異なる要素をランダムに選択するという意味である． 復元抽出については @unnonouno さんのブログなどに書いてあり，非復元抽出についてもリンクが張ってあったのだけれど，リンク先のブログ記事が読めない状態になっていていたのが残念． unnonouno: 高速な復元抽出の直感的な説明 はじめに std::vector
constexpr アルゴリズムの実装イディオム その１ - ボレロ村上 - ENiyGmaA Code
中３女子です。 今回は、constexpr におけるアルゴリズムの実装法について考える。 よく知られているように、constexpr 関数には言語規格上の制約が多くある。 ローカル変数が使えない、if や for などの制御構文が使えないなどは、C++11 に触れた者なら誰でも知っているだろう。 だが、それらは条件演算子や再帰によって、単純に代替できる問題である。 つまり、非 constexpr な実装に対して、処理の流れを本質的に変えることなく constexpr に書き換えることができる。 単純に書き換えられる例: template<typename T> T const& runtime_min(T const& a, T const& b) { if (b < a) return b; return a; } template<typename T> constexpr T con
GDD2011, DevQuizのスライドパズルの解答コードを公開しました - Goto_youthKの徒然日記
去年の話になりますが、Google Developer Day 2011(GDD2011)に参加するために、DevQuizに挑戦しました。 お分かりの通り、開催されてから1年以上は経っているのですが、つい最近になって探索アルゴリズムの復習でもしようと思って(研究とは全く関係ない…)、もう一度初めからDevQuizを解き直してブログを書くことにしました。参加してた時に書けよっていうツッコミは勘弁して下さい… あれから時間はかなり経っているとは言え一度やっている問題だからなのか、少しプログラミングの腕が上達しているからなのか、去年よりも少し短い期間で、しかも6つの探索アルゴリズムの動作を比較できるくらいまでに実装できてしまいました。 ■DevQuiz さて、そのDevQuizについてですが、去年の問題の構成は、 問題 ウォームアップクイズ クイズ：40点 分野別クイズ(最大2問が得点に加算)
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - intel/x86-simd-sort: C++ template library for high performance SIMD based sorting algorithms
Duff’s device in 2021 – Belay the C++
AtCoder Library (ACL) クイックリファレンス - naoya_t@hatenablog
Linked Lists with wait-free reads in C++ (LRLinkedList and LRLinkedListSingle)
MARISA: Matching Algorithm with Recursively Implemented StorAge