Mozilla発のRust言語のスレ
公式
https://www.rust-lang.org/
https://blog.rust-lang.org/
https://github.com/rust-lang/rust
Web上の実行環境
https://play.rust-lang.org
前スレ
Rust part8
https://mevius.5ch.net/test/read.cgi/tech/1579834072/
探検
Rust part9
■ このスレッドは過去ログ倉庫に格納されています
2020/08/23(日) 01:07:35.52ID:MgEpWwVh
134デフォルトの名無しさん
2020/09/18(金) 09:09:51.55ID:FytpOkUB 先頭や末尾への挿入削除だけならVecDequeでよくね
135デフォルトの名無しさん
2020/09/18(金) 09:26:18.23ID:/+t0myE3 >>123が参照してる記事でもっと詳細あったわ
https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
こっちは、挿入が挿入箇所のサーチも加わったことを断った上で比較してますね
サーチを加えてもデータサイズがでかい・コンストラクタのコストが重い場合はlistが有利っすね
挿入位置のサーチの分のコストを含めるかは難しいところだけど、先頭・末尾以外の一定位置にだけ挿入するってシチュエーションはそうそうないだろうし、
この程度の比較でいいんじゃねーのかな
https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
こっちは、挿入が挿入箇所のサーチも加わったことを断った上で比較してますね
サーチを加えてもデータサイズがでかい・コンストラクタのコストが重い場合はlistが有利っすね
挿入位置のサーチの分のコストを含めるかは難しいところだけど、先頭・末尾以外の一定位置にだけ挿入するってシチュエーションはそうそうないだろうし、
この程度の比較でいいんじゃねーのかな
136デフォルトの名無しさん
2020/09/18(金) 09:34:00.68ID:/+t0myE3137デフォルトの名無しさん
2020/09/18(金) 09:59:55.15ID:2RtYnDyr 実際には、挿入箇所のサーチなど必要無い事が多いので、リンクリストが速い。
テストする人は馬鹿なので、実際的な「ランダム」の意味が分かってない。
テストする人は馬鹿なので、実際的な「ランダム」の意味が分かってない。
138デフォルトの名無しさん
2020/09/18(金) 10:03:14.54ID:2RtYnDyr >>135
>挿入位置のサーチの分のコストを含めるかは難しいところだけど、先頭・末尾以外の一定位置にだけ挿入するってシチュエーションはそうそうないだろうし、
>この程度の比較でいいんじゃねーのかな
違う。
サーチが必要なく、分かっている途中の場所に挿入するケースが圧倒的に多い。
>挿入位置のサーチの分のコストを含めるかは難しいところだけど、先頭・末尾以外の一定位置にだけ挿入するってシチュエーションはそうそうないだろうし、
>この程度の比較でいいんじゃねーのかな
違う。
サーチが必要なく、分かっている途中の場所に挿入するケースが圧倒的に多い。
139デフォルトの名無しさん
2020/09/18(金) 10:30:57.15ID:2RtYnDyr >>133
それはリンクリストだけの問題ではなく、>>122のように、動的配列でも
現実的には事情は変わらない事が多い。
動的配列は、要素のサイズが小さくて、Heap領域へのポインタなどを中に持ってない
場合のみ、リンクリストに勝てる。
たとえば、この条件に当てはまっている典型的な例として、文字列を文字の集合とみなした場合や、
3Dの頂点座標などは、(動的/固定)配列で持っているのは正しい判断で、リンクリストで
持つべきではない。
たとえば、要素がメンバとして、CStringやstd::stringなどの文字列を持つ構造体の場合は、
>>122の状況が生じるので、要素を配列で持ってもキャッシュミスは避けられない。
それはリンクリストだけの問題ではなく、>>122のように、動的配列でも
現実的には事情は変わらない事が多い。
動的配列は、要素のサイズが小さくて、Heap領域へのポインタなどを中に持ってない
場合のみ、リンクリストに勝てる。
たとえば、この条件に当てはまっている典型的な例として、文字列を文字の集合とみなした場合や、
3Dの頂点座標などは、(動的/固定)配列で持っているのは正しい判断で、リンクリストで
持つべきではない。
たとえば、要素がメンバとして、CStringやstd::stringなどの文字列を持つ構造体の場合は、
>>122の状況が生じるので、要素を配列で持ってもキャッシュミスは避けられない。
140デフォルトの名無しさん
2020/09/18(金) 10:40:12.02ID:2RtYnDyr STLの設計も悪いが、リンクリストに対するランダム挿入のテストで、
ランダムな整数kを求めて「k番目の要素」の直前に挿入するような
馬鹿なテストをしている場合、リンクリストは、先頭からk番目までを
丁寧に辿らなければならないので、その時にO(k)の時間がかかる。
全体の要素がN個の場合、このようなランダムの場合、平均でN/2に比例した時間が
掛かるのでO(N)と表現される。
しかもこのとき、要素をk個もたどらなければならないので、キャッシュミスがあったら
かなりの時間が掛かってしまう。
逆に、動的配列の場合は、先頭からkまでをたどったとしても、キャッシュミスは軽微。
しかし、現実の途中の挿入は、このような「辿る操作」が全く必要無い事が多いので、
リンクリストは速い。
要素を識別するために、先頭から「k番」という番号で行うのは、「配列流」で
あって、ポインタが理解できない人には、それしか方法が分からないが、リンクリストは
そのような方法で要素を識別しない。
そして、その識別方法こそが、リンクリストが配列よりも圧倒的に便利であることに繋がる。
ポインタはとても賢い方法なのだが、頭が悪い人には理解できないので、どうしても、
先頭からの番号でしか要素を識別したがらない。
そしてそのことこそが、あらゆることを遅くし、プログラムを見通しの悪いものにしている
ことにも気づかない。
ランダムな整数kを求めて「k番目の要素」の直前に挿入するような
馬鹿なテストをしている場合、リンクリストは、先頭からk番目までを
丁寧に辿らなければならないので、その時にO(k)の時間がかかる。
全体の要素がN個の場合、このようなランダムの場合、平均でN/2に比例した時間が
掛かるのでO(N)と表現される。
しかもこのとき、要素をk個もたどらなければならないので、キャッシュミスがあったら
かなりの時間が掛かってしまう。
逆に、動的配列の場合は、先頭からkまでをたどったとしても、キャッシュミスは軽微。
しかし、現実の途中の挿入は、このような「辿る操作」が全く必要無い事が多いので、
リンクリストは速い。
要素を識別するために、先頭から「k番」という番号で行うのは、「配列流」で
あって、ポインタが理解できない人には、それしか方法が分からないが、リンクリストは
そのような方法で要素を識別しない。
そして、その識別方法こそが、リンクリストが配列よりも圧倒的に便利であることに繋がる。
ポインタはとても賢い方法なのだが、頭が悪い人には理解できないので、どうしても、
先頭からの番号でしか要素を識別したがらない。
そしてそのことこそが、あらゆることを遅くし、プログラムを見通しの悪いものにしている
ことにも気づかない。
141デフォルトの名無しさん
2020/09/18(金) 11:07:59.09ID:0XVxbS2k リンクリストをサーチする場合
1.次の要素のアドレスを取得
2.次の要素のメタデータを取得
3.データを評価
4.アンマッチだったら1に戻る
を繰り返すので、メモリ配置次第ではランダムアクセスになりやすく
無策だとキャッシュミスを発生させやすいって話じゃないの?
1.次の要素のアドレスを取得
2.次の要素のメタデータを取得
3.データを評価
4.アンマッチだったら1に戻る
を繰り返すので、メモリ配置次第ではランダムアクセスになりやすく
無策だとキャッシュミスを発生させやすいって話じゃないの?
142デフォルトの名無しさん
2020/09/18(金) 12:20:02.02ID:2RtYnDyr >>141
でも、要素の中にstd::stringなどを入れていた場合、そのstringの中味は、
Heap領域を指しているので、どうせ動的配列でもキャッシュミスは生じる。
だから動的配列がサーチで有利になるのは要素がトリビアルな場合のみ。
また、サーチしても、削除などを行うととたんに動的配列は遅くなる。
この場合、O(N)個のCopyまたはMoveが生じる。Moveでも
コピー動作が全く生じないわけではないので(途中の)1個の要素の削除でも、
動的配列はO(N)の時間が掛かる。
一方、リンクリストは、O(1)。
読み取りが中心になる場合は、動的配列はもちろん速い。
でも、要素の中にstd::stringなどを入れていた場合、そのstringの中味は、
Heap領域を指しているので、どうせ動的配列でもキャッシュミスは生じる。
だから動的配列がサーチで有利になるのは要素がトリビアルな場合のみ。
また、サーチしても、削除などを行うととたんに動的配列は遅くなる。
この場合、O(N)個のCopyまたはMoveが生じる。Moveでも
コピー動作が全く生じないわけではないので(途中の)1個の要素の削除でも、
動的配列はO(N)の時間が掛かる。
一方、リンクリストは、O(1)。
読み取りが中心になる場合は、動的配列はもちろん速い。
143デフォルトの名無しさん
2020/09/18(金) 12:35:56.71ID:2RtYnDyr >>141
リンクリストをサーチするのは pure Cで書けばこんなに簡単で、物凄く効率が良い:
CNode *pNode = pTop;
while (pNode != NULL ) {
(pNodeを検査);
pNode = pNode->m_pNext;
}
リンクリストをサーチするのは pure Cで書けばこんなに簡単で、物凄く効率が良い:
CNode *pNode = pTop;
while (pNode != NULL ) {
(pNodeを検査);
pNode = pNode->m_pNext;
}
144デフォルトの名無しさん
2020/09/18(金) 14:22:59.83ID:JNeepSOt ( ´,_ゝ`)プッ
145デフォルトの名無しさん
2020/09/18(金) 15:09:39.89ID:lOTfajhS >>141
同じO(n)でもLocalityの違いでVecとLinkedListじゃ桁違いの差が出るよって話
「無策だと」って言っても現実的にLinkedListをVecと同じようにCache Friendlyにする方法ないよね?
同じO(n)でもLocalityの違いでVecとLinkedListじゃ桁違いの差が出るよって話
「無策だと」って言っても現実的にLinkedListをVecと同じようにCache Friendlyにする方法ないよね?
146デフォルトの名無しさん
2020/09/18(金) 15:41:38.07ID:2RtYnDyr 実際にテキストエディタでも作ってみれば、LinkedListの優秀さが分かる。
行数が大きくなった場合、動的配列では遅くてどうしようもない。
行数が大きくなった場合、動的配列では遅くてどうしようもない。
147デフォルトの名無しさん
2020/09/18(金) 16:53:33.12ID:JNeepSOt なるほどね
テキストエディタという具体例があったか
テキストエディタという具体例があったか
148デフォルトの名無しさん
2020/09/18(金) 17:30:51.35ID:lOTfajhS エディタの場合はO(n)の探索じゃ困るからLinkedListで作られてるメジャーなのないでしょ
Piece Table, Gap Buffer, RopeのいずれかでRope以外は基本的に配列を中心に実装されてる
VS Codeの例
https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation
Heap ManagerとかMemory Allocatorみたいなのは内部的にLinkedList使ってる
Piece Table, Gap Buffer, RopeのいずれかでRope以外は基本的に配列を中心に実装されてる
VS Codeの例
https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation
Heap ManagerとかMemory Allocatorみたいなのは内部的にLinkedList使ってる
149デフォルトの名無しさん
2020/09/18(金) 18:36:08.52ID:2RtYnDyr >>148
>エディタの場合はO(n)の探索じゃ困るからLinkedListで作られてるメジャーなのないでしょ
「探索」とは何のことか知らないが、
「検索」に関しては、ArrayListでもLinkedListでもbig O表記は変わらないが。
>エディタの場合はO(n)の探索じゃ困るからLinkedListで作られてるメジャーなのないでしょ
「探索」とは何のことか知らないが、
「検索」に関しては、ArrayListでもLinkedListでもbig O表記は変わらないが。
150デフォルトの名無しさん
2020/09/18(金) 18:40:53.97ID:2RtYnDyr StackOverflowも、これに関してはデタラメ。
実測してLinkedListの挿入が遅いとした人のコード見てたら、
ノードの個数Nの値が、1から100までしかならないようになっていて、
それを、以下の様に外側から100000回くらいループした、二重ループになっていた。
for(100000回のループ) {
リストの変数を作成
for(100回挿入するループ) {
}
}
これだと、LinkedListのNodeがHeapから作製される遅さばかりを測定しているだけで、
全く、LinkedListの真骨頂であるところのNが大きな時の挿入はテストできていない。
StackOverflowはとても高度なことを答えている人もいるが、この件に関しては、
レベルの低い人の書き込みが目立っている。あれを信じてはいけない。
実測してLinkedListの挿入が遅いとした人のコード見てたら、
ノードの個数Nの値が、1から100までしかならないようになっていて、
それを、以下の様に外側から100000回くらいループした、二重ループになっていた。
for(100000回のループ) {
リストの変数を作成
for(100回挿入するループ) {
}
}
これだと、LinkedListのNodeがHeapから作製される遅さばかりを測定しているだけで、
全く、LinkedListの真骨頂であるところのNが大きな時の挿入はテストできていない。
StackOverflowはとても高度なことを答えている人もいるが、この件に関しては、
レベルの低い人の書き込みが目立っている。あれを信じてはいけない。
151デフォルトの名無しさん
2020/09/18(金) 18:42:40.33ID:UNsmlUgz152デフォルトの名無しさん
2020/09/18(金) 18:49:50.54ID:2RtYnDyr153デフォルトの名無しさん
2020/09/18(金) 19:35:36.32ID:nXbcIFBH Intelの最適化マニュアルを見ると、不規則なメモリアクセスで
ハードウェアプリフェッチが有効に機能しないシチュエーションでは
ソフトウェアプリフェッチが有効であると書いてある。つまり
>>141 2.5 次アクセスするメモリに対しプリフェッチ出来る命令を実行する
みたいにすればメモリのランダムアクセスに起因するレイテンシを短縮できる
あとサーチの場合メモリ配置の局所性以外の要因でも配列とリンクリストの速度差は発生する
リンクリストの場合メモリ帯域の一部をアドレスのロードに取られるのでデータのロードに使える帯域は減少する
配列の場合はレジスタにおいたアドレスを使ってロードできるし
ストリング命令が使えるプロセッサであればサーチ命令を使用する事も出来る
ハードウェアプリフェッチが有効に機能しないシチュエーションでは
ソフトウェアプリフェッチが有効であると書いてある。つまり
>>141 2.5 次アクセスするメモリに対しプリフェッチ出来る命令を実行する
みたいにすればメモリのランダムアクセスに起因するレイテンシを短縮できる
あとサーチの場合メモリ配置の局所性以外の要因でも配列とリンクリストの速度差は発生する
リンクリストの場合メモリ帯域の一部をアドレスのロードに取られるのでデータのロードに使える帯域は減少する
配列の場合はレジスタにおいたアドレスを使ってロードできるし
ストリング命令が使えるプロセッサであればサーチ命令を使用する事も出来る
154デフォルトの名無しさん
2020/09/18(金) 19:52:23.34ID:qGyW3gPx Twitterによくいるトンチンカンな知識の割に
謎の上から目線で口上垂れてる同類だな
謎の上から目線で口上垂れてる同類だな
155108
2020/09/18(金) 21:29:14.35ID:EwCVEpJE Elixir では、リストへの全走査が主体。
フィルターとか
ランダムアクセスではない。
全探索が基本
全探索はリスト、ランダムアクセスは配列。
リストは、次の要素しか分からないから
「1, 2, 3, 4, 5」という要素があって、奇数だけをフィルタリングしたら、
「1 -> 3 -> 5」みたいに、リンクをつなぎ直す。
2, 4 はGC の対象になる
こういう全走査では、リストが圧倒的!
これが動的配列なら、2の削除で、345 を前に移動して、
4の削除で、5 を前に移動してと、コピーの連続になって大変
だから、Elixir では、リストが主体になっている。
関数型では状態を変えず、パイプラインで、新たな要素を作っていくのが基本
全走査が基本で、ランダムアクセスしないからだろう
フィルターとか
ランダムアクセスではない。
全探索が基本
全探索はリスト、ランダムアクセスは配列。
リストは、次の要素しか分からないから
「1, 2, 3, 4, 5」という要素があって、奇数だけをフィルタリングしたら、
「1 -> 3 -> 5」みたいに、リンクをつなぎ直す。
2, 4 はGC の対象になる
こういう全走査では、リストが圧倒的!
これが動的配列なら、2の削除で、345 を前に移動して、
4の削除で、5 を前に移動してと、コピーの連続になって大変
だから、Elixir では、リストが主体になっている。
関数型では状態を変えず、パイプラインで、新たな要素を作っていくのが基本
全走査が基本で、ランダムアクセスしないからだろう
156デフォルトの名無しさん
2020/09/18(金) 22:34:29.90ID:lOTfajhS157デフォルトの名無しさん
2020/09/18(金) 23:42:30.07ID:JNeepSOt158デフォルトの名無しさん
2020/09/18(金) 23:44:17.88ID:JNeepSOt VS Codeの異常に早い検索はそれで実現されてるのか
159デフォルトの名無しさん
2020/09/19(土) 01:43:40.66ID:nzD54rrP IteratorでItemがimpl Futureをしてる型を返すっていう実装したいんですが、方法が分かりません。
どのように解決すればよいのでしょうか?
while Some(fut) = fut_iter.next() {
let result = fut.await;
}
どのように解決すればよいのでしょうか?
while Some(fut) = fut_iter.next() {
let result = fut.await;
}
160デフォルトの名無しさん
2020/09/19(土) 02:11:22.63ID:U+RTm7Td >>154
数学が分からん人には、LinkedListの優秀性も理解できない。
実験しても実験の仕方が間違っているので間違った結果になっているが、
本人が気づかない。
C++のStrousstrup氏も間違っている。
集団幻想。
それだけ数学的なことは才能が必要だということだ。
多数決では、ArrayListが圧勝と言うことになってしまっているが、それは
本等は間違い。
数学が分からん人には、LinkedListの優秀性も理解できない。
実験しても実験の仕方が間違っているので間違った結果になっているが、
本人が気づかない。
C++のStrousstrup氏も間違っている。
集団幻想。
それだけ数学的なことは才能が必要だということだ。
多数決では、ArrayListが圧勝と言うことになってしまっているが、それは
本等は間違い。
161デフォルトの名無しさん
2020/09/19(土) 02:19:57.57ID:U+RTm7Td 数学的なことは、99%位の人が正しく理解できないので、ベンチマークテスト
のプログラムも1%位の人しか正しくかけない。
だからデタラメな集団幻想が、LinkedListが過小評価に繋がっている。
まだ、雑誌などでは学歴フィルターというか、頭の良さフィルターをかけて入社
させない仕組みがあるので、あまり間違ってはないが、ネットはめちゃくちゃ。
見ていたら、論文にまでしてしまっているひとまでいるようだが、間違っている。
のプログラムも1%位の人しか正しくかけない。
だからデタラメな集団幻想が、LinkedListが過小評価に繋がっている。
まだ、雑誌などでは学歴フィルターというか、頭の良さフィルターをかけて入社
させない仕組みがあるので、あまり間違ってはないが、ネットはめちゃくちゃ。
見ていたら、論文にまでしてしまっているひとまでいるようだが、間違っている。
162デフォルトの名無しさん
2020/09/19(土) 02:23:16.42ID:Vwp+/AeQ >>95
グラフ表現とかでもlinkedlist使わんの?
グラフ表現とかでもlinkedlist使わんの?
163デフォルトの名無しさん
2020/09/19(土) 03:22:40.39ID:Q84IJBEo あーあっち側の人すかー
有意義な議論ができるかと思ってた
皆さまご苦労さまです
有意義な議論ができるかと思ってた
皆さまご苦労さまです
164デフォルトの名無しさん
2020/09/19(土) 11:06:03.78ID:Ltx9b8Lt とりあえずベンチマーク取ってみたらええやん。。よくいる種類の馬鹿だよね。
こういうタイプはフィボナッチヒープとか大好きなんだよな。
こういうタイプはフィボナッチヒープとか大好きなんだよな。
165デフォルトの名無しさん
2020/09/19(土) 11:36:48.27ID:iDecIr7K ArrayListおじさんはArrayDequeをどう評価するの?
166デフォルトの名無しさん
2020/09/19(土) 12:38:52.28ID:2HkJedVD >>162
グラフは何かしらのツリー構造を使うからLinkedListは使わないでしょ
グラフは何かしらのツリー構造を使うからLinkedListは使わないでしょ
167デフォルトの名無しさん
2020/09/19(土) 16:29:00.47ID:4d+Mnie5168デフォルトの名無しさん
2020/09/19(土) 16:47:45.15ID:4d+Mnie5169デフォルトの名無しさん
2020/09/19(土) 17:53:59.50ID:Qry/LSKT まだ続くなら、動的配列とリストの具体的なベンチマークのコードを載せてくれ
rustが好ましい
rustが好ましい
170デフォルトの名無しさん
2020/09/19(土) 18:25:43.76ID:nFBIHSQH >>167
Javaでは、末尾追加の aitと、途中削除の rit、先頭への追加 は、LinkedListの方が
速いという結果だね。
この場合、要素数が2万個だけど、もっと多くなると理論上、その差はいくらでも開いて行く。
また、単純に全要素を足すsumitとsumforでは、0.25%, 1.4% の差しかない。
逆に、末尾追加のalastは、ArrayListの方が4.8倍速い。
これはLinkedListの場合、1要素ずつメモリアロケーターを呼び出しているので遅くなっており、
予想通り。
しかし、先頭追加のa0とalastの時間差が、LinkedListではほとんどない(理論上は全くないのだが)
のに対し、ArrayListでは82倍もあるのも予想通りの結果。
LinkedListは、先頭、末尾、途中のどこを操作しても、理論上、時間差が(ほぼ)ないが、
ArrayListは、大きく違ってくるというのが理論上予想されたことで、このベンチマークは正しく
それを反映している。
Javaでは、末尾追加の aitと、途中削除の rit、先頭への追加 は、LinkedListの方が
速いという結果だね。
この場合、要素数が2万個だけど、もっと多くなると理論上、その差はいくらでも開いて行く。
また、単純に全要素を足すsumitとsumforでは、0.25%, 1.4% の差しかない。
逆に、末尾追加のalastは、ArrayListの方が4.8倍速い。
これはLinkedListの場合、1要素ずつメモリアロケーターを呼び出しているので遅くなっており、
予想通り。
しかし、先頭追加のa0とalastの時間差が、LinkedListではほとんどない(理論上は全くないのだが)
のに対し、ArrayListでは82倍もあるのも予想通りの結果。
LinkedListは、先頭、末尾、途中のどこを操作しても、理論上、時間差が(ほぼ)ないが、
ArrayListは、大きく違ってくるというのが理論上予想されたことで、このベンチマークは正しく
それを反映している。
171デフォルトの名無しさん
2020/09/19(土) 18:27:51.00ID:nFBIHSQH >>170
なお、末尾追加も、同じサイズのノードに限定したものなら、メモリアロケーターが
劇速のものが作れるので、LinkedListでも、ArrayListに匹敵するくらい速度が
出るように作れる。
なお、末尾追加も、同じサイズのノードに限定したものなら、メモリアロケーターが
劇速のものが作れるので、LinkedListでも、ArrayListに匹敵するくらい速度が
出るように作れる。
172デフォルトの名無しさん
2020/09/19(土) 18:28:30.00ID:nFBIHSQH173デフォルトの名無しさん
2020/09/19(土) 18:30:31.19ID:nFBIHSQH この結果は、JavaのLinkedListが、素直にLinkedListを素朴に実装しているから
出てきたもの。
一方、STLは、設計が悪いので初心者が誤解を招く結果が出てしまう。
それは、追加する場所をアドレスではなく、先頭からの通し番号で指定する
ことが標準になっていたりするから。
出てきたもの。
一方、STLは、設計が悪いので初心者が誤解を招く結果が出てしまう。
それは、追加する場所をアドレスではなく、先頭からの通し番号で指定する
ことが標準になっていたりするから。
174デフォルトの名無しさん
2020/09/19(土) 18:48:41.03ID:cxOsPIuF >>173
> 先頭からの通し番号で指定することが標準になっていたりするから。
なんでそんな間違った前提を置いてるんだ?
C++ の std::list にそんな機能はないってことをたびたび指摘されてるが、
あんたは今までリンクリストの優位性がどうこう言ってたのとは別の人なんか?
(いや、そんなはずはないよな、こんな荒らし野郎が何人もいるとは思いたくない。)
> 先頭からの通し番号で指定することが標準になっていたりするから。
なんでそんな間違った前提を置いてるんだ?
C++ の std::list にそんな機能はないってことをたびたび指摘されてるが、
あんたは今までリンクリストの優位性がどうこう言ってたのとは別の人なんか?
(いや、そんなはずはないよな、こんな荒らし野郎が何人もいるとは思いたくない。)
175デフォルトの名無しさん
2020/09/19(土) 19:00:07.16ID:iDecIr7K Javaはmalloc/freeが超速いので、他の言語よりはLinkedListに優しい
176デフォルトの名無しさん
2020/09/19(土) 19:14:15.33ID:6s6pvu7S >>175
どうせ妄想を書いてるだけだろ
どうせ妄想を書いてるだけだろ
177デフォルトの名無しさん
2020/09/19(土) 19:22:13.23ID:k5fZduun GC言語は領域の再利用をgc時に行うからnewの時に空きを探す手間が少ない。
単純に端っこから割り当てていくだけ。
単純に端っこから割り当てていくだけ。
178デフォルトの名無しさん
2020/09/19(土) 19:39:34.30ID:nFBIHSQH179デフォルトの名無しさん
2020/09/19(土) 19:57:18.05ID:X3OIhUCa Listスレかな?
180デフォルトの名無しさん
2020/09/19(土) 23:26:19.32ID:4d+Mnie5181デフォルトの名無しさん
2020/09/19(土) 23:52:44.02ID:61l8trcl ゲームエンジン・データベースなどの本には、メモリプールを作る方法が、よく載っている
同じサイズの要素を、まとめて確保して、そのプール内で管理する方法
同じサイズの要素を、まとめて確保して、そのプール内で管理する方法
182デフォルトの名無しさん
2020/09/20(日) 00:02:10.17ID:MLu0Cj9r 次はhashmap vs vector
183デフォルトの名無しさん
2020/09/20(日) 00:06:23.82ID:hvjw0ZD9 ここで定番のRustハッシュ関数遅い問題で一悶着
184デフォルトの名無しさん
2020/09/20(日) 00:17:48.39ID:mlVvoUwY185デフォルトの名無しさん
2020/09/20(日) 01:00:22.31ID:zH0CDqJ7 >>181
システムコールの呼び出し回数を押さえるため?
でも通常のmalloc/freeもプロセス再起動されなければ領域再利用されるよね。
なら最初にmallocでガバっと取って、実際に使う時にfreeしてmallocしなおせば良くない?
ゲーム専用機の場合はシステムのAPIもいまいちだったりするから自前でメモリ管理もありだと思うし、DBの場合もキャッシュやら共有メモリやらmmapしてどうたらで自前で管理したいのもわかる。
でもそれ以外で普通のOS上のアプリで自前でメモリプール管理するメリットってどれだけあるの?
システムコールの呼び出し回数を押さえるため?
でも通常のmalloc/freeもプロセス再起動されなければ領域再利用されるよね。
なら最初にmallocでガバっと取って、実際に使う時にfreeしてmallocしなおせば良くない?
ゲーム専用機の場合はシステムのAPIもいまいちだったりするから自前でメモリ管理もありだと思うし、DBの場合もキャッシュやら共有メモリやらmmapしてどうたらで自前で管理したいのもわかる。
でもそれ以外で普通のOS上のアプリで自前でメモリプール管理するメリットってどれだけあるの?
186デフォルトの名無しさん
2020/09/20(日) 01:12:40.58ID:GOdQy7G8 予め決まったサイズを確保することが多いから、予めまとめて確保しておいて数珠繋ぎにしておけば最速で出し入れできる
187デフォルトの名無しさん
2020/09/20(日) 01:16:59.26ID:GOdQy7G8 16msecの間にすべての処理を完了しないといけないからmalloc呼び出しなんてありえないよ
188デフォルトの名無しさん
2020/09/20(日) 01:29:40.54ID:mlVvoUwY >>167
このデータの作り方だとLinkedListでもかなり連続したメモリ領域が使われてる可能性が高いような気がする
Javaの場合はList<int>じゃなくList<Integer>で
値を使うケースだとポインタを辿る必要があるのでそれも結果に影響しそう
このデータの作り方だとLinkedListでもかなり連続したメモリ領域が使われてる可能性が高いような気がする
Javaの場合はList<int>じゃなくList<Integer>で
値を使うケースだとポインタを辿る必要があるのでそれも結果に影響しそう
189デフォルトの名無しさん
2020/09/20(日) 03:23:18.11ID:7hHTPvJJ >>159 に答えれる方いませんか?
ここはリスト議論のスレッドですか?
ここはリスト議論のスレッドですか?
190デフォルトの名無しさん
2020/09/20(日) 08:14:35.07ID:nUMPJonN191デフォルトの名無しさん
2020/09/20(日) 09:09:08.11ID:sD69NUu0 挿入が必要なら普通はヒープ組むのになんで誰も突っ込まんの?
192デフォルトの名無しさん
2020/09/20(日) 10:27:51.76ID:iRiS7kHZ テキストエディタのようなものだと、アプリを起動して編集し始めた時から、
新しく追加したデータに関しては、対応するノードは、Heapからアロケートしても、
連続したアドレスに載っている。
ロードした直後、最後の行のノードのアドレスと、編集で追加したノード
のアドレスが近い。
編集で追加した行の直前直後のノードのアドレスと、編集で追加したノードのアドレスは
不連続である。
しかし、キャッシュは、何も、最後の1つのページだけしか覚えておけないわけでなく、
1000種類位は覚えておける。
だから、このくらいだと、どちらもキャッシュに乗ることになる。
なお、ArrayListの場合、途中へ追加すると、半分近くの要素に対してコピー動作が
必要になるが、その際、キャッシュを全て使い切ってしまうことがある。
配列の全データが100MBだとすると、このコピー動作のために100MB分のデータが
いったんキャッシュに読み込まれる必要がある。
キャッシュはL3ですら8MB程度しかないので、これだと全くキャッシュが足りなくなる。
その点、LinkedListは、このようなキャッシュ汚染は生じない。
新しく追加したデータに関しては、対応するノードは、Heapからアロケートしても、
連続したアドレスに載っている。
ロードした直後、最後の行のノードのアドレスと、編集で追加したノード
のアドレスが近い。
編集で追加した行の直前直後のノードのアドレスと、編集で追加したノードのアドレスは
不連続である。
しかし、キャッシュは、何も、最後の1つのページだけしか覚えておけないわけでなく、
1000種類位は覚えておける。
だから、このくらいだと、どちらもキャッシュに乗ることになる。
なお、ArrayListの場合、途中へ追加すると、半分近くの要素に対してコピー動作が
必要になるが、その際、キャッシュを全て使い切ってしまうことがある。
配列の全データが100MBだとすると、このコピー動作のために100MB分のデータが
いったんキャッシュに読み込まれる必要がある。
キャッシュはL3ですら8MB程度しかないので、これだと全くキャッシュが足りなくなる。
その点、LinkedListは、このようなキャッシュ汚染は生じない。
193デフォルトの名無しさん
2020/09/20(日) 10:32:00.78ID:iRiS7kHZ194デフォルトの名無しさん
2020/09/20(日) 10:48:59.50ID:iRiS7kHZ >>193
テキストエディタの例だと、100万行のファイルを読み込んだとしても、
実際に閲覧したり、書き込んだりしたい場所は、数箇所に集中することが
多い。
LinkedListの場合だと、編集時に行を挿入する場合、全データを移動する
必要が無いので、1行当たり、数10バイトくらいのコピーで済む。
この場合、キャッシュ汚染はほとんど生じない。
一方、ArrayListだと、100万行のコピー動作が必要になり、その際に
キャッシュを浪費してしまう。
テキストエディタの例だと、100万行のファイルを読み込んだとしても、
実際に閲覧したり、書き込んだりしたい場所は、数箇所に集中することが
多い。
LinkedListの場合だと、編集時に行を挿入する場合、全データを移動する
必要が無いので、1行当たり、数10バイトくらいのコピーで済む。
この場合、キャッシュ汚染はほとんど生じない。
一方、ArrayListだと、100万行のコピー動作が必要になり、その際に
キャッシュを浪費してしまう。
195デフォルトの名無しさん
2020/09/20(日) 10:55:21.87ID:GOdQy7G8196デフォルトの名無しさん
2020/09/20(日) 11:02:59.45ID:iRiS7kHZ197デフォルトの名無しさん
2020/09/20(日) 14:40:25.89ID:2Z1dYVPL なんでテキストエディタの例でArratListが出てくるんだ
198デフォルトの名無しさん
2020/09/20(日) 17:50:32.22ID:rmF3ZCsn スレ間違ってますよ
199デフォルトの名無しさん
2020/09/21(月) 04:23:45.31ID:6Tk/tz3a200デフォルトの名無しさん
2020/09/22(火) 01:30:08.72ID:oMNW4x3G CSのスレでも立てればいいのにな
無駄なマウントとプライドで議論になってないじゃん
無駄なマウントとプライドで議論になってないじゃん
201デフォルトの名無しさん
2020/09/22(火) 02:42:29.78ID:EwzeVKsQ あっちで相手にされないからこっちに来るんだろう
202デフォルトの名無しさん
2020/09/22(火) 02:55:14.94ID:3nDER7vv あっちってどこ?
203デフォルトの名無しさん
2020/09/22(火) 03:04:18.34ID:EwzeVKsQ 本人にだけ判れば良いんだよ
204デフォルトの名無しさん
2020/09/23(水) 23:05:59.13ID:JL46F86k Rust 初心者ってか始めてもないけど、
fn main() {
println!("Hello, world!");
}
これってセミコロン要るの?
fn main() {
println!("Hello, world!");
}
これってセミコロン要るの?
205デフォルトの名無しさん
2020/09/23(水) 23:22:55.07ID:O1ICXtuo206デフォルトの名無しさん
2020/09/24(木) 04:24:32.56ID:sKL6gd3p なんでreturn文省略するん
207デフォルトの名無しさん
2020/09/24(木) 08:46:29.52ID:imaK44AN208デフォルトの名無しさん
2020/09/24(木) 19:57:00.21ID:AHitBJm/ 関数型のフリがしたいから。
209デフォルトの名無しさん
2020/09/24(木) 20:40:06.68ID:aHCv/EIt return省略は関数型なのか?
関数型をふりをするなら {} を省略して = で書くとかでは
関数型をふりをするなら {} を省略して = で書くとかでは
210デフォルトの名無しさん
2020/09/24(木) 21:02:07.22ID:anZxJGRt lispのprognみたいな感じじゃね。
セミコロンを書くとその後に空の式があるようにみなすのはイケてないと思うけど。
セミコロンを書くとその後に空の式があるようにみなすのはイケてないと思うけど。
211デフォルトの名無しさん
2020/09/24(木) 21:34:50.13ID:sW11ypIO expressionをstatementにするのがセミコロン
statementは`()`として扱われる
セミコロン不要にして必要に応じて`()`を明記するスタイルのほうがイケてたとは思う
returnを省略するのは慣習
関数を含めて式が値に評価されていくというメンタルモデルなので
”return文”という感覚ではないのかもね
statementは`()`として扱われる
セミコロン不要にして必要に応じて`()`を明記するスタイルのほうがイケてたとは思う
returnを省略するのは慣習
関数を含めて式が値に評価されていくというメンタルモデルなので
”return文”という感覚ではないのかもね
212デフォルトの名無しさん
2020/09/25(金) 01:43:09.63ID:rqLAnW3Q C++系言語に見た目を近づけるという設計意図があるから()を明記するという判断にはならなかっただろうとおもう
213デフォルトの名無しさん
2020/09/25(金) 06:33:09.44ID:JNOcuagu 戻り値型の宣言にも -> () っていちいち書かなくていいしなあ
そういうもんだとしか
そういうもんだとしか
214デフォルトの名無しさん
2020/09/25(金) 07:11:20.18ID:LUJK9/4D なんで戻り値は型推論してくんないんだろう。
215デフォルトの名無しさん
2020/09/25(金) 07:33:16.25ID:SbSfhD0k 単純に、セミコロンの有無だけで区別するのが視認性が良くないんだよな。
エディタの方で違いを目立たせられたりしたらいいけど。
エディタの方で違いを目立たせられたりしたらいいけど。
216デフォルトの名無しさん
2020/09/25(金) 07:58:20.78ID:ZK6gJNpW217デフォルトの名無しさん
2020/09/25(金) 19:12:30.94ID:yo3ZA1rx >>215
いまさらどうにもならないが、使いはじめの頃は、もっと視認性のあるフレーズ使ってくれてたらなぁと思ってた。
例えば、F#の
hofe |> ignore
なんかは、冗長ではあるが逆に視認性も良く、捨てる気満々の書き方で気に入ってる。
いまさらどうにもならないが、使いはじめの頃は、もっと視認性のあるフレーズ使ってくれてたらなぁと思ってた。
例えば、F#の
hofe |> ignore
なんかは、冗長ではあるが逆に視認性も良く、捨てる気満々の書き方で気に入ってる。
218デフォルトの名無しさん
2020/09/25(金) 23:12:55.80ID:ZK6gJNpW そういえばelse節の無いif式は()に評価されるんだっけか
219デフォルトの名無しさん
2020/09/25(金) 23:17:40.79ID:ZK6gJNpW https://doc.rust-lang.org/reference/expressions/return-expr.html
ってかそもそもRustのreturnは式だったわ
return bar;はreturn文じゃなくて式文の一種だったわ
ってかそもそもRustのreturnは式だったわ
return bar;はreturn文じゃなくて式文の一種だったわ
220デフォルトの名無しさん
2020/09/26(土) 06:07:19.66ID:Jy/kksq4 コンピューターはともかく、人間にはreturnくらいの文字的冗長性があった方が視認性がいい。
221デフォルトの名無しさん
2020/09/26(土) 08:31:48.23ID:2tuZfHCi ifは末尾}に;不要なのにletは末尾}に;必要なのだるい
222デフォルトの名無しさん
2020/09/26(土) 09:30:48.93ID:en54jqZM >>220
returnがあればearly returnだと識別できるのでその意味では視認性は高い
ただセミコロンというC系言語経験者が注視しない記号に新しく重要な意味をもたせたから戸惑う
>>221
ifブロック末尾のセミコロンは常に省略できるわけじゃない
https://doc.rust-lang.org/reference/statements.html#expression-statements
セミコロンがないと意図通りパースできないケースってほとんどないと思うので
そのうちJSのASIのようなものでセミコロン不要になる未来もある気がする
returnがあればearly returnだと識別できるのでその意味では視認性は高い
ただセミコロンというC系言語経験者が注視しない記号に新しく重要な意味をもたせたから戸惑う
>>221
ifブロック末尾のセミコロンは常に省略できるわけじゃない
https://doc.rust-lang.org/reference/statements.html#expression-statements
セミコロンがないと意図通りパースできないケースってほとんどないと思うので
そのうちJSのASIのようなものでセミコロン不要になる未来もある気がする
223デフォルトの名無しさん
2020/09/26(土) 10:01:37.83ID:GOW7LNc9 個人的にはセミコロンうんぬんよりifの中括弧が苦痛
/* c */
#include <stdio.h>
#define min(a, b) ((a) < (b) ? (a) : (b)) // スッキリ
int min2(int a, int b) {return a < b ? a : b;} // ややスッキリ
int min3(int a, int b) {
if (a < b) return a; else return b; // スッキリ?
}
int main() {
printf("%d ", min(3, 2));
printf("%d ", min2(3, 2));
printf("%d ", min3(3, 2));
return 0;
}
// rust
fn main() {
let min = |a, b| if a < b {a} else {b}; // 中括弧が嫌
//let min = |a, b| if (a < b) a else b; // これならスッキリ
//let min = |a, b| if a < b then a else b; // あるいはこれ
println!("{}", min(3, 2));
}
(* ocaml *)
let min a b = if a < b then a else b (* スッキリ *)
let () = print_int (min 3 2)
/* c */
#include <stdio.h>
#define min(a, b) ((a) < (b) ? (a) : (b)) // スッキリ
int min2(int a, int b) {return a < b ? a : b;} // ややスッキリ
int min3(int a, int b) {
if (a < b) return a; else return b; // スッキリ?
}
int main() {
printf("%d ", min(3, 2));
printf("%d ", min2(3, 2));
printf("%d ", min3(3, 2));
return 0;
}
// rust
fn main() {
let min = |a, b| if a < b {a} else {b}; // 中括弧が嫌
//let min = |a, b| if (a < b) a else b; // これならスッキリ
//let min = |a, b| if a < b then a else b; // あるいはこれ
println!("{}", min(3, 2));
}
(* ocaml *)
let min a b = if a < b then a else b (* スッキリ *)
let () = print_int (min 3 2)
224デフォルトの名無しさん
2020/09/26(土) 12:46:41.58ID:XnDuVG4Q はいはいdangling else dangling else
225デフォルトの名無しさん
2020/09/26(土) 13:01:32.24ID:nz56jET8 Goもそうだけど、条件式に括弧を使わないのがいまだに慣れない。
226デフォルトの名無しさん
2020/09/26(土) 13:49:35.37ID:Rxc/dJS+ BASIC は要らなかったから慣れてる。
3項演算子考えたやつは天才。
3項演算子考えたやつは天才。
227デフォルトの名無しさん
2020/09/26(土) 14:34:05.78ID:d+bfMgei228デフォルトの名無しさん
2020/09/26(土) 14:40:21.79ID:Lg3GZEAb >>225
そのへんとモジュールまわりはPythonの影響かなと思った
そのへんとモジュールまわりはPythonの影響かなと思った
229デフォルトの名無しさん
2020/09/26(土) 16:28:05.98ID:en54jqZM >>228
PythonというよりRubyだろね
コアチームは過去も含めてRubyコミュニティ出身者が多いから
モジュールはPythonのようにファイルベースじゃなくキーワードで名前空間をきちんと切るし
クロージャの書き方だったりreturnを書かない慣習だったりも他言語に比べて類似性が高い
PythonというよりRubyだろね
コアチームは過去も含めてRubyコミュニティ出身者が多いから
モジュールはPythonのようにファイルベースじゃなくキーワードで名前空間をきちんと切るし
クロージャの書き方だったりreturnを書かない慣習だったりも他言語に比べて類似性が高い
230デフォルトの名無しさん
2020/09/26(土) 16:42:46.56ID:d+bfMgei 型システムは ML 系の言語でよくあるやつだし、
そっち方面の影響もあるんじゃないの?
そっち方面の影響もあるんじゃないの?
231デフォルトの名無しさん
2020/09/26(土) 17:41:02.34ID:iHt0gIo3232デフォルトの名無しさん
2020/09/26(土) 17:52:07.70ID:YRaYmiXd233デフォルトの名無しさん
2020/09/26(土) 18:02:33.75ID:2tuZfHCi if a < b => a else => b っていう変なもんを思いついてしまった
だーめだこりゃ
だーめだこりゃ
■ このスレッドは過去ログ倉庫に格納されています
ニュース
- パワフル女性世界3位に高市首相 米誌フォーブス選出 [蚤の市★]
- テレ朝本社から社外スタッフの男性が転落し死亡 テレビ朝日がコメント [ひかり★]
- アイヌ民族の「戸籍簿」がヤフオクで落札 団体「人権無視」と憤り [蚤の市★]
- 【米FRB】0.25%利下げ決定 3会合連続、雇用下支え [蚤の市★]
- 「身を切る改革」どこへ? 維新「身内」への公金支出、地方でも続々 [蚤の市★]
- 訪米認証「ESTA」、SNS利用情報の提出義務化へ 日本人観光客も対象に [蚤の市★]
- スクリプトまじでやめてください
- 【画像】東京都民「助けて!満員電車もう無理いいぃぃいいぃぃぃいいいいいぃ😭」!!!! [732289945]
- 【誰食】おせち料理で確実にゴミ箱行きになる食材1位、「黒豆」 [748563222]
- 「おとうとのびょうきをなおして」7歳の兄がサンタに託した切実な願い
- 一般人「起きなきゃ…」 俺ら「寝ようかなzzz」
- AIに言われたからサブスマホ売ったよ
