The document discusses and benchmarks various string search algorithms, including Quick Search, strstr, and a custom implementation using SSE4.2 instructions. It finds that for short substrings, strstr in GCC utilizing SSE4.2 performs best, while for longer substrings, a modified Quick Search algorithm is faster. The author's own implementation using pcmpestri outperforms all other algorithms, bei
結局、やり出したら止まりません。私は以前、” I Wrote a Fast Hashtable(私が書いた高速なハッシュテーブル) “という記事と、それに次いで” I Wrote a Faster Hashtable(私が書いたより高速なハッシュテーブル) “という記事をブログにアップしましたが、今回ついに、最速のハッシュテーブルを書き上げました。これが意味するところは、ルックアップがどのハッシュテーブルよりも速いということです。それに加えて、挿入や削除も(最速とまではいかないまでも)非常に速く行えます。 秘訣は、探索回数の上限を設定したロビンフッドハッシュ法を使用することです。ある要素が、その理想的な位置からX数以上、離れた位置にある場合、テーブルを拡張することで、全ての要素が、その大きなテーブル内において、理想的な位置に近づくようにします。結果的に、このやり方は非常にうまくいきました。
あなたは円周率を何桁言えますか。3.14159…という、あの数字です。 円周率の小数部分は無限に続き、循環することもありません。 古来より、数学者は円周率の値を様々な幾何学的な近似や公式を用いて計算してきました。 その桁数は計算機の発明により飛躍的に伸び、収束の速い公式の発見や効率の良いアルゴリズムの発明などによって加速してきました *1。 5年前、私がまだ学生だった頃、円周率1億桁の計算に挑んだことがありました。 私にとって高精度計算の初めての挑戦で、様々な試行錯誤で苦労したのをよく覚えています。 itchyny.hatenablog.com 2017年現在、円周率計算の世界記録は22兆桁です。 円周率計算の歴史をご覧いただくとよく分かると思いますが、近年の円周率計算の世界記録からは次のような特徴が読み取れます。 2002年に1兆を超え、最新の記録 (2016年) は22兆桁 (10進数
essential information that every serious programmer needs to know about algorithms and data structures Online content. This booksite contains tens of thousands of files, fully coordinated with our textbook and also useful as a stand-alone resource. It consists of the following elements: Excerpts. A condensed version of the text narrative, for reference while online. Lectures. Curated studio-produc
This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms. All the features of this course are available
(注:2017/02/06、いただいたフィードバックを元に翻訳を修正いたしました。修正内容については、 こちら を参照ください。) Dependency HellはNP完全ですが、この状況から脱却できるかもしれません。 パッケージにおけるバージョン選択の問題とは、完全である(全ての依存関係を満たしている)かつ互換性のある(互換性のない2つのパッケージが選択されていない)トップレベルパッケージPをビルドするために使われる依存関係の集合を見つけることです。ただし、菱形依存問題があるので、このようなセットは存在しない可能性があります。菱形依存問題とは、AはBとCが必要、BはDのバージョン2ではなくバージョン1が必要、CはDのバージョン1ではなくバージョン2が必要といったような問題のことです。この場合、Dの両方のバージョンを選択することはできないため、Aをビルドすることができないわけです。 パッケ
Twitter連携とmixi連携を付けてみた。 はてなブログの使い方を練習しつつ連投する。 例によってこの本 確率と計算 ―乱択アルゴリズムと確率的解析― 作者: Michael Mitzenmacher,Eli Upfal,小柴健史,河内亮周出版社/メーカー: 共立出版発売日: 2009/04/24メディア: 単行本購入: 2人 クリック: 31回この商品を含むブログ (11件) を見る の話の続き。 そういえば。 この本に、バケツソートはある条件下で平均のソートができる、ということが書いてあって面白かった。ソートの下界はなのだが、条件を付ければ線形まで落とせるようだ。詳細はググればすぐに出そうなので書かないけれど、この内容で分割統治の力を再認識した。 分散も分割が基本戦略になると思うのだけれど、分割はいいとしてその統合(MapReduceで言うところのReduce)の実装って実はとても
なんとなくアルゴリズム系の読み物読んでみたかったので読んだ。 世界でもっとも強力な9のアルゴリズム 作者:ジョン・マコーミック日経BPAmazon この本は、著者が3つの基準で選んだ「偉大なアルゴリズム」について、エンジニアでなくても分かるような簡単な言葉を使って紹介してくれる本である。以下のようなアルゴリズムについて紹介している。 検索エンジンのインデクシング ページランク 公開鍵暗号法 誤り訂正符号 パターン認識 データ圧縮 データベース デジタル署名 話題がかなり身近なものであり、説明が本当にわかりやすいため、とりあえずアルゴリズムを学ぶ前の読み物として非常におすすめ。個人的には検索エンジンやページランク、パターン認識あたりが興味深かった。この本を読んで、興味を持った部分について、さらに深く学習をしていくと良いかもと思った。 読書メモ ## 検索エンジンのインデクシング - 検索エン
Intersection of sorted lists is a cornerstone operation in many applications including search engines and databases because indexes are often implemented using different types of sorted structures. At GridDynamics, we recently worked on a custom database for realtime web analytics where fast intersection of very large lists of IDs was a must for good performance. From a functional point of view, w
こんにちは!はてなアプリケーションエンジニアの id:takuya-a です。 みなさんは、このような疑問をもったことはありませんか? grep はどのように文字列を検索しているのか? MeCab はどうやって辞書を高速にルックアップしているのか? パーサやコンパイラを作りたいけど、何から始めればいいのか? 本稿では、「文字列アルゴリズムとはどんなものなのか?」「なぜ重要なのか?」「何を知っておくべきか?」「どうやって勉強すればいいのか?」といった疑問にお答えしていこうと思います。 文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。 このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんに
Go言語でSA-IS(Suffix Array - Induced Sorting)を実装しました。SA-ISは接尾辞配列(Suffix Array)の構築アルゴリズムです。本記事の内容は次の3本になります。 Go言語で実装したSA-IS(go-sais)について紹介します SA-ISのアルゴリズムについて解説します Go言語の入門書を執筆しました Go言語のSA-IS実装 Go言語の標準パッケージには、既に接尾辞配列の実装(index/suffixarray)が存在します。標準パッケージのソースコードを見たところLarsson-Sadakane法(qsufsort)であったため、より高速と言われているSA-ISを実装しました。 実装内容 SA-ISは接尾辞配列の構築部分のアルゴリズムです。そのため、構築部分の実装のみ標準パッケージから置き換えています。接尾辞配列を使用した検索部分やテスト
,. -‐'''''""¨¨¨ヽ (.___,,,... -ァァフ| あ…ありのまま 今日 起こった事を話すぜ! |i i| }! }} //| |l、{ j} /,,ィ//| 『BWT について調べていたら Suffix Array のライブラリができていた』 i|:!ヾ、_ノ/ u {:}//ヘ |リ u' } ,ノ _,!V,ハ | /´fト、_{ル{,ィ'eラ , タ人 な… 何を言ってるのか わからねーと思うが /' ヾ|宀| {´,)⌒`/ |<ヽトiゝ おれも何をされたのかわからなかった… ,゙ / )ヽ iLレ u' | | ヾlトハ〉 |/_/ ハ !ニ⊇ '/:} V:::::ヽ 頭がどうにかなりそうだった… // 二二二7'T'' /u' __ /:::::::/`ヽ /'
Fast Lossless Compression of Scientific Floating-Point Data Paruj Ratanaworabhan, Jian Ke, and Martin Burtscher Computer Systems Laboratory School of Electrical and Computer Engineering Cornell University, Ithaca, NY 14853 {paruj, jke, burtscher}@csl.cornell.edu Abstract In scientific computing environments, large amounts of floating-point data often need to be transferred between computers as wel
Research Differentiable neural computers Published 12 October 2016 Authors Gregory Wayne, Alexander Graves In a recent study in Nature, we introduce a form of memory-augmented neural network called a differentiable neural computer, and show that it can learn to use its memory to answer questions about complex, structured data, including artificially generated stories, family trees, and even a map
[WIP: 時間あるときに書きます] 先日発表された論文の適当訳. 実験の部分などは面倒くさいので訳してないです. ANNは変数とかデータ構造とかうまく扱えない. コンピュータのように外部メモリを持たせることで, これを解決する. 実験では, 最短経路問題を解かせるとか, 家系図の人物間の関係を答えるなどができた. 重要なのは, こういった問題を, アルゴリズム(ダイクストラ法etc)を設計する必要なしに, データドリブンにend-to-endで学習し解くことができるという点. https://deepmind.com/blog/differentiable-neural-computers/ http://www.nature.com/nature/journal/vaop/ncurrent/full/nature20101.html 関連(してそうなとこ) https://arxiv.
Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く