バブルソートよりも非効率なソートアルゴリズムを探して ―― ストゥージソートとスローソート - Line 1: Error: Invalid Blog('by Esehara' )
はじめに 恐らく、プログラマの中で配列内の要素を整列させたりするソートにお世話にならなかった人、というのは余り考えられないのではないでしょうか。しかし、とはいえ、大抵はソートを自前で実装せず、組み込み関数であったり、あるいは何らかのライブラリで済ませることが殆どだと思う。 車輪の再発明というよりも、バグとか、自分が考慮していなかった挙動などを避けるために、自前でソートを組むことは余りないのですが、とはいえ、自分なりにソートを実装して見ると、それがどういう特徴を持ったソートであるか、というのがわかりますし、また、ソートというのはいったいどういう操作で実現されるのかという洞察が深まってくるなあ、という実感があったりする。 なので、今回はあるソート二つについての話を書くのが趣旨です。 最高のアルゴリズムはある、だが最悪のアルゴリズムは何か 一口にソートといったところで、ソート自体にも銀の弾丸があ
Fisher-Yates Shuffle - Faith and Brave - C++で遊ぼう
Fisher-Yates Shuffle – An Algorithm Every Developer Should Know てきとうに抜粋して書く。 以下のシャッフルアルゴリズムは間違っていて、 def incorrect_shuffle(items): for i in range(len(items)): randomIndex = random.randint(0, len(items)-1) temp = items[randomIndex] items[randomIndex] = items[i] items[i] = temp return items これには、以下の3つの問題がある： 偏る 偏る 偏る 実は1つだったけど、これは大きな問題だ。 Fisher-Yates Shuffle (Knuth Shuffleとも呼ばれる)の実装は、以下のようになる： def fi
ボロノイ図を使ってラベルの重なり合いを解消する
画像をクリックすると、デモページに飛びます。 見づらいラベル 地図上に沢山のラベルを並べると、位置によっては重なり合ってとても見ずらくなります。 このラベルの配置位置をボロノイ図を利用して重なり合わないように配置してみます。 母点から中心点へ まず、ポイントを母点としたボロノイ図を描きます。 各ボロノイのセル（ボロノイ領域）の中心点を求め、母点から中心点へのラインを引きました。 ボロノイ領域の中心点は、母点から見て空きスペースの方角となります。 この角度を利用してラベルを配置します。 中心点に向けてラベルを配置 単純にラインに沿う角度でテキストを回転(rotate)させました。 重なり合いは解消されましたが、必ずしも見やすくはありません。 （これはこれで活用方法がありそうですが） ラベル開始位置をずらす 母点からボロノイ領域の中心点の方角へ、ラベルの開始位置を少しずらして配置した例です。
PROJECT LOP
プロジェクトのあらまし ＪＲの最長片道きっぷのルートを自力で求める 募金により実際に最長片道きっぷを買い、旅行する 旅行のようすをほぼリアルタイムで報告する プロジェクトの総括を「プロシン」で発表する 余った募金で「四国最長片道きっぷ」を買い、旅行する プロジェクトの産物 PROJECT LOP Report（実乗の記録） 最長片道きっぷ奮闘記（コンピュータサイエンス誌「bit」2001年２月号掲載） 最長片道きっぷ −理論と実践−（2001年プログラミング・シンポジウム発表、 共同研究者あり）→「山内奨励賞」を受賞 毎日新聞夕刊に掲載（2000年10月14日） 「だから LOP って何やねん」というあなたへ。LOP は Longest One-way ticket Problem の略です。実はさらにオチがあるんですけどね。 最長経路の導出過程をトレースした人には分かります。 Index
スクールガールストライカーズの 内製クライアントエンジン
近年、ハイスペックなスマートフォン、高品質なネットワークが普及し、それによりモバイルゲームの制作手法やそれを取り巻く環境も変化してきました。スクウェア・エニックスでは、そのような環境の変化に対して、日々新たなチャレンジをし続けています。そして、このようなスピード感溢れる業界の流れには、会社の枠を超えた技術情報の共有、交流が欠かせないと感じております。 そこでこの夏、社内のエンジニア・テクニカルディレクターによる最新のモバイル開発の技術情報や社内モバイルエンジン、開発秘話によるセッションをメインに、スクウェア・エニックス モバイル オープンカンファレンスを開催する運びとなりました。また、セッションの後は登壇する弊社スタッフと直接ディスカッションやフリートークができる場を設けております。この機会にスクウェア・エニックスという会社についても、より詳しく知って頂ければ幸いです。 マネージャー・テク
How to Write a Spelling Corrector
One week in 2007, two friends (Dean and Bill) independently told me they were amazed at Google's spelling correction. Type in a search like [speling] and Google instantly comes back with Showing results for: spelling. I thought Dean and Bill, being highly accomplished engineers and mathematicians, would have good intuitions about how this process works. But they didn't, and come to think of it, wh
Visualizing Algorithms
The power of the unaided mind is highly overrated… The real powers come from devising external aids that enhance cognitive abilities. —Donald Norman Algorithms are a fascinating use case for visualization. To visualize an algorithm, we don’t merely fit data to a chart; there is no primary dataset. Instead there are logical rules that describe behavior. This may be why algorithm visualizations are
一様乱数の生成 - 人工知能に関する断創録
Pythonによるモンテカルロ法入門（2014/6/20） 最初にPythonで [0.0, 1.0] 間の一様乱数を生成してみます。 一様分布 一様分布（Uniform distribution）の確率密度関数（pdf）は下の式になります。 引用：http://en.wikipedia.org/wiki/Uniform_distribution_(continuous) numpy.randomによる一様乱数の生成 numpy.random.uniformで一様分布に従う乱数が生成できます。下のスクリプトでは、下限を0.0、上限を1.0とした一様乱数をNsim個生成し、ヒストグラムを描画しています。 # 一様乱数の生成してヒストグラムを描画 import numpy as np import matplotlib.pyplot as plt np.random.seed() N = 10
機械学習アルゴリズムへの招待 | POSTD
機械学習の問題 については以前に紹介したので、次はどんなデータを収集し、どんな機械学習アルゴリズムを使うことができるのかを見ていきましょう。本投稿では、現在よく使用されている代表的なアルゴリズムを紹介します。代表的なアルゴリズムを知ることで、どんな技法が使えるかという全体的なイメージもきっとつかめてくるはずですよ。 アルゴリズムには多くの種類があります。難しいのは、技法にも分類があり拡張性があるため、規範的なアルゴリズムを構成するものが何なのか判別するのが難しいということですね。ここでは、実際の現場でも目にする機会の多いアルゴリズムを例にとって、それらを検討して分類する2つの方法をご紹介したいと思います。 まず1つ目は、学習のスタイルによってアルゴリズムを分ける方法。そして2つ目は、形態や機能の類似性によって（例えば似た動物をまとめるように）分ける方法です。どちらのアプローチも非常に実用的
その21 クォータニオンによるボーンの姿勢制御
ホーム < ゲームつくろー！ < DirectX技術編 < クォータニオンによるボーンの姿勢制御 その21 クォータニオンによるボーンの姿勢制御 ボーンは回転します。ぐるぐる回ります。そして、ボーンの先端には子ボーンがしっかりくっついています。また、子ボーンはそれ自身の座標系を持っていて、親ボーンと独立した回転を成します。2Dの場合、親ボーンの座標軸に対する子ボーンの座標のひねりは1つの角度で表現できますが、3Dとなると大変です。3つの軸角度で制御すると子ボーンのジンバルロックも招いてしまいます。3Dの場合、ボーンの回転はクォータニオンで制御するのが楽に思えます。この章では、ボーンの姿勢をクォータニオンで制御する方法について考えて見ます。 ① ボーンの先にくっついている子ボーンの座標系のねじれ ローカルオブジェクトに埋め込まれているボーンは、デフォルトで軸上にあります。ZXY軸回りを仮定す
オイラー角 | たむぶん
オイラー角 対称軸のある剛体の自由回転(その3 やり直しの続き)の続きです。 回っている剛体から見たときの角運動量と角速度ベクトルがどう動くかは多少分りましたが、止っている人(空間座標)から見たときの剛体の運動が分らないとあまり嬉しくありません。ここで説明するオイラー角を使うと、空間座標から見たときの剛体の動きが表現し易くなります。 オイラー角は、三つの角度θ,φ,ψを使って、剛体の空間座標系に対する傾きを表現する方法で、一般の剛体に対して使えますが、ここでは、話を単純にするために、対称軸のある剛体を使って説明します。 まず、角度θ,φを使って、対称軸を定めます。空間座標軸をx,y,z軸として、θはz軸に対する対称軸の傾き、φは、対称軸をxy平面に射影した直線のx軸からの傾きです。 そして、最後に角度ψを使って、剛体が対称軸回りにどれだけ回転したかを定めます。回転の基準として、ψ=0のとき
座標変換
ベクトルで座標を表し、行列で変換することを扱います。 ロボットの世界は３次元が基本ですが、平面上で３次元を扱うことが、そもそも分かりにくいことなので、ここでは主に２次元平面を扱います。 ２次元と３次元、異なる点はいろいろありますが、３次元はだいたいは「２次元＋1」か「２次元×３」なので、まずは２次元でしっかりイメージをつかみましょう。 表 記 これから座標を扱うに当たって、表記の仕方を原則として以下のようにきめておきます。 座標、ベクトルはボールドイタリック(太字斜体)、小文字 座標変換のための行列などはボールドイタリック(太字斜体)、大文字 座標軸名、点などはローマン体(普通の)大文字 座標、ベクトル、行列の左肩に、基準となる座標系を記載する。 もちろん、不要なら省略します。(詳細は追って) 例： ベクトル p 1を座標系Aで観察したものを転置(横ベクトル)。 なお、通常の文章(HTML
JavaScript (ECMAScript) の整数の精度と乱数の精度について / LiosK-free Blog
2010-05-30 カテゴリ: Client Side タグ: JavaScript Tips 久しぶりにJavaScript (というよりECMAScript) のネタ。今日はECMAScriptで扱える整数と乱数について。 ECMAScriptの数値 (Number) はIEEE 754の倍精度浮動小数点数であると仕様書に明記されている。 ECMAScript Language Specification 5th edition 4.3.19 Number value primitive value corresponding to a double-precision 64-bit binary format IEEE 754 value. (強調は引用者) ECMAScript Language Specification 3rd edition 4.3.20 Number Ty
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Gamasutra: Amir Fassihi's Blog - "0 – 60 fps in 14 days!" What we learned trying to optimize our game using Unity3D.
Teppei Baba presentations
Account Suspended
2014 TCO Marathon Round 3 (yowa)
kkaneko.com
Mesh Smoothing
http://arc360.info/algo/privatekey.html