てきとうなメモ

本の感想とか技術メモとか

Algorithm

java.util.Hashtableとjava.util.HashMap

Togetter - 「hashtableのn * 2 + 1の意義」 なるほど。Hashtableのハッシュ関数はハッシュの再作成するときに、 protected void rehash() { ... int newCapacity = oldCapacity * 2 + 1; Entry[] newMap = new Entry[newCapacity]; ... } と、古いサイズnに…

ハッシュ表のサイズ

2009-07-16 - ザリガニが見ていた...。 ハッシュ表のサイズ - odz buffer 確かに素数で剰余を取ることにあまり意味は感じないかなあと.素数で剰余を取ることでばらけさせるのではなく,ハッシュ関数そのものの方でばらけさせるべきではと.他の言語ではどう…

シャッフル

単純で正しそうなものが正しいとは限らない - Radium Software どこかで見た問題と思ったら結城さんのところで見た問題だった. [結] 2005年10月 - 結城浩の日記 後者の証明はid:shinichiro_hさんがされている. 2005-10-20 - 兼雑記 また,ランダム値を与え…

Perlのstable quicksort

stableなquicksortないかなと思っていろいろ探していたらPerlのquicksortがstableな実装だった.perl5.10.0のpp_sort.cより引用.Perlのquicksortについては以下のようなデータ構造を利用している. indir list1 +----+ +----+ | | --------------> | | ----…

Arrays#sort

JavaにはArrays#sortというメソッドがあって配列をソートすることができる.ソートする対象がプリミティブ型だとquick sortで実装され,オブジェクトだとmerge sortで実装している.オブジェクトのソートはstableであるという仕様のためだと思われる.さらに…

自然なソート

Coding Horror: Sorting for Humans : Natural Sort Order人間にとって自然なソートとsort関数がよくやるソートは別物だよという話. Perl や Python の実装が用意されてるってことはこれらの言語にはこの機能はないってことなんだろうな。Perl にはあっても…

libicpc wiki

FrontPage - libicpc wikiアルゴリズム集っぽい.いろいろ参考になりそう.

ハッシュと比較と検索

404 Blog Not Found:tips - MD5のコスト重複ファイルを消すPythonスクリプトソースはちゃんと見ていないのだが,メモリに載るならハッシュを使って検索した方が速いのでは?読み終わった.早とちりしてた.一つ一つファイルを検索して消すのかと思ってた.重…