echizen_tm https://blog.hatena.ne.jp/echizen_tm/ EchizenBlog-Zwei https://echizen-tm.hatenadiary.org/ 計算機科学 ちょっと前に「4人のロシア人の方法(Method of Four Russians)」というのを論文で見かけて面白かったので紹介しておく。 簡単に言ってしまうと、ある処理を高速化したい時にデータ全体を小さなブロックに分割してブロック単位での結果を事前に計算したテーブルで持っておくよ、というアルゴリズム。 名前は知らなくてもアルゴリズム自体は知ってる人は多いかもしれない。 Method of Four Russians - Wikipedia, the free encyclopedia アルゴリズム自体は汎用的なものだが編集距離の高速化を例として説明するのが一般的なようなのでそれに倣う。 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fechizen-tm.hatenadiary.org%2Fentry%2F20120520%2F1337516536" title="「4人のロシア人の方法」で編集距離を高速化する - EchizenBlog-Zwei" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2012-05-20 21:22:16 rich https://echizen-tm.hatenadiary.org/entry/20120520/1337516536 1.0 100%