先日、アルゴリズムの授業でソートのアルゴリズムをいくつか習いました。ソートアルゴリズムの名前と原理くらいは聞いたことがありましたが、実装したことはなかったのでいい機会だと思い実装してみることにしてみました。ただ実装するだけでは面白くないので高速化の限界に挑戦してみたいと思います。 計測用プログラム 今回の計測では、ランダム値が入った配列のソートを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 で見ることができます。単純なアニメーションによってこうした重要なアルゴリズムを明らかにできることは

By voyageAnatolia.blogspot.com 仮想通貨「Bitcoin(ビットコイン)」はPCや専門ハードウェアを使って計算することで新しいビットコインを生み出せます。このビットコインを発掘する行為は「マイニング」と呼ばれ、ハイスペックなマシンと膨大な時間が必要となっているのですが、そのマイニングに「紙」と「鉛筆」と「頭脳」だけで挑む強者が現れました。 Ken Shirriff's blog: Mining Bitcoin with pencil and paper: 0.67 hashes per day http://www.righto.com/2014/09/mining-bitcoin-with-pencil-and-paper.html ビットコイン決済ではすべてのビットコインのやりとり(取引)は、「ブロック」という単位で管理されており、このブロックとブロックを

見ていて楽しい感じだったのでご紹介。マニアックだが。 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つのアルゴリ

何度かこのブログでデータ圧縮（書庫やエンコードなど）について解説してきましました。 しかし、その詳しい仕組についてはまだ書いていません。実際、実践的なところは難しすぎるので私もよく分かっておらず、専門的なことまではわかりません。（プログラミングは今後しっかり勉強していきたいですね。） ですが、漠然と「取り敢えずデータが少なくなるんだよ！」と言われても釈然としないでしょう。少なくとも、私は「元の情報を残したままデータを小さくするってどうやるんだろう？」と疑問を持ちました。 なので、この記事ではデータ圧縮の基礎部分でよく使われる「ハフマン符号化」について書いてみたいと思います。 情報数学のお話になりますが、概要だけならとても理解しやすいものなので、今回はこれをテーマにしてみます。データの圧縮とはどうゆうことなのか、その一端でも知りたい方はお付き合いください。 ついでに「なぜコンピューターは0と

概要 ニュートン法（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!