先日、アルゴリズムの授業でソートのアルゴリズムをいくつか習いました。ソートアルゴリズムの名前と原理くらいは聞いたことがありましたが、実装したことはなかったのでいい機会だと思い実装してみることにしてみました。ただ実装するだけでは面白くないので高速化の限界に挑戦してみたいと思います。 計測用プログラム 今回の計測では、ランダム値が入った配列のソートを100回行い、平均時間を各アルゴリズムに競わせるというシンプルなルールにしました。プログラムは以下の通りです。 C++11で入ったメルセンヌ・ツイスタなどの機能を使っているので、ビルド時には-std=c++11を指定する必要があります。 実験に使用したパソコンのCPUはCore i3-3227U@1.90GHz、コンパイラはgcc version 4.8.4で最適化オプションには-O3を指定しました。 #include <iostream> #in

はじめに この記事では、プログラムの計算量を求める方法を説明します。プログラミングの初心者向けに、厳密さよりも分かりやすさを優先して説明していきます。 サンプルコードについて この記事のサンプルコードは、C言語（C99）で記述しています。 計算量とは？ 計算量とは、 「そのプログラムがどれくらい速いかを大雑把に表す指標」 です。 もう少し正確に言うと、 「入力サイズの増加に対して、実行時間がどれくらいの割合で増加するかを表す指標」 です。 グラフによる計算量の表現 計算量をグラフで表すと、以下のようになります。 これは、**「入力サイズ $n$ が増加するにつれて、実行時間が $n$ に比例して増加する」**ということを表しています。 別のグラフも見てみましょう。 これは、**「入力サイズ $n$ が増加するにつれて、実行時間が $n^2$ に比例して増加する」**ということを表しています

2016/07/18追記 CountingSortについて誤りがあったため訂正しました #ソートアルゴリズム全般考察 典型的なソートアルゴリズムでは、最善で $O(n log n)$ 、最悪で $O(n^2)$ である。理想は $O(n)$ である。 比較ソートでは、必ず $O(n log n)$ の比較が必要となる。 汎用手法による分類。挿入、交換、選択、マージなどがある。 Wikipedia https://ja.wikipedia.org/wiki/ソート 授業で習った基本的なソートアルゴリズムをまとめたいと思います。 実際はライブラリを使うかもしれませんが、内部を知っていて損はないので覚書です。 #まとめるソートアルゴリズム バブルソート 選択ソート Counting Sort マージソート クイックソート 奇偶転置ソート ##バブルソート バブルソート (bubble sort)

ニュートン法とは ニュートン法とは、f(x)=0になるようなxを求めるアルゴリズムの１つで、方程式の解を近似的に求めることができる方法です。 ニュートン法を用いると、√2の値やsin(x)=0.5になるようなxの値など近似的に求めることができます ニュートン法の考え方 ニュートン法では、以下の考え方に基づいて計算が行われます f(x) = 0になるような値xを探す時、ある値x1における接線の切片x2は、元の値x1より真の値xに近くなる この考え方は下の図のように、f(x)という関数においてf(x) = 0になるようなxを求めたいとき、ある値x1における接線f'(x)の切片x2を求めると、求めたい値xに対して、x1よりもx2の方が近くなるということを意味しています 先ほど算出したx2の値を元にして同様の操作を行うと、x3は目的となる値xにより近づきます この手順を繰り返せば繰り返すほど、算出

2015-01-05 Pythonで基本のアルゴリズムを書いてみた Programming アルゴリズムを学ぶ意義みたいなものはいろいろなところで語り尽くされていると思うので私からは特にコメントしませんが、今回の勉強に利用した書籍でも引用されていた言葉が印象的なので、記しておきます。 最先端の機械を使って製品をつくるのは簡単で、しかも楽なことだが、基本技術を固める前に楽なほうに流れていってしまった。俺のような基本的なことがきちんとできるローテクが、今、我が世の春を謳歌しているんだ。 岡野雅行さんという職人さんの言葉のようです。そういえば随分前にこんな記事が盛り上がりました。 今すぐ辞めて欲しい、「Ruby on Rails勉強してます」「CakePHP勉強してます」 最新技術だけではなくて、その基礎となる技術をしっかり理解しなければダメだよということでしょう。ということで基本のアルゴリ

