画期的（？）なソートアルゴリズム「Sleep Sort」 | gihyo.jp
ソートアルゴリズムにはクイックソートやマージソートといった伝統的なものから、PythonやJava 7のデフォルト実装になっている「Timsort」までいろいろな種類があります。中には正しいソート順になるまでひたすらシャッフルし続ける「Bogosort」のようなジョークアルゴリズムもあります。これから紹介するアルゴリズムもそのうちの一つに入るかもしれません。 「4chan」という2ちゃんねるに似たアメリカの匿名掲示板があり、そのプログラミング板にて「Genius sorting algorithm: Sleep sort」というスレッドが立ちました。2ちゃんねる風に訳すと「ちょwwwすごいソートアルゴリズム思いついたwwwww」といった感じでしょうか。スレッドを立てた1氏は「Sleep Sort」と称したリスト2のようなシェルスクリプト実装を載せています。 ソート対象の数値データを次々にs
B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
Lempel-Ziv-Markov chain-Algorithm - Wikipedia
Lempel-Ziv-Markov chain-Algorithm（略してLZMA）は、2001年から開発されているデータ圧縮アルゴリズムで、7-Zipアーカイバの7zフォーマットやXZ Utilsのxzフォーマットで使用されている。LZMAは、LZ77に少々類似した辞書式圧縮法（英語版）を使用し、通常bzip2以上の高い圧縮率と伸張速度、および最大4GBのサイズ可変な圧縮辞書を特徴とする。 LZMA2は、圧縮されていないデータとLZMAデータの両方を含むことができ、複数の異なるLZMAエンコーディングパラメータを含むことができる単純なコンテナ形式である。 LZMA2は、任意にスケーラブルなマルチスレッドの圧縮と展開と、部分的に非圧縮データの効率的な圧縮をサポートする。 LZMAは、改良LZ77圧縮アルゴリズムと、バックエンドにレンジコーダー（Range Coder）を使用している。 辞書
SubversionのDiffをC++に移植
何ですかこれは？ 二つのシーケンスのLongest Common Subsequence, Longest Common Subsequence Distance及びShortest Edit Scriptを求めるクラス。 Subversionのコードを、C++に移植したものです。 アルゴリズムは、"An O(NP) Sequence Comparison Algorithm" (Sun Wu et al.)に述べられているものと同一で、計算量は最悪でO(NP)、平均的にはO(N+PD)です。ただし、N=二つのシーケンスの長さの和、P=D/2-Δ/2、D=LCS距離、Δ=二つのシーケンスの長さの差です。 ここでいうLCS距離(longest common subsequence distance)は、あるシーケンスを別のシーケンスに変化させるために必要な、シンボルの挿入及び削除操作の最小
HyperHyper EstraierEstraierのの 設計と実装設計と実装 株式会社ミクシィ 平林 幹雄 mikio@users.sourceforge.net 2006年11月6日 「オープンソースの全文検索、DBMSシステム」 講演資料 アジェンダアジェンダ
HyperHyper EstraierEstraierのの 設計と実装設計と実装 株式会社ミクシィ 平林 幹雄 mikio@users.sourceforge.net 2006年11月6日 「オープンソースの全文検索、DBMSシステム」 講演資料 アジェンダアジェンダ • Hyper Estraierの概要 • N.M-gramインデックス • スケールアウト戦略 HyperHyper EstraierEstraierの概要の概要 HyperHyper EstraierEstraierとはとは • 読み方 – ハイパーエストレイ(ア|ヤ)(ー)? – estraier： [古仏] 迷う、はぐれる = stray • 全文検索システム – 大量の文書を対象に「フリーワード検索」ができる – 予め転置インデックスを用意することで高速に処理 • 文書規模Nに対する時間計算量 – 全体のインデク
どうなっているの？あのソフトの仕組み - 今からでも遅くない！アルゴリズム入門：selfup
Webの全体像を効率よく取り込み，分類する 「YSTのシステムは大まかに三つの機能に分かれます（図2）。最初は世界中のWebページをYSTのシステムに取り込む『クローリング（crawling）』という機能です」（Yahoo! JAPAN，リスティング事業部 検索企画室の宮崎光世氏，以下同）。 取り込むと簡単に言っても，Webページの数は膨大なうえ，更新の頻度や情報の質などがまちまちです。すべてのページに同じようにアクセスしていると非効率なことこの上ありません。そこで，限られた時間で質の良い検索ができるようにするための工夫をしています。例えば，クローリングを繰り返すうちに頻繁に更新されることがわかったページは短いサイクルでチェックし，ほとんど更新のないページはチェックの頻度を落とす，といったことをしているそうです。 ただ，更新の頻度が単に高いだけではダメです。重要性が高いと考えられるWebサ
[を] Suffix Array の解説文書のリンク集
Suffix Array の解説文書のリンク集 2006-04-10-3 [Algorithm] Suffix Array について解説している日本語による文書のうち、 Webで閲覧できるもののリンク集。随時更新予定。 - 用語解説: Suffix Array (PDF) via http://nais.to/~yto/tools/sufary/ - Suffix Array の解説 in D論 (PDF) via http://nais.to/~yto/tools/sufary/ - 横着プログラミング 第9回: sary: Suffix Array のライブラリとツール http://0xcc.net/unimag/9/ - Suffix Arrayの簡単な説明 http://sary.sourceforge.net/docs/suffix-array.html
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.ricoh.co.jp/rdc/techreport/No27/Ronbun/A2705.pdf