- 1 名前：デフォルトの名無しさん mailto:sage [2021/04/24(土) 08:04:49.48 ID:nPKzA798.net]
- 競え
- 159 名前：デフォルトの名無しさん mailto:sage [2021/11/21(日) 14:25:17.13 ID:qwOTZsAN.net]
- Rustを使うなら、次のデータ構造をCのように「効率よく扱う」のは諦めるしかない:
・リンクリスト
・ツリー構造(バイナリツリーなども含む)
なんどもいうが、unsafeモードをいくら使っても言語の構造上、
無理なものは無理。
俺は数学の天才。最初から結論が分かる。
- 160 名前：デフォルトの名無しさん mailto:sage [2021/11/21(日) 14:27:35.80 ID:qwOTZsAN.net]
- 何度も言おう。
Rustでリンクリストやツリー構造をO(1)でsafeモードからランダムアクセス
できないことは数学的に完全に証明できる。
そしてそれは、unsafeモードをいかに工夫して使っても無理。
無理なものは無理。これは絶対。
俺は数学の天才。
- 161 名前：デフォルトの名無しさん mailto:sage [2021/11/21(日) 14:30:47.72 ID:qwOTZsAN.net]
- [補足]
それが出来るんだったらもっと普及してるし、もっと真似されてる。
Rustのやり方では不可能だから普及できない。
- 162 名前：デフォルトの名無しさん mailto:sage [2021/11/21(日) 14:37:38.26 ID:ekMm5ue5.net]
- >>155
つまりunsafe使えばできるのね
- 163 名前：デフォルトの名無しさん mailto:sage [2021/11/21(日) 14:54:12.46 ID:uAxr+NUo.net]
- >>159
アプリのあらゆる場所を unsafe にすれば出来る。
unsafeの閉じ込めが出来ない。
- 164 名前：デフォルトの名無しさん mailto:sage [2021/11/21(日) 19:24:03.14 ID:a8amZ/lG.net]
- >>157
また嘘つきがRust叩きをしているのか
＞リンクリストやツリー構造をO(1)でランダムアクセスできない
これは全てのプログラミング言語で不可能
もちろんC言語でも不可能
以前も皆に論破されて逃走したのにまた戻ってきたのか
- 165 名前：デフォルトの名無しさん mailto:sage [2021/11/21(日) 19:46:49.29 ID:/ddxrWFf.net]
- >>161
馬鹿は黙っとれ。
お前は全くリンクリストを理解できてない。
- 166 名前：デフォルトの名無しさん mailto:sage [2021/11/21(日) 19:47:48.85 ID:/ddxrWFf.net]
- ここはレベルが低すぎる。
丁寧に説明したのに全く理解を示さないやつばかり。
- 167 名前：デフォルトの名無しさん mailto:sage [2021/11/21(日) 19:49:09.49 ID:/ddxrWFf.net]
- C/C++が速いのは、リンクリストのおかげだ。
Stroustrapも馬鹿だからリンクリストを理解できてない。
vectorだけでは人気アプリの速度は達成できてない。
- 168 名前：デフォルトの名無しさん mailto:sage [2021/11/21(日) 20:11:47.26 ID:ru7ojY1Q.net]
- よく知らんけど、ツリーとかリンクリストうまく扱えないの？
- 169 名前：デフォルトの名無しさん mailto:sage [2021/11/21(日) 20:18:26.10 ID:ekMm5ue5.net]
- >>163
コード例頂けないでしょうか
Cでうまく書けるものがRustでうまく書けない例
- 170 名前：デフォルトの名無しさん mailto:sage [2021/11/21(日) 20:23:22.75 ID:a8amZ/lG.net]
- std::collections::LinkedList
https://doc.rust-lang.org/std/collections/struct.LinkedList.html
std::collections::BTreeMap
https://doc.rust-lang.org/std/collections/struct.BTreeMap.html
- 171 名前：デフォルトの名無しさん [2021/11/21(日) 20:53:48.92 ID:ZPin+mWW.net]
- 算数得意おじちゃんが生えてきたな
- 172 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 00:48:17.10 ID:saDsX792.net]
- >>165
本来の速度性能が出ない。
CではO(1)で済むところが、O(N)必要になってしまう。
- 173 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 00:50:22.67 ID:saDsX792.net]
- >>168
余りにも馬鹿すぎるから、発言者の背景を示すしかなかった。
IQの違いが大きすぎると話が通じないと言われるが、まさに
このスレがそうで、ちゃんと言わないと、正しいことを言ってる
人が馬鹿にされるから。
- 174 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 01:02:53.27 ID:saDsX792.net]
- >>166
・Cだとリンクリストやツリーの中のノードを識別するのに、通し番号ではなく
ポインタが使われる。そのポインタは、関数内部にとどまらず、
アプリ全体で大規模に保持され続け、ノードが必要になった場合、それを
介してノードにアクセスする。だから、読み込みも書き込みも自由自在に
行える。一つのツリーの中の有るノードを削除し、あるノードに子ノード
を追加し、あるノードの直後に弟ノードを追加し、あるノードを読み取り、
あるノードに書き込む、などを全く任意のタイミングで行える。
繰り返しになるが、これらのポインタはある関数の内部だけで完結
せずに、関数の外のグローバル変数にアプリの起動時から終了時まで
恒久的に保持され、必要なタイミングで使用される。
・Rustではこのようなことが不可能。ツリーのノードを指す参照を、
グローバル変数に複数保持して、書き込みと読み込みを自由自在に
行うことが不可能だかっら。
- 175 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 01:07:59.95 ID:saDsX792.net]
- >>171
[補足]
Cの方で説明したやり方は、C++/C/Javaでも可能。
JSやRuby、Pythonでも可能。
Rustだけが不可能。
つまり、多くの言語が出来る中でRustだけが出来ない。
その結果、数学的な意味での「一般的」には、TreeやLinkedListでまともな性能が出ない。
もちろん、特定のケースでは同等性能が出ることはあるが。
- 176 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 01:08:41.45 ID:saDsX792.net]
- なお、今言ったことは、未踏や研究テーマで扱うことは禁止する。
- 177 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 01:32:04.72 ID:saDsX792.net]
- >>172
[補足2]
通し番号ではなく、ポインタでノードを識別することで、末尾以外のノードを
削除した時でも、識別番号の書き換えが不要であるメリットもある。
ポインタとはアドレスを保持する変数のことであるが、リンクリストや
ツリー構造の場合、途中のノードを削除しても、別のノードのアドレス
は全く変化しないので、削除したノード以外のポインタ値は全く変更されないので
書き換えも必要ないからである。
一方、初心者がやりがちなのは、リンクリストでも先頭のノードを0番にして、
それ以後のノードを1、2、3 という通し番号で識別しようとする方法。
これだと、5番のノードを削除した時、6番以後のノードは番号の付け替えが
必要になるのでものすごく効率が下がる。
また、k 番のノードをアクセスする際には、O(k)の時間が掛かってしまう。
本来、Cではノードを識別するのは、このような通し番号ではなく、
ポインタ(アドレス)で行うのが伝統であって、アルゴリズムの教科書でも
それが前提になっている。
それがいつからか、リンクリストでも通し番号で識別する流儀を誰かが持ち込み
初めて混乱が生じるようになった。
- 178 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 01:46:12.87 ID:4Q+A1yLL.net]
- >>171
日本語読めます？
ソースコードをくれって言っている
- 179 名前：165 mailto:sage [2021/11/22(月) 02:04:09.01 ID:43z4eYfr.net]
- >>169,172
なるほど、そうなんだ
でも正直、なにを言ってるのかまだよくわからんから、ちょっとベンチマークを投稿して遅さを示してみてくれん？
Linked Listの実装なんてその投稿よりも圧倒的に短く書けるとおもうし、ちょっとやってみせておくれ
- 180 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 10:14:51.86 ID:ejqG4gpN.net]
- pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T>
This is a nightly-only experimental API. (linked_list_cursors #58533)
CursorMutのStabilisedがまだ来てないことへの批判ってこと？
- 181 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 10:24:02.08 ID:EEj8G+es.net]
- >>157
> Rustでリンクリストやツリー構造をO(1)でsafeモードからランダムアクセスできない
どんな言語で書いてもO(1)でランダムアクセスできないのでRustでも同様にO(1)でできないのは当たり前
一般的にランダムでkが与えられた時にリンクリストでk番目を得るにはO(n)かかる
C言語でもO(n)でありO(1)では不可能
- 182 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 11:08:38.58 ID:0RwULqeG.net]
- >>178
リンクリストとポインタを学び直してから出直せ。
- 183 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 11:37:54.58 ID:0LbM6y2O.net]
- あと何回Cursorって言えばいいんですか？
- 184 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 11:50:19.99 ID:EEj8G+es.net]
- >>179
君はプログラムを書いたことがないのかね？
どんな言語でもランダムでkが与えられた時にリンクリストでk番目を得るにはO(n)かかる
O(1)でできると主張するならば実行可能なソースコードを出しなさい
- 185 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 12:28:55.95 ID:8vjqlXjx.net]
- 説明足りてないな。
「過去に一度対象となるコンテンツのポインタを確認&記録している場合」じゃなきゃO(1)は無理だろ。
- 186 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 13:01:13.80 ID:ejqG4gpN.net]
- あ、CursorMutの指摘は既にされてんのねｗ
- 187 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 13:15:10.95 ID:EEj8G+es.net]
- >>182
ランダムでkが与えられた時にリンクリストのk番目を常にO(1)で得るためには
全てのk番目の位置を別途ベクターで保持管理しないといけなくなる
そしてリンクリストで挿入削除が行われるたびにk番目がズレるから保持管理ベクターで毎回O(n)の移動が発生する
つまりどんな言語でもO(1)は絶対に不可能
- 188 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:14:17.10 ID:HWCOZSD4.net]
- >>181
そう思うのは、ランダムアクセスの定義をあなたが誤解してるからだ。
確かに、リンクリストに置いて、何の情報も無く「k番目」のノードに
アクセスするにはO(k)の時間が掛かる。
しかし、そのアクセス方法は、ランダムアクセスする場合に必須ではない。
p1, p2, ..., p_a
というa個のポインタがあって、それをランダムに選び取ってアクセスする場合の
1つあたりに掛かる時間が、O(1)であれば、ランダムアクセスの時間はO(1)
だと言えるから。
連続アクセス以外は、全てランダムアクセスなんだ。
具体的には、最初から100個のノードのアドレスを、100個のポインタに記録していたとしよう。
そのポインタは、リンクリストの中の位置で見ると、連続して並んでいるわけではないとする。
そのポインタを順番に参照してリンクリストのノードをアクセスすれば、連続アクセスでは無いから、
ランダムアクセスに分類される。
もう一度言おう、連続的な位置では無いノードを複数個アクセスすればランダムアクセスだ。
IQが低い人は、こういうトンチのようなものに弱い。
だから、IQの高い人とIQの低い人では誤解が生じ、大変な結果となる。
- 189 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:17:59.19 ID:HWCOZSD4.net]
- >>184
どうしてあなたは、2つの概念を切り分けられないんだ。
kを任意に与えられてk番目のノードをアクセスするには、確かにO(k)の
時間が掛かるが、ランダムアクセスは、最初からアドレスが分かっている
ノードをa個アクセスした場合の1つ当りのアクセスに掛かる時間でも
いいんだから、必ずしもO(k)ではなく、O(1)になる場合がある。
数学は精密な学問だから、場所をランダムにアクセスすることと、
毎回kという通し番号が与えられて毎回前から順番に辿ることとは
全く別の事象である。
ちなみに俺は、数学は毎回100点とっていたような数学マンだ。
- 190 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:18:11.48 ID:EEj8G+es.net]
- >>185
ランダムでkが与えられた時にリンクリストのk番目を常にO(1)で得るためには
全てのk番目の位置を別途ベクターで保持管理しないといけなくなる
そしてリンクリストで挿入削除が行われるたびにk番目がズレるから保持管理ベクターで毎回O(n)を必要とする移動が発生する
つまりどんな言語でどんな手法でもO(1)は絶対に不可能
- 191 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:26:17.83 ID:HWCOZSD4.net]
- IQが低い人向けに書いておこう。どうせ書いても理解できないかも知れないが。
リンクリストの中にx0〜x_{N-1}のN個のノードがあったとしよう。
ランダムアクセスの定義は、「連続アクセス以外の全てのアクセス方法」であるので、
以下のようになっている:
[連続アクセス]
x0,x1,x2,x3,x4,...
[ランダムクセス]
x10,x1,x8,x5,x3,x7,x100,x6,x200,...
ここで、馬鹿をさらしている人達は、ランダムアクセスは、毎回
通し番号kを乱数で発生させてからアクセスするものだと誤解している。
それは数学的には0点である。
ランダムアクセスとはそのような定義ではないからだ。
とにかく、「連続アクセスでなければなんでもいい」というのが正しい定義。
だから、キメウチで最初から、
&x10,&x1,&x8,&x5,&x3,&x7,&x100,&x6,&x200,...
というアドレスの列が分かっていて、それを順番にアクセスすれば、
ランダムアクセスの定義にあてはまる。
そしてそのようにしたとき、1回当たりに掛かる時間がO(1)である、
というのが、数学的に正しい見方。
何度も言うが、俺は、数学はほとんど満点だった。
繰り返し言うが、リンクリストに置いて、ノードへのランダムアクセスに
必要な時間は、O(1)が正しい。O(N)と思ってるのは、ランダムアクセスの定義
を誤解している。
O(N)かかるのは、リンクリストに置いて「通し番号からノードのアドレスを求めるのに掛かる時間」
である。リンクリストに置いて、通し番号からノードのアドレスを求めることは、
ランダムアクセスには一般的には不要である。だから、O(1)で正しい。
- 192 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:29:51.54 ID:HWCOZSD4.net]
- >>187
だから、それはランダムアクセスの定義では無いんだと何度入ったら分かるんだよ。
どうして、k番目を乱数で与えると思ってるんだ。
ランダムアクセス度は、「ランダム数で与えられたノードでアクセスする」
ことではなく「ランダムな位置のノードをアクセスするためこと」だぞ。
数学的には全く別概念だ。
何でも言うが俺は、数学はほぼ満点だった。
- 193 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:33:29.42 ID:ejqG4gpN.net]
- https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=8866d679a9e61d53c5b588d0f0d51c45
#![feature(linked_list_cursors)]
fn main() {
use std::collections::LinkedList;
let mut list = LinkedList::from([1, 2, 3]);
let mut cursor = list.cursor_front_mut();
cursor.move_next();
println!("{:?}", cursor.current()); // Some(2)
cursor.insert_after(20); // O(1) insertion
println!("{:?}", list); // [1, 2, 20, 3]
}
- 194 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:33:38.88 ID:HWCOZSD4.net]
- 例えば、位置が最初から分かっていても、どうやってもランダムアクセスが
遅くなる例としては、テープレコーダーがあげられる。
これは、どう頑張っても、長さNに対して、O(N)の時間がかかってしまう。
繰り返しになるのが、リンクリストの場合は、O(1)だ。
ただし、先頭からの通し番号 k を与えられた時に、データが有るアドレスを計算するのに
掛かる時間は、O(k)だ。
しかし、ランダムアクセスに掛かる時間はO(1)だ。
この違いが分からない人は数学が出来なかったことであろう。
- 195 名前：165 mailto:sage [2021/11/22(月) 17:35:33.12 ID:43z4eYfr.net]
- 理屈はもういいので、プログラミングできるならベンチマークを出して、他の言語より遅いことを示してくれませんか？
- 196 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:38:53.52 ID:43z4eYfr.net]
- ってあれ、 ID:saDsX792 と別人かな
- 197 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:38:58.35 ID:HWCOZSD4.net]
- 何故これが重要となるかといえば、実際にこの性質を利用して、
C言語では古くから、リンクリストをO(1)の時間でランダムアクセスして
きたからだ。O(k)ではなく、O(1)だ。
この例としては、リンククリストの中の不連続な100個のノードのアドレスを
どこかの配列にいてれておいて順番にアクセスする例がある。
この場合、一個当りの平均アクセス時間はO(1)、全体に掛かる時間はその100倍で済む。
しかし、アドレスではなく、ノードを通し番号で識別した場合、
一個当りの平均アクセス時間は、O(N)、全体に掛かる時間はその100倍になってしまう。
この意味に置いて、アドレス(ポインタ)でノードを識別することに徹すれば、
リンクリストにランダムアクセスする時間は、O(1)である。
しかし、このようなアクセス法は、Rustは一般的には無理。
- 198 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:39:58.88 ID:HWCOZSD4.net]
- >>192
プログラミングは理屈が重要。
O(1)の記法も実験せずに思考実験で結論を得るためにある。
- 199 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:41:09.75 ID:43z4eYfr.net]
- ああ、 ID:HWCOZSD4 が書いてるのは当然のことだ
- 200 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:48:40.73 ID:43z4eYfr.net]
- 「Rustだとできない」っていうのはよくわからないし、そこだけ気になってるんだけど、
Rustって参照を持ち回すことがそんなにできないんだ
- 201 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:49:16.27 ID:EEj8G+es.net]
- C言語であろうがなかろうが言語に関係なくO(1)は無理
わからない人はコーディングすればすぐわかる
ランダムでkが与えられた時にリンクリストのk番目を常にO(1)で得るためには
全てのk番目の位置を別の配列で保持管理しないといけない
そしてリンクリストで挿入削除が行われるたびにk番目がズレるから保持管理する配列で毎回O(n)を必要とする移動が発生
どんな言語でどんな手法を用いてもO(1)は絶対に不可能
- 202 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:53:40.47 ID:ejqG4gpN.net]
- >>198
俺もそう思う
彼の主張にはポインタの配列をケアする時間を含んで無さそうに聞こえたけどｗ
せっかくのリクリストとは別にアクセス用のポインタ配列をケアするってことも
ふしぎなコーディングだけど
そこまでするなら最初から配列だけでやれって思うけどｗ
- 203 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:55:47.65 ID:HWCOZSD4.net]
- >>198
その別の配列に用意したアドレスに基いてアクセスすれば、立派なランダム
アクセスなんだ。
ランダムアクセスとは、毎回デタラメにアクセスすることでは無いぞ。
テープレコーダーの場合、キメウチで、100, 1, 200, 10, 30, 2, 1000
の位置の7個のデータを取得するには、シーク時間が必要だから、
100+99+199+190+20+28+998 の時間が掛かる。
そしてこの読み取りを2回行ってもまた同じだけの時間が掛かる。
その意味で、ランダムアクセス時間は、テープの長さがNの時、O(N)とされている。
ところが、リンクリストの場合、アドレスが毎回決まっている 7 個のデータ
をアクセスするには、一個当りのノードに掛かる平均時間は O(1)だ。
これを2回行っても同じ。
あなたがおもっているような、シーク時間はリンクリストの場合には不要だから。
- 204 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:56:50.13 ID:HWCOZSD4.net]
- >>199
そうでなくて、その配列が既に決まっている場合もあるんだということだ。
それを上手く用意することが出来るケースが現実にかなり有る。
- 205 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:57:28.92 ID:ejqG4gpN.net]
- いや配列ケアのほうは時間はそれほどでもないか
挿入削除場所以降のコピーする必要が出るだけで
- 206 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:59:39.65 ID:ejqG4gpN.net]
- >>201
へー
- 207 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 17:59:44.70 ID:HWCOZSD4.net]
- なぜかというと、アドレスは、ノードを追加した時に分かるから、それをどこかに
記録しておけば「シーク時間」が不要だから。
例えば、100個のノードを任意の位置に追加したとしよう。そのアドレスは、
100個分は既知である。そのアドレスをまたどこかのリンクリストの末尾に
でも順番に追加して全て記録しておいたとしよう。
そうすると、元のリンクリストは、立派にO(1)でランダムアクセスできるんだ。
- 208 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:00:15.83 ID:43z4eYfr.net]
- > リンクリストの場合、アドレスが毎回決まっている 7 個のデータをアクセスするには、
> シーク時間はリンクリストの場合には不要だから。
そら、あらかじめアドレスがわかってればできるだけで、別にLinked Listの性質ではないよね
- 209 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:01:09.38 ID:EEj8G+es.net]
- >>200
そこでO(1)とは配列のアクセスのみ
つまりリンクリストは全く関係なく配列のアクセスがO(1)だと主張していることに気付こう
そしてリンクリストで削除や挿入が行われるたびにその配列でO(n)の大移動が行われる
結論: O(1)ではどんな言語でもプログラミングできない
- 210 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:02:14.47 ID:HWCOZSD4.net]
- >>206
そんなことない。
あなたは、ポインタを使ったプログラミング経験が浅い。
- 211 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:04:00.68 ID:HWCOZSD4.net]
- >>205
そうでない。
テープレコーダーとリンクリストでは、明らかにランダムアクセスに掛かる時間の
性質が違う。
「アドレスが既知」であるのは、ポインタを全面的に使ったプログラミング法
では当たり前の事だから、リンクリストに置いてシーク時間は不要。
- 212 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:05:44.36 ID:HWCOZSD4.net]
- >>206
違う。
ツリーの場合でも、番号ではなく、ノードをポインタで識別することで、
0の時間でシークできる。
リンクリストでも同じ。
通し番号を使おうとするから遅くなってるだけ。
ノードの識別をポインタで統一してしまうと、本当に O(1)でいける。
- 213 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:07:52.10 ID:EEj8G+es.net]
- >>204
あなたの主張を整理すると
「k番目をO(1)でアクセスできる配列」は「k番目をO(n)でアクセスできるリンクリスト」よりも優れている、となる
O(1)の部分はリンクリストと全く無関係であることに気付かないとね
ここまで壮大な勘違いをしてるのはおそらくプログラミングをしたことがないのだろうけど
- 214 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:09:34.28 ID:43z4eYfr.net]
- アドレスへのランダムアクセスは定数オーダー。そりゃメモリはそういう設計で作られてるんだから当然
テープレコーダーはランダムアクセスできない。これも当然
なんでテープレコーダーと、メモリ上に実装したLinked Listを比較しているのか意味がわからない
何を説明しようとしてるんだろう
- 215 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:10:17.50 ID:ejqG4gpN.net]
- >>206
なんか話途中から首突っ込んだけど
結局はそういうしょうもないオチっぽいなこれｗ
ポインタの指す先のデータ構造に一切関わらず
アクセス用のポインタを回収して配列にするんならそりゃO(1)だもんな
そしてわざわざそれをしたいという動機もよーわからんかった
- 216 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:12:45.44 ID:HWCOZSD4.net]
- 例えば、データベースの様なものが有ったとしよう。
個人情報がリンクリストに入っているが、ID番号と個人情報は別に配列の中に
入っていて、ID番号の構造体には、リンクリストのノードのアドレスも
入っているとする。
これだと、ID番号を全て巡って、それぞれの個人情報を巡る時、
個人情報の1個当りのアクセスに掛かる平均時間はO(1)だ。
しかし、ノードのアドレスの変わりに、ノードの通し番号を入れてしまって
いたとすると、ノードをシークするためにO(N)の時間が掛かってしまう。
なので、ノードの識別をポインタにしてしまえば、O(1)で、通し番号に
してしまえばO(N)の時間が掛かる。
だから、リンクリストを使う場合には、通し番号ではなく、ポインタを
使うことが推奨されている。ところが、Rustではそれがほぼ不可能。
- 217 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:14:22.43 ID:43z4eYfr.net]
- へー、Rustってそんなこともできないんだ
- 218 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:15:23.83 ID:HWCOZSD4.net]
- >>210
いや、ノードの識別をアドレスで行いさいすれば、
リンクリストと配列のランダムアクセスに掛かる時間はどちらもO(1)だから
リンクリストが劣っていることは無い。
なぜなら、乱数で与えられた位置のノードをアクセスする必要は無いから。
ランダムアクセスする場合でも、アクセスすべき位置は、アドレスで決まっている。
シークの時間は不要。
- 219 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:16:52.13 ID:HWCOZSD4.net]
- >>214
次の借用規則に引っかかる。
・1個でも書き込みの参照が有る場合、読み込み参照は1つも持てない。
書き込み参照も1個しか持てない。
- 220 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:26:59.33 ID:5egSOJea.net]
- >>214
Rustが次々とC/C++の領域を置き換えていってるように
両者で実現できることは同じ
彼はアルゴリズムとオーダーについてもよく理解できていないだけでなく
Rustについても全く理解していない
- 221 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:28:27.85 ID:43z4eYfr.net]
- なるほど。もうちょっとRust覚えたらそういうデータ構造も自分で実装して試してみるよ
- 222 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:31:34.64 ID:HWCOZSD4.net]
- >>217
計算時間のオーダーが全く違ってくる。
データベースなどは速度やメモリー効率を高めるために、さまざまな構造を
駆使して作られていることが有り、Rustでは自由に作ることが難しいことが
有り得る。
100万行のテキストエディタの先頭に1000行のデータをペーストするような
時にもリンクリストが大活躍する。単純な配列では遅すぎて駄目。
- 223 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:34:23.79 ID:HWCOZSD4.net]
- >>217
あなたは、データ構造やポインタを深く理解して無いか、
高度な実践的プログラミング経験が浅いかのどちらか。
- 224 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:41:12.00 ID:EEj8G+es.net]
- >>219
やはりプログラミングしたことがないようだな
そこで50万行目に行く場合に配列併用なし実装だとリンクを50万回たどるO(n)
配列併用あり実装だと50万行目へ一気に行けるO(1)が挿入削除時のたびに配列内で大移動O(n)
つまりO(1)になっているのは配列アクセスのみ
- 225 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:45:29.95 ID:HWCOZSD4.net]
- >>221
リンクリストAの中のランダムな位置のノードのアドレスを、
別のリンクリストBに入れておいて、Bの先頭から順番にループすれば、
リンクリストAのノードをランダムアクセスできるが、その時の
一個のノードあたりの平均アクセス時間はO(1)だ。
ここに配列は一個も出てこない。
- 226 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:51:10.61 ID:5egSOJea.net]
- >>222
それ、あるkが与えられたときにk番目のアクセスがO(n)になってる
それがリンクリストの性質
ランダムアクセスすなわちk番目のアクセスはO(1)の配列が圧倒的に有利
- 227 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:54:15.44 ID:HWCOZSD4.net]
- >>221
それはテキストエディタでは結構問題になる部分だが、
実際的には、ページ単位の大きな移動は文字挿入や文字削除などの編集操作に比べて時々しか
行わないことと、現在位置から相対的な移動距離は大きくないことが多いことから、
行の記憶は配列ではなくリンクリストにしておく手法を取ると良い。
実際に行の記憶を何も配慮せずに配列でやると、ペーストした時にとても遅くなる。
一方、行の記憶をリンクリストにすると、実際問題はかなり快適になる。
スクロールなども速い。
一気に決め打ちの行番号に移動するのはO(N)の時間が掛かることはかかるが、
決め打ちの番号に移動することは、たまにしか行わないので遅くは感じない。
- 228 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:55:48.2
]
- [ここ壊れてます]
- 229 名前：9 ID:HWCOZSD4.net mailto: >>223
どうして、あなたは、いつまでたっても、頑なに番号k からノードを
辿ろうとするんだ。
ポインタだと速いのに。
何のためにポインタが発明されたのか理解して無いな。 [] - [ここ壊れてます]
- 230 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 18:59:38.49 ID:HWCOZSD4.net]
- >>223
ランダムアクセスとランダムに生成した通し番号 k のノードにアクセスする
ことは別の概念だぞ。
- 231 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 19:03:37.90 ID:kGsgeZzB.net]
- 結局Rustで実装できないテキストエディタ向けのデータ構造って具体的にはなんなんだ…
ropeもgap bufferもpiece tableも普通にRust実装あるが
- 232 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 19:07:47.11 ID:HWCOZSD4.net]
- >>227
それは、人の知らないものを出してきて、根本問題から目を背けさせる手法。
どんなcrateがあろうと、根本的に出来無い事がRustには有るという話をしてる。
- 233 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 19:18:39.97 ID:4Q+A1yLL.net]
- >>228
だからそのデータ構造をCでもC++でもなんでみいからはよソースコードで示せ
- 234 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 19:19:12.02 ID:5egSOJea.net]
- >>225
まずCプログラマーには常識だけど
インデックスの番号を持つこととポインタを持つことでオーダーOが変わることはない
次に各々への複数のポインタを持つには配列やリンクリストなどの構造が必ず必要となる
いずれにせよポインタを使うことでオーダーOが変わることはない
>>228
そんなウソをついて何がしたいのかさっぱりわからない
- 235 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 19:21:02.53 ID:HWCOZSD4.net]
- >>230
>インデックスの番号を持つこととポインタを持つことでオーダーOが変わることはない
>次に各々への複数のポインタを持つには配列やリンクリストなどの構造が必ず必要となる
>いずれにせよポインタを使うことでオーダーOが変わることはない
なんで、このスレはこんなにレベルが低いの。
- 236 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 19:21:28.08 ID:HWCOZSD4.net]
- >>230
>そんなウソをついて何がしたいのかさっぱりわからない
真実だから。
- 237 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 19:27:10.84 ID:DZQ1+JmR.net]
- >>232
数学の専門家であってプログラミング経験がないからソースコード出せとの指摘には一切答えられないということかな
- 238 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 19:32:17.29 ID:fRCpO7Rh.net]
- >>194
ここであなたがおっしゃっているのは、以下のような実装のことでしょうか？
Element *array[] = {l0, l1, l2, l3, ...};
lnはリストのn番目の要素
- 239 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 19:43:59.25 ID:HWCOZSD4.net]
- >>234
近いが、初期値が、{ &l5, &l1, &l123, &l25, ... };
のようになっているイメージ。
ただし、実際には、
・初期化子リストには書かず、プログラムの途中でリンクリストに挿入した直後に記録するような
ことが多い。
・ノードの識別を常にポインタで扱うので、& で書くことは無い。
・固定配列ではなく、それもまたリンクリストにすることが多い。
なぜなら、リンクリストは効率が良いことが多いから。
- 240 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 19:46:52.11 ID:HWCOZSD4.net]
- >>233
そうではなく、
・大規模すぎて、こういうところには抽出して書ききれない。
・言葉で書いたほうが理解し易いはずだと思った。
抽象概念を理解しにくい人がこんなに多いスレだとは思わなかったから。
・しかし、これだけ書いても理解できないと言うことは、具体的に書いても
ますますそのコードの本質的な意味が理解できないと思われる。
- 241 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 19:57:10.45 ID:43z4eYfr.net]
- 中国共産党のお偉いさんって本当に偉いんですね
- 242 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 19:57:37.97 ID:43z4eYfr.net]
- スレ間違えた まいいか
- 243 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 20:02:20.61 ID:fRCpO7Rh.net]
- >>235
ある要素が複数のリストに所属するイメージでしょうか
例えば全要素が連なっているリストのn番目、特定の要素だけが抽出された別のリストのm番目に属すといったような
要素の削除に当たっては属するすべてのリストについて前後の要素からの参照を外す
- 244 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 20:03:50.15 ID:5egSOJea.net]
- 配列でもリンクリストでも他のコレクションでも全てに言えること
「格納要素が『データ本体でも、ポインタでも、何らかのid番号でも、他のインデックス番号でも、』そこは一切関係なく、様々な操作のオーダーOが変わることはない」
まずこの大原則をID:HWCOZSD4は理解できていないのたろう
だからポインタを使うと魔法のようにオーダーがO(1)になる
- 245 名前：と勘違いしている []
- [ここ壊れてます]
- 246 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 20:04:15.63 ID:HWCOZSD4.net]
- >>239
今回例としてあげたのはそういうケース。
ただそれは一例であってさまざまなケースがある。
- 247 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 20:04:48.66 ID:HWCOZSD4.net]
- >>240
アホか。
俺は現実世界では天才と言われてるのに。
- 248 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 20:05:43.93 ID:fRCpO7Rh.net]
- >>241
この一例もやはりRustでは実装できないのでしょうか
- 249 名前：デフォルトの名無しさん [2021/11/22(月) 20:07:17.81 ID:HWCOZSD4.net]
- >>243
読み込みオンリーに限定して、一切削除もしないという条件なら可能。
ノードの中に書き込んだり、ノードを削除するなら、不可能。
- 250 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 20:08:42.39 ID:HWCOZSD4.net]
- >>244
[補足]
C/C++/Java/C#/JS/Ruby/Python など多くの言語では可能だが、Rust
だけが不可能。
なので、Rustだけが仲間はずれであり、他の言語でできる事ができない。
- 251 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 20:10:06.74 ID:5egSOJea.net]
- >>243
C言語で可能なことはRustでも可能
>>244
嘘つき
- 252 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 20:11:54.24 ID:4Q+A1yLL.net]
- >>236
gistでもどこでもいいからコード貼り付けてリンクここに貼ってください
日本語でうだうだ話すより議論が早く終わるでしょうあなたの言うことが正しければ
- 253 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 20:14:36.47 ID:EEj8G+es.net]
- >>245
Rustでプログラミングをしたこともない人がデタラメな妄想を撒き散らしてるなｗ
- 254 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 20:14:53.48 ID:HWCOZSD4.net]
- >>246
デタラメ一言ってんじゃないぞ!!
>>247
具体例を書いても、それはレアケースだの、本質的にはリンクリストの速度では
間違った評価が下るだけ。
そもそも、極簡単な話を書いてるのに理解できないのにコードを書いても理解できる
とは思えない。
そもそも、ランダムアクセスの意味すら理解出来て無い、ここの人達は。
- 255 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 20:15:30.95 ID:HWCOZSD4.net]
- >>248
うそつきは黙れ。
- 256 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 20:18:44.14 ID:HWCOZSD4.net]
- >>246
>>244 は、Rustの借用規則からそうなってる。
- 257 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 20:21:30.15 ID:4Q+A1yLL.net]
- そもそもRustだって最悪UnsafeCell使えば1変数への多数読み書き参照は保持できるのだが
- 258 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 20:27:13.86 ID:4Q+A1yLL.net]
- >>249
僕はリンクリストの速度がどうこう評価するつもりはあんまりなくて、
他言語で書かれたソースコードが本当にRustでは無理なのかを確認したいだけ
だから、その「Rustでは無理なコード」を見てみたい、と言っている
最悪ソースコードの中身は理解不能なものでもよい
- 259 名前：デフォルトの名無しさん mailto:sage [2021/11/22(月) 20:27:43.67 ID:43z4eYfr.net]
- >>249
説明するつもりもないのに、お前らはどうせ理解もできないバカだ、俺はいつも数学100点の天才だ、俺を信じろ
とか言ってても狂人扱いされるだけに決まってるじゃん・・・
|
 |
