algorithm - ソート済み配列をソートしなおすべからず : 404 Blog Not Found
2012年01月08日20:30 カテゴリアルゴリズム百選Math algorithm - ソート済み配列をソートしなおすべからず 珠玉のプログラミング Jon Bentley / 小林健一郎訳 ぐぬぅ。男子ゆえ女子をこじらせようがないとはいえ、風邪が普通にこじれている。 というわけでアルゴリズムのことなどつらつら考えていた。 高速な安定ソートアルゴリズム “TimSort” の解説 : Preferred Research Timsort - Wikipedia, the free encyclopedia 要はソートすべき配列中にすでに存在する秩序を活用するのがtimsortなのだと。 だけどすでにソート済みの配列を活用するなら、こういう方法もありではというわけでentry。 If it ain't broke, don't fix it. ソート済みの配列に要素を加えるなら、要素を加
algorithm - mapBetween - 配列の隣接する2項にそれぞれ演算を施した配列 : 404 Blog Not Found
2012年01月04日21:00 カテゴリLightweight Languages algorithm - mapBetween - 配列の隣接する2項にそれぞれ演算を施した配列 言語を増やしたかったのと、そういう関数に名前を付けたかったのとで1 entry割くことにしました。 等差数列 - タイトル 配列の隣接する2項にそれぞれ演算を施した配列を得たい。つまり、 f (+) [1,2,3,4,5] = [3,5,7,9] のような f が欲しい。 名前 もちろん等差数列を作るのにもこの関数は使えるのですが、この一般的に使える関数に使う名前としてはあまりに局所的。というわけで mapBetween としてみました。使いどころはかなり多そうです。各言語に標準装備されていないのがちょっと不思議なほど。 JavaScriptによる実装 Array.prototype.mapで滅多に使われない第
algorithm - 重みをつけて乱択する : 404 Blog Not Found
2011年12月27日17:15 カテゴリ algorithm - 重みをつけて乱択する 数学ガール/乱択アルゴリズム 結城浩 同意なのだけど… Perlで生でrand関数をごちゃごちゃ使うコードはもう嫌だ | hirobanex.net とにかく、プログラムッチクというとなにかとランダムという要件が多いし、こんなコードばかりグチャグチャ書くのはもういやですね。 これを一般化するという問題はアルゴリズムの実習にちょうど手頃なサイズなので。 JavaScriptによる実装 頻度を高い順に並べて、乱数＜合計頻度となったところでそれを選択します。O(n)ですが選択肢を頻度順に並べることでその分ループが回る確率を抑えています。 (function(global){ var make_random_picker = function(picks){ var choices = Array.proto
perl - @_をコピーするコスト : 404 Blog Not Found
2011年07月17日22:00 カテゴリLightweight LanguagesTips perl - @_をコピーするコスト Perl Best Practices Damian Conway [邦訳:Perlベストプラクティス] これ、やけに差がないと思いきや… Perlで重複した要素をユニークにする - ichirin2501の日記 ふと、どのコードが速いのか気になったのでベンチマークを取ってみました。 id:ichirin2501のコードのどこに問題があるかは、以下のベンチマークを走らせてみればわかります。 #!/usr/bin/env perl use 5.012; use Benchmark qw/:all/; sub uniq_copy { my @array = @_; my %hash; @hash{@array} = (); return keys %hash; }
見事な取捨選択 - 書評 - 数学ガール/乱択アルゴリズム : 404 Blog Not Found
2011年03月09日22:00 カテゴリ書評/画評/品評Math 見事な取捨選択 - 書評 - 数学ガール/乱択アルゴリズム 数学ガール/乱択アルゴリズム 結城浩 著者ご本人より督促が。 弾さん、ツッコミRTもうれしいのですが、書評を書いて下さらんか（半分マジ） RT @dankogai: ミルカミザルカ< @hyuki: 数学セガール／沈黙のアルゴリズムless than a minute ago via Echofon結城浩 hyuki お待たせしました。 「カルキュラスのアリエッティ」でも「算法少女ミルカ☆テトラ」でもありません。本当の第四作です。 本書「数学ガール/乱択アルゴリズム」は、大好評シリーズとなった数学ガール第四作。 404 Blog Not Found:書評 - 数学ガール 404 Blog Not Found:孤独解消型数学入門 - 書評 - 数学ガール/フェルマー
一行のコードにも五分の魂 - 書評 - ハッカーのたのしみ : 404 Blog Not Found
2010年09月15日16:00 カテゴリ書評/画評/品評Math 一行のコードにも五分の魂 - 書評 - ハッカーのたのしみ 「虚数の情緒」と一緒に購入した。 ハッカーのたのしみ Henry S. Warren Jr. 滝沢徹 / 玉井浩 / 鈴木貢 / 赤池英夫 / 葛毅 / 藤波順久訳 [原著:Hacker's Delight] 棚から声がしたのである。「俺を買え」、と。 「英語版は持っている上に、Google Booksで試し読みまで出来るのに、なぜ?」、と心の中で抗議したのだが、結局買ってしまった。戻ったら案の定英語版が行方不明になっている上、日本語版は単なる翻訳ではなかったからである。訳注も充実している上、原著の証明に不足があればそれまで補完している。 これは楽しい。楽しすぎる。 しかもそれで終わらない。すこぶる役にたっているのだ。 たとえあなたがプログラムを一行も書かなかった
javascript - Mathを再発明してみた : 404 Blog Not Found
2010年09月14日06:30 カテゴリMathLightweight Languages javascript - Mathを再発明してみた 「基本というからには四則演算で三角関数実装しないとねー」と思いつつ書いていたら… C言語による最新アルゴリズム事典 奥村晴彦 [javascript]三角関数の基本 Math.random()を除いてMathを全部再発明しおえたので。 多倍長演算バージョンを作る時の下ごしらえにもなるかも。 下ごしらえ 仕様は Math - MDC アンチョコはもはや最新というにはあまりに古い、しかし代わりなき「C言語による最新アルゴリズム事典」。低レベルな車輪を再発明する人必携! 初期化と定数 定数の精度はおおげさに。 MyMath = {}; MyMath.E = 2.718281828459045235360287471352662497757; MyMat
Algorithm - 0と1を次々と返す簡単なお仕事 : 404 Blog Not Found
2010年09月03日05:30 カテゴリLightweight LanguagesMath Algorithm - 0と1を次々と返す簡単なお仕事 ごもっとも。 0と1を次々返す方法 - a2c.get.diary TrueだったらFalseで、FalseだったらTrueにしたい。 なんかそんなことそこかしこで必要で、その為の便利なものが あるのかなぁと思ったんだけど無いぽい Closure 本来は一番おすすめなのだが… JavaScript ()が煩わしいが、perlやrubyよりは自然。 #!/usr/bin/js var flipflop = function(p){ p = !p; return function(){ return p = !p; }; }; var fl = flipflop(); console.log(fl()); console.log(fl()); c
perl - 配列の∪と∩ : 404 Blog Not Found
2010年05月01日13:15 カテゴリLightweight Languages perl - 配列の∪と∩ これを解くためには、配列の∩(交わり、intersection)がわかればいいのですが… Perl Cookbook (English) Christiansen / Torkington [邦訳: Perlクックブック] perlかPHPで解決したいです。 複数(最大200程度)の配列があり、 それぞれ有している数字(それぞれ最大50程度)のうち、 二つ以上の値が同じ配列名を抜き出す。 という事をし.. - 人力検索はてな複数(最大200程度)の配列があり、 それぞれ有している数字(それぞれ最大50程度)のうち、 二つ以上の値が同じ配列名を抜き出す。 実にエレガントな方法が、Perl Cookbookに載っています。 以下、実例。 #!/usr/bin/perl use st
ITの礎 - 書評 - 通信の数学的理論 : 404 Blog Not Found
2009年09月06日17:00 カテゴリMath ITの礎 - 書評 - 通信の数学的理論 Amazonで見つけてあわてて購入。 通信の数学的理論 Warren Weaver / Claude Shannon / 植松 友彦訳 [原著:Mathematical Theory of Communication] 知らなかった。 このあまりに重要な業績が、本書まで邦訳されていなかったことを。 [追記あり] 本書「通信の数学的理論」は、情報科学にとっての「プリンキピア」。情報をデジタルに扱うという、今我々が空気のように扱っている手法は、すべてここから始まったのだ。 目次 通信の数学的理論への最近の貢献(ワレン・ウィーバー) 通信の数学的理論(クロード・E.シャノン) I 離散的無雑音システム II 雑音のある離散的通信路 III 連続情報 IV 連続通信路 V 連続情報源のレート 付録 訳者解
Variable Byte Code と UTF-8、またはUTF-24が存在しないわけ : 404 Blog Not Found
2009年08月05日00:30 カテゴリLightweight Languages Variable Byte Code と UTF-8、またはUTF-24が存在しないわけ 実は、これに非常に良く似た符号化を、我々は日々目にしています。 γ符号、δ符号、ゴロム符号による圧縮効果 - naoyaのはてなダイアリー 通常の整数は 32 ビットは 4 バイトの固定長によるバイナリ符号ですが、小さな数字がたくさん出現し、大きな数字はほとんど出現しないという確率分布のもとでは無駄なビットが目立ちます。 UTF-8です。 UTF-8は、0x0から0x10FFFFまでの整数を、以下のようにしてバイト列に変換します。 Range/Offset0123 0x00-0x7F0xxxxxxx 0x80-0x3FF110xxxxx10xxxxxx 0x400-0xFFFF1110xxxx10xxxxxx10xx
C - でも一番右端の立っているビット位置を求めてみた : 404 Blog Not Found
2009年07月07日03:30 カテゴリMathLightweight Languages C - でも一番右端の立っているビット位置を求めてみた 素晴らしい。 2009-07-04 - 当面C#と.NETな記録 問題の説明はここまでにして、コードの紹介です。Hacker's delight のコードより4〜5倍速く、そして、イミフ加減が半端じゃない！これ一つで 64bit 値以下のすべての値に対応できます。 でも、実際にどれくらい威力があるか試してみたかったのでCに移植してみた。意外な結果が出ております。 0x03F566ED27179461ULL まずは黒魔術。より黒魔術っぽくしてみました。 typedef unsigned long long U64; #define HASH 0x03F566ED27179461ULL static int ntzhash[64]; void i
algorithm - 最近点検索をkd-treeで : 404 Blog Not Found
2009年04月30日01:00 カテゴリMathLightweight Languages algorithm - 最近点検索をkd-treeで というわけで、kd-treeによる検索も実装してみました。 はてなブックマーク - ototoiのブックマーク データ数が少ない場合、この全検索が高速。ただデータが多くなってくるとkd-treeがいいと思う。点ならば配列をソートするだけで実現できる。 以下のデモでは、単にkd-treeによる検索だけではなく、kd-tree構築の速度と、総当たりの場合の速度の比較もできるようにしてあります。10,000点ぐらいだと、その差を顕著に感じることが出来るでしょう。100,000点ぐらいあると、感動的なほど差が出ます。それだけあってもkd-treeの方はほぼ1ms以内に検索が終わるのですから(ただしこの場合、デモの実行に合計10秒以上かかるので注意!)。
algorithm - correction - 最近点検索 : 404 Blog Not Found
2009年04月29日07:45 カテゴリMathアルゴリズム百選 algorithm - correction - 最近点検索 これ、「素直な解答」の方が間違っている。 404 Blog Not Found:algorithm - 最近点検索 ぬじゃらだーさんのコメント このアルゴリズムって点が原点から等距離に分布している場合はまったく働かないですよね。 その通り。その一方で、「近い順にソート」は合っている。しかしこれだとO(n log n)。 TSさんのコメント もとの最近点探索の問題を解くには、点集合Pのボロノイ図データを作っておいて問い合わせに答えるのが正攻法ではないでしょうか これだと確かに高速。点がすべて格子点上にある場合(たとえばビットマップ)、ボロノイ図があらかじめ用意してある場合はO(1)で判定できる。たとえば各格子点にあらかじめどの点が一番近いかを記録しておき、それを読
algorithm - 最近点検索 : 404 Blog Not Found
2009年04月28日23:30 カテゴリMathLightweight Languages algorithm - 最近点検索 食後のデザートにちょうどよいサイズの問題。 二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています 高速、低負荷で検索するにはどうしたらいいでしょうか？ 条件は次の通りです .. - 人力検索はてな 条件は次の通りです 集合Pはあらかじめ、任意の順番でソートしておける 点ｐの近似点にする条件は、margin範囲内で一番近いものとするが、margin値はそのときどきで変わる まずは素直に答えを。 点集合は、あらかじめ原点からの距離順にソートしておく。 その集合を、検索したい点の原点からの距離を使って二分探索(binary search)する。 二分探索は exact match でなくてもいいので、この方法でOKです。O(
アルゴリズム - 同じ文字列の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
アルゴリズム - 合コンの効用を最大化する : 404 Blog Not Found
2008年03月16日19:00 カテゴリアルゴリズム百選 アルゴリズム - 合コンの効用を最大化する 実は、1対1という制約を課せば、全体として最も満足が行く縁結びを決定するアルゴリズムがすでに存在する。 金融日記:東京 - ニューヨーク - ロンドン - パリ 世界の先進国の恋愛シーンで今起こっていること これから紹介する計量経済学モデルは、あらゆる社会科学の理論の中でも最もエレガントでそしてシンプルなもののひとつだと思います。 C言語による最新アルゴリズム事典 奥村晴彦 C言語による最新アルゴリズム事典 P. 4 安定な結婚の問題 stable mariage problem N人の男性とN人の女性が集団見合いをし、おのおのの異性を好みの順に順位付けした。この順位表をもとにして安定な縁結びの仕方を決めるのがこの問題である。仮に男性M1と女性F1が結婚したが、じつはM1はF1よりF2を
perl - Text::Tx も一応作った : 404 Blog Not Found
2007年12月24日06:30 カテゴリLightweight Languages perl - Text::Tx も一応作った WEB+DB PRESS vol. 42 404 Blog Not Found:perl - Text::Darts 0.02 Released!でも余裕があればText::Txとかも作ってみたいところ。 眠れないので勢いにまかせて作っちゃいましたよ岡野原さん。 /lang/perl/Text-Tx/ - CodeRepos::Share - Trac svn co http://svn.coderepos.org/share/lang/perl/Text-Tx で取って下さい。 CPANに上げるのはまだ。理由はこれから書きます。 CPANにまだ上げない理由その一。txはlibraryとして素直に使うにはちょっと問題があるのです。 tx.cpp 140: fp
perl - Text::Darts 0.02 Released! : 404 Blog Not Found
2007年12月24日02:00 カテゴリLightweight Languages perl - Text::Darts 0.02 Released! WEB+DB PRESS vol. 42の岡野原さんの記事を読んでいたら、昔放置した奴思い出して、ついムラムラと作りました。 /lang/perl/Text-Darts - CodeRepos::Share - Trac @CPAN (coming soon) Txじゃないのは、Txはまだちょっとインターフェイスが少なかったから。でも余裕があればText::Txとかも作ってみたいところ。 Darts #0.31以降をインストールしてから、普通にmakeしてください。 SYNOPSIS use Text::Darts; my $td = Text::Darts->new(qw/ALGOL ANSI ARCO ARPA ARPANET ASC
c - strchr()って使えねえ : 404 Blog Not Found
2007年12月23日03:00 カテゴリLightweight Languages c - strchr()って使えねえ ある文字が文字列で指定された文字種の中に含まれているかどうかという目的であれば、strchr()は使うべきではないでしょう。というか、strchr()はlibcに数多く埋まった地雷の一つのような気が。 strchr() ではまった話 - bkブログ 標準Cライブラリに strchr() という関数があります。文字列の先頭から指定した文字を探すという単純な関数なのですが、先日、意外な仕様を知りました。 strchr()は線形探索なので、文字種が増えれば増えるほど遅くなります。こういう場合は、素直にtable lookupを使うべきでしょう。 実際どれくらい差が出るのか調べてみました。念のために過剰最適化がなされていないことを、gperfで確認してあります。MacBook
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
