Bonanzaで使われているinsertion sortとは何か？ - Bonanzaソース完全解析ブログ
■ Bonanzaで使われているinsertion sortとは何か？ Bonanzaで使われているsort(並べ替え)は、 1) insertion sort 2) shell sort 3) quick sort の3種類である。 3)はCのqsort関数を呼び出しているだけなので解説は不要だろう。また、3)は定跡データベースのメンテナンスにのみ使われており、実際の探索で使われているのは1),2)のみだ。 また、2)には1)が必要である。そこで、今回は1)について解説する。 ■ Bonanzaのnext.c Bonanzaのnext.cは、次の指し手を生成するcoroutineである。ここでinsertion sortが使われている。 指し手生成をcoroutineにしないでいきなり全部の手を生成したり、全部の手に対して点数をつけてquick sortしたりすると劇的なパフォーマンスの
「最強最速」を見せつけた浪速の高専生
高専生にとっての大イベント、「高専プロコン」の季節がまたやってきた。競技部門では、大人をもうならせる良問に、優れたアルゴリズムを携えてしのぎを削る学生たちの姿があった。 秋晴れに包まれた10月17日、18日にかけて、千葉県木更津市にある「かずさアカデミアホール」にて、「全国高等専門学校 第20回プログラミングコンテスト」（高専プロコン）が開催された。 高等専門学校の学生を対象とした情報処理技術系コンテストといえば「高専ロボコン」が特に有名だが、1990年にはじまった高専プロコンも歴史を重ね、いまでは高専ロボコンとの二枚看板の様相を呈している。 大きな節目となる20回目を迎えた今回の高専プロコンのテーマは「集まれ手作りの未来たち――海を越え！翔けろ！橋になれ！――」。課題、自由、競技と3部門が設けられている同大会だが、競技部門はほかの部門と比べてエンターテインメント性を強く押し出し、メディア
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意して
最強最速アルゴリズマー養成講座：あなたの論理的思考とコーディング力は3倍高められる (1/2) - ITmedia エンタープライズ
全世界で20万人を超える凄腕のコーダーが集うプログラミングコンテスト「TopCoder」。本稿では、アルゴリズム部門のSRMで取り上げられる問題を考えながら、論理的思考力およびコーディングのテクニックを養っていきます。 はじめに はじめまして。高橋直大です。本連載「最強最速アルゴリズマー養成講座」では、全世界で20万人を超える凄腕のコーダーが集うプログラミングコンテスト「TopCoder」について、そこで出題される数学・アルゴリズムのパズルを考えることで、コーディングのテクニックおよび論理的思考力を磨くことを目的に開始するものです。ここで扱う技法は主にアルゴリズムのそれですが、その根底にはロジカルな思考術が存在します。そうした能力を養いたい方にとって少しでも役に立てれば幸いです。 なお、本稿は必要に応じてコーディング例も紹介しますが、TopCoderで出題される問題の中から比較的やさしい問
各言語でのフィボナッチ数列に関する3つのアルゴリズムでの速度比較 - CanI's diary
ベンチマークみたいなあれです。 思えば、過去にいろいろしてきました。 フィボナッチ数列に関する3つのアルゴリズムの速度比較のRubyとPythonでの比較＠Python, Ruby - CanI’s Diary とか。 で、rubyたんが1.9になったとか、pythonが3.0系になったとかいろいろあったので、改めて速度比較をしてみようかなと。 今回は、我らがIronpythonとIronrubyにも加わっていただきました。 @Ruby Source id:qnighyさんの フィボナッチ数列に関する３つのアルゴリズムの速度比較＠Ruby - 簡潔なQ から。 以下、引用。 #!/usr/bin/ruby -Ku require 'matrix' def fib_recursive(n) case n when 0 return 0 when 1 return 1 else return
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
Double-Array
ダブル配列（ Double-Array ）は， トライ（ Trie ）のデータ構造の一種であり， 小さい辞書で高速に検索できるという特長を持っています． 実際に，茶筌（ ChaSen ）や 和布蕪（ MeCab ）などの 形態素解析器で利用されているという実績があります． ダブル配列では，配列を使ってトライを表現します． 配列の各要素が BASE, CHECK という二つの整数を持つので，頭文字をとって配列 BC と呼ぶことにします． 以降の説明では，配列 BC の要素 x の BASE, CHECK を それぞれ BC[x].BASE, BC[x].CHECK と記述します． 通常，BASE, CHECK は個別の配列として紹介されますが， 特に分割して考える必要がないので，このような説明にしました． 基本的に，配列 BC の各要素は トライの節と一対一で対応します． そのため，対応する
)
ハッシュ結合について
ハッシュ結合には、ビルド入力とプローブ入力という 2 つの入力があります。クエリ オプティマイザでは、2 つの入力のうち小さい方がビルド入力になるように、ロールを割り当てます。 ハッシュ結合は多種多様な集合の照合操作に使用されます。ハッシュ結合を使用できるのは、Inner Join、Left Outer Join、Right Outer Join、Full Outer Join、Left Semi Join、Right Semi Join、Intersect、Union、Diff です。また、ハッシュ結合の派生形では、重複の削除やグループ化を行うことができます (SUM(salary) GROUP BY department など)。このような変更では、ビルドとプローブの両方のロールに 1 つの入力しか使用しません。 ここでは、インメモリ ハッシュ結合、猶予ハッシュ結合、再帰的ハッシュ結合
最小全域木問題(クラスカル法とプリム法) - ぬいぐるみライフ？
最小全域木問題を解くためのアルゴリズム「クラスカル法」と「プリム法」を使ってみた． 最小全域木について クラスカル法 プリム法 PKUの問題 クラスカル法による解答 プリム法による解答 メモリ使用量と実行時間の比較 最小全域木について まず，全域木(Spanning tree)とは連結グラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のこと．つまり，連結グラフから適当な辺を取り除いていき，閉路をもたない木の形にしたものが全域木となる．ここで，グラフの各辺に重みがある場合，重みの総和が最小になるように辺を選んで作った全域木のことを最小全域木(Minimum spanning tree)という． 最小全域木を求めるアルゴリズムとしては以下の二つが有名である． クラスカル法 (Kruskal's algorithm) プリム法 (Prim's algorithm) いずれも貪欲
猫はうろうろ - yasuhisa's blog
にゃーにゃー、ではなくてw。情報学類(今名前変わったんだっけか)のほうで出ている自然言語処理の講義ほうで、形態素解析をするための「wikipedia:ビタビアルゴリズム(Viterbi algorithm)」というのを勉強しました(GWの前くらいに)。なんか全然分かっていなかったので、書いてみることにしました。アルゴリズムの種類としては動的計画法(Dynamic Programming)に入るので、アルゴリズムデザインのほうの勉強にもなるし(という合理化)。 「猫はうろうろ」という文字列は「猫、はう、ろう、ろ」や「猫、は、うろうろ」など様々な形で形態素解析することができます。これをある基準で分解したいのですが、ここでは一番単純そうな単語数最小法と呼ばれる方法でやります。 このやり方で「猫はうろうろ」と「家におくりました」を形態素解析すると結果は次のようになります。 /tmp% ruby v
ナップサック問題 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "ナップサック問題" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2016年9月) ナップサック問題 ナップサック問題（ナップサックもんだい、英: Knapsack problem）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、n 種類の品物（各々、価値 vi、重量 wi）が与えられたとき、重量の合計が W を超えない範囲で品物のいくつかをナップサックに入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいか」という整数計画問題である。同じ種類の品物を1つまでしか入れられ
ビタビアルゴリズム
ビタビ・アルゴリズム Ｖｉｔｅｒｂｉ ａｌｇｏｒｉｔｈｍ ホーム 情報通信のハイパーテキストは下記へ移動しました。 http://www.mnc.toho-u.ac.jp/v-lab/ お探しの内容は、下記の目次にあります。 http://www.mnc.toho-u.ac.jp/v-lab/yobology/index.htm
株式会社エス・スリー・フォー » STLport のハッシュ・コンテナ
STLport のハッシュ・コンテナ 標準C++ライブラリが提供するコンテナは、vector, list, deque, set, multiset, map, multimap の7種です。 これらコンテナから特定の要素を検索するとき、その時間計算量は vector, list, deque では O(N), set, multiset, map, multimap では O(logN) となります。 これ以上に高速な検索が可能なコンテナとしてハッシュ表(hashtable)を利用すれば、適切なハッシュ関数を与えることによって検索に要する時間計算量をコンテナ内の要素数に関わらず O(1) に近づけることができますが、残念ながら標準C++ライブラリにはハッシュ表で実装されたコンテナ(ハッシュ・コンテナ)を提供していません。 SGI(Silicon Graphics社)のSTL実装をベースに
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた - てっく煮ブログ
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、RESET を押すと好きなパラメータで試すことができます。こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。K-means 法とはK平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージになります。各点にランダムにクラスタを割り当てるクラスタの重心を計算する。点のクラスタを、一番近い重心のクラスタに変更する変化がなければ終了。変化がある限りは 2. に戻る。これ
マルコフ連鎖 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "マルコフ連鎖" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2018年1月) マルコフ連鎖（マルコフれんさ、英: Markov chain）とは、確率過程の一種であるマルコフ過程のうち、とりうる状態が離散的（有限または可算）なもの（離散状態マルコフ過程）をいう。また特に、時間が離散的なもの（時刻は添え字で表される）を指すことが多い[注釈 1]。マルコフ連鎖は、未来の挙動が現在の値だけで決定され、過去の挙動と無関係である（マルコフ性）。各時刻において起こる状態変化（遷移または推移）に関して、マルコフ連鎖は遷移確率が過去の状態によらず、
接尾辞配列 - Wikipedia
接尾辞配列（せつびじはいれつ）やサフィックス・アレイ（英: suffix array）とは、文字列の接尾辞（開始位置を異にし終端位置を元の文字列と同じくする部分文字列）の文字列中の開始位置を要素とする配列を、接尾辞に関して辞書順に並べ替えて得られる配列である。接尾辞木の配列版。主に文字列探索、全文検索などに利用される。1990年に Udi Manber と Gene Myers が発表した[1]。
ジュリア集合 - Wikipedia
P を2次以上の複素多項式 P(z) = anzn + an−1zn−1 + … + a0 とする。係数 an, an−1 … a0 も複素数である。まず、複素平面 C からそれ自身への多項式函数 P : C → C の充填ジュリア集合（英: filled Julia set）を KP で表し、 と定義する[17][18]。つまり、軌道が無限遠へ行かないような点の集まりが充填ジュリア集合である[19]。 ジュリア集合は、充填ジュリア集合の境界として定義される。すなわち、P のジュリア集合を JP と表せば である[20][18]。この定義のジュリア集合は、軌道が無限遠へ行かないような点の集まりと軌道が無限遠へ行く点の集まりの境目になる[19]。扱う函数が多項式のときは、この定義のジュリア集合と、上記の正規族を使った定義のジュリア集合とは同値である[21]。 複素函数 P(z) = z2 の
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Index of /~nishihara
ヒープソートのアルゴリズム
データ構造とプログラミング2003年度秋学期講義ノート（Ｓ２６）