ほとんどの開発者は、自動のガベージコレクション（GC）を当たり前のように使っています。これは、私たちの仕事を容易にするために言語ランタイムが提供する素晴らしい機能の1つです。 しかし、最新のガベージコレクタの中をのぞいてみれば、実際の仕組みは非常に理解しづらいことが分かります。実装の詳細が無数にあるため、それが何をしようとしているのか、また、それがとんでもなく間違った事態を引き起こしかねないことについて十分理解していない限り、すっかり混乱してしまうでしょう。 そこで、5種類のガベージコレクションアルゴリズムを持つおもちゃを作ってみました。小さいアニメーションはランタイムの動作から作成しました。もっと大きいアニメーションとそれを作成するコードは github.com/kenfox/gc-viz で見ることができます。単純なアニメーションによってこうした重要なアルゴリズムを明らかにできることは

見ていて楽しい感じだったのでご紹介。マニアックだが。 Algomationはさまざまなアルゴリズムをアニメーションで解説してくれるサイトだ。 よくあるソート系のアルゴリズムや、オセロを題材にした人工知能のアルゴリズムまで網羅している。 また自分でアルゴリズムを作って投稿することも可能だ。これ系の思考実験が好きな人は覗いてみるといいですね。

アルゴリズムを理解するのにビジュアル化することは非常に有効で、プログラムをビジュアル化することで理解が進むのもまた同じ。そこで、アルゴリズム・プログラミングの理解が進むようにと、アルゴリズムを記述したプログラムコードを一挙にビジュアル化することで、アルゴリズム＆プログラミングを同時に学習できる一挙両得なサービス「VisuAlgo」が公開されています。 VisuAlgo - visualising data structures and algorithms through animation https://visualgo.net/en 上記のVisuAlgoサイトで試しにソートアルゴリズムの基本プログラム「バブルソート」をビジュアル化してみます。「Sorting」の「bubble」をクリック。 検索窓の下に「bubble」と表示されたのを確認したら「Sorting」の画像をクリック。

By Kai Schreiber IT技術の進化のスピードには目を見張るものがありますが、それを支えているのはアルゴリズムと呼ばれる処理方法(技術的アイデア)です。さまざまなアルゴリズムの中でも、コンピュータの進化に革命的な影響をもたらしたとされる偉大なアルゴリズムは以下の通りです。 Great Algorithms that Revolutionized Computing http://en.docsity.com/news/interesting-facts/great-algorithms-revolutionized-computing/ ◆ハフマン符号(圧縮アルゴリズム) Huffman coding(ハフマン符号)は、1951年にデービッド・ハフマン氏によって開発されたアルゴリズム。頻出頻度の大小によって対戦するトーナメントツリーを考えて、ブロックごとに0と1の符号をもたせる

なぜアルゴリズムを学ぶのか GCによる停止時間が長くなり、アプリケーションの処理時間が短くなると、業務に使える時間が短くなってしまいます。その問題を解決するために、GCをチューニングすることで、アプリケーションの停止時間を短くすることが考えられます。 その際大事なのは、GCのアルゴルズムを把握しておくことです。 GCのチューニングを行うときは、GCで行われている処理の内、どの処理に時間がかかっているかをモニタリング⇒分析⇒チューニングする、という流れになります。しかし、GCのアルゴリズムを知らないと、モニタリング結果を見てもどこに問題があるかがわからず、分析やチューニングを行うことができません。 今回は、以下の4つのアルゴリズムをご紹介します。 マーク＆スイープGC コンパクション コピーGC 世代別GC GCのアルゴリズムはJVMの実装によって異なりますが、多くの場合、上記4つのアルゴリ

概要 ニュートン法（Newton’s method）とは、方程式の解を数値計算により近似的に求める手法の一つ。解を求めようとする範囲において微分可能かつ単調増加で下に凸であり、一次導関数が導出できる場合に適用できる。 方程式f（x）=0に対して関数y=f（x）を考え、まず適当なxを取ってf（x）に対する接線を求める。接線がx軸の交点におけるxの値は最初のxよりも解に近いため、このxについて再び接線を求めると、そのx軸との交点はさらに解に近づく。この操作を何度も繰り返し行なっていくと、xの値は解に収束していくため、適当な回数で操作を打ち切ることにより、回数に応じた精度の解の近似値を得ることができる。 非線形方程式を数値的に求める手法として古くから広く知られており、二分法より収束が早く、少ない計算回数で効率よく近似解の精度を高められる。1669年に万有引力の法則などで知られるアイザック・ニュー

