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 - 兼雑記 また，ランダム値を与え…

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

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

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

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

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