「C++の色々配慮してめんどくさい感じは好きだけど、実務になったらメモリ安全性とか考えて今後Rustに変わっていくんかな」
「うだうだ言ってないで仕事で必要なのをやればいいんだよ、趣味なら好きなのやればいい」
っていう雑談スレ。
結局C++とRustってどっちが良いの? 4traits
https://mevius.5ch.net/test/read.cgi/tech/1686046386/
関連スレ(マ板): Google&MS「バグの70%はC/C++。Rustにする」
https://medaka.5ch.net/test/read.cgi/prog/1619943288/
探検
結局C++とRustってどっちが良いの? 5traits
■ このスレッドは過去ログ倉庫に格納されています
2023/06/30(金) 21:56:35.52ID:PDIJ4aZy
667デフォルトの名無しさん
2023/07/18(火) 04:44:55.78ID:20jZ4czG オープンソースは、暴力と同じ。
暴力を振るうことは人間の能力の一つではあるが、
それだと社会が成り立たなくなるので近代社会では禁止
されているのと同様、オープンソースは禁止すべきだ。
暴力を振るうことは人間の能力の一つではあるが、
それだと社会が成り立たなくなるので近代社会では禁止
されているのと同様、オープンソースは禁止すべきだ。
668デフォルトの名無しさん
2023/07/18(火) 04:47:39.80ID:20jZ4czG >>667
発展途上国で低賃金でミシン労働者を使うのは搾取なので
禁止すべきと言われているが、それとオープンソースは同じ。
逆に、ミシンの方だけ禁止してオープンソースは許容
するのは差別。
LGBTやジェンダーだけ問題視するのもおかしい。
オープンソースは人権侵害だ。
発展途上国で低賃金でミシン労働者を使うのは搾取なので
禁止すべきと言われているが、それとオープンソースは同じ。
逆に、ミシンの方だけ禁止してオープンソースは許容
するのは差別。
LGBTやジェンダーだけ問題視するのもおかしい。
オープンソースは人権侵害だ。
669デフォルトの名無しさん
2023/07/18(火) 08:55:35.36ID:D1xcke2e 情報工学系ニキに聞いてみたい
volatileと書いたら、ついついatomicも付いてくると考えがちなのは、何の誤謬なのかな
volatileと書いたら、ついついatomicも付いてくると考えがちなのは、何の誤謬なのかな
670デフォルトの名無しさん
2023/07/18(火) 10:13:13.27ID:xpmB4AL6 イメージとしては両者は逆だな
volatileはIOメモリなどアクセスのためメモリ直接演算の最適化せずに律儀に値の読み込み→値の演算→値の書き込み
atomicはマルチスレッドなど競合に対処するためアトミック指定のメモリ直接演算
volatileはIOメモリなどアクセスのためメモリ直接演算の最適化せずに律儀に値の読み込み→値の演算→値の書き込み
atomicはマルチスレッドなど競合に対処するためアトミック指定のメモリ直接演算
671デフォルトの名無しさん
2023/07/18(火) 11:09:47.82ID:8SlkaJNb672デフォルトの名無しさん
2023/07/18(火) 14:01:35.52ID:Jy8oOC40 高速に動くプログラムを作るには極力if文を減らす、コピーを減らす等のキャッシュ効率の向上、+=, -=, *=, /=等の演算子でできるだけ四則演算を回していく。ここら辺か。
Rustでこの様な工夫をしたところ、かなりサイズの大きい配列の計算が速くなった。
Rustでこの様な工夫をしたところ、かなりサイズの大きい配列の計算が速くなった。
673デフォルトの名無しさん
2023/07/18(火) 15:28:04.66ID:FdSfzeLG >>672
本当はどんなマシン語(アセンブリコード)になるかを
知っていないと十分な高速化は難しいことがある。
それと、それ以上にアルゴリズムの
O(1)、O(log N)、O(N)、O(N logN)、
O(N^2)などの違いの方が遥かに重要だったりする。
数学が出来ない人は、後者が理解できない。
B.J.Stroustrup 氏もその辺が全く理解できて無い。
本当はどんなマシン語(アセンブリコード)になるかを
知っていないと十分な高速化は難しいことがある。
それと、それ以上にアルゴリズムの
O(1)、O(log N)、O(N)、O(N logN)、
O(N^2)などの違いの方が遥かに重要だったりする。
数学が出来ない人は、後者が理解できない。
B.J.Stroustrup 氏もその辺が全く理解できて無い。
674デフォルトの名無しさん
2023/07/18(火) 15:40:09.79ID:Jy8oOC40 >>673
アルゴリズムの最適化は当然だろ。それはやった上での話だよ。
アルゴリズムの最適化は当然だろ。それはやった上での話だよ。
675デフォルトの名無しさん
2023/07/18(火) 15:42:48.20ID:FdSfzeLG676デフォルトの名無しさん
2023/07/18(火) 15:55:20.63ID:Jy8oOC40 >>675
Stroustrupって誰だよ。自分は全然知らないな。普通はアルゴリズムの最適化を行い、プログラム自体の最適化を行うもんだろ。
Stroustrupって誰だよ。自分は全然知らないな。普通はアルゴリズムの最適化を行い、プログラム自体の最適化を行うもんだろ。
677デフォルトの名無しさん
2023/07/18(火) 16:06:28.75ID:fggT64M6 遅くなるの判ってても
.clone() しまくりたくなる誘惑
.clone() しまくりたくなる誘惑
678デフォルトの名無しさん
2023/07/18(火) 16:12:19.35ID:Jy8oOC40 >>677
できる限り参照返しにしてる。
できる限り参照返しにしてる。
679デフォルトの名無しさん
2023/07/18(火) 16:23:03.42ID:fggT64M6680デフォルトの名無しさん
2023/07/18(火) 16:26:10.43ID:fggT64M6 >>678
hoge.clone() したくなる場面(というかRustcがシレっとhoge.clone()しろって薦めてくるとき)
&hoge[..] とするだけで済むケースが結構あるけどこれ速くなってるよね?
hoge.clone() したくなる場面(というかRustcがシレっとhoge.clone()しろって薦めてくるとき)
&hoge[..] とするだけで済むケースが結構あるけどこれ速くなってるよね?
681デフォルトの名無しさん
2023/07/18(火) 16:53:51.58ID:fFSHFUc1 仕事でやってるやつでアルゴリズムの単純なオーダーを理解できないやつなんていないだろ
amortizedを理解できないとかそういう話ならまだわからなくもないが
amortizedを理解できないとかそういう話ならまだわからなくもないが
682デフォルトの名無しさん
2023/07/18(火) 17:12:16.37ID:FdSfzeLG >>681
アメリカ人は学者ですらちゃんと理解できて無い。
アメリカ人は学者ですらちゃんと理解できて無い。
683デフォルトの名無しさん
2023/07/18(火) 18:33:02.09ID:ArV4bzaH684デフォルトの名無しさん
2023/07/19(水) 00:05:33.03ID:OLP4lycj >>676
StroustrupはC++を作った人で少し前にその人の書いた記事が話題になってた
要約すると↓みたいな流れだったと思う
記事(英語)の内容
ファームウェアみたいにメモリアクセスが高価な環境では多少非効率でも
vectorを使った方がキャッシュ等の関係でパフォーマンスがよくなる
実測データでも数万件程度(うろ覚え)ではvectorが優位だった
記事に対するこのスレでの批判
何にでもvectorを使うように推奨するのはアルゴリズムを理解できてないからだ
StroustrupはC++を作った人で少し前にその人の書いた記事が話題になってた
要約すると↓みたいな流れだったと思う
記事(英語)の内容
ファームウェアみたいにメモリアクセスが高価な環境では多少非効率でも
vectorを使った方がキャッシュ等の関係でパフォーマンスがよくなる
実測データでも数万件程度(うろ覚え)ではvectorが優位だった
記事に対するこのスレでの批判
何にでもvectorを使うように推奨するのはアルゴリズムを理解できてないからだ
685デフォルトの名無しさん
2023/07/19(水) 00:22:21.27ID:A8l3aPdJ 算数100点大先生がcache localityを理解できないという話をまたやるのか
686デフォルトの名無しさん
2023/07/19(水) 00:38:56.49ID:BVUrsxWl >>680
どういうコードでhoge.clone()をお勧めされるんですか?
どういうコードでhoge.clone()をお勧めされるんですか?
687デフォルトの名無しさん
2023/07/19(水) 01:09:55.37ID:uHB1pLL3 ハッシュテーブルが遅くなる攻撃を思いつくような奴は確率を信じてない
というかこのラインをこえたら信じないというローカルルールがある
そもそもローカルがグローバルより劣っているみたいな考えは数学で扱わないので
そんなものを信じる義理はない
というかこのラインをこえたら信じないというローカルルールがある
そもそもローカルがグローバルより劣っているみたいな考えは数学で扱わないので
そんなものを信じる義理はない
688デフォルトの名無しさん
2023/07/19(水) 01:44:50.95ID:I9n1c/oL >>685
理解できて無いのはこのスレの馬鹿どもとStroustrup氏の法だ。
理解できて無いのはこのスレの馬鹿どもとStroustrup氏の法だ。
689デフォルトの名無しさん
2023/07/19(水) 04:04:32.47ID:hoAEd/Nt 文脈が全くわからないのだがStroustrupの記事ってどれ?
690デフォルトの名無しさん
2023/07/19(水) 08:41:42.67ID:fSe9gnNy691デフォルトの名無しさん
2023/07/19(水) 09:52:37.73ID:R6hIykH/ ハゲは>>684記事で実測を示したんでしょ?
692デフォルトの名無しさん
2023/07/19(水) 11:34:57.60ID:x9es5cRL >>676
C/C++ スレでハゲと描かれていたらそいつのことだ
C/C++ スレでハゲと描かれていたらそいつのことだ
693デフォルトの名無しさん
2023/07/19(水) 11:37:33.24ID:x9es5cRL694デフォルトの名無しさん
2023/07/19(水) 12:59:18.29ID:j0DQe/l9 >>690
「ほとんどの」というのが嘘だ。
「ほとんどの」というのが嘘だ。
695デフォルトの名無しさん
2023/07/19(水) 13:00:42.03ID:j0DQe/l9 この板は馬鹿ばっかりで、それで納得してしまうのかも
知れんが、海外のサイトだと、ちゃんと、リンクリストが
有利な場合が沢山あげられている。
知れんが、海外のサイトだと、ちゃんと、リンクリストが
有利な場合が沢山あげられている。
697デフォルトの名無しさん
2023/07/19(水) 13:07:03.89ID:j0DQe/l9698デフォルトの名無しさん
2023/07/19(水) 13:15:37.13ID:R6hIykH/699デフォルトの名無しさん
2023/07/19(水) 14:05:33.79ID:uHB1pLL3 価値観を押し付け合うのは実は平和的だよな
相手の価値観に合わせる柔軟なタイプが最も危険で
相手が戦争嫌いではないと知ったら嫌いになるまで戦争をやめない
相手の価値観に合わせる柔軟なタイプが最も危険で
相手が戦争嫌いではないと知ったら嫌いになるまで戦争をやめない
700デフォルトの名無しさん
2023/07/19(水) 14:24:01.78ID:+s9cgmAB Stroustrup師って、一人でさらさらって書いて出しちゃう御仁なのかな
こーゆうツッコミが入るのはわかるだろうにね やっぱ原著見ないとか
こーゆうツッコミが入るのはわかるだろうにね やっぱ原著見ないとか
701デフォルトの名無しさん
2023/07/19(水) 14:45:35.26ID:x9es5cRL >>699
なるほど折伏ですね判ります
なるほど折伏ですね判ります
702デフォルトの名無しさん
2023/07/19(水) 15:39:26.34ID:ZB5rrH9Z703デフォルトの名無しさん
2023/07/19(水) 16:11:16.93ID:KlTfFVa+704デフォルトの名無しさん
2023/07/19(水) 16:21:05.94ID:izSWunkt705デフォルトの名無しさん
2023/07/19(水) 20:59:38.09ID:OLP4lycj 興味ある人のためにStroustrup氏の記事のリンク(Rust本スレのPart18で議論されてた)
https://www.stroustrup.com/Software-for-infrastructure.pdf
URLからも分かるけど記事のタイトルは「Software Development of Infrastracture」で内容は少しハード寄り
https://www.stroustrup.com/Software-for-infrastructure.pdf
URLからも分かるけど記事のタイトルは「Software Development of Infrastracture」で内容は少しハード寄り
706デフォルトの名無しさん
2023/07/19(水) 21:18:14.58ID:Ss9DWb65 >>702
スゲーCOBOLに勝ててるんじゃん
スゲーCOBOLに勝ててるんじゃん
707デフォルトの名無しさん
2023/07/19(水) 21:21:56.85ID:L5673Vn2 >>705
ハゲの言うinfrastructure softwareはハードよりかどうかは関係ない
ハゲの言うinfrastructure softwareはハードよりかどうかは関係ない
708デフォルトの名無しさん
2023/07/19(水) 22:58:56.01ID:hoAEd/Nt 俺はハゲに同意かな
LinkedListはもはや古いデータ構造だと思う
現代のアーキテクチャにおいてはキャッシュメモリに乗せることがめちゃくちゃ重要なんだよ
LinkedListは挿入や削除を繰り返すとメモリアドレスがめちゃくちゃになりがちだし
ポインタを辿るという操作もページアウトなどを引き起こす
普通にポインタ配列のvectorが良い
もちろんreallocのコストが無視できない環境だと有効であるのは間違いない
LinkedListはもはや古いデータ構造だと思う
現代のアーキテクチャにおいてはキャッシュメモリに乗せることがめちゃくちゃ重要なんだよ
LinkedListは挿入や削除を繰り返すとメモリアドレスがめちゃくちゃになりがちだし
ポインタを辿るという操作もページアウトなどを引き起こす
普通にポインタ配列のvectorが良い
もちろんreallocのコストが無視できない環境だと有効であるのは間違いない
709デフォルトの名無しさん
2023/07/19(水) 23:21:25.02ID:hoAEd/Nt キャッシュメモリがゴミカスレベルのサイズ
もしくは存在しないレベル
メモリアロケーションのコストが高い
追加削除が頻繁に起きまくるようなソフトウェア
これらの場合はLinkedListで良いかも
もしくは存在しないレベル
メモリアロケーションのコストが高い
追加削除が頻繁に起きまくるようなソフトウェア
これらの場合はLinkedListで良いかも
710デフォルトの名無しさん
2023/07/19(水) 23:33:20.68ID:/VZakDHW コンパイラとかもろもろ最適化して計測するとndarrayクレートのArrayのイテレータよりも自分の作った多次元構造体のイテレータの方がまだ10倍くらい遅い。nextメソッドで呼び出される自作の外部関数の呼び出しがコストになってるっぽい。
711デフォルトの名無しさん
2023/07/20(木) 02:38:53.91ID:w+pPERAN 馬鹿な人ほど、LinkedListを嫌う傾向がある。
712デフォルトの名無しさん
2023/07/20(木) 02:50:37.46ID:o+4teY+W ほとんどのケースでLinkedListが使われないのは遅いしメモリも余分に食うためだ
次の位置のアドレスを得るためにメモリアクセスが必要となり遅い
Vectorなら次の位置のアドレスはインクリメントするだけだ
前の位置も辿りたいならLinkedListだと双方向リンクでさらにメモリ使用量も増える
次の位置のアドレスを得るためにメモリアクセスが必要となり遅い
Vectorなら次の位置のアドレスはインクリメントするだけだ
前の位置も辿りたいならLinkedListだと双方向リンクでさらにメモリ使用量も増える
713デフォルトの名無しさん
2023/07/20(木) 03:04:02.05ID:w+pPERAN714デフォルトの名無しさん
2023/07/20(木) 03:09:08.59ID:w+pPERAN >>713
>次のアドレスを得るのはどちらも mov 命令1つで、
>どちらも1クロックで時間に差は無い。
間違えた。
正しくは、
「インクリメントは、add、次のアドレスを得るのは movだが、
どちらも1クロックで必要時間に差は無い。」
>次のアドレスを得るのはどちらも mov 命令1つで、
>どちらも1クロックで時間に差は無い。
間違えた。
正しくは、
「インクリメントは、add、次のアドレスを得るのは movだが、
どちらも1クロックで必要時間に差は無い。」
715デフォルトの名無しさん
2023/07/20(木) 03:15:52.51ID:zPjslGgC いやだからメモリアクセスが支配的になるという話なのだが?
キャッシュメモリに乗ってないと致命的な速度低下となる
キャッシュメモリに乗ってないと致命的な速度低下となる
716デフォルトの名無しさん
2023/07/20(木) 03:18:02.86ID:o+4teY+W >>713
メモリアクセスに時間がかかることすら知らないならコンピューターの入門レベルからやり直せ
メモリアクセスに時間がかかることすら知らないならコンピューターの入門レベルからやり直せ
717デフォルトの名無しさん
2023/07/20(木) 03:22:57.78ID:w+pPERAN >>716
キャッシュメモリに乗っている場合の話だ。
乗っていない場合には、もちろんペナルティーが発生する。
ただ、ArrayListは、途中への挿入や削除がO(N)かかるが、
LinkedListは、O(1)だから、Nが10万の時には10万倍
の時間差となる。
一方、キャッシュのペナルティーは15(ns)くらいだから、
現在のCPUでは、45クロック位。
これだと、最悪のケースでも9倍程度だから、圧倒的に
LinkedListの方が時間的に安定。
キャッシュメモリに乗っている場合の話だ。
乗っていない場合には、もちろんペナルティーが発生する。
ただ、ArrayListは、途中への挿入や削除がO(N)かかるが、
LinkedListは、O(1)だから、Nが10万の時には10万倍
の時間差となる。
一方、キャッシュのペナルティーは15(ns)くらいだから、
現在のCPUでは、45クロック位。
これだと、最悪のケースでも9倍程度だから、圧倒的に
LinkedListの方が時間的に安定。
718デフォルトの名無しさん
2023/07/20(木) 03:25:15.25ID:w+pPERAN はっきりいって、ここの数学的才能の無い連中にも
俺は説得できる説明が出来る自信は有るが、敢えて
やってない。なぜなら、それを論文にしてステップアップ
に利用すると言うずるがしこい連中を多く見てきた
からだ。
俺は説得できる説明が出来る自信は有るが、敢えて
やってない。なぜなら、それを論文にしてステップアップ
に利用すると言うずるがしこい連中を多く見てきた
からだ。
719デフォルトの名無しさん
2023/07/20(木) 03:29:46.06ID:w+pPERAN この板の人は、数学的才能の無い人ばっかなので
異常に馬鹿丁寧に説明しないと理解できない。
今回の説明でも馬鹿丁寧だが、経験上、この程度の
丁寧さでは理解できないだろう。
もっとアセンブリコードまで徹底して書いて、
キャッシュとメインメモリの関係の図を書いて、
大量の比較コードを提示して、やっと僅かに理解できる人が
一人現れる程度だ。
それなのに、自分は賢いと思い込んでいる。
また、文書が読めない人が多い。
音声で言わないと理解できないらしい。
だから、掲示板では無理。
異常に馬鹿丁寧に説明しないと理解できない。
今回の説明でも馬鹿丁寧だが、経験上、この程度の
丁寧さでは理解できないだろう。
もっとアセンブリコードまで徹底して書いて、
キャッシュとメインメモリの関係の図を書いて、
大量の比較コードを提示して、やっと僅かに理解できる人が
一人現れる程度だ。
それなのに、自分は賢いと思い込んでいる。
また、文書が読めない人が多い。
音声で言わないと理解できないらしい。
だから、掲示板では無理。
720デフォルトの名無しさん
2023/07/20(木) 05:22:45.38ID:ShEsV12p はよ賢い人たちに説明しにいって、出禁にされてこい
721デフォルトの名無しさん
2023/07/20(木) 06:31:51.97ID:zPjslGgC722デフォルトの名無しさん
2023/07/20(木) 06:47:19.72ID:WN56tjQW LinkedListすらまともに作れない言語ってどうなんだろうなw
723デフォルトの名無しさん
2023/07/20(木) 07:29:26.02ID:o+4teY+W >>717
キャッシュメモリに載っていてもいなくてもメモリアクセスのペナルティが発生する
キャッシュに載っていないメインメモリならレジスタの数百倍
L3キャッシュに載っていればレジスタの数十倍
L2キャッシュに載っていればレジスタの十数倍
L1キャッシュに載っていてもレジスタの数倍かかる
メモリアクセスはこのようにとても遅い
したがってレジスタのインクリメントだけでアドレスを得られるVectorの方が有利になる
さらにVectorなら次の要素はほぼ必ずL1キャッシュに載っている恩恵も加わる
ほとんどのケースでVectorが速いのはこれらメモリアクセスの観点も効いている
キャッシュメモリに載っていてもいなくてもメモリアクセスのペナルティが発生する
キャッシュに載っていないメインメモリならレジスタの数百倍
L3キャッシュに載っていればレジスタの数十倍
L2キャッシュに載っていればレジスタの十数倍
L1キャッシュに載っていてもレジスタの数倍かかる
メモリアクセスはこのようにとても遅い
したがってレジスタのインクリメントだけでアドレスを得られるVectorの方が有利になる
さらにVectorなら次の要素はほぼ必ずL1キャッシュに載っている恩恵も加わる
ほとんどのケースでVectorが速いのはこれらメモリアクセスの観点も効いている
724デフォルトの名無しさん
2023/07/20(木) 08:26:57.52ID:uyFqK2iH ランダムアクセスになる場合なんかはlinkedlistなんかメチャクチャ遅くなる
例えばバッファサイズが8のフーリエ変換だと
1-5,2-6,3-7,4-8,
1-3,2-4,5-7-6-8,
1-2,3-4,5-6,7-8
とアクセスする
頭から読んでいくとものすごいコストがかかる
例えばバッファサイズが8のフーリエ変換だと
1-5,2-6,3-7,4-8,
1-3,2-4,5-7-6-8,
1-2,3-4,5-6,7-8
とアクセスする
頭から読んでいくとものすごいコストがかかる
725デフォルトの名無しさん
2023/07/20(木) 08:40:23.30ID:WN56tjQW そのレベルで速度気にするんならCやC++の方がよくね?
726デフォルトの名無しさん
2023/07/20(木) 09:05:41.95ID:o+4teY+W 全員がプログラミング言語に全く依存しない話をしてるところで唐突だな
727デフォルトの名無しさん
2023/07/20(木) 09:35:16.93ID:2+rEEHlb728デフォルトの名無しさん
2023/07/20(木) 11:05:22.25ID:397DPwdK ハゲの書いてることは00年代中盤にはCSでは一般常識化してた内容
実測すれば答えすぐ出るから
実測すれば答えすぐ出るから
729デフォルトの名無しさん
2023/07/20(木) 12:39:51.73ID:OPngbi2z >>720
出禁にされた結果がこのスレや
出禁にされた結果がこのスレや
730デフォルトの名無しさん
2023/07/20(木) 12:47:25.92ID:6BSTmMYa cargo は便利だけど crates.io の複数のモジュール同時使用で衝突するケースがあるよな
それぞれ単独で使うと問題起きないのに組み合わせて使うと死ねる
それぞれの開発者はたぶんお互いを認知してないかあるいは
どうなろうと知ったこっちゃないんだろ
それぞれ単独で使うと問題起きないのに組み合わせて使うと死ねる
それぞれの開発者はたぶんお互いを認知してないかあるいは
どうなろうと知ったこっちゃないんだろ
731デフォルトの名無しさん
2023/07/20(木) 12:56:38.69ID:6BSTmMYa732デフォルトの名無しさん
2023/07/20(木) 13:00:04.58ID:6BSTmMYa733デフォルトの名無しさん
2023/07/20(木) 13:03:06.20ID:6BSTmMYa >>721
明らかに君が可笑しい
明らかに君が可笑しい
734デフォルトの名無しさん
2023/07/20(木) 14:30:33.52ID:LhjzUCmo バランスを考えるのをやめろ
両極端の宗派はそのままにしておけ
統一するな
両極端の宗派はそのままにしておけ
統一するな
735デフォルトの名無しさん
2023/07/20(木) 15:21:54.49ID:zPjslGgC736デフォルトの名無しさん
2023/07/20(木) 15:33:00.56ID:E8mUVG43737デフォルトの名無しさん
2023/07/20(木) 15:43:18.38ID:7U3pGa9H LinkedListが一直線のリンクで実現してるのか、二分木とか赤黒木とかまで含んでるのかで話が変わる
738デフォルトの名無しさん
2023/07/20(木) 15:51:48.08ID:zPjslGgC >>736
うーん、じゃあもういいやw
うーん、じゃあもういいやw
739デフォルトの名無しさん
2023/07/20(木) 16:09:51.27ID:+MYe1bAK 同じO(N)でも性能は全く違うって話なのは理解してる?
740デフォルトの名無しさん
2023/07/20(木) 16:12:38.55ID:zPjslGgC このスレではLinkedListは常にO(1)ってことにしようw
よし使いまくるぞ!w
よし使いまくるぞ!w
741デフォルトの名無しさん
2023/07/20(木) 17:35:21.34ID:E8mUVG43742デフォルトの名無しさん
2023/07/20(木) 18:03:33.53ID:7Xbf5imk なおRust標準ライブラリのLinkedListの扱い
(https://doc.rust-lang.org/std/collections/index.html)
Use a `LinkedList` when:
* You want a `Vec` or `VecDeque` of unknown size, and can't tolerate amortization.
* You want to efficiently split and append lists.
* You are *absolutely* certain you *really*, *truly*, want a doubly linked list.
(https://doc.rust-lang.org/std/collections/index.html)
Use a `LinkedList` when:
* You want a `Vec` or `VecDeque` of unknown size, and can't tolerate amortization.
* You want to efficiently split and append lists.
* You are *absolutely* certain you *really*, *truly*, want a doubly linked list.
743デフォルトの名無しさん
2023/07/20(木) 18:32:16.87ID:zPjslGgC744デフォルトの名無しさん
2023/07/20(木) 18:57:14.98ID:KJVi0UK+ 1. ソートされた状態でデータを管理したい
2. 走査は激遅でいいけどキーに対応する値1件の取得/挿入/削除は高速に行いたい
3. 取得/挿入/削除時に先頭末尾以外位置はリストにアクセスしなくても分かる
これらを満たしてる場合にのみLinkedListが候補の1つに上がる
2. 走査は激遅でいいけどキーに対応する値1件の取得/挿入/削除は高速に行いたい
3. 取得/挿入/削除時に先頭末尾以外位置はリストにアクセスしなくても分かる
これらを満たしてる場合にのみLinkedListが候補の1つに上がる
745デフォルトの名無しさん
2023/07/20(木) 20:29:35.29ID:2+rEEHlb 数学の人とオープンソースの人はひょっとして同じ人?
746デフォルトの名無しさん
2023/07/20(木) 21:52:17.16ID:aEdleXCL ひょっとしなくても同じやつだろ
747デフォルトの名無しさん
2023/07/20(木) 21:57:32.90ID:neDY19sM >>744
>> 3. 取得/挿入/削除時に先頭末尾以外位置はリストにアクセスしなくても分かる
それはLinkedList全ての要素へのポインタ一覧を持っていないと無理だな
それをベクタで持つならその削除問題が発生してLinkedList利用の唯一の利点が消える
別のLinkedListで持つなら再び激遅な走査問題が起きる
>> 3. 取得/挿入/削除時に先頭末尾以外位置はリストにアクセスしなくても分かる
それはLinkedList全ての要素へのポインタ一覧を持っていないと無理だな
それをベクタで持つならその削除問題が発生してLinkedList利用の唯一の利点が消える
別のLinkedListで持つなら再び激遅な走査問題が起きる
748デフォルトの名無しさん
2023/07/20(木) 23:49:45.08ID:KJVi0UK+ >>747
一般的にはLinkedListとHashMapを組み合わせる
一部の言語に実装されてるLinkedHashMap/OrderedDictionaryや
基本的なLRUキャッシュの実装でその組み合わせが使われてる
一般的にはLinkedListとHashMapを組み合わせる
一部の言語に実装されてるLinkedHashMap/OrderedDictionaryや
基本的なLRUキャッシュの実装でその組み合わせが使われてる
749デフォルトの名無しさん
2023/07/21(金) 00:53:33.35ID:JyRjpbQR 一般的なLinkedListはともかくとしてRustに標準に実装されてる
use std::collections::LinkedList;
は前後のノードへのポインタで実現してるらしい
赤黒木がどうこうとかいうものではとてもなさそう
ランダムアクセスなんか劇遅やろ
そもそもLinkedListのくせに
「リストの中間地点に要素を追加したり、削除する操作が効率的にできるのも連結リストの特徴ですが、Rust1.26の時点では、そのような操作のためのメソッドが用意されていません」
とはどういうつもりなんやと
https://qiita.com/garkimasera/items/a6df4d1cd99bc5010a5e
use std::collections::LinkedList;
は前後のノードへのポインタで実現してるらしい
赤黒木がどうこうとかいうものではとてもなさそう
ランダムアクセスなんか劇遅やろ
そもそもLinkedListのくせに
「リストの中間地点に要素を追加したり、削除する操作が効率的にできるのも連結リストの特徴ですが、Rust1.26の時点では、そのような操作のためのメソッドが用意されていません」
とはどういうつもりなんやと
https://qiita.com/garkimasera/items/a6df4d1cd99bc5010a5e
750デフォルトの名無しさん
2023/07/21(金) 02:25:21.34ID:bXmgkOZk LinkedList単体で使おうとするとベクタ系での実装に対するアドバンテージがほとんどのケースで存在しない
またソートを維持したいならLinkedListよりもBTreeMapが有利
他にもそれぞれ目的別に有利なデータ構造がある
>>748
Rustにも毎日10万ダウンロードされているLinkedHashMapがある
https://crates.io/crates/linked-hash-map
またソートを維持したいならLinkedListよりもBTreeMapが有利
他にもそれぞれ目的別に有利なデータ構造がある
>>748
Rustにも毎日10万ダウンロードされているLinkedHashMapがある
https://crates.io/crates/linked-hash-map
751デフォルトの名無しさん
2023/07/21(金) 02:46:28.99ID:yV1TyWhB アルゴリズムやデータ構造の性能を評価する上で、
よく使われてきた計算量という指標の実用性も微妙になっちゃったな
よく使われてきた計算量という指標の実用性も微妙になっちゃったな
752デフォルトの名無しさん
2023/07/21(金) 03:01:04.83ID:2VYXkkOH >>724
そのように番号で場所にアクセスするような
事に使用するにはArrayが有利。
単純なLinkedListは、番号でアクセスする用途には向いていない。
LinkedListを効率よく利用するには番号ではなくアドレスでアクセスする。
アドレスとは、ノードに付けられた唯一無二の名前。
この板の人達はその概念が全く理解できず、
いつまでも番号によるアクセスから頭が切り替えられないでいる。
そのように番号で場所にアクセスするような
事に使用するにはArrayが有利。
単純なLinkedListは、番号でアクセスする用途には向いていない。
LinkedListを効率よく利用するには番号ではなくアドレスでアクセスする。
アドレスとは、ノードに付けられた唯一無二の名前。
この板の人達はその概念が全く理解できず、
いつまでも番号によるアクセスから頭が切り替えられないでいる。
753デフォルトの名無しさん
2023/07/21(金) 03:38:53.42ID:uRvhRVMm ndarrayクレートはイテレータの高速化のためにZip構造体を使ってるって聞いたんだけど、Zip構造体ってどんなことやってんの?誰か教えて。
754デフォルトの名無しさん
2023/07/21(金) 03:40:00.01ID:bXmgkOZk755デフォルトの名無しさん
2023/07/21(金) 03:49:23.59ID:bXmgkOZk >>753
今一瞬しか見ていないがndarray::Zipは単なるタプル化
今一瞬しか見ていないがndarray::Zipは単なるタプル化
756デフォルトの名無しさん
2023/07/21(金) 08:45:47.57ID:JJPP05HL これがRustの実力だ
FirefoxがついにChromeよりも高速なブラウザに
https://gigazine.net/news/20230720-firefox-surpassed-chrome-speedometer/
FirefoxがついにChromeよりも高速なブラウザに
https://gigazine.net/news/20230720-firefox-surpassed-chrome-speedometer/
757デフォルトの名無しさん
2023/07/21(金) 09:30:46.83ID:wvgr6UMJ そろそろ、(Rust世代の知見を組み入れた新世代の)C++でフルスクラッチが試みられてもいい頃合だな
758デフォルトの名無しさん
2023/07/21(金) 09:59:32.61ID:7DNLJ1Kp >>756
記事にはRustのRの字もないのだが本当に早くなった要因なの?
記事にはRustのRの字もないのだが本当に早くなった要因なの?
759デフォルトの名無しさん
2023/07/21(金) 10:11:38.01ID:QmRMHzGa まぁそんな結論出せるわけない
その結論出すにはFireFoxと同じアルゴリズムで別の言語で組み直して実測するしかない
そんな事誰もしない
しかしRustは他の言語に比べて抽象度はやや高め(C++等とでは)だから速度面とかでは不利になるはず
しかしそのディスアドバンテージが跳ね返されるくらいの性能がある事は実証されたとしていいやろ
その結論出すにはFireFoxと同じアルゴリズムで別の言語で組み直して実測するしかない
そんな事誰もしない
しかしRustは他の言語に比べて抽象度はやや高め(C++等とでは)だから速度面とかでは不利になるはず
しかしそのディスアドバンテージが跳ね返されるくらいの性能がある事は実証されたとしていいやろ
760デフォルトの名無しさん
2023/07/21(金) 10:27:50.89ID:AI3linaX761デフォルトの名無しさん
2023/07/21(金) 11:44:03.63ID:wjGhTghi >>751
絶対的性能を評価するためのものではなくて
要素数の変化に対する性能変化の次数(order of growth)を分かりやすく把握するためのもの
“計算量”という誤った訳語から受ける印象に引きずられてはいけない
絶対的性能を評価するためのものではなくて
要素数の変化に対する性能変化の次数(order of growth)を分かりやすく把握するためのもの
“計算量”という誤った訳語から受ける印象に引きずられてはいけない
762デフォルトの名無しさん
2023/07/21(金) 11:51:22.56ID:7DNLJ1Kp トータルの消費時間を決定する要因は複数なんだから
律速段階も見極めずに最適化しても意味はない
律速段階も見極めずに最適化しても意味はない
763デフォルトの名無しさん
2023/07/21(金) 14:00:29.86ID:7qvd6Y5g >>759
抽象度が高いことによる速度面の不利はコンパイル時間の方で吸収してると思う
抽象度が高いことによる速度面の不利はコンパイル時間の方で吸収してると思う
764デフォルトの名無しさん
2023/07/21(金) 14:39:47.78ID:73tgjVOL FireFoxは糞ブラ
↓
Rustは糞言語
↓
C/C++勝利
↓
Rustは糞言語
↓
C/C++勝利
765デフォルトの名無しさん
2023/07/21(金) 15:20:14.46ID:a1CVw2PP >>763
w
w
766デフォルトの名無しさん
2023/07/21(金) 16:03:44.31ID:JG1QJO7i767デフォルトの名無しさん
2023/07/21(金) 19:13:00.15ID:EuuKLcB1 フィールズ賞を受賞してる日本人で広中さんって人がいるよな
広中さんは「自分は鈍才だが、森君は天才」と言ってるそうな(wikipedia調べ)
このスレで数学の才能がどうのと言ってる人はこれもう
ひょっとしたら森さんなのかもしれんな
森さんって人も、フィールズ賞受賞してる数学の天才
このスレすげーな
広中さんは「自分は鈍才だが、森君は天才」と言ってるそうな(wikipedia調べ)
このスレで数学の才能がどうのと言ってる人はこれもう
ひょっとしたら森さんなのかもしれんな
森さんって人も、フィールズ賞受賞してる数学の天才
このスレすげーな
■ このスレッドは過去ログ倉庫に格納されています
ニュース
- 中国・ロシア両軍の爆撃機が東京方面へ向かう「異例のルート」を共同飛行…核も搭載可能、連携して威嚇か [ぐれ★]
- 高市首相の答弁書に「台湾有事答えない」と明記 存立危機発言当時 ★8 [蚤の市★]
- 「中国人の訪日熱は冷めた」 人気旅行先から日本外れる 14日で自粛呼びかけ1カ月 ★3 [蚤の市★]
- 京都のホテル大幅値下げ 訪日中国人客、年1000万人目前で急ブレーキ [蚤の市★]
- 【福岡】「50歳くらいの男性が倒れている」血を吐いた状態で歩道に倒れている女性見つかる 女性はその後死亡 事件と事故の両面で捜査 [ぐれ★]
- 「1800万円の売り上げゼロに…」中国インバウンドに特化の宿の今 ★3 [蚤の市★]
- 僕は反出生主義で安楽死合法化支持、そして人間の自由意志を否定してます ←どんな人物像?
- 【悲報】高齢者、マルチコピー機で自分の逮捕状を印刷してしまう [394133584]
- 女児(6)「大きくなったら素敵なお嫁さんになるー!」→女(24)「旦那様のチンポジュル!ジュルルル!グッポグッポ!」 [762037879]
- 【悲報】ゆたぼん、事故の治療費をネットで乞食して整形代に使ってる疑惑浮上wwwwwww
- 【高市リスク】京都のホテル大幅値下げ [115996789]
- 東京「女性の人権守ろう 子どもの人権守ろう 高齢者の人権守ろう」⇦成人男性ガン無視でワロタwwwwwwwwwww