２点間の距離の計算では平方根が必要になりますが、平方根は少し重い計算です。ということで、平方根を使わず、掛け算・割り算・足し算と絶対値・最大・最小だけで距離を近似する方法についての記事を翻訳してみました。 flipcode - Fast Approximate Distance Functions (12:02 補足：おそらく今の標準的なCPUでやる意味はほとんどないと思います。近似のアプローチとして面白いというくらいの話。Z80でやりましょう) 距離関数高速近似 by Rafael Baptista (27 June 2003) ２点間のユークリッド距離を求める計算式は次のようになる。 二次元では次のようになる。 この関数の計算には、平方根が必要になる。これは最近のコンピュータでも高価な計算である。平方根は逐次近似によって求められる。つまり、コンピュータは平方根近似のループを行って、与え

This domain may be for sale!

みなさん、こんにちは、今回は乱数の話です。 特に複数機種でのコンシューマ機でゲームを開発をしていると、機種間で乱数値を統一するために乱数生成アルゴリズムを自作しますよね。 そこでよく使われるアルゴリズムが「線形合同法」です、内容は至って簡単で、以下の漸化式を使います。 A,B,Mは定数で、どの値が入るかは処理系依存です。 例えばUnixなどの処理系ではA=1103515245,B=12345,M=2147483647などが入ります。 C言語ですと以下のようになります。 static unsigned int x=1; void srand(unsigned int s) { x=s; } unsigned int rand() { x=x*1103515245UL+12345UL; return x&2147483647UL; } この「線形合同法」は計算が簡単で高速ですから、いろいろな環

アルゴリズムの話では、計算量の解析がかかせません。 計算量はオーダー記法で表されますが、これは、データの入力量に対してどのくらい時間がかかるかをあらわしたものです。 こういった話はどのアルゴリズムの本にも載ってるはずですが、具体的にどのようなプログラムを書くとそのオーダーになるかという記述はあまりありません。 ということで、やってみました。 計算時間表示のための共通処理を行うクラスは、一番最後に書いてます。 O(1) 計算時間がO(1)のアルゴリズムは、処理が入力の量によらない場合です。 配列の要素のアクセスや、ハッシュテーブルによるデータ検索、連結リストへの追加削除などがこれにあたります。 コードには入力量でのループが含まれません。 public class O1 extends ViewCompFrame{ @Override void compute(int n) { proc();

概要 エラトステネスの篩（sieve of Eratosthenes）とは、与えられた整数以下の素数をすべて発見する計算手順(アルゴリズム)の一つ。整数のリストから各素数の倍数を順に削除していくことで素数のみがリストに残る。 2から目的の数までの整数のリストを用意する。このリストの中から最初の素数である2の倍数を消していく。リストに残った整数のうち、先頭にある3が次の素数である。次に、リストの中から3の倍数を消してゆき、残った整数のうち先頭にある5が次の素数である。 このように、先頭に残った数の倍数をリストから消してゆき、その都度先頭に残った数を集めると、素数のリストが得られる。このアルゴリズムが「篩」（ふるい）と呼ばれるのは、この一連の操作が、粉状のものを何段階もふるいにかけてより分ける作業に似ていることに由来する。古代ギリシャの学者であるエラトステネス（Eratosthenes）が紀元

2007年12月04日08:30 カテゴリアルゴリズム百選Math アルゴリズム百選 - 二分探索(binary search) 今回は二分探索を取り上げます。 検索:コンピューターの最もよくある利用法 「二分探索って何?」「ググレカス」と言われないためにこの記事は存在するのですが、Webの検索に限らず、「目的のデータを見つけて取り出す」というのは、およそコンピューターの利用法で最もポピュラーなものです。 配列:コンピューターがデータを扱う根本的な方法 そのデータはコンピューターのなかでどう置かれているかというと、非常に単純です。デジタル化されたデータ=数値が一定間隔で並んでいるだけです。こういうデータ構造を、配列(array)といい、この数値一個一個のことを要素(element)と言います。 現代のコンピューターでは、最小要素はバイト(byte)と呼ばれています。このバイトの中には0と1