常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream (legacy)
TwitterのTLで知ったのだが、少し前に海外の掲示板で"sleep sort"というソートアルゴリズムが発明され、公開されたようだ。このアルゴリズムが面白かったので紹介してみる。 Genius sorting algorithm: Sleep sort 1 Name: Anonymous : 2011-01-20 12:22 諸君！オレは天才かもしれない。このソートアルゴリズムをみてくれ。こいつをどう思う？ #!/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 なん…だと
編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが
芸能人の相関関係を探ってみるスクリプト - download_takeshi’s diary
ちょっとした実験をしてみました。芸能人の相関関係を機械的に探索してみます。 具体的には「○○というタレントと関係が深い芸能人は？」といった、芸能人にフォーカスした類似検索みたいな実験です。 技術的には「潜在的意味インデキシング」（Latent Semantic Indexing）といった手法を使います。 これは普通は自然言語処理の世界で使われるテクニックですが、なにも言語だけでなく他のデータ素材でも面白い結果が得られるかもしれないので、やってみようという試みです。 以下に大まかな手順をまとめます。 wikipedia から有名人のリストを抽出 それらの有名人リストについて、一人ずつ「誰と関連が深いか」を集計。具体的には有名人個々のwikipediaのページ中に、先ほど抽出しておいた人名リストとマッチする人名がどれだけ掲載されているかをピックアップしていきます。 上記の方法で有名人の間の相関
ダイクストラ法, 貪欲アルゴリズム - naoyaのはてなダイアリー
現実逃避をしながらウェブを眺めていたら ダイクストラ法（最短経路問題） にたどり着きました。単一始点最短路問題におけるダイクストラ法の解説です。 何を思ったのか、図を眺めていたところ動かしたい衝動に駆られて、気付いたらパワポでアニメーションができていました。 http://bloghackers.net/~naoya/ppt/090319dijkstra_algorithm.ppt 実装もしてみました。隣接ノードの表現は、ここではリストを使いました。 #!/usr/bin/env perl use strict; use warnings; package Node; use base qw/Class::Accessor::Lvalue::Fast/; __PACKAGE__->mk_accessors(qw/id done cost edges_to prev/); package Q
PDL で PageRank - naoyaのはてなダイアリー
id:smly さんが PageRank や HITS を Python で実装 されているのに触発されて、自分も PageRank を Perl で実装してみました。 PageRank の計算の中心になるのは Power Method (べき乗法) です。べき乗法では行列とベクトルの積を計算しますので、手軽に使える行列演算ライブラリがあると楽でしょう。 色々調べてみたところ、PDL (The Perl Data Language) が良く使われているようでしたので、これを選択しました。PDL では各種行列演算が簡単に行える他、文字列評価をオーバーライドして行列の文字列出力を良い具合で定義してくれていたりと、なかなかに便利です。PDL は行列計算以外にも色々な科学技術計算やグラフ描写などの操作をサポートしているようです。 さて、PDL を使った PageRank 計算のコードは以下のように
「日本語テキストを分類するベイジアンフィルタ」を簡単につくるyo - download_takeshi’s diary
数週間前の話になりますが、「はてブのリニューアル会見」の記事を読んでいたところ、はてブにも「自動カテゴライズによる記事分類」の機能が搭載されるとか。。。 同じようなタイミングで「似たようなモノ」というか「ほぼ同じようなモノ」を作っていたので、すごーくインスパイアされてしまいました。ジュワ〜。（アドレナリンの放出音） 数週間たってもいまだ興奮冷めやらぬ状態なので、今日はその件について書いてみようと思います。 Lingua::JA::Categorize - a Naive Bayes Classifier for Japanese document. http://search.cpan.org/~miki/Lingua-JA-Categorize-0.00001/ 「はてブのパクリ」ではありません。「ベイジアンによる日本語テキスト分類器」を「簡単に作る」ことを目的としたモジュールです。 も
モンテカルロ法でサイコロ関数を検証 - harupiyoの日記
モンテカルロ法をご存知でしょうか？ 初めての方に、ちょっとだけ私から解説をさせてください！ 例えば、サイコロの目。 サイコロを振って、今出た目が３、だったとしましょう。 この時、３が出た確率は（一回しか振ってないので)100% ですが、更に何回か振ると３以外の目が出て％は下がって行きますよね。 しかし、下がるとは言っても、サイコロですからそれぞれの出目の確率は1/6。最終的には1/6…約16% に落ち着いていくはずです。 振る回数が多いほど1/6 に近くなるというところがポイントで、このように一回の出目はランダムでも、たーーくさんの回数を稼いで期待する答えを導き出すという考え方がモンテカルロ法です。 実際にこれを確かめるPerl プログラムを書いてみました。 このプログラムでは、サイコロを振る関数dicing を、何回も(ENOUGH_MANY_TO_TRY回) 振ってみて、各出目の確率が
[を] 転置インデックスによる検索システムを作ってみよう！
転置インデックスによる検索システムを作ってみよう！ 2007-11-26-5 [Algorithm][Programming] 転置インデックス[2007-06-17-6]による検索システムの実装は パフォーマンスを無視すれば意外と簡単です。 それを示すために Perl で簡単な検索システムを作ってみました。 検索方式は転置インデックス(Inverted Index)、 ランキングには TF-IDF[2005-10-12-1] を用いました。 検索対象ファイルは一行一記事で以下のフォーマットとします。 [記事ID][SPC][記事内容]\n 記事IDは数字、記事内容は UTF-8 の文字で構成されるものとします。 以下のようなサンプル test.txt を用意しました。 1 これはペンです 2 最近はどうですか？ 3 ペンギン大好き 4 こんにちは。いかがおすごしですか？ 5 ここ最近疲れ
![[を] 転置インデックスによる検索システムを作ってみよう！](https://cdn-ak-scissors.b.st-hatena.com/image/square/af37977ee866988286b95e74fff98500a190545c/height=288;version=1;width=512/https%3A%2F%2Fchalow.net%2Fimages%2Ftcl-logo-25.png){kind=logo}
404 Blog Not Found:javascript - Array#sortがオレquicksortより遅い!?
2006年11月23日14:45 カテゴリLightweight Languages javascript - Array#sortがオレquicksortより遅い!? な、なんだってー!? ごっつええブログ - JavaScriptによるソートアルゴリズムの比較実験 『JavaScriptを使って一定以上の数量をもった数値配列をソートする場合は、組み込みメソッドよりもクイックソートを使用したほうが高速である』 自分でも検証してみた。 どうやらMozilla系列のJavaScript実装に関しては嘘ではないらしい。以下で確認してほしい。 Firefox 2に関してはほぼ同等だが、Mac IE 5, Safari 2.0.4, Opera 9.02ではbuiltinの方が速かった。しかしその差は最も大きかったSafariでも3倍程度で、builtinとしてはやはり遅いように見える。 # of
2006-11-06
最近はPerl Best Practiceを読んでいることが多いので、おもしろかった部分をまとめて書いておこうかと思う。ということで、本日はPerl Best Practice 8.1章 ソートからのネタ。 sortはブロックを渡すことでソート方法を柔軟にコントロールできる。ただ、そのブロック内での計算量が大きくなるとソートの効率が落ちる。ソート中に何度も比較を行うちに同じ計算を何度もすることになってしまうからだ。 そこで、いろいろな工夫が考えられているらしい。PBPで紹介されていたもを以下にまとめてみた。 工夫なしでそのまま まず、一番ベタなソートが、以下のコード。 use Digest::SHA1 qw(sha1); my @sorted_titles = sort { sha1($a) cmp sha1($b) } @titles;このままだと、何度も同じ値のダイジェストを計算するこ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
