- 1 名前：デフォルトの名無しさん [2008/05/31(土) 15:57:02 ]
- やばい！論文書きます
- 115 名前：デフォルトの名無しさん [2011/12/11(日) 21:40:13.84 ]
- nコアで値分だけnop発行とか?
- 116 名前：デフォルトの名無しさん mailto:sage [2011/12/11(日) 22:00:16.82 ]
- >>115
あ、なるほど。勉強になりました。
- 117 名前：デフォルトの名無しさん mailto:sage [2011/12/11(日) 23:19:42.22 ]
- 1クロックですべてのデータを投入することが出来れば
クロックに合わせたスリープソートは実現可能。
でなければデータ投入にかかるクロックを厳密に計算しなければならない。
- 118 名前：デフォルトの名無しさん mailto:sage [2011/12/12(月) 06:22:42.30 ]
- データ量に応じていろいろ考えないといけないね。
キャッシュミスしたら死ぬし。
- 119 名前：デフォルトの名無しさん [2011/12/12(月) 22:12:37.15 ]
- つまりあれだ、SIMD的な何かがあればいいのか
SSXとか
- 120 名前：デフォルトの名無しさん mailto:sage [2011/12/17(土) 00:23:05.91 ]
- このスレまだあったのｗｗｗ
俺が大学生の時に建てたスレだｗ
- 121 名前：デフォルトの名無しさん mailto:sage [2011/12/17(土) 03:57:54.28 ]
- >>120
なんだ、中退したのか?
- 122 名前：デフォルトの名無しさん [2011/12/24(土) 23:09:10.65 ]
- 今ならGPUでバイトニックソート使うのが速さ的には一番だろうな
- 123 名前：デフォルトの名無しさん mailto:sage [2011/12/31(土) 12:21:00.78 ]
- うんこぶりぶり。
精子ドピュッドピュ
- 124 名前：デフォルトの名無しさん [2012/01/06(金) 15:18:24.61 ]
- 中央値を高速に見つけたいんだけど、やっぱソートしなきゃダメかね
- 125 名前：デフォルトの名無しさん mailto:sage [2012/01/06(金) 17:33:36.32 ]
- Wikipediaにはソートが必要だからO(nlogn)かかるって書いてあるね。
中央値 - Wikipedia ja.wikipedia.org/wiki/%E4%B8%AD%E5%A4%AE%E5%80%A4
以下、データ数nが奇数だという前提の下でソートから省ける処理がないか考えてみた。
n-1個のソートされたデータに対してn番目のデータを追加するとき、
中央値を得るだけが目的ならば暫定中央値候補2つとの比較だけすればいい。
時間を戻して、同様にn-2個のソートされたデータに対してn-1番目,n番目のデータを
追加することを考えると、n-1番目のデータは暫定中央値候補3つとの比較だけでよい。
nを101だとすると、52番目までは普通にソート。
53番目は50回比較。
…
100番目は3回比較。
101番目は2回比較。
…ダメか。(n+3)/2個のデータのソートは必要なので、
係数は変化するかもしれんが計算量がO(nlogn)であることからは逃れられん
っていうかむしろO(n^2)の部分を含んでるしorz。
高速化自体が目的なら、データ数次第では計算量のみで必ずしも優劣が決まるというわけではないけど。
- 126 名前：デフォルトの名無しさん [2012/01/10(火) 11:21:24.00 ]
- 両端の極端な値を落としてだいたい真ん中らへんの値
がほしいだけだから、アバウトでいいんだけど
適当にグループ分けて中央値の中央値を取ればいいのかな
でもその時点で最後までソートしても大差なさそうだな
- 127 名前：デフォルトの名無しさん mailto:sage [2012/01/10(火) 14:23:21.29 ]
- >>123
うわっ
俺の書き込みだわこれ
懐かしい
- 128 名前：125 mailto:sage [2012/01/10(火) 18:54:46.37 ]
- どーでもいーけど>>125の訂正。
このやりかただとO(nlogn)でFAでした。なぜなら2分探索すると次のようになるから。logの底は2。
53番目は50回、じゃなくてlog(50)回比較。
…
100番目は3回、じゃなくてlog(3)比較。
101番目は2回、じゃなくてlog(2)比較。
アバウトでいいなら計算時間が許容範囲になるまで間引くとかも考えられるけど
（合計値の）中央値の中央値とかのほうがまっとうだね。
データ数はすごく大きいのかな？
- 129 名前：128 mailto:sage [2012/01/11(水) 01:41:06.89 ]
- 訂正。（合計値の）←これナシで。
- 130 名前：デフォルトの名無しさん mailto:sage [2012/01/12(木) 23:38:01.46 ]
- >>125
それは Wikipedia が間違っている。
中央値は平均ではなく最悪O(n)で求められる。
- 131 名前：デフォルトの名無しさん mailto:sage [2012/01/14(土) 00:50:16.48 ]
- わかりにくい文だが中央値を平均O(n)で求められるなんて書かれていないぞ。
「平均値」を求める計算量がO(n)と言ってるだけ。
とくに何も断っていなければO記法の定義から最悪値の話に決まってる。
中央値を最悪O(n)で求められるというのが本当ならどのみち間違ってるけど本当?
- 132 名前：デフォルトの名無しさん mailto:sage [2012/01/14(土) 11:02:11.82 ]
- よく読んだらたしかに平均O(n)とも言ってないな。
平均O(n)でいいなら std::nth_element でいいし、最悪O(n)が欲しいなら以下:
(1) a_0,...,a_{n-1} を D個ずつ(ここではD=5) のグループに分ける:
a_0, a_1, a_2, a_3, a_4 | a_5, a_6, a_7, a_8, a_9 | a_10, ...
(2) 各グループのメディアンを求める。
求めたメディアン m_i は、各グループの先頭要素と交換しておく。
(3) ストライド 5 にして (m_i だけを見るようにして) 再帰し、m_i のメディアン M をもとめる。
(4) M をピボットにして quick sort 的な分割を行う。
(5) 求めたい順位が含まれるほうへ再帰。
ピボットの選び方を工夫しているので、(5) では多くても 7n/10 の要素に絞ることができる。
- 133 名前：デフォルトの名無しさん mailto:sage [2012/01/14(土) 11:20:44.38 ]
- (1) から (5) までにかかる時間 T(n) の内訳は
(2) と (4) は Kn (K は定数)
(3) は n/5 個の要素で再帰するので T(n/5)
(5) は多くても T(7n/10)
よって T(n) < Kn + T(n/5) + T(7n/10)
n をある有限の範囲内 (たとえば n < 100) のときに限れば、
十分大きい定数 L を持ってきてT(n) < Ln たらしめることができる。
そこで、L をあらかじめ巨大にとっておけば (K << L になるように)
帰納法によって任意のnに関し T(n) < Kn + 9/10 Ln < Ln が示せる。
- 134 名前：デフォルトの名無しさん mailto:sage [2012/01/14(土) 14:13:47.68 ]
- (3)が結局O(nlogn)じゃーんそれ
- 135 名前：デフォルトの名無しさん mailto:sage [2012/01/14(土) 14:45:20.29 ]
- いや訂正、(3)はO(n)か
- 136 名前：デフォルトの名無しさん mailto:sage [2012/01/14(土) 16:06:19.43 ]
- 結局全体ではO(nlogn)じゃーん？
O(n)の処理によって候補を最悪でも7/10に絞り込めるけど、
つまりデータ量が(10/7)倍になるごとにそのO(n)の処理をプラス1回やんなきゃいけなくなるわけだから。
- 137 名前：デフォルトの名無しさん mailto:sage [2012/01/14(土) 16:49:05.32 ]
- >>136
5で割り切れないときとかを端折って証明も添えたけど
理解できないか？
その辺の教科書によく書いてある有名な話だよ。
実際は、重いピボット選択を適当にサボるほうが平均的には速い。
gcc の nth_element の実装はサボってる。
(だから平均 O(n), 最悪 O(nlogn))
- 138 名前：136 [2012/01/14(土) 17:32:24.11 ]
- >>137
証明って、十分大きい数を用意する話はそもそもO記法の表現には関係なくないですか？
＞Kn + T(n/5) + T(7n/10)
いわゆる”O(n/5)”も”O(7n/10)”も全部O(n)ですから、
「この計算時間はKn + T(n/5) + T(7n/10) 」→「このアルゴリズムはO(n)」
の→(ならば)の部分には異存はないんです。ただそもそも計算時間はそれじゃないんじゃないかというのが>>136です。
俺が誤解してるとしたらT(n/5)の意味ですが、これってTの値がn/5の一次式で表現されるって解釈でいいんでしょうか？
- 139 名前：デフォルトの名無しさん mailto:sage [2012/01/14(土) 17:42:48.66 ]
- あー失礼T(n/5)の意味がわかりました、漸化式みたいなもんだったんですね。
- 140 名前：デフォルトの名無しさん [2012/01/15(日) 18:39:40.87 ]
- ちょっとでも数学を知っていればO(n)なんてあり得ないこと位、理解できそうなもんだ
O(n)であるということは、各々のデータの順位を求める処理の量がnの値に関係なく一定であることを意味している
つまりデータ同士の比較(これの処理量はｎの値に相関する)を使うことはできないということ
ではどうする？お前らに問いたい
- 141 名前：デフォルトの名無しさん mailto:sage [2012/01/16(月) 18:32:57.16 ]
- >>140
バケットソートはO(n)なんだが。
なにごとも前提しだいと言うことだ。
- 142 名前：デフォルトの名無しさん mailto:sage [2012/01/16(月) 20:33:31.15 ]
- バケツソートは「比較によらないソート」であって、一般にソートと言えば
比較によるソートのことだからな。
- 143 名前：デフォルトの名無しさん mailto:sage [2012/01/16(月) 22:19:53.56 ]
- ソーティングの下界はnlognだと証明されてる
- 144 名前：デフォルトの名無しさん mailto:sage [2012/01/17(火) 07:55:22.96 ]
- 未来予知するアルゴリズムがあればO(n)を実現できるよ
- 145 名前：デフォルトの名無しさん mailto:sage [2012/01/17(火) 08:09:52.41 ]
- テーブル展開してしまえばO(1)だよ、使用メモリは宇宙の全ての物質を使っても全然足りないけどなｗｗｗ
- 146 名前：デフォルトの名無しさん mailto:sage [2012/01/17(火) 11:56:53.50 ]
- >>145
O(n)の間違いじゃね？
- 147 名前：デフォルトの名無しさん mailto:sage [2012/01/17(火) 11:57:49.99 ]
- >>142
ではどうする？ に対して言ってるのに何を言ってんだお前は。
バカじゃないのか？ アホなのか？
- 148 名前：145 mailto:sage [2012/01/17(火) 12:57:57.01 ]
- >>146
ソート前のデータ全てのビット列をメモリアドレスに見立てて、
メモリの出力をソート済みの全データのビット列として取り扱うものとすればいいんじゃね
- 149 名前：デフォルトの名無しさん mailto:sage [2012/01/17(火) 15:00:03.00 ]
- >>148
データが重複してないことが前提じゃね？
- 150 名前：145 mailto:sage [2012/01/17(火) 15:47:18.22 ]
- 面倒だから数字一桁のソート(1と3と5が重複)
メモリアドレス：31415926535
↓
メモリデータ：11233455569
- 151 名前：145 [2012/01/17(火) 16:11:51.66 ]
- >>140
ほら、比較なしでソートできたzo
- 152 名前：デフォルトの名無しさん mailto:sage [2012/01/17(火) 19:04:41.96 ]
- char型の値2つのソートをテーブルで実現するときそのサイズは32KB。
short型(16bit)の値2つなら16GB。char型の値4つでも16GB。今のPC事情ならメモリ上に展開できる。
int型(32bit)の値2つなら…1TBのストレージが1000円で買えたとして1475億円か。国家プロジェクトにすればいける！
- 153 名前：デフォルトの名無しさん mailto:sage [2012/01/17(火) 21:54:31.33 ]
- チューリングマシンって無限長テープ(メモリ)だよな
ランダムアクセスできないけど
- 154 名前：デフォルトの名無しさん mailto:sage [2012/01/18(水) 15:46:49.43 ]
- >>150
なるほど〜
アイデアとしてはアリなんだな。
問題はメモリの効率化だけだな。
- 155 名前： 忍法帖【Lv=3,xxxP】 mailto:sage [2012/01/19(木) 02:46:38.42 ]
- いいね
- 156 名前：デフォルトの名無しさん mailto:sage [2012/01/20(金) 22:33:47.52 ]
- >>153
まあ数学者は計算が有限時間で終わるかどうかにしか興味ないから
- 157 名前：デフォルトの名無しさん mailto:sage [2012/01/20(金) 22:53:10.42 ]
- >>145
対応できる入力のサイズに上限があるからそもそもO記法の適用範囲ではない。
(データに応じてテーブルを大きくするんじゃなくて、どんなサイズのデータにも
対応できるテーブルをあらかじめ用意していないとダメ)
チューリングマシンのテープの長さは無限だけど、あらかじめ書きこんでおける
空白以外の記号は高々有限個だけ。
つまりあらかじめ用意しておけるテーブルのサイズも高々有限
- 158 名前：デフォルトの名無しさん [2012/01/22(日) 17:45:39.00 ]
- >>156
んなわけないだろ、だったらＰとかＮＰとかの発想出てこねえよ
ＰだってＮＰだって有限時間で終わるけど興味の対象だろうがよ
- 159 名前：デフォルトの名無しさん [2012/01/22(日) 17:47:10.56 ]
- ΩとかΘ記号の話が出てこないようじゃ話してる人のレベルが知れるな
記号はＯだけじゃないぞ
- 160 名前：デフォルトの名無しさん mailto:sage [2012/01/22(日) 19:22:33.28 ]
- >>159
いずれの記号もnを無限に大きくできなければ適用できない
- 161 名前：デフォルトの名無しさん mailto:sage [2012/01/22(日) 19:26:15.84 ]
- >>158
「数学者は」というのは一般化しすぎだったけど計算可能解析学のマイナーさを考えたら
大半の数学者が興味持ってないのは事実だろ。
有限時間内での計算量を扱う分野は数学ではなくて計算機科学に分類されることが多いし
- 162 名前：デフォルトの名無しさん mailto:sage [2012/01/23(月) 15:40:36.27 ]
- >>161
多くの数学者にとっても計算時間は重要じゃね？
無限に時間を使っていいならこの世どころかあの世も含め
すべての事象は計算可能なわけだし。
- 163 名前：デフォルトの名無しさん mailto:sage [2012/01/23(月) 20:55:50.37 ]
- >>162
またまたー
じゃあ停止問題解いてみろよ
- 164 名前：デフォルトの名無しさん mailto:sage [2012/01/23(月) 21:50:40.32 ]
- 問題を解くのに無限の時間がかかるってのは解けるって言うのか
- 165 名前：デフォルトの名無しさん mailto:sage [2012/01/26(木) 22:18:27.41 ]
- >>163
無限時間チューリング機械なら停止問題は解けるよ
そもそも無限に時間を使っていいなんて言った覚えはないけど。
数学者は無限でなければ気にしないとは言ったが
- 166 名前：デフォルトの名無しさん mailto:sage [2012/01/30(月) 20:12:24.96 ]
- 英語版Wikipediaにはちゃんと中央値を求める線形時間アルゴリズムが載ってた
https://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm
わかってたことだがやっぱ日本語版はうんこだ
- 167 名前：デフォルトの名無しさん mailto:sage [2012/01/30(月) 21:03:23.16 ]
- >>166
それじゃ、日本語版を改善してやってくれ。
- 168 名前：デフォルトの名無しさん mailto:sage [2012/01/30(月) 21:51:36.13 ]
- 日本語版「ん？」
選択アルゴリズム - Wikipedia
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
|
 |
