アルゴリズム総合スレ in ム板

ふう

同相写像がないから、という理由は変じゃないか？
連続でなくても全単射があればいいわけで（ないけど）

区間を広げて一部をとる、ではだめかね

>>945
棄却なしだからだめ

可能性があるのは、毎回、値を少しずつずらすくらいだな
無限回試行したときに均等になればよい

棄却なしの場合はと言ってますぜ

>>940
有限精度の浮動小数点を仮定する。
以下のようにしたら一応棄却はしてない乱数が作れる。

十分な大きさのbool配列を固定小数点として使い、それぞれのbitを
rand( [0,1) ) が0.5以上
→ビットを1に
それ以外
→ビットを0に

のように計算する。その結果を浮動小数点に直す。

あ、十分な大きさとってしまったら、下位ビットを棄却してることになるね。
浮動小数点の精度をちょうど満たすところで止めるようにしないと。

まぁ、どうせ揚げ足取りみたいな回答だけど...
でも有限精度の小数点なら、かたよりなしって考え方そのものが若干微妙だし、
有限精度じゃないのなら表現がまず難しい。

(1-delta)で割っちゃだめなん？＞[0,1]
指数が0.5で仮数が全部1な奴

棄却って何ですか？

>>950
割り算が決定的な限り、かならず偏る

本当の意味での(無限精度の)実数の場合:
そもそも[0,1)の一様乱数自体が存在しない。
存在したとしても、ちょうど0, ちょうど1が出る確率はないから、そのまんま[0,1],(0,1)として使える

有限精度実数の場合:
float, doubleなどのIEEE 754形式を使う場合:
[0,1)と[0,1]と(0,1)はそれぞれとりうる「場合の数」が違うわけだから、
情報量を勝手に補う、勝手に捨てる、をしないといけない。

独自形式で構わない場合:
形式を
struct{
int type;
unsigned int val;
};
とする。
type == 0のとき、val * deltaなる実数と解釈する。 ただしここでのdeltaは1/(UINT_MAX+1)なる有理数。
type == 1のとき、val * deltaなる実数と解釈する。 ただしここでのdeltaは1/UINT_MAXなる有理数。
type == 2のとき、val * delta + deltaなる実数と解釈する。ただしここでのdeltaは1/(UINT_MAX+2)なる有理数。
[0,1)の一様乱数は、typeを0, valを0〜UINT_MAXまでの一様乱数として表現できる。
[0,1]への変換は、typeを1にすることで実現でき、(0,1)への変換はtypeを2にすることで実現できる。

元が64bitの乱数だとdoubleにする時って、小さい値はデノーマライズされてるの？

>>954
そりゃ、そうならざるをえないだろ。

>>953
>存在したとしても、ちょうど0, ちょうど1が出る確率はないから、そのまんま[0,1],(0,1)として使える

いやそれを言ったらちょうど0.5が出る確率もちょうど1/πがでる確率もないことにならん？

>>956
無限精度だから
lim(x→∞) 1/x＝0
になる、んじゃね？

２つの乱数があったとして
両方が(1.0-delta)だと(1.0-delta)+(1.0-delta)って、四捨五入で2.0になっちゃうの？

>>957
だからその論法だと0と1の間の任意のxについて出る確率が0って
ことになるだろ。測度とか確率密度とかでぐぐって勉強するといいよ。

簡単にいうと閉集合と開集合は長さが一緒だから
確率も一緒ってことだよ。

「[0,1)で一様な実数乱数を生成する」って時点でもう現実に実行することは不可能なのだ。
有限のリソースで記述できない数はいくらでもある。

>>959
任意の特定の値が出る確率は全て0だよ。当然。

連続的な確率密度関数から値求めるときって、ちょうどxが出る確率なんてのは意味が無くて、
xからyまでの間の値が出る確率を求めないといけないんじゃないの？

