コンテンツに最適なソートを使おう！ JavaScriptで使用するソートアルゴリズムのまとめ - ICS MEDIA
普段、みなさんはプログラムでデータのソートをするとき、内部でどのようなアルゴリズムが働いているか意識していますか？ 大半の方はプログラム言語にあらかじめ用意されているソート関数を使用し、特別にアルゴリズムについて意識することは少ないと思います。ソートのアルゴリズムにはデータ量やデータの初期の状態に応じた向き不向きがあり、それぞれのアルゴリズムについての理解を深めて適したものを選択すると、ソートにかかる時間を短縮できることがあります。 ソートアルゴリズムの可視化デモ （HTML5製） 次のデモはソートのアルゴリズム可視化するコンテンツです。HTML5 Canvas要素とJavaScriptで作成しています。画面下のプルダウンでアルゴリズムの種類を選択すると、ランダムに配置されたデータが選択した方式に応じたアルゴリズムでソートされる様子を表示します。 デモを別ウインドウで再生する ソースコード
「クイックソート」「バブルソート」などのソート・アルゴリズムをフォークダンスで説明する恐るべきムービー集「AlgoRythmics」
たくさんのデータを大小関係に従って、小さい順(昇順)や大きい順(降順)に並び替える作業はソート(整列)と呼ばれ、ソフトウェア・プログラムではよく使われています。このようなソート作業を行うために並び替えの方法を手順化したのが「ソート・アルゴリズム」で、アイデアを理解すると「ほほー、なるほど」と思えるのですが、複雑すぎて理解しづらいものもあります。そんなソート・アルゴリズムの中でも有名で、仕組みを理解しておきたいものばかりを題材に、なんとフォークダンスに合わせてアルゴリズムを表現するムービー集「AlgoRythmics」が公開されており、学習効果があるかどうかは脇に置いて、思わず見入ってしまう魅惑のムービーとなっています。 最も有名なソート・アルゴリズムの一つである「バブルソート」をハンガリーのフォークダンスにのせて表現するのが「Bubble-sort with Hungarian ("Csá
「巡回セールスマン問題」を解くアルゴリズムを可視化したムービー
by Gaël Sacré いくつもの都市を移動するセールスマンが、すべての都市を最も効率よく(最小の移動コストで)移動できる方法を求める問題を「巡回セールスマン問題」といいますが、その解き方をビジュアル化したムービーがYouTubeで公開されています。 Traveling Salesman Problem Visualization - YouTube たとえば8つの都市があるとき、これを結ぶルートは5040通りが考えられます。 解法の一つが「欲張り法(Greedy Algorithm)」という、1つの都市から常に最寄りの都市へ移動しようと考える方法。 「最適」ではないものの、最適に近い答えを導き出してくれます。 ここで、組み合わせて使うのが「2-opt法」という方法。かなり単純なアルゴリズムで、2辺を繋ぎ直していきます。このとき、ルートに重なりがあると解消して新しいルートを作ります。
ナップサック問題でマラソンマッチ入門 - notブログ
マラソンマッチって？ 競技プログラミングのうち、「より良い解を求める」ことを競うコンテストをマラソン形式と呼びます。 例えば厳密解を求めることができない問題について、近似解のスコアを競ったりします。 マラソンでよく使われるアルゴリズム マラソンで頻出なのは「ビームサーチ」と「焼きなまし法」です。 この記事ではナップサック問題を例にしてこの２つのアルゴリズムを解説します。 もちろん、この２つのアルゴリズムはどちらも近似アルゴリズムなので最適解は求められません。 ビームサーチ まずは順番にナップサックに入るだけ入れるコードを書いてみます。 #include <iostream> using namespace std; int main() { // 個数 const int N = 100000; // ナップサックの大きさ const int W = 100000; // 重さ・価値 in
乱数のたのしい話と遺伝アルゴリズム - きしだのHatena
金曜日の「プログラマのための数学勉強会＠福岡」で乱数の話をしてきました。 プログラマのための数学勉強会@福岡 #3 - connpass で、乱数の生成だとか、クイックソートや素数判定などの乱択アルゴリズムの話とかをしました。 乱数タノシイヨ 乱数のたのしい話 from なおき きしだ その中で、遺伝アルゴリズムで巡回セールスマン問題(TSP)を解くというのをやってみました。遺伝アルゴリズム、すいぶん昔から名前は知ってて、どういうアルゴリズムかも知ってて、実装もそんな難しくないと知りつつ、書く機会がありませんでした。なので、この機会に書いてみようと。 とりあえず最初に完全にランダムでTSPを解いてみます。 TSP with random ぐちゃぐちゃですね。 下部のグラフはその時点での最短距離。最初に距離が短いものをみつけていくけどだんだんみつかりにくくなる、という感じになっています。 1
累積和の使い方を学ぶ – himajinworks::blog
ちょっととあるところで出くわしたので。 アルゴリズム苦手勢として、やったことはまとめておきたい。 あるデータ列Xがあって、Xのk個ずつの区間でのそれぞれの和を必要とする問題。(k≦|X|=N) 安直にやったら t_element x[N], r[N-K]; t_counter i, j; for (i = 0; i < N - K; i++) { r[i] = 0; for (j = 0; j < K; j++) { r[i] += x[i + j]; } } みたいな感じな気がする(コンパイルしてない)。でも超絶遅い。 でぐぐってみたら http://togetter.com/li/617816 の記事というかまとめを発見。累積和なるものを知る。 要は、 こんなことすると速くなるで、ってこと。 残念ながらそれまでの自分の頭のなかは画像の一番最後辺りの # zsh echo $(($(e
分散システムについて語るときに我々の語ること ― 分散システムにまつわる重要な概念について | POSTD
分散システムについては、もう随分と前から学びたいと思っていました。ただ、それは一度首を突っ込んだら最後、ゴールのない迷路に迷い込むようなものなのです。どこまでも続いているウサギの穴のようなものです。分散システムに関する文献は星の数ほど存在します。様々な大学からたくさんの論文が発表されているばかりでなく、膨大な数の書籍もあるのです。私のような全くの初心者には、どの論文を読んだらいいのか、どの書籍を買ったらいいのか、見当もつきません。 そんなとき、一部のブロガーが、 分散システムエンジニア （それがどういう意味であれ）になるなら知っておくべき論文というものを推奨しているのを見つけました。その一部を紹介しましょう。 FLP , Zab , Time, Clocks and the Ordering of Events in a Distributed Systems , Viewstamped
競馬の解析をガチでやったら回収率が100%を超えた件 - stockedge.jpの技術メモ
記事のタイトル通り、競馬で回収率100%を超える方法を見つけたので、その報告をする。 ちなみに、この記事では核心部分はぼかして書いてあるため、読み進めたとしても「競馬で回収率100%を超える方法」が具体的に何なのかを知ることはできない。（私は本当に有効な手法を何もメリットが無いのに公開するほどお人好しではないので） 本当に有効な手法を見つけたいのであれば、あなた自身がデータと向き合う以外の道は無い。 ただし、大まかな仕組み（あと多少のヒントも）だけは書いておくので、もしあなたが独力でデータ解析を行おうという気概のある人物なのであれば、この記事はあなたの助けとなるだろう。 ちなみに、これは前回の記事の続きなので、読んでない方はこちらからどうぞ。 stockedge.hatenablog.com オッズの歪みを探す さて、前回からの続きである。 前回の記事のブコメで「回収率を上げたいならオッズ
絶対に見逃せない投稿が、そこにはある - Qiita
Qiita の 「見逃せない投稿」 を独自に評価してランキングするサービス Qaleidospace を作りました。 本投稿では、そのようなサービスを作ろうと思った理由、投稿を評価するアルゴリズム、システム構成について書きます。 余談ですが、今なら Yearly Ranking がほぼ 2015 年の投稿ランキングとなっており、眺めていて楽しいです。 TL;DR Qiita の「見逃せない投稿」をランキングするサービス Qaleidospace を作った。 適切な評価システムがあれば、書き手も読み手もみんな幸せになれるはず。 ストック数だけで評価すると、初心者向けの投稿やキャッチーなキーワードを散りばめただけの投稿が注目されやすい。誰がストックしたのかを重視して「見逃せない投稿」を評価する。 風変わりなシステム構成: GitHub Pages でホスティング + Swift で書かれたバッ
安定結婚問題を解きながらHaskellプログラミングを紹介しつつ恋愛について学ぶ - Qiita
問題 n人の男性とn人の女性がいて,男性も女性もそれぞれ異性に対して明確な順序づけができる好みを持つとする. nは2以上の有限な自然数. 男性と女性がペアを作る問題を考えるが,このときに安定マッチング(不安定対がないようにマッチング)せよ. 安定マッチングというのは次の条件を満足するもの. そのマッチングを構成するあるペアとは異なるペアを組んだときに,新しいペアの2人がともに元のペアより好ましい相手を得る場合,もとのペアは安定ではない(不安定対).そのようなペアがないようなマッチングが安定マッチング. 不安定対というのは要は他に好き同士がいるので,今の相手との組(関係)は壊れやすいものだと思えばよさそう. Gale - Shapley のアルゴリズム この問題にはGale-Shapleyのアルゴリズムというのが知られている. Shapley先生というのは2012年にノーベル経済学賞を受賞さ
強くなるためのプログラミング -様々なプログラミングコンテストとそのはじめ方- - ぴよぴよ.py
みなさんは何のためにプログラミングをしていますか？ 仕事のため、何かをつくるため。 それも良いけれど、「強くなる」ためにプログラミングしてみませんか。 様々なジャンルのプログラミングコンテストとまだ見ぬライバルたちがあなたを待っています。 今回はアルゴリズム/AI/機械学習/セキュリティ等の様々なジャンルのコンテストとその始め方について紹介したいと思います。 ※これはPyConJPでの発表を文字におこしたものです。が、Pythonの話は殆どないです。 プログラミングコンテストとは？ すべてのコンテストに共通する、「コンテストに参加する利点」 1. 自分と同じ問題を解いた、他の人の解法を知ることができる 2. 同じコンテストに出ていた、たくさんのライバルと知り合える アルゴリズムのコンテスト 問題1 問題2 TopCoder Single Round Match CodeForces AtC
ソートアルゴリズム高速化への道 - kivantium活動日記
先日、アルゴリズムの授業でソートのアルゴリズムをいくつか習いました。ソートアルゴリズムの名前と原理くらいは聞いたことがありましたが、実装したことはなかったのでいい機会だと思い実装してみることにしてみました。ただ実装するだけでは面白くないので高速化の限界に挑戦してみたいと思います。 計測用プログラム 今回の計測では、ランダム値が入った配列のソートを100回行い、平均時間を各アルゴリズムに競わせるというシンプルなルールにしました。プログラムは以下の通りです。 C++11で入ったメルセンヌ・ツイスタなどの機能を使っているので、ビルド時には-std=c++11を指定する必要があります。 実験に使用したパソコンのCPUはCore i3-3227U@1.90GHz、コンパイラはgcc version 4.8.4で最適化オプションには-O3を指定しました。 #include <iostream> #in
定番アルゴリズム本リスト - カレーなる辛口Javaな加齢日記
どうせ何度も使い回ししそうなので，独立した項目に切り離した． アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (世界標準MIT教科書) 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一出版社/メーカー: 近代科学社発売日: 2012/08/02メディア: 単行本購入: 1人 クリック: 16回この商品を含むブログ (21件) を見るアルゴリズムイントロダクション 第3版 第2巻: 高度な設計と解析手法・高度なデータ構造・グラフアルゴリズム (世界標準MIT教科書) 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一出版社/メーカー: 近代科学社発売日: 2012/12/26メディア: 単行本購入: 1人 クリック: 4回
ITエンジニアなら知っておきたい、今更聞けないアルゴリズムの種類一覧 - paiza times
Photo by Oferico 皆さんはアルゴリズムやデータ構造について勉強したことはありますか？そして、基本的なアルゴリズムについて、どのようなものがあって、どのようなときに使うとよいかといったことを説明することができますか？ 仕事をしていると、プログラミング言語等の勉強や業務に忙しくて、正直アルゴリズムどころではないという場合がほとんどでしょう。しかし、いつか勉強しようと思っていたけど、基本的なアルゴリズムにどんなものがあるのかなんて今更聞けないな……ということもあるかと思います。 今回はそんな方に向けて、基本的なアルゴリズムの一部の概要に加え、アルゴリズムの勉強に役立つサイト、書籍をご紹介したいと思います。 ■アルゴリズムを学ぶ意味 例えば、ソート等については、通常はすでにソート関数があるので、自分で作らなくても済む＝アルゴリズムも勉強しなくていいと思ってしまうかもしれません。しか
遺伝的アルゴリズムでFX自動売買 その3 OandaAPIで実際に取引 - Qiita
前回の記事 pythonと遺伝的アルゴリズムで作るFX自動売買システム その1 遺伝的アルゴリズムでFX自動売買 その2 進化する売買AIの実装 今回作るモノ 自動売買システムを作ったときに使ったOandaAPIの紹介と、売買注文の発注機能について書いていこうと思います。 自動売買で使ったOandaAPI 5種類のAPIを使って構築しました。詳細はOandaのAPIDocument参照 OAuth2のTokenは、口座開いてログインするとWebで発行できます。 トークンはcurlコマンドHeaderのAuthorization: Bearer ********に設定します。 """ 01.アカウント情報API curl -H "Authorization: Bearer ********" https://api- fxtrade.oanda.com/v1/accounts/12345 "
リレーショナルデータベースの仕組み (1/3) | POSTD
リレーショナルデータベースが話題に挙がるとき、私は何かが足りないと思わずにはいられません。データベースはあらゆるところで使われており、その種類も、小規模で便利なSQLiteからパワフルなTeradataまで様々です。しかし、それがどういう仕組みで機能しているかを説明したものとなると、その数はごくわずかではないでしょうか。例えば「リレーショナルデータベース 仕組み」などで検索してみてください。ヒット数の少なさを実感できると思います。さらにそれらの記事は短いものがほとんどです。逆に、近年流行している技術（ビッグデータ、NoSQL、JavaScriptなど）を検索した場合、それらの機能を詳しく説明した記事はたくさん見つかると思います。 リレーショナルデータベースは、もはや大学の授業や研究論文、専門書などでしか扱われないような古くて退屈な技術なのでしょうか？ 私は開発者として、理解していないものを
本当に実用的なたったひとつのソートアルゴリズム - CARTA TECH BLOG
コンテンツメディア事業本部の新卒エンジニア坂本がお送りいたします。 突然ですが、皆さんの好きなソートアルゴリズムはなんですか？ 私は基数ソートのスマートでストイックな雰囲気に惹かれます。 とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。 むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。 ということで（？）、そのような現実的な場面で、本当に実用的なソートアルゴリズムを決める戦いが始まりました。 選手紹介 今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。 1 挿入ソート シンプル・イズ・ベスト！正直言ってベンチマークの噛ませ犬！ 2 クイックソート 「クイック」の名前はダテじゃない！王者の貫禄を見せてやれ！ 3 マージソート 安定感のある隠れた実
Pythonで基本のアルゴリズムを書いてみた - Something Beyond
2015-01-05 Pythonで基本のアルゴリズムを書いてみた Programming アルゴリズムを学ぶ意義みたいなものはいろいろなところで語り尽くされていると思うので私からは特にコメントしませんが、今回の勉強に利用した書籍でも引用されていた言葉が印象的なので、記しておきます。 最先端の機械を使って製品をつくるのは簡単で、しかも楽なことだが、基本技術を固める前に楽なほうに流れていってしまった。俺のような基本的なことがきちんとできるローテクが、今、我が世の春を謳歌しているんだ。 岡野雅行さんという職人さんの言葉のようです。そういえば随分前にこんな記事が盛り上がりました。 今すぐ辞めて欲しい、「Ruby on Rails勉強してます」「CakePHP勉強してます」 最新技術だけではなくて、その基礎となる技術をしっかり理解しなければダメだよということでしょう。ということで基本のアルゴリ
[KMP77] を読んでみた - d.y.d.
17:53 14/12/22 ソートの逆流れ クイックソートってあるじゃないですか、クイックソート。 配列、たとえば [4,2,1,7,0,6,5,3] があったときに、 小さい方を左に、大きい方を右にまず適当に集める。 この「小さい方」と「大きい方」への二分割を、いわゆる再帰的に、 分かれたブロック両方で同じ事を繰り返していくと… なんと、小さい順に並んだ配列 [0,1,2,3,4,5,6,7] が出来上がるというアルゴリズムです。 逆向き！ このデータの流れを「逆向きに」見てみたい。つまり、ソートが終わった最終状態から話が始まります。 しかも、さっきから説明なしで意味ありげにくっついていた、 「入力配列で元々どの位置にあったか」を表す値に注目していきます。 0の上に[4]がくっついているのは、最初は値0は配列のインデックス[4]の位置にあった、 ということを意味しています。（上のソート
![[KMP77] を読んでみた - d.y.d.](https://cdn-ak-scissors.b.st-hatena.com/image/square/e6fe840dfdcca31b69f48171e0de96a69b93595b/height=288;version=1;width=512/http%3A%2F%2Fwww.kmonos.net%2Fwlog%2Fsub%2Fdual%2F8.png)
Rubyで実装して楽しむ古典データ構造再入門（平衡木編） - hama_duのブログ
Competitive Programming Advent Calendar 2014 7日目です。 今回は古典的なデータ構造をRubyで実装してみます。 まず通常の木、二分木からはじめ、その次に二分探索木、そして二分探索木に少し機能を加え高性能にした平衡二分探索木を扱います。 冒険の地図 木 二分木 二分探索木 平衡二分探索木 ランダム挿入二分探索木 Treap 基本 木(Tree) 以下の図は木の例です。一番上にある頂点（丸）を根と呼びます。各頂点に直接ぶら下がっている頂点たちをまとめて子と呼びます。子を持たない頂点を葉と呼びます。 頂点同士は辺（棒）で結ばれています。木には、辺によってループができないという特徴があります。 木の性質 木には素晴らしい性質があります。各頂点の子を根と考える（上の部分は無視する）と、それぞれの子も木になっているという点です。それらの木のことを部分木と呼
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
