タグ

algorithmに関するtakefのブックマーク (7)

  • きまぐれ日記: 動的配列への追加コストはなぜ O(1)?

    動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが,どうしてかと言われると意外と難しいものです. というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです.実装を知っていないと答えられません. 一般論として,1つ要素を追加するとき,配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります.コピーのコストは O(n) だから,追加コストも O(n) になるという議論が混乱の元になっています. こういうときは,要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです.一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです. さて,s

  • vincent krutler

    WHO Genf Bundescampus Ittigen AHV Genf Alterswohnungen Kreuzlingen Kaiserhof Malters Kantonales Kunstmuseum Lausanne Kollerpavillon Basel Botschaft Singapur Wasserreservoir Bruderholz Orientierungsschule Vouvry St. Jakobshalle Basel Feuerwehr Pratteln LOAD MORELOADINGNO MORE

  • 良い乱数・悪い乱数

    C言語標準ライブラリの乱数rand( )は質に問題があり、禁止している学会もある。 他にも乱数には様々なアルゴリズムがあるが、多くのものが問題を持っている。 最も多くの人に使われている乱数であろう Visual Basic の Rnd の質は最低である。 そもそも乱数とは 乱数とは、来サイコロを振って出る目から得られるような数を意味する。 このような乱数は予測不能なものである。 しかし、計算機を使って乱数を発生させた場合、 次に出る数は完全に決まっているので、予測不能とはいえない。 そこで、計算機で作り出される乱数を疑似乱数(PRNG)と呼び区別することがある。 ここでは、特にことわらない限り乱数とは疑似乱数のことを指すとする。 計算機でソフト的に乱数を発生させることの最大のメリットは、 再現性があることである。 初期状態が同じであれば、発生する乱数も全く同じものが得られる。 このことは

    takef
    takef 2006/12/07
    メルセンヌ・ツイスタ
  • 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

    404 Blog Not Found:javascript - Array#sortがオレquicksortより遅い!?
  • BlockSorting

    BlockSortingは、今までのデータ圧縮で有名な方法であるLZ法とは全く違う、ユニークな操作を用 いてデータを圧縮する方法であり、M.BurrowsさんとD.J.Wheelerさんが作者なので「BWTransform」 ともいいます。 このアルゴリズムは簡単に言ってしまえば、「データをぐるぐる回してソートして出力」というも のです。簡単すぎるかもしまいませんが、当にそうなんです。 ちなみに、このBlockSorting、単体では全く圧縮しません。ただ可逆な形にデータを変換すると いうものです。しかし、BlockSorting後のデータは非常に圧縮されやすい状態になります。例える と、色々な形をしたスポンジ(データ)が箱にごちゃごちゃに入って山積みになっているとします 。 これをそのまま上からギューっと押しつぶすのがLZ法やHuffman法なのに対し、一度、形が似た も

  • "comb sort" Motoyuki's Diary:2000年5月下旬

    昨日から延々とサーバ構築。 SCSI HDD の騒音に耐えかねて再インストール決行。 旧おうちサーバで使っていた 20GB IDE HDD を入れて IDE 10GB + 20GB 体制にする。 データの転送に時間をとられた *1ため、ほぼ二日間の間メールの読み書きができなかった。

    takef
    takef 2005/12/29
    bubble sortの改良
  • Think Labyrinth: Maze Algorithms

    Mazes in general (and hence algorithms to create Mazes) can be organized along seven different classifications. These are: Dimension, Hyperdimension, Topology, Tessellation, Routing, Texture, and Focus. A Maze can take one item from each of the classes in any combination. Dimension: The dimension class is basically how many dimensions in space the Maze covers. Types are: 2D: Most Mazes, either on

    takef
    takef 2005/12/09
    いろいろな迷路
  • 1