プログラミング初心者だけどfor文について質問がある

1: 2019/06/12(水) 20:43:29.720 ID:pa0wRb6n0
for文って例えばある配列のi番目の要素をprintするみたいにイテレータが走る順序によって結果が変わる場合と各iについてある配列のi番目の要素をiにする、みたいに順序がどうだろうが関係無い場合があるじゃん?
後者の場合ってfor文で回すと計算量がO(n)だけど並行処理すればO(1)のオーダーで済むはずなんだがその辺の効率化って皆どうしてんの?

2: 2019/06/12(水) 20:44:30.003 ID:3Ilrvi4Td
つまり
for文って例えばある配列のi番目の要素をprintするみたいにイテレータが走る順序によって結果が変わる場合と各iについてある配列のi番目の要素をiにする、みたいに順序がどうだろうが関係無い場合があるじゃん?
後者の場合ってfor文で回すと計算量がO(n)だけど並行処理すればO(1)のオーダーで済むはずなんだがその辺の効率化って皆どうしてるのかを聞きたいの?

4: 2019/06/12(水) 20:44:51.523 ID:/KtZ5u6b0
cuda使う

8: 2019/06/12(水) 20:47:15.455 ID:pa0wRb6n0
>>4
行列計算とかのライブラリは多分そうやって最適化してるよね

5: 2019/06/12(水) 20:45:35.785 ID:UUiOW+P70
並列化でggれ

9: 2019/06/12(水) 20:48:09.152 ID:D9EYNfWO0
SIMD命令の限界まで

10: 2019/06/12(水) 20:54:34.340 ID:pa0wRb6n0
>>9
ググったら…うげええええ
今までアセンブラ避けてきたけどコンパイラ最適化に手だそうとするとやはり避けては通れないか

12: 2019/06/12(水) 20:56:55.700 ID:UUiOW+P70
>>10
だから世の中にはintrinsicという概念があるんだ
特別な関数呼び出しをコンパイラが自動的に適切な機械語に置換してくれる

17: 2019/06/12(水) 20:59:41.397 ID:pa0wRb6n0
>>12
組み込み関数を越える関数を編み出したいなぁ…まあ無理か

11: 2019/06/12(水) 20:55:11.710 ID:0RkyWYbI0
今どきそんくらいの処理で効率化を考えるほうが非効率

13: 2019/06/12(水) 20:56:59.174 ID:pa0wRb6n0
>>11
そんなことはないと思うが…
計算量O(n)とO(1)って天と地の差じゃね?

14: 2019/06/12(水) 20:58:31.670 ID:UUiOW+P70
>>13
よほどの巨大な並列化じゃない限り、

並列化処理の準備に必要なコスト>>>並列化による速度向上

20: 2019/06/12(水) 21:02:12.616 ID:pa0wRb6n0
>>14
まあ俺が準備しようとしたらそうなるだろうな
組み込み関数作る人ってすげーや

15: 2019/06/12(水) 20:58:54.499 ID:iTgdfXjdd
parallel_forでおk

20: 2019/06/12(水) 21:02:12.616 ID:pa0wRb6n0
>>15
え、まさにそれじゃん
何の言語よ

16: 2019/06/12(水) 20:59:04.638 ID:Ikl4FhYu0
並行処理すると問題のオーダーって変わるの?
初心者だからわかんないや

19: 2019/06/12(水) 21:02:01.685 ID:UUiOW+P70
>>16
時間オーダーが必要コア数のオーダーに変換されるから、時間オーダーだけは減るじゃん?
でもコア数ってGPU使っても所詮は数万だし、銀の弾丸ではない

23: 2019/06/12(水) 21:06:03.647 ID:pa0wRb6n0
>>19
数万じゃ足りないケースってそんなあるかな
機械学習で膨大なデータ流すくらいしか思い浮かばない

25: 2019/06/12(水) 21:07:09.748 ID:UUiOW+P70
>>23
1000×1000のデータを並列化させるだけで100万だぞ

27: 2019/06/12(水) 21:08:05.686 ID:pa0wRb6n0
>>25
ああ、確かに
二重forになったらあっという間にリソース尽きるか

29: 2019/06/12(水) 21:13:27.097 ID:UUiOW+P70
>>27
つまり結局、実際に線形処理したらどれだけ速度が遅くて、
アルゴリズムの見直しだけではどれくらいまでしか減らなくて、
どこを並列化させると短縮時間-準備処理時間がどれだけになるかを全部検討した上で使えってこったな
実用上困ってないなら、わざわざCPUを選ぶ処理を書く必要はない

32: 2019/06/12(水) 21:19:09.042 ID:pa0wRb6n0
>>29
計算量のネックになってない部分で効率化しても大して恩恵無いしな
でも全体を考慮したうえでこの箇所には最適化が必要かどうか?ってことを常に考えながら書いてくのって難しいというか俺は普段全く出来てないや

33: 2019/06/12(水) 21:22:04.064 ID:UUiOW+P70
>>32
だから、しなくてよいのだ
する時には、実際に遅くて困る事態が発生して、実際にどの部分に時間がかかっているのかを測定した後でいい
明確に「これはくそ時間かかる処理を独立にやってるだけだから並列化しとけばいいよね」ってとこなら話は別だが

36: 2019/06/12(水) 21:29:26.578 ID:pa0wRb6n0
>>33
確かに必要になってから考えればいいか
ただ処理が遅い場合ってやろうとしてることがそもそもどう頑張っても時間がかかってしまうから仕方ない場合と単に無駄なことしてるせいで遅くなってる場合があってどっちのパターンなのか判別つかないから考えるのをやめてしまうことが多いわ俺は

26: 2019/06/12(水) 21:07:13.438 ID:q8gCfGyA0
ワイ2年前基本情報アセンブラ選択合格
去年応用情報合格

>>1
わからない

28: 2019/06/12(水) 21:09:40.801 ID:pa0wRb6n0
>>26
まじか…お前でも分からないなら諦めるしかないか…

34: 2019/06/12(水) 21:26:15.258 ID:RWbgHctY0
並列計算しようがO(n)はO(n)だぞ

37: 2019/06/12(水) 21:29:55.249 ID:pa0wRb6n0
>>34
なんでじゃ

39: 2019/06/12(水) 22:08:28.302 ID:RWbgHctY0
>>37
例えば、要素数nに対して100n秒で終わるアルゴリズムがあったとして、これを10並列にすると10n秒になるわけだが、nに対して比例関係なのは変わらない
100nだろうが、10nだろうが、O(n)だ

35: 2019/06/12(水) 21:27:48.516 ID:BRUtTomcd
最適化するな

38: 2019/06/12(水) 21:30:11.441 ID:+USo22k3d
画像処理で行単位で処理とかならFPGAで並列計算回路組んじゃったほうが楽ということも…

40: 2019/06/12(水) 22:29:46.512 ID:Zg+bgBTC0
常に十分量のコアがあると仮定して並列化のコストを無視すればO(1)