タグ

algorithmとprogrammingに関するpipeheadのブックマーク (37)

  • ソートアルゴリズム高速化への道 - kivantium活動日記

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

    ソートアルゴリズム高速化への道 - kivantium活動日記
    pipehead
    pipehead 2015/11/03
    バブルソート, 挿入ソート, マージソート, ヒープソート, クイックソート
  • [初心者向け] プログラムの計算量を求める方法 - Qiita

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

    [初心者向け] プログラムの計算量を求める方法 - Qiita
    pipehead
    pipehead 2015/07/31
    O 記法, 時間計算量, 空間計算量
  • 基本的なソートアルゴリズムまとめ+α。C言語での実装例 - Qiita

    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)

    基本的なソートアルゴリズムまとめ+α。C言語での実装例 - Qiita
    pipehead
    pipehead 2015/06/21
    バブルソート, 選択ソート, Counting Sort, マージソート, クイックソート, 奇偶転置ソート
  • ニュートン法とは何か??ニュートン法で解く方程式の近似解 - Qiita

    ニュートン法とは ニュートン法とは、f(x)=0になるようなxを求めるアルゴリズムの1つで、方程式の解を近似的に求めることができる方法です。 ニュートン法を用いると、√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により近づきます この手順を繰り返せば繰り返すほど、算出

    ニュートン法とは何か??ニュートン法で解く方程式の近似解 - Qiita
    pipehead
    pipehead 2015/06/13
    > ニュートン法とはf(x)=0となるxを求めるための手法で、繰り返し計算を行うことでxについて近似的に算出することができます。また、誤差範囲を指定することで、有効桁数が保証された値を得ることができます
  • Pythonで基本のアルゴリズムを書いてみた - Something Beyond

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

    Pythonで基本のアルゴリズムを書いてみた - Something Beyond
    pipehead
    pipehead 2015/01/05
    線形探索法 (リニアサーチ), 二分探索法 (バイナリサーチ), ハッシュ探索法, 単純選択法 (選択ソート), 単純交換法 (バブルソート), 単純挿入法 (挿入ソート), クイックソート, エラトステネスのふるい, ユークリッドの互除法
  • 視覚化による5つのガベージコレクションアルゴリズム入門 | POSTD

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

    視覚化による5つのガベージコレクションアルゴリズム入門 | POSTD
    pipehead
    pipehead 2014/11/10
    http://spin.atomicobject.com/2014/09/03/visualizing-garbage-collection-algorithms/ の和訳; 参照カウントコレクタ, マークスイープコレクタ, マークコンパクトコレクタ, コピーコレクタ
  • さまざまなアルゴリズムをアニメーションで解説してくれる『Algomation』 | 100SHIKI

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

    さまざまなアルゴリズムをアニメーションで解説してくれる『Algomation』 | 100SHIKI
  • アルゴリズムとプログラミングをビジュアルで一挙に理解できる「VisuAlgo」

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

    アルゴリズムとプログラミングをビジュアルで一挙に理解できる「VisuAlgo」
  • コンピュータを進化させてきた偉大なるアルゴリズムまとめ

    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の符号をもたせる

    コンピュータを進化させてきた偉大なるアルゴリズムまとめ
  • http://www.sat.t.u-tokyo.ac.jp/~omi/random_variables_generation.html

    http://www.sat.t.u-tokyo.ac.jp/~omi/random_variables_generation.html
    pipehead
    pipehead 2013/04/19
    一様乱数; 線形合同法と Mersenne Twister の比較
  • 第5回 チューニングのために理解しておきたいGCの4つのアルゴリズム | gihyo.jp

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

    第5回 チューニングのために理解しておきたいGCの4つのアルゴリズム | gihyo.jp
    pipehead
    pipehead 2013/03/27
    マーク & スイープ GC, コンパクション, コピー GC, 世代別 GC
  • ニュートン法とは - IT用語辞典

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

    ニュートン法とは - IT用語辞典
  • 簡単な画像の類似度計算手法「Average Hash」 » Untitled Blog

    画像の類似度を計算する方法を調査していたところ、面白い手法を紹介している方がいたので、この場でシェアしたいと思います。 この手法は「Perceptual Hash」という、「比較可能なハッシュ」を生成するための一手法です。 一般的にMD5やSHA1などのハッシュ値は、1バイトでもデータが違えば、まったく違うハッシュ値を返してきますが、「Perceptual Hash」は似たようなデータには似たようなハッシュ値を返してきます。 元ネタのブログによれば、これから紹介する手法のことを、ブログのオーナーであるDr. Neal Krawetzさんは「Average Hash」と呼んでいるようです。 元ネタのブログ記事は、以下のリンクからたどることができます。 Looks Like It – The Hacker Factor Blog いたってシンプルな手法ではありますが、例えば高速で「それなりの精

  • 平方根を使わずに高速で2点間の距離を近似する - きしだのHatena

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

    平方根を使わずに高速で2点間の距離を近似する - きしだのHatena
    pipehead
    pipehead 2012/06/04
    http://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtml の和訳; 三次元: d = (X^2 + Y^2 + Z^2)^(1/2); 二次元: d = (X^2 + Y^2)^(1/2)
  • fam.cx

    This domain may be for sale!

    fam.cx
  • Xorshift - Wikipedia

    Xorshiftは疑似乱数列生成法の1つである。George Marsaglia(w:George Marsaglia)が2003年に提案した。演算が排他的論理和とビットシフトのみであるため高速である[1] などの特徴がある。 #include <stdint.h> struct xorshift32_state { uint32_t a; }; /* The state word must be initialized to non-zero */ uint32_t xorshift32(struct xorshift32_state *state) { /* Algorithm "xor" from p. 4 of Marsaglia, "Xorshift RNGs" */ uint32_t x = state->a; x ^= x << 13; x ^= x >> 17; x ^=

  • すごい乱数生成アルゴリズム「xorshift」 - Pashango’s Blog

    みなさん、こんにちは、今回は乱数の話です。 特に複数機種でのコンシューマ機でゲームを開発をしていると、機種間で乱数値を統一するために乱数生成アルゴリズムを自作しますよね。 そこでよく使われるアルゴリズムが「線形合同法」です、内容は至って簡単で、以下の漸化式を使います。 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; } この「線形合同法」は計算が簡単で高速ですから、いろいろな環

    すごい乱数生成アルゴリズム「xorshift」 - Pashango’s Blog
    pipehead
    pipehead 2009/07/18
    冒頭で線形合同法のかんたんな説明
  • 計算量を具体的に見てみる 2009-01-06 - きしだのはてな

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

    計算量を具体的に見てみる 2009-01-06 - きしだのはてな
    pipehead
    pipehead 2009/01/06
    O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n), O(n!)
  • エラトステネスの篩とは - IT用語辞典

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

    エラトステネスの篩とは - IT用語辞典
  • 404 Blog Not Found:アルゴリズム百選 - 二分探索(binary search)

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

    404 Blog Not Found:アルゴリズム百選 - 二分探索(binary search)
    pipehead
    pipehead 2007/12/04
    > 「真ん中」を割り出す演算をさらに注意深くしています。「aとb間を取る」のに(a + b) / 2と素直にやると、a + b がオーバーフローする可能性があるのです。