C++の高速なハッシュテーブル、ankerl::unordered_dense::{map, set}の実装を読んでみた。 作者によるとabsl::flat_hash_map(通称SwissTable。Google製)と同程度に挿入・検索が速く、特にイテレートはstd::vectorと同等で最速らしい。 Comprehensive C++ Hashmap Benchmarks 2022にベンチマークがある。 (作者自身による計測なので、多少のバイアスはあるかもしれない) 基本のアルゴリズム Robin Hood hashing + Backward shift deletionを使用している。 まずこれを理解すると分かりやすい。 アニメーション付き Robin Hood Hashing | Programming.Guide 詳細な説明 Robin Hood hashing | Code

レイトレ合宿９(*)のセミナー発表スライドです。 * https://sites.google.com/view/rtcamp9/home - 2023/09/08 “除算法2”追記。（@Reputelessさんありがとうございました）

第16回 StringBeginners での発表資料

PHPとPythonとRubyの連想配列のデータ構造がそれぞれ4〜5年ほど前に見直され、ベンチマークテストによっては倍以上速くなったということがありました。具体的には以下のバージョンで実装の大変更がありました。 PHP 7.0.0 HashTable高速化 (2015/11) Python 3.6.0 dictobject高速化 (2016/12) Ruby 2.4.0 st_table高速化 (2016/12) これらのデータ構造はユーザーの利用する連想配列だけでなく言語のコアでも利用されているので、言語全体の性能改善に貢献しています1。 スクリプト言語3つが同時期に同じデータ構造の改善に取り組んだだけでも面白い現象ですが、さらに面白いことに各実装の方針は非常に似ています。独立に改善に取り組んだのに同じ結論に至ったとすれば興味深い偶然と言えるでしょう2。 本稿では3言語の連想配列の従来実

1. はじめに ～メインを読むための準備～ まず、大きな数の計算の話をする前に、少しコンピューターと計算回数について話しましょうか。 コンピューターは、現代ではソフトウェアやアプリケーションの開発に使われていますが、これには重要な背景があります。これは「計算がめっちゃ速いこと」です！人間なんかと比べたら、圧倒的な計算スピードを誇ります。 1-1. 人間の計算速度はどのくらい？ まず人間はどのくらいの速度で計算できるでしょうか？速い人も遅い人もいると思います。 例えば、$628 \times 463$ の計算を、今やってみましょう。10 秒以内で計算できたらかなり速い方でしょう。この計算では、次のように「単純計算」を合計 28 回もしていることになります。 9 回の 1 桁 × 1 桁の掛け算 6 回の 1 桁 × 1 桁の足し算 13 回の繰り上がり計算 もし $628 × 463$ が

この記事は続編です。 前回の記事で、SFC版風来のシレンのROMデータの解析内容を元に乱数がどのようにして生成されているかを解説しています。そちらを読んでからこの記事を読んでいただくと、より内容を理解しやすいかと思います。 前回の記事：SFC版風来のシレンの乱数生成アルゴリズムの話 解析編 SFC版風来のシレンの乱数の品質を調べる さて前回の記事でSFC版風来のシレンの乱数生成アルゴリズムが線形帰還シフトレジスタの一種であることが分かりました。 しかし乱数生成アルゴリズムは理解したものの、それによって生成された乱数が妥当な物なのかというのはアルゴリズムを見ただけでは分かりません。 シレンの乱数は偏りやすいと断言できるような目に見えて質が悪いものなのでしょうか。 この項でそれを考察してみたいと思います。 先にお断りしておきますが、本気で定量的・客観的に乱数の品質を検証しようと思うと本格的な統

SFC版風来のシレンの乱数について 私はローグライクゲーム好きなのでローグライク系ゲームの動画をニコニコ動画等でたまに見たりします。中でも、SFC版の初代風来のシレンはもう20年以上も前のゲームですが、完成されたゲームシステムと絶妙なゲームバランスにより、今なお根強い人気があります。 さて、そのSFC版風来のシレンの動画を見ていると、たまにゲーム上で「連続して攻撃を外す」「同じアイテムばかり出る」といった偏った現象が発生した時に「シレンの乱数は偏りやすい」といったようなコメントがよく書き込まれています。 人間の感覚というのものは偏った現象に気づきやすいものであり、この手の意見は大抵誤っている（特に最近ではソシャゲのガチャが操作されている！などとすぐに言われますね）のですが、風来のシレンはSFC時代のゲームという事もあり実際に質の悪い乱数生成ルーチンになっている可能性もあります。 そこで気に