ここで何を言おうが、メモリが無尽蔵にあろうが、コンピュータでは連続値を扱えないけど。

無限の広さを取る二次元空間に存在する点p_1, p_2, ..., p_nを、左上と右下の二点からなる矩形qと衝突判定したいんですが、
有効な方法はありますか？
一度p_nを座標からハッシュして有限の領域にマップしようと思ったのですが、
矩形qを成すそれぞれの座標軸の区間[x_1, x_2], [y_1, y_2]内の点q_a, ..., q_bをまとめて得る方法が分からず、頓挫しました。

矩形なら問題ないんじゃね

>>963
kD木

>>963
http://marupeke296.com/COL_2D_No8_QuadTree.html
これが恐らく最速

「恐らく」＝「根拠無し」

脳内最速

適当なこと書けば、誰かが答えてくれる。
実は催促なんだろ。

梅最強

>>966
正解
>>969
間違っています

>>966は空間が固定だから無理。
実際の所、kD木で解決したから問題なし。
妄想で出鱈目を書かないように。

DPCMについて
画像を圧縮する時に単純に左のピクセルとの差分にしてから圧縮する場合
日本で特許に触れるんでしょうか？
DPCMなんて古い枯れた技術だから大丈夫かと思ってたら
関連特許が山のように出願されてるみたいで怖いです。
ttp://www.jpo.go.jp/shiryou/s_sonota/map/denki14/1/1-3-1-2.htm

それをやっているPNGが特許にひっかかってないなら平気じゃない？

二つの円が重なったひょうたんの様な図形から二つの円を抽出するアルゴリズムありませんか？
図形はひょうたんの様に10%程度重なってるものから鏡餅の様に80%重なってるものまでを対象にしています。
円の直径は可変です。できれば2-5程度の複数円を抽出したいと思ってますが、２個すらできてません。
今日午前中潰して考えたんですが、なかなかいいアイディアがでません。
よろしくお願いします。

図形がy = f(x)で与えられているなら、f'が0になる点がそれぞれの円に2点ずつあるはずだから
その間の中点を二つの円で求めれば、半径と中心が出る。
f'が0な点がfで2つしかないなら二つの円の中心を結んだ点がy軸に並行で上の方法ができない。
その場合はx軸とy軸を交換して処理すれば良い。

>>976
>>975はビットマップ画像から中心座標と半径を求めるということじゃないかな
とりあえずこんな感じでどう？
1. 輪郭線を抽出
2. それぞれの円毎に輪郭線を分割（輪郭線の傾きが急激に変わる箇所で分割）
3. 輪郭線ごとに輪郭線上の任意の2点で接線に垂直な線を求める
4. 求めた2本の線の交点が1つの円の中心点
5. 円の中心点と3.の2点までの距離が半径

中心座標と半径を遺伝子にしてGAするとかどうだろうか？

ルービックキューブは20手以内で必ず解ける、数学者チームが特定
2010年08月17日 14:41　発信地:ワシントンD.C./米国
http://www.afpbb.com/article/environment-science-it/science-technology/2748734/6083818
【8月17日 AFP】米グーグル（Google）の支援を受けた国際研究チームが、
人気立方体パズル「ルービックキューブ（Rubik's Cube）」の全パターンを調べ上げ、
どんな状態からでも20手以内で全面の色をそろえることができることを突き止めた。

　これを突き止めたのは、米オハイオ（Ohio）州立ケント大学（Kent State University）の
Morley Davidson氏、グーグルのエンジニア、John Dethridge氏、ドイツの数学教師の
Herbert Kociemba氏、米カリフォルニア（California）州のプログラマーのTomas Rokicki氏ら
を含む数学者チーム。

　数学者チームによると、「（ルービック）キューブを解く人は手順をまとめたアルゴリズムを使う。
さまざまな種類のアルゴリズムがあり、複雑性の度合いや必要な手数などが異なっているが、
人間が記憶できるアルゴリズムは、最小手でも40手以上を必要とする」のだという。

