FM-indexによる全文検索
4. 前処理１：接尾辞配列の構築 0 mississippi$ 1 ississippi$ 2 ssissippi$ 3 sissippi$ 4 issippi$ 5 ssippi$ 6 sippi$ 7 ippi$ 8 ppi$ 9 pi$ 10 i$ 11 $ 11 $ 10 i$ 7 ippi$ 4 issippi$ 1 ississippi$ 0 mississippi$ 9 pi$ 8 ppi$ 6 sippi$ 3 sissippi$ 5 ssippi$ 2 ssissippi$ 辞書順でソートする ※$は任意のアルファベットよりも 順位が小さいとする 接尾辞配列SA
"リトライ"の実装: Truncated Binary Exponential Backoff - Qiita
exponential backoff はシステムが許容可能な速度を見つけるために各処理の実行速度を遅延させるためのアルゴリズムです。簡単に言えば最適なリトライ ─ 例えば通信が切断された時に自動で再接続するまでの遅延時間を計算する方法のこと。exponential backoff は連続失敗回数を $n$ とした時に $0$ から $x^{n-1}$ までの間の乱数を使用する。 よく使われているアルゴリズムは $2$ のべき乗で計算する binary exponential backoff というもの。 $t = a \times 2^{n-1}$ $t$, $a$ を秒とした場合、1回目のリトライは $0～a$[sec]、2回目のリトライは $0～2a$[sec]、3回目のリトライは $0～4a$[sec]、... の間のランダムに選んだ時間をおく。 ただこの式だけでは $t$ がすぐ
Elsevier · Herlihy, Shavit: The Art of Multiprocessor Programming · Welcome
Discover Books & Journals by subject Life sciences Agricultural & Biological SciencesDrug DiscoveryImmunologyLife SciencesMicrobiology & VirologyNeurosciencePharmaceutical SciencesPharmacologyToxicologyPhysical sciences & Engineering Astronomy, Astrophysics, Space ScienceBuilt EnvironmentChemical EngineeringChemistryComputer ScienceEarth & Planetary SciencesEnergy & PowerEngineering & TechnologyEn
文字列アルゴリズムの学びかた - Hatena Developer Blog
こんにちは！はてなアプリケーションエンジニアの id:takuya-a です。 みなさんは、このような疑問をもったことはありませんか？ grep はどのように文字列を検索しているのか？ MeCab はどうやって辞書を高速にルックアップしているのか？ パーサやコンパイラを作りたいけど、何から始めればいいのか？ 本稿では、「文字列アルゴリズムとはどんなものなのか？」「なぜ重要なのか？」「何を知っておくべきか？」「どうやって勉強すればいいのか？」といった疑問にお答えしていこうと思います。 文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。 このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんに
アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP
計算量 † アルゴリズムがどれだけ効率的かを示す概念が計算量です。通常、単に計算量と述べた場合は、データ数nに対してどれだけ時間がかかるかを示す時間計算量を指しますが、場合によってはどれだけメモリを消費するかを示す空間計算量を問題にするケースもあります。計算量は、通常データ数nが十分大きい場合にnのどういう関数に比例して計算時間／メモリ消費が増えるかという形式で表します。 具体的に、下に述べている線形探索の例で計算量を考えてみましょう。この関数では、ループをサイズn回だけ回していますが、このループ1回辺り時間tだけかかるとしましょう。さらに、関数の呼び出し等により、データ数にかかわらず一定の時間sがかかると考えられます。従ってこの関数に費やす時間はnt+sですね。この時、十分大きいnを考え、かつ定数倍は無視して考えます。例えばntがsの10000倍だと仮定しましょう。この時sの寄与は、体重
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Practical String Searching
A very fast substring search algorithm
ESMAJ : EXACT STRING MATCHING ALGORITHMS