404 Blog Not Found:アルゴリズム百選 - ハッシュを再発明する
2007年12月03日11:15 カテゴリアルゴリズム百選 アルゴリズム百選 - ハッシュを再発明する (実はハッシュを使って)配列を再発明したところで、今度は配列を使ってハッシュを再発明してみます。 現代におけるプログラミングでは、連想配列(associative array)というものを非常によく使います。通常の配列では、データを取り出すのに整数の番号を使いますが、連想配列ではその代わりに文字列を使います。これは非常に便利で、多くの言語ではオブジェクトの実装にこの連想配列を用いています。JavaScriptのオブジェクトも実は連想配列です。 しかし、これを実装するには、少し工夫が必要です。単なる配列であれば、ただ等間隔に並べておけば、「何番目を出してくれ」で事足りますが、連想配列で「'dankogai'番目」といっても人間にもコンピューターにもなんのことかさっぱりわかりません。 誰でも
アルゴリズム百選 - フィボナッチ数列にO()を学ぶ : 404 Blog Not Found
2007年11月28日18:00 カテゴリアルゴリズム百選Math アルゴリズム百選 - フィボナッチ数列にO()を学ぶ 404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10、これほどの反響になるとは。200ブクマぐらいは予想していたが、もいくとは。 とりあえず、本の仮題を「アルゴリズム百選」として、「アマグラマーのすすめ」と同じように本blogに草稿を書いていくことにする。「メインページ」の「アルゴリズム大募集! C&R研究所 - トップページ」の方も適宜更新していくが、「その場で動かせるコードサンプル」はここでないと書けないので。 ただし、「アマグラマーのすすめ」よりは書き方は順不同になるはず。それでも序文相当のことは「チラ見」ならぬ「チラ書き」しておいた方がいいだろう。というわけで、序文に変えて紹介するのが、本Entry。 ヒントとな
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
「ボナンザVS勝負脳」を読む。 - IHARA Note
bonanzaというコンピュータ将棋のソフトが半年前に人間のトッププロ棋士と対局した。このことは、この記事をわざわざ読みに来る人は知っていることと思う。そして、その対局に関する新書が出た。それが「ボナンザVS勝負脳」である。私は将棋が強いわけでもなければコンピュータ将棋に詳しいわけでもない。ただ、専門分野が情報工学なので、この本を多少専門的な観点から読むことができるはずである。以下、数項目に渡って、解説や感想を書こうと思う。 ２６ページ「制御理論というのは、そもそも工学の分野で使われるものである」 著者の保木氏は唐突に「制御理論」というキーワードを出した。制御理論を知らない人はこう思うはずである。「ここは飛ばして読もう」。 制御というととっつきづらいイメージがあるかもしれないが、「コントロール」と言い換えると少しはアレルギー反応を抑えることができるかもしれない（制御というのはコントロールの
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 こんなことやって意味あるのかどうか正直言って迷いました。プログラマはたいてい知っているような内容だし見る人もいないんじゃないかと思いましたが、これからプログラミングを始めてみようという方にとっては参考になるかもしれないし、何よりも自分にとって頭の中を整理できたりするので、これから定期的にやっていこうかと考えてます。 ところで、紹介する内容はほとんど過去に出版された書物関係から抜粋しています。一応下の方に参考文献として挙げておきますので興味を持たれた方は書店などで探してみてはいかがでしょうか？ ということで、まずはライン・ルーチン(画面に直線を描画する)についての紹介です。
高速に非復元抽出をする方法はないだろうか？ (2) - アルゴリズムマニア2.0
googleで調べたら、それっぽいものがありました。An Efficient Method for Weighted Sampling without ReplacementC. K. Wong and M. C. Easton中身はまだ未確認です。だって、有料・・・（そのうち独占禁止法が発令されるとは思うのですが、アメリカはせこいのでいつになるのやら・・・） 当初は順序統計量が使えるんじゃないかといろいろ考えてみたりしました。乱数をN個発生させた時の、最大値or最小値の確率分布がかけるので、最大値や最小値だけの乱数が生成できます。乱数をN個出す必用はありません。これで例えば、1000個から400個選びたい時は、1個目が400個乱数を出した時の最小値が、そのサンプルの生成に寄与するかしないかを見て、1つづつ処理していけばいいと思ったのですが、よく考えてみるとダメです。順序統計量の乱数は何か
最強のたらいまわし : 404 Blog Not Found
2007年05月25日05:00 カテゴリLightweight Languages 最強のたらいまわし これ、現在知られている中で最強のたらい回しアルゴリズムだと思われます。 404 Blog Not Found:Cで強引にたらいを後回し - a-higutiさんのコメント 以前、同じことを考えたことがあります。 で、出た結論が → http://ml.tietew.jp/cppll/cppll/article/10669 オリジナルのC版はリンク先をご覧頂くとして、JavaScriptに移植したものが、以下です。 function laziest_tarai(x, y, zx, zy, zz){ return x <= y ? y : laziest_tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(zx, zy, zz) - 1,
新人SEのための楽しく学ぶアルゴリズム---目次
Visual Basicに代表される開発ツールの普及により，あらかじめ用意されたソフト部品を組み合わせれば，それなりのプログラムは作れるようになってきた。でも，それだけで大丈夫だろうか？ もしあなたがSEやプログラマを目指すなら，どんなにツールの使い方を極めても，きっと不安が残るはずだ。不安を取り除くために，プログラミングの中核となるアルゴリズムを楽しく学習していこう。 第1回 アルゴリズムとは？(1) 第1回 アルゴリズムとは？(2) 第1回 アルゴリズムとは？(3) 第1回 アルゴリズムとは？(4) 第1回 アルゴリズムとは？(5) 第2回 データ構造(1) 第2回 データ構造(2) 第2回 データ構造(3) 第2回 データ構造(4) 第2回 データ構造(5) 第3回 シミュレーションと再帰(1) 第3回 シミュレーションと再帰(2) 第3回 シミュレーションと再帰(3) 第3回 シミ
computer programming II
AVL木 木の一部だけがあまり茂らないように配慮しながら頂点を追加することで、 検索時間の最悪値がlog2(n)とまではいかなくても、 nよりは良くなるようなやり方を考えましょう。 根と葉の距離(葉から根に至る頂点列の長さ)が 全てhかh-1と揃った状態に保てれば理想的ですが、 頂点を追加するときの仕事が多くなり過ぎるという問題があります。 そこで、この条件を若干緩和したものを考えます。 いろいろな条件を考えることができますが、 ここでは 「 木の任意の頂点に対し、 左の子を根とする部分木の高さと右の子を根とする 部分木の高さの差は高々1である」という条件を考えます。 この条件を満たす木を AVL木 といいます。 (AVL木はAdelson-VelskiiとLandisが開発した。) この木は、根の左の部分木の高さが1で、右の部分木の高さが3ですので、 AVLの条件を満たしません。 AVL
良い乱数・悪い乱数
Ｃ言語標準ライブラリの乱数rand( )は質に問題があり、禁止している学会もある。 他にも乱数には様々なアルゴリズムがあるが、多くのものが問題を持っている。 最も多くの人に使われている乱数であろう Visual Basic の Rnd の質は最低である。 そもそも乱数とは 乱数とは、本来サイコロを振って出る目から得られるような数を意味する。 このような乱数は予測不能なものである。 しかし、計算機を使って乱数を発生させた場合、 次に出る数は完全に決まっているので、予測不能とはいえない。 そこで、計算機で作り出される乱数を疑似乱数(PRNG)と呼び区別することがある。 ここでは、特にことわらない限り乱数とは疑似乱数のことを指すとする。 計算機でソフト的に乱数を発生させることの最大のメリットは、 再現性があることである。 初期状態が同じであれば、発生する乱数も全く同じものが得られる。 このことは
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://ml.tietew.jp/cppll/cppll/article/10669
http://www.ic-net.or.jp/home/takaken/pz/index.html
MIT OpenCourseWare OCW Home