オープンソース版 Open Data Structures 日本語訳の PDF ファイルを以下で公開しています。最新のソースコードは GitHub のリポジトリ https://github.com/spinute にあり、適宜こちらの PDF ファイルに反映しています。 以下のものは C++ 版です（Java 版はこちら、疑似コード版はこちらにあります）。 目次 訳者まえがき 本書の読み方 訳者謝辞 なぜこの本を書いたのか 謝辞 第1章 イントロダクション 効率の必要性 インターフェース 数学的背景 計算モデル 正しさ、時間計算量、空間計算量 コードサンプル データ構造の一覧 ディスカッションと練習問題 第2章 配列を使ったリスト ArrayStack：配列を使った高速なスタック操作 FastArrayStack：最適化された ArrayStack ArrayQueue：配列を使ったキュ

情報科学科の卒業生やプログラマの中には、UberやNetflixのような新興企業や、 Amazon 、 Microsoft 、 Google のような大企業や、InfosysやLuxsoftのようなサービスを基本とする企業で、プログラミング、コーディング、ソフトウェア開発の仕事に就きたいと考える人が大勢います。しかし、実際にそういった企業で面接を受ける場合、大半の人が プログラミングに関してどのような質問をされるか 見当もつきません。 この記事では、 新卒生からプログラマになって1〜2年までの 経験値が異なる人たち向けに、それぞれの プログラミングの面接でよく聞かれる質問 をいくつか紹介していきます。 コーディングの面接では、主に データ構造とアルゴリズムに基づいた質問 がされますが、 一時変数を使わずにどのように2つの整数をスワップするのか 、というような論理的な質問もされるでしょう。

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

自分用のメモも兼ねて、C言語での、複数キーに基づくソートのqsort()を使ったシンプルな書き方についてまとめる。 問題設定 C言語を使って、構造体の複数の要素に基づいたソートを行う問題を考える。 例えば、AOJ-ITP2_5_B http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_5_B&lang=jp Sorting Tuples n個の品物が与えられます。各品物は{価値、重さ、型、日時、名前}の属性を持ち、これらはそれぞれ整数、整数、英大文字、整数、英小文字の文字列で表されます。 与えられた品物を以下の優先順で出力してください。 価値が低い品物を先に出力する 価値が同じ場合は、重さが小さい品物を先に出力する 重さが同じ場合は、型がアルファベット順で小さい品物を先に出力する 型が同じ場合は、日時が早い品物を先に出力

はじめに 長さ$n$の昇順にソートされた配列から指定したkeyが格納された位置$i$（もしそのkeyがなければ、その値が格納されるべき位置）を返す問題を考えます。 よく知られた二分探索を使えば、$O(\log n)$時間で解くことが出来ますが、指数探索（exponential search）を使えばより高速に、$O(\log i)$時間で解くことが出来ます（正確に言うと$i$は高々$n$なので指数探索は二分探索よりも同等あるいは高速に動作します）。 オーダー表記では定数項を無視しているので実際には二分探索の方が速い場面も多いですが、特殊なケース、例えばクエリに偏りがあり、配列の前方ばかりを返すような場合には二分探索よりも高速に動作します。 指数探索アルゴリズム アルゴリズムは２つのフェーズに分かれます。 第一フェーズ 第一フェーズでは、keyが格納されている範囲を特定します。 ここでは配列

1. はじめに 今回は実務プログラミングにおいて知らず知らずのうちに遅いコードになっていそうな例をいくつか挙げて、それを計算量の観点から高速化してみたいと思います。 2. 計算量を意識することにどんな意味があるか 身近な例として、Qiita Contribution ランキングの作成を考えてみましょう。ランキングを作成するためには、各ユーザーの Contribution 数を大きい順に並び替える処理、すなわちソートが必要になります。 Qiita ユーザー数は現在およそ $30$ 万人です。標準ライブラリの sort を用いれば、それほどの計算時間はかからないと思います。しかし仮にこれを愚直な sort アルゴリズム (例えば、挿入ソートやバブルソートなど) で実行したら恐ろしいことになります。 愚直なソートは、並び替える要素の個数の 2 乗に比例した時間がかかります。すなわち $n$ を並

