■_
moleskin のノート新調。
1010 ということで銭湯へ。
あら割と近くだ。 活版印刷と三軒茶屋の夫婦の物語 - デイリーポータルZ：@nifty
昨今日本でよく見かけるのとは違う意味で 「eat in」というイディオムがあるのを知って驚く (どんな意味かは各自で調べること :)
2013年10月05日
■_
ここ何日か elastic search なる言葉を良く見かける。なんじゃろこれ。
プログラマーのための数学勉強会。プログラマの為の数学勉強会 第4回 - PARTAKE 時間的やら場所的がネックで参加できないのだけど、 いちおー発表スライドは追いかけてる…んだけど 第4回に入っていくつかわからんところがあるんだけど聞けるような人がいねーなー (twitter経由などはなしで)。 例示された式の変形の途中がわからんとかだから本やら見て調べられないのよねー これまでのスライドはこちら→ プログラマの為の数学勉強会
時計。切れたベルトを修理。525円也。
北海道物産展。とある用事を片付けたあとで近くのデパートでやってたので行ってみたが人ごみに負けた
for dummies シリーズにビッグデータを題材にしたのがあってびっくりぎょーてん。
Manning Publications Co. から宣伝メールが来たんですが
Data Science! + 45% off selected books - hogemuta@gmail.com - Gmail Mastering the formal academic discipline of data science can involve years of study in sophisticated mathematics, complex pattern recognition, machine learning, uncertainty modeling, and other esoterica. For most of us non-academics, though, it's the practical task of extracting relevant, useful information from the sea of data generated by businesses, governments, and people. These Manning books will help you combine the programming skills you already have with the growing number of tools and technologies that make practical data science less daunting. (略) Languages As a developer, programming languages are your bread and butter. Established languages like Python and Ruby, along with their numerous high-quality libraries, have emerged as low-overhead ways to tackle data analysis tasks. Functional programming languages like Scala and Clojure provide a closer match between your code and data, and offer a scalable coding paradigm for data science. The Quick Python Book » pBook, PDF, ePub, and Kindle Hello! Python » pBook, PDF, ePub, and Kindle The Well-Grounded Rubyist, Second edition » MEAP Scala in Action » pBook, PDF, ePub, and Kindle Scala in Depth » MEAP Clojure in Action, Second Edition » MEAP The Joy of Clojure, Second Edition » MEAP Functional Programming with Scala » MEAP
your bread and butter
なんて表現あるんですねえ。
■_ C の入門書
ただし洋書 :)
なんかこれも最近出ていたものらしい。
■_ quick select
某スレ。
C言語なら俺に聞け（入門編）Part 120 440 デフォルトの名無しさん [sage] 2013/10/04(金) 18:16:39.31 ID: Be: 要素が20~30個のデータに対して 高速なソートアルゴリズムの名前を教えてください。 78K0Rという16bit CPUを13.5MHzで動かしていますが 中央値を求めるために4ms以下にしたいです。 バブルソートにしたら8ms以上かかってしまいました。 データは struct{ int x, y; } v1, v2; 比較式は (long)v1.y * v2.x < (long)v2.y * v1.x intは2バイト、データはint x, y; ポインタは4バイトです。 442 デフォルトの名無しさん [sage] 2013/10/04(金) 18:32:21.47 ID: Be: >>440 ソートは自前で実装してる? inline化するとか、変数をregisterに割り付けるとか、どうだろうか 443 デフォルトの名無しさん [sage] 2013/10/04(金) 18:32:36.65 ID: Be: >>440 それって A>B かつ B>C のときに A>C が成り立たないから ソート結果に意味がなさそうな気がする 444 デフォルトの名無しさん [sage] 2013/10/04(金) 18:53:29.95 ID: Be: ごめん >>443 は勘違い 445 440 [sage] 2013/10/04(金) 19:03:02.79 ID: Be: みなさんありがとうございます。 >>441 クイックソートでしょうか。 とりあえず、探してきます。 >>442 自前です。ライブラリは使えません。 比較式はソート関数内に直接書いています。 registerも使ってみます。カウンタに使えば良いでしょうか? >>443 条件を書き忘れてました。すいません。 データの範囲は0≦xです。 もとは以下の式です。 v1.y / v1.x < v2.y / v2.x (実数として) 傾きの大きさを比較します。 446 デフォルトの名無しさん [sage] 2013/10/04(金) 19:08:57.14 ID: Be: >>445 コムソートがお手軽で省メモリ 447 デフォルトの名無しさん [sage] 2013/10/04(金) 19:55:45.67 ID: Be: >>445 inlineっつうのは、C89ならマクロ関数で書くってことだ 展開されたアセンブリコード見て、サイクル数足していけばそれが本当に出来るか分かるんじゃないかね 448 デフォルトの名無しさん [sage] 2013/10/04(金) 20:00:30.18 ID: Be: シェルソートもあるよ 455 440 [sage] 2013/10/04(金) 21:31:32.67 ID: Be: >>446 >>448 コムソートとシェルソート使えそうなので試してみます。 >>447 マクロ関数というのが使えるか調べてみます。 みなさん、ありがとうございます。 457 ◆QZaw55cn4c [sage] 2013/10/04(金) 21:57:04.75 ID: Be: >>455 http://toro.2ch.net/test/read.cgi/tech/1313183984/425 にコムソートを書いておきましたリストのソートにも適用しやすいのがよいところ しかし高々20～30なら選択ソートや挿入ソートも検討の余地があると 458 ◆QZaw55cn4c [sage] 2013/10/04(金) 21:58:31.13 ID: Be: 半分おわったところで打ち切っていいしね 460 デフォルトの名無しさん [sage] 2013/10/05(土) 08:18:13.20 ID: Be: >>440 > (long)v1.y * v2.x < (long)v2.y * v1.x 意味不明 > (long)v1.y * v1.x < (long)v2.y * v2.x ならわかるが。 こういう事ならソートする前に積を計算しとけ。 中央値を求めるならば全部ソートする必要はなくて、クイックセレクトと呼ばれるアルゴリズムが存在する。 こんなのに喜々として公開オナニーを見せつけるゴミクズはいつまで生きているんだろう。 とっとと死ねばいいのに。 463 ◆QZaw55cn4c [sage] 2013/10/05(土) 09:32:36.11 ID: Be: >>460 ＞クイックセレクト thx4 keywords これはいいね 466 デフォルトの名無しさん [sage] 2013/10/05(土) 10:55:54.49 ID: Be: >>445 >比較式はソート関数内に直接書いています。 ソート関数にしないで、main内に比較式を書く。 468 デフォルトの名無しさん [sage] 2013/10/05(土) 11:12:32.98 ID: Be: >>466 コールとリターンで9サイクル浮くな 0.7usくらいか 469 440 [sage] 2013/10/05(土) 12:12:25.76 ID: Be: コムソートとシェルソートを試して、5msくらいになりました。 >>457 >>458 charやintのインデックスのソートに置き換えてみましたが、 インデックス構築とアドレス演算のコストがバカにならないらしく 遅くなってしまいましたのでリストも使えなそうです。 あとは、代入回数を減らすとか、そういう最適化になりそうです。 ありがとうございました。 487 デフォルトの名無しさん [sage] 2013/10/05(土) 22:18:19.91 ID: Be: >>440>>445 > v1.y / v1.x < v2.y / v2.x (実数として) 比較関数で毎回この計算していたら遅くなるね。 最初に20～30個の y / x を求めて、それに対してソートすれば ずいぶん早くなるんじゃないの。 488 デフォルトの名無しさん [sage] 2013/10/05(土) 22:20:33.20 ID: Be: >>445 > データの範囲は0≦xです。 > v1.y / v1.x < v2.y / v2.x (実数として) x == 0.0 の時もあるのか… 490 デフォルトの名無しさん [sage] 2013/10/05(土) 22:51:13.59 ID: Be: >>487 割り算入れたくないんだろ 491 487 [sage] 2013/10/05(土) 22:57:40.84 ID: Be: >>490 ああ、そうか。 > v1.y / v1.x < v2.y / v2.x (実数として) を計算するわけじゃないね。 俺の書き込みは見なかったことにしてください。
なんかタイミングよく reddit にこういうのが。 The quickselect algorithm is now available as a task on the Rosetta Code site. : programming Quickselect algorithm - Rosetta Code
リンク先を見たらサンプルプログラムがいくつかの言語で書かれている中に Perl 6 があったので大笑い。
Quickselect algorithm - Rosetta Code my @v = <9 8 7 6 5 0 1 2 3 4>; say map { select(@v, $_) }, 1 .. 10; sub partition(@vector, $left, $right, $pivot-index) { my $pivot-value = @vector[$pivot-index]; @vector[$pivot-index, $right] = @vector[$right, $pivot-index]; my $store-index = $left; for $left ..^ $right -> $i { if @vector[$i] < $pivot-value { @vector[$store-index, $i] = @vector[$i, $store-index]; $store-index++; } } @vector[$right, $store-index] = @vector[$store-index, $right]; return $store-index; } sub select( @vector where +@vector, $k is copy where $k > 0, $left is copy where (0 <= $left <= @vector) = 0, $right is copy where ($left <= $right <= @vector) = @vector.end ) { loop { my $pivot-index = ($left..$right).pick; my $pivot-new-index = partition(@vector, $left, $right, $pivot-index); my $pivot-dist = $pivot-new-index - $left + 1; given $pivot-dist <=> $k { when Same { return @vector[$pivot-new-index]; } when Decrease { $right = $pivot-new-index - 1; } when Increase { $k -= $pivot-dist; $left = $pivot-new-index + 1; } } } }
select の引数のところの書き方が見慣れない書式だけどなんだろこれ (最近まともに追いかけてないからなあ)。 is やら copy やらはなんか見覚えあるけど where ねえ。
■_
- mixiの衰退の原因は、サービスの内容の問題というより、「寿命がきた」だけ - いつか電池がきれるまで
-
Rubinius 2.0 Released - Rubinius
With the 2.0 release, Rubinius regains a laser focus on supporting the future of Ruby. Rubinius 2.0 is expected to be compatible with Ruby 2.1.
- カーネルパラメータとお茶目なガチャピン先生 - Togetter