「しかし神であればもっと効率的なアルゴリズム、常に最短の手数で済むアルゴリズムを
用いるだろうと人びとは考える。これは『ゴッドアルゴリズム（神のアルゴリズム、
God's Algorithm）』と呼ばれている。また、このアルゴリズムで解くために最大で必要な手数は
『ゴッドナンバー（神の数、God's Number）』と呼ばれている。そしてついに、
ゴッドナンバーは20であることを突き止めた」（数学者チーム）

　研究チームは、グーグルが提供した同社内のコンピューターの空き時間を用いて、
膨大なキューブの状態のそれぞれの解法をすべて突き止めた。それにかかった時間は
「わずか数週間」だった。グーグルは研究に提供したコンピューターの詳しい仕様などは
明らかにしていない。(c)AFP

どもです。
>>976
後出しで申し訳ありませんが、図形はビットマップなので最初の式が作れません
>>977
テスト画像でやってみました、いい感じで求まりました。
ありがとうございます。
実際にはビットマップの解像度が悪いせいで２の抽出が困難ですが
それは別問題なので解決とさせて頂きます。
どうもありがとうございました。

>>978
これでも求まりそうです、
特にビットマップの解像度が低い輪郭に相当量のノイズが混入してる場合は
むしろベストかもしれません。
まだ未挑戦ですが、これも一案として試行錯誤してみます。

>>980
問題の性質上、円は作業面に対して完全に内包されていて、全体が１つのオブジェクトを
構成しているんだから、２値化して、左上からラスタスキャンかけて、最初に見つかった
オブジェクトの要素から、右方向へ輪郭を追いかけていけば細線化する必要はないんじゃないか？
次の点が今まで辿ってきた要素から予測される方向以外へ向いているときその点を弧の接点と見なす。
最初の点は弧の頂点のはずだから以降の判定は容易だよね。
多少先読みすれば、同じ半径の円が少しだけずれて接しているような場合でも切り分けられるんじゃないかな。
ずっと追いかけ続けて、元の点に戻ってくれば走査終了。後は接続点から少し離れた充分にこの一部である
２点を使って計算すれば、誤差もすくなくなるかと。

>>982
細線化ってのは別にビットマップとして線を出してるわけではないです。輪郭点の配列です。
ビットマップ上の円は上下左右方向でドットが一列に並んでしまうという宿命があるんです。
ある程度小さい（解像度の低い）円になるとそれが無視できなくなるんです。
その辺の判定をした後でないと、半径探しの為に必要な適切な点が判定できませんので
細線化したデータはメモリに保管しておいたほうがベストと判断しています。

15000個のdoubleを昇順にソートして小さい順に3000個得る作業をできる限り高速に行いたいです。
残りの12000個は必要なく、また安定でなくても良いです。
どのようなソートが適しているでしょうか？

ソート後の小さい方から一部だけしか必要でない場合には速くなるような方法があるのでしょうか？

>>984
普通に考えるとソートを途中で止めるだけでいい気がしますが
データに特に特徴がなければクイックソートでいい気がします。

>>984
なんか面白そうな話だな。
最初の3000個だけ旨く得ることができたら爽快だろうな。
クイックソートを途中で止めると出来ると思う。

いかん、被ったorz

最初からデータを昇順に格納しておく

STLのpartial_sort()はヒープソートだな

上位 3000 がソートされている必要が無ければ（上位 3000 でありさえすればよいなら）、クイックソートを途中までするのがいい。
STL でいえば nth_element()。
上位 3000 がソートされている必要があればヒープソートを途中まで。
>989 にあるように STL の partial_sort()。

>>985-987
現在クイックソートでやってますが途中で止めてみます。

>>988
それはちょっと…

>>989-990
partial_sort()試してみます。

ありがとうございました。

ttp://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

の「k個の最小・最大要素の選択」