Leo Robinovitch @ The Leo Zone
I implemented a simple hash table in C when solving a problem in CS Primer. Solving it helped me gain better intuition around hash functions, pointers, and memory segments like the stack and the heap. BasicsYou have probably encountered a hash table in the wild, like a dict in Python, map in Go, or Map in JavaScript. Hash tables associate a key with a value. Setting, looking up, and deleting value
読書: 計算量とマスター定理 • masu-mi's blog(dirty pages)
読書: 計算量とマスター定理 マスター定理の意味を押さえたい。周辺を整理して押さえた上で漸近計算量の見積もりをやれるようになりたい。 マスター定理は分割統治法による時間計算量を求める定理です。分割統治法では下のような漸化式が出てくることがしばしばある。 T(n)={aT(n/b)+f(n)if n>n0cif otherwisefor ∃c,n0,a≥1,b>1 \begin{aligned} T(n) = & \begin{cases} aT(n/b) + f(n) &\text{if } n > n_0 \\ c &\text{if otherwise} \end{cases} \\ & \text{for } \exists c,n_0,a \ge 1, b \gt 1 \end{aligned} T(n)={aT(n/b)+f(n)cif n>n0if otherwisef
分割統治とマスター定理の紹介
基本的な分割統治は，最悪実行時間をT(n)T(n)T(n)とすると， T(n)={O(1)(n=1)2T(n2)+O(n)(otherwise) T(n) = \begin{cases} O(1) &(n =1)\\ 2T(\frac{n}{2}) + O(n)&(otherwise) \end{cases} T(n)={O(1)2T(2n)+O(n)(n=1)(otherwise) という形で書き表すことができ，T(n)=O(nlogn)T(n) = O(n \log n)T(n)=O(nlogn)であることが知られています このことは，図で書き表すことによりすぐにわかります．つまり，12\frac{1}{2}21になっていくのでn=1n=1n=1にlogn\log nlogn回の再帰でたどり着き，各深さで合計O(n)O(n)O(n)しかかからないのでO(nl
最適輸送の解き方
最適輸送問題（Wasserstein 距離）を解く方法についてのさまざまなアプローチ・アルゴリズムを紹介します。 線形計画を使った定式化の基礎からはじめて、以下の五つのアルゴリズムを紹介します。 1. ネットワークシンプレックス法 2. ハンガリアン法 3. Sinkhorn アルゴリズム 4. ニューラルネットワークによる推定 5. スライス法 このスライドは第三回 0x-seminar https://sites.google.com/view/uda-0x-seminar/home/0x03 で使用したものです。自己完結するよう心がけたのでセミナーに参加していない人にも役立つスライドになっています。 『最適輸送の理論とアルゴリズム』好評発売中！ https://www.amazon.co.jp/dp/4065305144 Speakerdeck にもアップロードしました: https
高速逆平方根(fast inverse square root)のアルゴリズム解説 - 滴了庵日録
高速逆平方根とは？ C言語のコード 検証 アルゴリズムの要点 [1] 逆平方根の計算を対数・指数の計算に置き換える [2] 浮動小数点型の内部表現を利用した対数・指数の近似計算 [2.1] 対数の近似 [2.2] σの最適値 [2.3] 整数型での解釈 [2.4] 逆平方根の計算とマジックナンバー0x5F3759DF [3] ニュートン法による収束で精度アップ 感想 高速逆平方根とは？ 高速逆平方根(fast inverse square root)とは、平方根の逆数 を高速に計算するアルゴリズムです。平方根の逆数は逆平方根とも呼ばれます。逆平方根はベクトルの正規化などに用いられるので、これを高速に計算できるアルゴリズムには大きなご利益があります。 参照： Fast inverse square root - Wikipedia C言語のコード 高速逆平方根の関数を示します。0x5F375
N番目の素数を求める - すぎゃーんメモ
SNSなどで話題になっていたので調べてみたら勉強になったのでメモ。 環境 Pythonでの実装例 例1 例2 例3 エラトステネスの篩 Rustでの実装例 試し割り法 エラトステネスの篩 アトキンの篩 おまけ: GMP Benchmark 高速化のテクニック 上限個数を見積もる Wheel factorization オチ Repository References 環境 手元のMacBook Pro 13-inchの開発機で実験した。 2.8 GHz Intel Core i7 16 GB 2133 MHz LPDDR3 Pythonでの実装例 例1 最も単純に「2以上p未満のすべての数で割ってみて余りが0にならなかったら素数」とする、brute force 的なアプローチ。 import cProfile import io import pstats import sys def m
Sign in - Google Accounts
Not your computer? Use a private browsing window to sign in. Learn more about using Guest mode
A walk through the SA-IS algorithm - Screwtape's Notepad
A walk through the SA-IS Suffix Array Construction Algorithm¶ Some time ago, while looking for solutions to some string-searching problem I was having, I stumbled across the Suffix Array data-structure. It seemed promising, so I looked up the algorithm Wikipedia recommended (the “SA-IS” algorithm from the paper “Linear Suffix Array Construction by Almost Pure Induced-Sorting” by G. Nong, S. Zhang
接尾辞配列(Suffix Array) - Shogo Computing Laboratory
接尾辞配列(Suffix Array)は，全文検索などに用いられるデータ構造です． それ以外にも，単語の出現回数を高速に求められたり， データ圧縮に使えたりなど，様々な応用例が提案されています． 2012年現在，SA-ISと呼ばれる手法がもっとも効率的に Suffix Array を求められるようです． その基礎となる考え方を１つずつ見ていくことにしましょう． Suffix Arrayとは Suffix Array とはどんなものなのでしょう？ 定義にそった，もっとも簡単なアルゴリズムを紹介します． バケットソート 基数ソートとバケットソートは，ソートする対象の種類が有限で範囲がはっきりしている場合に 非常に有効なソート手法です． これを使って Suffix Array を求めてみます． 2段階ソート 隣り合った接尾辞の比較は非常に簡単にできます． ことのことを利用してソートを高速化します
SA-IS 法のメモ - まめめも
suffix array を線形時間で構築する SA-IS 法についてのメモです。 SA-IS 法の解説はわりと世の中にいっぱいありますが、実際のプログラムにする方法がよくわからなったり、どうしてそれでうまく行くのか書かれてなくて気持ち悪かったりするものが多くて、自分の望む感じのものがありませんでした。アルゴリズムは当然プログラムで見たいし、厳密な証明は要らないけど直観的な理由は知りたい。 ということで、自分なりの理解を書いてみました。 suffix array とは 文字列の suffix とは、文字列の途中から最後までの部分文字列のことです。題材の文字列を "mmiissiissiippii" とすると、次の 17 個の部分文字列です。 0 mmiissiissiippii$ 1 miissiissiippii$ 2 iissiissiippii$ 3 issiissiippii$ 4
Suffix Array - Qiita
これは「データ構造とアルゴリズム Advent Calendar 2018」9日目の記事です． はじめに Suffix array1 はよく知られたデータ構造のひとつです．1990年に提案2されて以来，その使われ方は多岐にわたります．本記事では，この suffix array の基本事項として， suffix array とは何か suffix array を全文索引として用いる方法 を紹介したいと思います． パターンマッチングと全文索引 パターンマッチング とは，文字列 $T$ から，パターンと呼ばれる文字列 $P$ を探す問題です．たとえば， $T =$ 麒麟鼬蝙蝠駱駝蝦蟇鼈樹懶鼠膃肭臍羆狒狒鰐麒麟猩猩鼠鼠鼠鼠鼠蟒蛇鼈鼬羆蜥蜴駱駝羆麒麟鼈鼬狒狒狒狒羆蝙蝠膃肭臍麒麟蝙蝠鼬蜥蜴鼬狒狒蝮樹懶鼬羆蝮膃肭臍麒麟羆駱駝蝙蝠蟒蛇狒狒蝙蝠樹懶鼈蜥蜴駱駝羆鼬羆樹懶犀鰐蝙蝠鼠狒狒蝦蟇鼬蜥蜴鼠蝮蝦蟇蜥蜴龍麒
Theory of Algorithms
平成26年度2-2期・I431アルゴリズム論(Theory of Algorithms) 本ページは平成26年度2-2期にJAISTの石川キャンパスで 開講されている『I431アルゴリズム論(Theory of Algorithms)』の授業のページです． 担当は上原隆平(Ryuhei UEHARA)です． サポート情報 基本情報 シラバス| Syllabus 教場: I2講義室 講義時間(Lectures): 水曜日1時限(Wed:9:20〜10:50)・金曜日2時限(Fri:11:00〜12:30) オフィスアワー(Office Hour):水曜日3時限(Wed:13:30〜15:00) 教室での授業を録画したビデオ(Videos taken in the classroom) 大学内のみ視聴可能で，Windows 上の IE のみ対応しているようです． (It is availabl
Sorting 1 million 8-decimal-digit numbers with 1 MB of RAM
I have a computer with 1 MB of RAM and no other local storage. I must use it to accept 1 million 8-digit decimal numbers over a TCP connection, sort them, and then send the sorted list out over another TCP connection. The list of numbers may contain duplicates, which I must not discard. The code will be placed in ROM, so I need not subtract the size of my code from the 1 MB. I already have code to
大規模データを解析するストリーミングアルゴリズムをサクッと見てみる
こんにちは、プレイドの @makinoy といいます。 私たちはKARTEというサービスを提供していますが、解析色が非常に強いサービスなので社内では解析周りのアルゴリズムの利用検討をよく行っています。 その流れで、最近ストリーミングアルゴリズムについて検討したので、代表的なものをちょっとここで書いてみることにします。 この紹介では、”大規模データ解析のためのストリーミングアルゴリズムをサクっと見てみる”をテーマにしようと思います。 ストリーミングアルゴリズムとは、一連のデータの流れであるストリームを処理するアルゴリズムです。 データは次々にやってくるので、基本的にひとつのデータ単位（イベント）に対して１回だけ処理をするのが特徴です。大量なデータを処理するために、ひとつのイベントに対して、短い計算時間で限られたメモリを使うところも特徴のひとつです。 そのアルゴリズムの代表的なものを、適当にピ
バレンタインデーにquadsortがやってきた・・・けど - Qiita
quadsortとは？ それはバレンタインデーにやってきた 「なんか、qsortよりも良い結果がでたっぽいんだけど！」という話がでてきて、みんな色々検証をしていた。 もとスレッドは「モダンってなんだよ！」とか「それならこっちのアルゴリズムとか見たほうが良いんじゃ？」とか、なかなかエキサイティングしているっぽい。 ソースコードとか技術的な説明はこちら。 性能検証結果 qsort: sorted 1000000 elements in 0.101402 seconds. (random order) quadsort: sorted 1000000 elements in 0.000912 seconds. (forward order) qsort: sorted 1000000 elements in 0.027091 seconds. (forward order) quadsort:
GitHub - scandum/quadsort: Quadsort is a branchless stable adaptive mergesort faster than quicksort.
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
SA-IS
プログラミングコンテストでの乱択アルゴリズム
競技プロ的なアルゴリズムのスライドのまとめ Wiki - yukicoder
[PDF]陣内佑 (2020) ヒューリスティック探索入門