a]:flex [&>a]:flex-row [&>a]:justify-between [&>a]:py-[18px] [&>a]:border-t [&>a]:border-lightgray [&>a]:border-opacity-20 [&_li]:my-1 [&_li]:list-['-_'] [&_li]:py-[18px] [&_li]:border-t [&_li]:border-lightgray [&_li]:border-opacity-20 [&_.Label]:transition-all [&_.Label]:w-fit [&_.content]:transition-all [&_.content]:h-0 [&_.content]:pt-0 [&_.content]:px-5 [&_.content]:overflow-hidden [&_.toggle:

Programming Place Plus へようこそ。 当サイトはプログラミングに関する学習サイトで、現在はＣ言語と C++ を扱っています。 プログラミングの入門～中級（自分でプログラミングできるレベル）までをサポートすることを目指して、コンテンツを作成、更新しています。 最近行われた更新を、ここから確認できます。 お知らせ ’2023/4/30 次月から、参考書籍に本を追加するタイミングを、最終土曜日に変更します ’2023/4/23 「セール情報」のページを追加しました 参考書籍 で紹介している本を中心に、お買い得情報を取り上げます（週１回程度の更新予定） ’2023/1/29 オフライン版を更新しました ’2022/6/12 「今後の予定」を更新しました コンテンツ Programming Place Plus のコンテンツです。最近行われた更新はこちら。 以下の検索窓から、す

BIT については hos さんの資料 Binary Indexed Tree のはなし に極めてよくまとまっています。BIT の基本から二次元 BIT、区間加算対応 BIT、BIT 上の二分探索で $k$ 番目の値を取得するところまでカバーしています。 平衡二分探索木についての資料としては、 プログラミングコンテストでのデータ構造 2　～平衡二分探索木編～ (秋葉さん) 平衡二分木を使う問題 (よすぽさん) がとても読みやすいです。また自前で実装を用意するのが大変でも G++ 拡張の Policy Based Data Structure の一つに tree と呼ばれるものがあるようです。$k$ 番目に小さな値を取得することもできるようです。使い方は hogloid さんの以下の記事にまとまっています。 g++拡張・tree 整理 要素の値 v が 1 〜 D に限られているとき (D

現実世界でもコンピュータの中でも、何らかの性能指標だけを追求すると参加者にとって極端に不公平になってしまうことがある。例えばエレベータとHDDは共通点がありそうに思えないが、この2つは性能特性的にとてもよく似ていて、リーズナブルな性能と公平性を両立させるために同じ制御方法が使われている。これについてちょっと説明してみよう。 1基しかない場合のエレベータの動き方は単純だ。一度上に動き出すと、上で待ってる人や降りる人がいる限り上昇し続ける。同じように、一度下に動き出すと、下で待っている人や降りる人がいる限り下降し続ける。これ以外の動き方をするエレベータはまず存在しないので、これが唯一の制御方法のように思えるけど、別にこうしなければいけないというルールはない。 エレベータの平均待ち時間を最適化することを考えてみよう。そうすると、一方向に動き続ける代わりに、エレベータが現在存在する階に一番近い人の

インクルードするだけで使えるNon-movingで正確なGCをC言語用に作りました。 行数がコメントを除いて100行に満たない非常に小さなライブラリです。 GCのアルゴリズムとしてはCheneyのコピーGCを採用しています。 通常のCheneyのコピーGCではメモリ空間のうち半分が無駄になってしまいメモリ効率が悪かったり、 GC発生時にオブジェクトが移動してしまいC言語のようなポインタを直接触れる言語との相性が悪いという欠点がありました。 今回はヒープ全体を二重連結リストとして管理することでそのような問題を解決しています。 ちなみにこれはTreadmill GCのアイデアと同じです。(が、アルゴリズム自体はTreadmill GCではありません。) APIはLinuxのlist.hに非常に近い見た目になっています。 ある構造体をgcで管理したい場合はstruct gc_head型のメンバを

こんにちは、最近ハマっている初期化配列について紹介したいと思います。 はじめに 皆さんプログラミングをする時に配列を使ってますか？使ってない人はほとんどいないのではないでしょうか？ 長さNの固定長配列AはN個の要素を格納でき、かつ任意の位置に保存された要素A[i]を最悪定数時間（以下、定数時間）で読み書き可能な最も基本的なデータ構造の一つです。配列の様々な操作の中で読み書きについで頻出する重要な操作が、配列の全ての要素を指定した値に書き換える初期化操作です。配列の初期化は配列長に対して線形な時間がかかるため、配列長が長い場合や、初期化が頻出する処理では配列の初期化操作が大きなボトルネックとなります。この問題を解決するデータ構造が初期化配列です。本記事ではシンプルな初期化配列の実装法、folkloreアルゴリズムを紹介したいと思います。 初期化配列とは通常の読み書きに加え、配列の全ての要素を