ESMAJ : EXACT STRING MATCHING ALGORITHMSContents EXACT STRING MATCHING ALGORITHMS Animation in Java Christian Charras - Thierry Lecroq Laboratoire d'Informatique de Rouen Université de Rouen Faculté des Sciences et des Techniques 76821 Mont-Saint-Aignan Cedex FRANCE
50以下挿入ソート、5万以下マージソート、あとはクイックソート | TECHSCORE BLOG | TECHSCORE BLOG
こんにちは、鈴木です。 TECHSCORE Advent Calendar 2014 の 6 日目の投稿です。 寒くなってきたのでソーティングアルゴリズムをいくつか実装して、速度を比較しました。 測定用のプログラムは以下の場所で公開しています。 https://github.com/suzuki-kei/sorting-algorithm 測定結果 まずは測定結果です。 ランダムな整数（int 型）の配列をソートする C++ のプログラムを書いて比較しました。 背景が黄色のセルはその条件（データ数）で最も速かったもの、背景がピンクのセルは 2 番目に速かったものです（時間がかかりすぎて測定を打ち切ったものはグレーです）。 データ数は 2 のべき乗にしたので厳密に速度が逆転するデータ数は分かりませんが、 データ数が 50 以下なら挿入ソート (Insertion Sort) データ数が 5
アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 : 404 Blog Not Found
2009年01月31日01:00 カテゴリLightweight LanguagesMath アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 これなのですが.... 同じ文字列のn回繰り返しを作る最速の方法を探求してみた - muddy brown thang ちょっとした事情により、ある文字列のn回繰り返しを作る関数 (PHPでいうところのarray_repeat(), Perlで言うところの「"..." x n」、RubyやPythonで言うところの「"..." * n」) を高速に実装しなければならない状況に遭遇したのでベンチマークをとってみたところ、その結果がとても新鮮で驚いたので、これを共有しつつもダメ出ししてもらえないかなーと思って晒してみることに。 なぜかもっとシンプルな奴がなかったので。 以下、比較。初期値はIEにあわせてあります。Firefox/Saf
シマンテック、ハッシュアルゴリズム「SHA-1」利用停止までのロードマップを解説
シマンテックは2014年2月5日、Webサイト閲覧を安全に行うために使われる電子証明書で利用されるハッシュアルゴリズムを、現在の「SHA-1」から「SHA-2」へ移行を促すための解説を行った。 WebブラウザーでSSL通信を行うためには、（1）ブラウザーなどにルート証明書を入れること、（2）認証局がSSLサーバー証明書を発行すること、（3）Webサイト管理者が正しくSSLサーバー証明書をインストールすることの3つの条件がそろうことが必要だ。 暗号化通信を始める場合、利用者がブラウザーを使ってWebサーバーにアクセスすると、WebサーバーはSSLサーバー証明書、中間認証局証明書をブラウザーに向け送付する。送付されたSSLサーバー証明書が、シマンテックをはじめとする正しい証明書発行機関のものかどうかを判断するため、ハッシュアルゴリズムを適用し、ハッシュ値を算出する。このとき使われているのが、S
Inflate 実装を作って PDF.js の凄さを思い知った話 (前編) : document
4月25 Inflate 実装を作って PDF.js の凄さを思い知った話 (前編) はじめに まずは宣伝から。 このたび JavaScript で Inflate の実装を行いました！ GitHubで公開中で MIT License です。（以前作った Deflate 実装もセットになってます） https://github.com/imaya/zlib.js このエントリーでは、本来ならいかに自分の実装がスゴいかを紹介するところなのですが、前編では自分よりはるか以前に公開された PDF.js の Inflate 実装の素晴らしさを、最適化を進めるにつれて思い知ったのでご紹介させていただくことにします。 バッファ管理の効率の良さ 最初は気持ち悪いと思っていたのですが、一番よく考えてるなと思ったのがバッファ管理です。 PDF.js は Typed Array でバッファを持っているのですが
高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは2003年に提案されたデータ構造、wavelet tree（以下「WT」と表記）です。WTは圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。WTは文字列T[0...n-1]が与えられた時、次の2つの操作を定数時間でサポートします。 rank(p, c)――T[0...p]中のcの出現回数を返す select(i, c)――(i+1)番目のcの位置を返す WTの作業領域量は、文字列をそのまま保存した時の約2倍程度です。 対象読者 C++の
古くて新しい自動迷路生成アルゴリズム - やねうらおブログ(移転しました)
最近、ゲーム界隈ではプロシージャルテクスチャー生成だとか、プロシージャルマップ生成だとか、手続き的にゲーム上で必要なデータを生成してしまおうというのが流行りであるが、その起源はどこにあるのだろうか。 メガデモでは初期のころから少ないデータでなるべくど派手な演出をするためにプロシージャルな生成は活用されてきたが、ゲームの世界でプロシージャル生成が初めて導入されたのは、もしかするとドルアーガの塔(1984年/ナムコ)の迷路の自動生成かも知れない。 なぜ私が迷路のことを突然思い出したのかと言うと、最近、Twitterで「30年前、父が7年と数ヶ月の歳月をかけて描いたA1サイズの迷路を、誰かゴールさせませんか。」というツイートが話題になっていたからである。 この迷路を見て「ああ、俺様も迷路のことを書かねば！俺様しか知らない(?)自動迷路生成のことを後世に書き残さねば！」と誰も求めちゃいない使命感が
汎用ソート殺し - d.y.d.
00:26 12/12/18 BookLive! 7月に出会ってからずっと電子書籍ストアとして BookLive! をひいきにしているのですが、一体どこが好きなのか語りたくなりました。 ITMedia の これでもう迷わない、電子書店完全ガイド という一連の記事の、 電子書籍の端末の話よりストアの話をしましょうよというコンセプトに思いっきり影響されています。 といっても、第一印象が「普通のことが普通にできるので感激した！！」というもので、 つまり今年の前半に使っていた幾つかの電子書籍ストア/専用アプリが残念だっただけかもしれません。 買った本がどこをクリックすれば読めるのか理解するのに10分かかった、とか、 6冊以上買うと本棚アプリから画面外に本がはみ出るので手でいちいち棚を変えて整理しないと読めない、とか。 本当に普通に使えるという以上に特筆することもないんですが、 あ、でも、今年になる
アルゴリズムを学ぼう
関連サイト出版社による関連ページが公開されています。 アルゴリズムを学ぼう (KADOKAWA/アスキー・メディアワークス) 関連書籍本書の続編『続・アルゴリズムを学ぼう』も好評発売中です。 内容紹介本書のテーマは、ガチのアルゴリズムとデータ構造、そして計算量です。 いや、確かに本書は女の子がいろいろでてきたり、小話が入っていたりと、ゆるふわなオーラが漂っています。しかし、あえていいましょう。それは、見かけだけである、と。 プログラミングを学ぶにあたって、アルゴリズムとデータ構造は、どの言語を用いるにしてもすべての基礎であり、避けて通ることはできない道です。アルゴリズムとデータ構造を知らずにプログラムを書くことは、無免許で車を運転するぐらいに危険な行為です。 しかし、アルゴリズムとデータ構造をきちんと理解せずに、プログラムを書いているプログラマーが多数いるのも事実です。それは、アルゴリズム
Algorithm - 連想配列の実装としてのハッシュはオワコン? : 404 Blog Not Found
2012年01月17日11:45 カテゴリアルゴリズム百選Tips Algorithm - 連想配列の実装としてのハッシュはオワコン? 珠玉のプログラミング Jon Bentley / 小林健一郎訳 つまり「終わったコンテナ」。 以前からうすぼんやりと考えて来た危惧が、すこしはっきりと見えてきた。 徳丸浩の日記: Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 もうそろそろハッシュ(テーブル)以外の手段の連想配列の実装手段を本格的に模索するべきではないか、と。 そのデータ構造は、君の魂を差し出すに足るものかい? 連想配列(Associative array)がコレクション(Collection)、すなわち数多のデータ構造をまとめるデータ構造としての覇者となったのはもはや疑いようがない事実でしょう「配列で実装されるデータ構造ではなくて、配列を実装するデータ構
Algorithm - Suffix Array を JavaScript で再発明してみた : 404 Blog Not Found
2012年01月16日16:30 カテゴリアルゴリズム百選Lightweight Languages Algorithm - Suffix Array を JavaScript で再発明してみた WEB+DB 総集編 [Vol. 1〜60] もう10年以上前に某社のCTOだったころ、Suffix array(接尾辞配列)の解説を毎週の技術者ミーティングでしたら一名を除いて「ハァ?」状態だったことを思い出しつつ。 Suffix Arrayは何が画期的だったのか? 以下は、計算機科学者でなくても直感的に理解できると思います。 ソートされていない通常のデータの中にあるサブデータ(キー)を検索しようとすると、データの大きさに比例した時間(O(n))がかかる。 ソート済みのデータであれば、二分探索でデータの大きさの対数時間(O(logn))でキーを検索できる。 さらにキーからIDを定数時間で作成でき
RE: sort を使うときは，LC_ALL=C を忘れずに - ny23の日記
Twitter ID も livedoor ID もないので直接コメントできないが，sort (GNU coreutils) の名誉のために，ここにメモしておく． 404 Blog Not Found:algorithm - bucketsort.[ch] - 汎用かつlibcの*sortより高速な まず第一印象として，この程度のサイズのファイルのソートで sort (GNU coreutils) がいまどきこんなに遅いはずはない．LC_ALL=C で追試すると，やはり bucketsort との差は無くなった．上の記事（に対するツイート）は Twitter 上でもそれなりにリツイートされているように見えるのだけど，この実行時間に違和感を感じる人が全くいないのはどういうことなのだろうか．sort を実際に使う人がほとんど見ていないのか，それとも計算量が違うから速くて当然という思い込みか．
アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
仕事でコードを書いていますがどうしても同期と比べて仕事が遅いです。早くコードを書くコツや短くまとめるコツなどがあれば教えてほしいです。あと普段どんなことを意識してコー��
私は昔、趣味で作っていたアプリに機能を「追加」する度に、アプリケーション(実行ファイル)の総サイズを「減らす」、というのを繰り返していたよ。速度も同様に。 これによって「あるパターンはこう簡潔に直せる」というパターン知識が積み上がっていった気がするな。 さらに、それを実現する過程で、限界に見えた状況を打開するために色んな既存アルゴリズムを勉強して実際に使って身につけていくことになった。 ある問題があるときに、的確に適合するアルゴリズムや構成が発見(選択)できると、劇的に簡潔になることがある。そこにたどり着けるかどうか考えるのが楽しい。 あと、同じコードを何年も「育てる」という経験をすると、保守性の低いコードがどう困るかが身に染みるようになるよね。ソースコードは「人が読む物」でもあり、読みやすいというのも保守するなら重要なパラメータになる。これはコメントを書けという意味じゃない。コメ
Cuckoo Hashing - Radium Software
ハッシュテーブルからエントリーを検索する処理は，一般に定数時間で済むとされている。つまり，どんなにエントリーが増えても検索の速さは変わらない，ということ。データ構造の教科書には必ず載っていることだね。 でも実際には，ハッシュの衝突が起こった場合に，速度の低下が発生する可能性がある。例えば，一般的なチェイン法（オープンハッシュ）だと，衝突したエントリーに関して線形検索を行うことになるから，衝突が多ければ多いほど，定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing （カッコウ・ハッシング）は仕組みが面白い。こいつは，エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では，２つのハッシュ関数と，２つのテーブルを用いる。ここでは，２つのハッシュ関数をそれぞれ h1, h2 として，２つのテー
せっかくの夏休みだから、今こそまとめて買っておきたいコンピュータ書５冊 - 思っているよりもずっとずっと人生は短い。
と言えばやっぱりこれですよね。 The Art of Computer Programming,Volume 4, Fascicle 0 Introduction to Combinatorial Algorithms and Boolean Functions 日本語版 (ASCII Addison Wesley Programming Se) 作者: Donald E. Knuth,和田英一出版社/メーカー: アスキー・メディアワークス発売日: 2009/10/22メディア: 大型本購入: 1人 クリック: 40回この商品を含むブログ (13件) を見るThe Art of Computer Programming Volume 4, Fascicle 1 Bitwise Tricks & Techniques; Binary Decision Diagarms 日本語版 (ASCII
実用的な同時並行ソートを実装する話 - akihiro4chawonの日記
scala の parallel collection は、普通の collection を使うように使っているだけで、並列計算の恩恵を受けられる場合も多いのですが、そうではない場合も多いです。 その典型例が、ソートです。実は、並列のソートは、まだ実装されていません。 じゃあ、自分で実装すればいいのか、というと、これは半分正しくて半分間違いです。 どういう事かというと、シングルスレッドの java.util.Arrays.sort がとても高速なので、これより速いソートを自前で実装するのは難しいのです。Arrays.sort が速いのは、単にアルゴリズムだけの問題ではありません。自分で Array の整列処理を書くとすると、当然、配列の要素に添字でアクセスしますよね。すると、JVMは配列の範囲内かどうかをチェックしますよね。このオーバヘッドがあるために、java.util.Arrays.s
Home
Knife throwing is both an art and a skill that’s difficult to master...
4chan BBS - Genius sorting algorithm: Sleep sort
1 Name: Anonymous : 2011-01-20 12:22 Man, am I a genius. Check out this sorting algorithm I just invented. #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 Oh god, it works. But I don't like to wait 218382 seconds to sort '(0 218382)
Sleep sortの各言語での実装まとめ – Yuyak
盛り上がってるSleep sort。 僕もどの言語かで実装しようと思ったけどもう色々やられていて悔しいのでまとめてみる。 随時更新。 そもそもの発端 4chan BBS – Genius sorting algorithm: Sleep sort （本家） 常識を覆すソートアルゴリズム！その名も”sleep sort”！ – Islands in the byte stream bash 4chan BBS – Genius sorting algorithm: Sleep sort （本家） 4chan BBS – Genius sorting algorithm: Sleep sort C# 4chan BBS – Genius sorting algorithm: Sleep sort JavaScript 話題のソートアルゴリズム「sleep sort」をJavascriptで実
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
