C++ vs Rust

**デフォルトの名無しさん** · 2021/04/24(土) 08:04:49.48

競え

**デフォルトの名無しさん** · 2021/10/24(日) 18:05:52.35

チューニングマシンて

**デフォルトの名無しさん** · 2021/10/24(日) 20:19:43.90

c++とrustってチューニング完全なんですよね。意外にこれ知られてない

**デフォルトの名無しさん** · 2021/10/24(日) 20:55:50.68

rustの所有権は所謂、線形型
普通に理論として確立している
数学できるくんの主張は線形型によってチューニングマシンの計算複雑性が変化するってことだろう
証明できたらチューニング賞ものだろう
何十年ぶりじゃないか?記述計算量に新しい概念が導入されるのは

**デフォルトの名無しさん** · 2021/10/24(日) 22:07:03.33

rustの所有権や借用や、コンパイルが通らずにいらいらきますが、慣れればスラスラというか、ストレスなく書けるようになるのかな

**デフォルトの名無しさん** · 2021/10/24(日) 22:10:42.59

日本語がおかしいですが、
所有権や借用が、やりたいことをストレスなく書けるようになる気がしなくて…

**デフォルトの名無しさん** · 2021/10/24(日) 22:29:10.11

慣れみたいなものはあると思う
コンパイル通るようコード直すことを繰り返す内に最初からコンパイル通すことができるようになるかと

**デフォルトの名無しさん** · 2021/10/24(日) 22:41:32.45

>>133
ありがとうございます
やはり繰り返しと慣れですね…

もう少し分かるまで粘ってみます
取り急ぎお礼まで

**デフォルトの名無しさん** · 2021/10/25(月) 17:58:05.73

>>131
細かいことにいちいち煩い姑のようだからね。
別に大したご利益もないし。

**デフォルトの名無しさん** · 2021/10/25(月) 20:25:16.68

>>135
ご利益の大小はソフトウェアの種類によって変わるだろうね
OSやブラウザのようなメモリアクセス違反が即致命的な脆弱性に繋がり得る、かつ、巨大でバグを取り除ききるのが難しいソフトではご利益大きい
逆に多少バギーでも困らないソフトならただ煩わしいだけというのは正しいかも
とはいえ慣れればコンパイルが通るようにコードを書くのは多くの場合難しくないので、個人的にはカジュアルユースでもコストよりメリットが多いように感じる

**デフォルトの名無しさん** · 2021/10/26(火) 18:03:05.91

>>136
め早口

**デフォルトの名無しさん** · 2021/10/26(火) 20:06:45.12

>>131
「最後に消費するのは誰か？」を明確にするだけでよくて
その人以外に渡す時は借用してもらうだけだよね
あとはmut借用だけ一時的独占でルールおしまい

**デフォルトの名無しさん** · 2021/10/26(火) 22:54:07.10

>>138
コメントありがとうございます
いまはまだおっしゃることにピンとこないのですが、「最終消費者は誰か」は常にこころに留めて進めてみます
まだサンプルコードを写経している段階なので、具体的なテーマを見つけて苦労してみます

>>135 さんもありがとうございます
ホント、小煩い姑状態です
親父の小言は後に効く、といいますが…

haskellでいう型クラスや、代数データ型、パターンマッチなど魅力的な機能があり、はやく馴染みたいです…

**デフォルトの名無しさん** · 2021/10/26(火) 23:17:46.13

>>29
まさに半年経ってようやくカーネルにアロケーター導入されたわけだが
完璧に君の負けだよね
お疲れ様です

**デフォルトの名無しさん** · 2021/10/27(水) 08:20:39.13

こんな実装するならrust使う意味ないけどねw
https://doc.rust-lang.org/stable/std/alloc/trait.Allocator.html
頭悪いからさらに時間使っちゃいそうでかわいそう。

**デフォルトの名無しさん** · 2021/10/27(水) 09:20:32.30

ゴールをずらせば負けたことにならないまで読んだ

**デフォルトの名無しさん** · 2021/10/27(水) 09:23:36.95

あちゃちゃｗそれ別のapiじゃんｗ
お馬鹿さんだからメーリス追えないんだねｗｗ

**デフォルトの名無しさん** · 2021/10/27(水) 09:29:13.91

話追えるようになってから来てくださいね🤗

**デフォルトの名無しさん** · 2021/10/27(水) 09:30:10.86

頭悪いのどっちかな

**デフォルトの名無しさん** · 2021/10/27(水) 14:57:34.79

は？linuxの方ならここから話全く進んでないんだが。。誤魔化せると思ったのかな。。
https://lkml.org/lkml/2021/7/7/349

**デフォルトの名無しさん** · 2021/10/27(水) 15:49:20.46

だからそれだけ貼られても経緯とかなんもわからんし読む気もおきんって

**デフォルトの名無しさん** · 2021/10/27(水) 16:58:29.94

顔真っ赤っかで草ｗ
悔しいねえｗ

**デフォルトの名無しさん** · 2021/10/27(水) 16:59:43.91

>>146
頭悪いの君だよね？

**デフォルトの名無しさん** · 2021/10/27(水) 18:36:52.66

あわしろ氏がLinuxをRustで書き直すプロジェクト始めなかったっけ。

**デフォルトの名無しさん** · 2021/11/21(日) 11:28:03.98

どんなに簡単でも、できることに制限がある言語は流行らない、という経験法則がある。
Rustも使えるアルゴリズムに制限があるのだが。
例えば、C言語で使えていたアルゴリズムは、C++/Java/C#ではそのまま使える。
特にC++とC#には、Cから移行するときの制限が少ない。
ところがRustでは、これらのコードからはシンプルには移植できないものが存在
してしまう。
C#やJavaは速度を遅くする代わりに安全性と自由性の両方を確保できているが、
Rustは、速度は余り遅くならないが、自由性を犠牲にしている。
これは大問題となるだろう。

**デフォルトの名無しさん** · 2021/11/21(日) 11:54:39.30

C++に勝てるワケねぇだろ

**デフォルトの名無しさん** · 2021/11/21(日) 13:31:58.91

unsafeあるくせにできないことあるのか

**デフォルトの名無しさん** · 2021/11/21(日) 13:33:18.01

いつもの奴だ

**デフォルトの名無しさん** · 2021/11/21(日) 14:23:27.74

>>153
unsafeの中だけに閉じ込めきれないのが問題。
例えば、C言語の場合、アセンブラにしか掛けないことは、アセンブラでコードを書いた
ものをCの関数にして、Cから呼び出すことが出来たので問題なかった。
ところがRustの場合、リンクリストをポインタや参照を使って高速に扱うことが
unsafeの中だけでは完結できないので無理。
結論的には、リンクリストをO(1)でアクセスすることがRustのsafeモードでは
完全に不可能といえる。たとえ unsafe モードを使っても、safeモードに
「しみ出してきて」駄目になる。

**デフォルトの名無しさん** · 2021/11/21(日) 14:25:17.13

Rustを使うなら、次のデータ構造をCのように「効率よく扱う」のは諦めるしかない:
・リンクリスト
・ツリー構造(バイナリツリーなども含む)
なんどもいうが、unsafeモードをいくら使っても言語の構造上、
無理なものは無理。
俺は数学の天才。最初から結論が分かる。

**デフォルトの名無しさん** · 2021/11/21(日) 14:27:35.80

何度も言おう。
Rustでリンクリストやツリー構造をO(1)でsafeモードからランダムアクセス
できないことは数学的に完全に証明できる。
そしてそれは、unsafeモードをいかに工夫して使っても無理。
無理なものは無理。これは絶対。
俺は数学の天才。

**デフォルトの名無しさん** · 2021/11/21(日) 14:30:47.72

[補足]
それが出来るんだったらもっと普及してるし、もっと真似されてる。
Rustのやり方では不可能だから普及できない。

**デフォルトの名無しさん** · 2021/11/21(日) 14:37:38.26

>>155
つまりunsafe使えばできるのね

**デフォルトの名無しさん** · 2021/11/21(日) 14:54:12.46

>>159
アプリのあらゆる場所を unsafe にすれば出来る。
unsafeの閉じ込めが出来ない。

**デフォルトの名無しさん** · 2021/11/21(日) 19:24:03.14

>>157
また嘘つきがRust叩きをしているのか

＞リンクリストやツリー構造をO(1)でランダムアクセスできない

これは全てのプログラミング言語で不可能
もちろんC言語でも不可能
以前も皆に論破されて逃走したのにまた戻ってきたのか

**デフォルトの名無しさん** · 2021/11/21(日) 19:46:49.29

>>161
馬鹿は黙っとれ。
お前は全くリンクリストを理解できてない。

**デフォルトの名無しさん** · 2021/11/21(日) 19:47:48.85

ここはレベルが低すぎる。
丁寧に説明したのに全く理解を示さないやつばかり。

**デフォルトの名無しさん** · 2021/11/21(日) 19:49:09.49

C/C++が速いのは、リンクリストのおかげだ。
Stroustrapも馬鹿だからリンクリストを理解できてない。
vectorだけでは人気アプリの速度は達成できてない。

**デフォルトの名無しさん** · 2021/11/21(日) 20:11:47.26

よく知らんけど、ツリーとかリンクリストうまく扱えないの？

**デフォルトの名無しさん** · 2021/11/21(日) 20:18:26.10

>>163
コード例頂けないでしょうか
Cでうまく書けるものがRustでうまく書けない例

**デフォルトの名無しさん** · 2021/11/21(日) 20:23:22.75

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

**デフォルトの名無しさん** · 2021/11/21(日) 20:53:48.92

算数得意おじちゃんが生えてきたな

**デフォルトの名無しさん** · 2021/11/22(月) 00:48:17.10

>>165
本来の速度性能が出ない。
CではO(1)で済むところが、O(N)必要になってしまう。

**デフォルトの名無しさん** · 2021/11/22(月) 00:50:22.67

>>168
余りにも馬鹿すぎるから、発言者の背景を示すしかなかった。
IQの違いが大きすぎると話が通じないと言われるが、まさに
このスレがそうで、ちゃんと言わないと、正しいことを言ってる
人が馬鹿にされるから。

**デフォルトの名無しさん** · 2021/11/22(月) 01:02:53.27

>>166
・Cだとリンクリストやツリーの中のノードを識別するのに、通し番号ではなく
　ポインタが使われる。そのポインタは、関数内部にとどまらず、
　アプリ全体で大規模に保持され続け、ノードが必要になった場合、それを
　介してノードにアクセスする。だから、読み込みも書き込みも自由自在に
　行える。一つのツリーの中の有るノードを削除し、あるノードに子ノード
　を追加し、あるノードの直後に弟ノードを追加し、あるノードを読み取り、
　あるノードに書き込む、などを全く任意のタイミングで行える。
　繰り返しになるが、これらのポインタはある関数の内部だけで完結
　せずに、関数の外のグローバル変数にアプリの起動時から終了時まで
　恒久的に保持され、必要なタイミングで使用される。

・Rustではこのようなことが不可能。ツリーのノードを指す参照を、
　グローバル変数に複数保持して、書き込みと読み込みを自由自在に
　行うことが不可能だかっら。

**デフォルトの名無しさん** · 2021/11/22(月) 01:07:59.95

>>171
[補足]
Cの方で説明したやり方は、C++/C/Javaでも可能。
JSやRuby、Pythonでも可能。
Rustだけが不可能。
つまり、多くの言語が出来る中でRustだけが出来ない。
その結果、数学的な意味での「一般的」には、TreeやLinkedListでまともな性能が出ない。
もちろん、特定のケースでは同等性能が出ることはあるが。

**デフォルトの名無しさん** · 2021/11/22(月) 01:08:41.45

なお、今言ったことは、未踏や研究テーマで扱うことは禁止する。

**デフォルトの名無しさん** · 2021/11/22(月) 01:32:04.72

>>172
[補足2]
通し番号ではなく、ポインタでノードを識別することで、末尾以外のノードを
削除した時でも、識別番号の書き換えが不要であるメリットもある。
ポインタとはアドレスを保持する変数のことであるが、リンクリストや
ツリー構造の場合、途中のノードを削除しても、別のノードのアドレス
は全く変化しないので、削除したノード以外のポインタ値は全く変更されないので
書き換えも必要ないからである。

一方、初心者がやりがちなのは、リンクリストでも先頭のノードを0番にして、
それ以後のノードを1、2、3 という通し番号で識別しようとする方法。
これだと、5番のノードを削除した時、6番以後のノードは番号の付け替えが
必要になるのでものすごく効率が下がる。
また、k 番のノードをアクセスする際には、O(k)の時間が掛かってしまう。
本来、Cではノードを識別するのは、このような通し番号ではなく、
ポインタ(アドレス)で行うのが伝統であって、アルゴリズムの教科書でも
それが前提になっている。
それがいつからか、リンクリストでも通し番号で識別する流儀を誰かが持ち込み
初めて混乱が生じるようになった。

**デフォルトの名無しさん** · 2021/11/22(月) 01:46:12.87

>>171
日本語読めます？
ソースコードをくれって言っている

**165** · 2021/11/22(月) 02:04:09.01

>>169,172
なるほど、そうなんだ
でも正直、なにを言ってるのかまだよくわからんから、ちょっとベンチマークを投稿して遅さを示してみてくれん？
Linked Listの実装なんてその投稿よりも圧倒的に短く書けるとおもうし、ちょっとやってみせておくれ

**デフォルトの名無しさん** · 2021/11/22(月) 10:14:51.86

pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T>
This is a nightly-only experimental API. (linked_list_cursors #58533)

CursorMutのStabilisedがまだ来てないことへの批判ってこと？

**デフォルトの名無しさん** · 2021/11/22(月) 10:24:02.08

>>157
> Rustでリンクリストやツリー構造をO(1)でsafeモードからランダムアクセスできない

どんな言語で書いてもO(1)でランダムアクセスできないのでRustでも同様にO(1)でできないのは当たり前
一般的にランダムでkが与えられた時にリンクリストでk番目を得るにはO(n)かかる
C言語でもO(n)でありO(1)では不可能

**デフォルトの名無しさん** · 2021/11/22(月) 11:08:38.58

>>178
リンクリストとポインタを学び直してから出直せ。

**デフォルトの名無しさん** · 2021/11/22(月) 11:37:54.58

あと何回Cursorって言えばいいんですか？

**デフォルトの名無しさん** · 2021/11/22(月) 11:50:19.99

>>179
君はプログラムを書いたことがないのかね？
どんな言語でもランダムでkが与えられた時にリンクリストでk番目を得るにはO(n)かかる
O(1)でできると主張するならば実行可能なソースコードを出しなさい

**デフォルトの名無しさん** · 2021/11/22(月) 12:28:55.95

説明足りてないな。
「過去に一度対象となるコンテンツのポインタを確認&記録している場合」じゃなきゃO(1)は無理だろ。

**デフォルトの名無しさん** · 2021/11/22(月) 13:01:13.80

あ、CursorMutの指摘は既にされてんのねｗ

**デフォルトの名無しさん** · 2021/11/22(月) 13:15:10.95

>>182
ランダムでkが与えられた時にリンクリストのk番目を常にO(1)で得るためには
全てのk番目の位置を別途ベクターで保持管理しないといけなくなる
そしてリンクリストで挿入削除が行われるたびにk番目がズレるから保持管理ベクターで毎回O(n)の移動が発生する
つまりどんな言語でもO(1)は絶対に不可能

**デフォルトの名無しさん** · 2021/11/22(月) 17:14:17.10

>>181
そう思うのは、ランダムアクセスの定義をあなたが誤解してるからだ。
確かに、リンクリストに置いて、何の情報も無く「k番目」のノードに
アクセスするにはO(k)の時間が掛かる。
しかし、そのアクセス方法は、ランダムアクセスする場合に必須ではない。
p1, p2, ..., p_a
というa個のポインタがあって、それをランダムに選び取ってアクセスする場合の
1つあたりに掛かる時間が、O(1)であれば、ランダムアクセスの時間はO(1)
だと言えるから。
連続アクセス以外は、全てランダムアクセスなんだ。
具体的には、最初から100個のノードのアドレスを、100個のポインタに記録していたとしよう。
そのポインタは、リンクリストの中の位置で見ると、連続して並んでいるわけではないとする。
そのポインタを順番に参照してリンクリストのノードをアクセスすれば、連続アクセスでは無いから、
ランダムアクセスに分類される。
もう一度言おう、連続的な位置では無いノードを複数個アクセスすればランダムアクセスだ。

IQが低い人は、こういうトンチのようなものに弱い。
だから、IQの高い人とIQの低い人では誤解が生じ、大変な結果となる。

**デフォルトの名無しさん** · 2021/11/22(月) 17:17:59.19

>>184
どうしてあなたは、2つの概念を切り分けられないんだ。
kを任意に与えられてk番目のノードをアクセスするには、確かにO(k)の
時間が掛かるが、ランダムアクセスは、最初からアドレスが分かっている
ノードをa個アクセスした場合の1つ当りのアクセスに掛かる時間でも
いいんだから、必ずしもO(k)ではなく、O(1)になる場合がある。
数学は精密な学問だから、場所をランダムにアクセスすることと、
毎回kという通し番号が与えられて毎回前から順番に辿ることとは
全く別の事象である。
ちなみに俺は、数学は毎回100点とっていたような数学マンだ。

**デフォルトの名無しさん** · 2021/11/22(月) 17:18:11.48

>>185
ランダムでkが与えられた時にリンクリストのk番目を常にO(1)で得るためには
全てのk番目の位置を別途ベクターで保持管理しないといけなくなる
そしてリンクリストで挿入削除が行われるたびにk番目がズレるから保持管理ベクターで毎回O(n)を必要とする移動が発生する
つまりどんな言語でどんな手法でもO(1)は絶対に不可能

**デフォルトの名無しさん** · 2021/11/22(月) 17:26:17.83

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)で正しい。

**デフォルトの名無しさん** · 2021/11/22(月) 17:29:51.54

>>187
だから、それはランダムアクセスの定義では無いんだと何度入ったら分かるんだよ。
どうして、k番目を乱数で与えると思ってるんだ。
ランダムアクセス度は、「ランダム数で与えられたノードでアクセスする」
ことではなく「ランダムな位置のノードをアクセスするためこと」だぞ。

数学的には全く別概念だ。

何でも言うが俺は、数学はほぼ満点だった。

**デフォルトの名無しさん** · 2021/11/22(月) 17:33:29.42

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]
}

**デフォルトの名無しさん** · 2021/11/22(月) 17:33:38.88

例えば、位置が最初から分かっていても、どうやってもランダムアクセスが
遅くなる例としては、テープレコーダーがあげられる。
これは、どう頑張っても、長さNに対して、O(N)の時間がかかってしまう。
繰り返しになるのが、リンクリストの場合は、O(1)だ。
ただし、先頭からの通し番号 k を与えられた時に、データが有るアドレスを計算するのに
掛かる時間は、O(k)だ。
しかし、ランダムアクセスに掛かる時間はO(1)だ。

この違いが分からない人は数学が出来なかったことであろう。

**165** · 2021/11/22(月) 17:35:33.12

理屈はもういいので、プログラミングできるならベンチマークを出して、他の言語より遅いことを示してくれませんか？

**デフォルトの名無しさん** · 2021/11/22(月) 17:38:53.52

ってあれ、 ID:saDsX792 と別人かな

**デフォルトの名無しさん** · 2021/11/22(月) 17:38:58.35

何故これが重要となるかといえば、実際にこの性質を利用して、
C言語では古くから、リンクリストをO(1)の時間でランダムアクセスして
きたからだ。O(k)ではなく、O(1)だ。

この例としては、リンククリストの中の不連続な100個のノードのアドレスを
どこかの配列にいてれておいて順番にアクセスする例がある。
この場合、一個当りの平均アクセス時間はO(1)、全体に掛かる時間はその100倍で済む。

しかし、アドレスではなく、ノードを通し番号で識別した場合、
一個当りの平均アクセス時間は、O(N)、全体に掛かる時間はその100倍になってしまう。

この意味に置いて、アドレス(ポインタ)でノードを識別することに徹すれば、
リンクリストにランダムアクセスする時間は、O(1)である。

しかし、このようなアクセス法は、Rustは一般的には無理。

**デフォルトの名無しさん** · 2021/11/22(月) 17:39:58.88

>>192
プログラミングは理屈が重要。
O(1)の記法も実験せずに思考実験で結論を得るためにある。

**デフォルトの名無しさん** · 2021/11/22(月) 17:41:09.75

ああ、 ID:HWCOZSD4 が書いてるのは当然のことだ

**デフォルトの名無しさん** · 2021/11/22(月) 17:48:40.73

「Rustだとできない」っていうのはよくわからないし、そこだけ気になってるんだけど、
Rustって参照を持ち回すことがそんなにできないんだ

**デフォルトの名無しさん** · 2021/11/22(月) 17:49:16.27

C言語であろうがなかろうが言語に関係なくO(1)は無理
わからない人はコーディングすればすぐわかる
ランダムでkが与えられた時にリンクリストのk番目を常にO(1)で得るためには
全てのk番目の位置を別の配列で保持管理しないといけない
そしてリンクリストで挿入削除が行われるたびにk番目がズレるから保持管理する配列で毎回O(n)を必要とする移動が発生
どんな言語でどんな手法を用いてもO(1)は絶対に不可能

**デフォルトの名無しさん** · 2021/11/22(月) 17:53:40.47

>>198
俺もそう思う
彼の主張にはポインタの配列をケアする時間を含んで無さそうに聞こえたけどｗ
せっかくのリクリストとは別にアクセス用のポインタ配列をケアするってことも
ふしぎなコーディングだけど
そこまでするなら最初から配列だけでやれって思うけどｗ

**デフォルトの名無しさん** · 2021/11/22(月) 17:55:47.65

>>198
その別の配列に用意したアドレスに基いてアクセスすれば、立派なランダム
アクセスなんだ。
ランダムアクセスとは、毎回デタラメにアクセスすることでは無いぞ。

テープレコーダーの場合、キメウチで、100, 1, 200, 10, 30, 2, 1000
の位置の7個のデータを取得するには、シーク時間が必要だから、
100+99+199+190+20+28+998 の時間が掛かる。
そしてこの読み取りを2回行ってもまた同じだけの時間が掛かる。
その意味で、ランダムアクセス時間は、テープの長さがNの時、O(N)とされている。

ところが、リンクリストの場合、アドレスが毎回決まっている 7 個のデータ
をアクセスするには、一個当りのノードに掛かる平均時間は O(1)だ。
これを2回行っても同じ。

あなたがおもっているような、シーク時間はリンクリストの場合には不要だから。

**デフォルトの名無しさん** · 2021/11/22(月) 17:56:50.13

>>199
そうでなくて、その配列が既に決まっている場合もあるんだということだ。
それを上手く用意することが出来るケースが現実にかなり有る。

**デフォルトの名無しさん** · 2021/11/22(月) 17:57:28.92

いや配列ケアのほうは時間はそれほどでもないか
挿入削除場所以降のコピーする必要が出るだけで

**デフォルトの名無しさん** · 2021/11/22(月) 17:59:39.65

>>201
へー

**デフォルトの名無しさん** · 2021/11/22(月) 17:59:44.70

なぜかというと、アドレスは、ノードを追加した時に分かるから、それをどこかに
記録しておけば「シーク時間」が不要だから。

例えば、100個のノードを任意の位置に追加したとしよう。そのアドレスは、
100個分は既知である。そのアドレスをまたどこかのリンクリストの末尾に
でも順番に追加して全て記録しておいたとしよう。

そうすると、元のリンクリストは、立派にO(1)でランダムアクセスできるんだ。

**デフォルトの名無しさん** · 2021/11/22(月) 18:00:15.83

> リンクリストの場合、アドレスが毎回決まっている 7 個のデータをアクセスするには、
> シーク時間はリンクリストの場合には不要だから。

そら、あらかじめアドレスがわかってればできるだけで、別にLinked Listの性質ではないよね

**デフォルトの名無しさん** · 2021/11/22(月) 18:01:09.38

>>200
そこでO(1)とは配列のアクセスのみ
つまりリンクリストは全く関係なく配列のアクセスがO(1)だと主張していることに気付こう
そしてリンクリストで削除や挿入が行われるたびにその配列でO(n)の大移動が行われる
結論: O(1)ではどんな言語でもプログラミングできない

**デフォルトの名無しさん** · 2021/11/22(月) 18:02:14.47

>>206
そんなことない。
あなたは、ポインタを使ったプログラミング経験が浅い。

**デフォルトの名無しさん** · 2021/11/22(月) 18:04:00.68

>>205
そうでない。
テープレコーダーとリンクリストでは、明らかにランダムアクセスに掛かる時間の
性質が違う。
「アドレスが既知」であるのは、ポインタを全面的に使ったプログラミング法
では当たり前の事だから、リンクリストに置いてシーク時間は不要。

**デフォルトの名無しさん** · 2021/11/22(月) 18:05:44.36

>>206
違う。
ツリーの場合でも、番号ではなく、ノードをポインタで識別することで、
0の時間でシークできる。
リンクリストでも同じ。
通し番号を使おうとするから遅くなってるだけ。
ノードの識別をポインタで統一してしまうと、本当に O(1)でいける。

**デフォルトの名無しさん** · 2021/11/22(月) 18:07:52.10

>>204
あなたの主張を整理すると
「k番目をO(1)でアクセスできる配列」は「k番目をO(n)でアクセスできるリンクリスト」よりも優れている、となる
O(1)の部分はリンクリストと全く無関係であることに気付かないとね
ここまで壮大な勘違いをしてるのはおそらくプログラミングをしたことがないのだろうけど

**デフォルトの名無しさん** · 2021/11/22(月) 18:09:34.28

アドレスへのランダムアクセスは定数オーダー。そりゃメモリはそういう設計で作られてるんだから当然
テープレコーダーはランダムアクセスできない。これも当然

なんでテープレコーダーと、メモリ上に実装したLinked Listを比較しているのか意味がわからない
何を説明しようとしてるんだろう

**デフォルトの名無しさん** · 2021/11/22(月) 18:10:17.50

>>206
なんか話途中から首突っ込んだけど
結局はそういうしょうもないオチっぽいなこれｗ
ポインタの指す先のデータ構造に一切関わらず
アクセス用のポインタを回収して配列にするんならそりゃO(1)だもんな
そしてわざわざそれをしたいという動機もよーわからんかった

**デフォルトの名無しさん** · 2021/11/22(月) 18:12:45.44

例えば、データベースの様なものが有ったとしよう。
個人情報がリンクリストに入っているが、ID番号と個人情報は別に配列の中に
入っていて、ID番号の構造体には、リンクリストのノードのアドレスも
入っているとする。
これだと、ID番号を全て巡って、それぞれの個人情報を巡る時、
個人情報の1個当りのアクセスに掛かる平均時間はO(1)だ。
しかし、ノードのアドレスの変わりに、ノードの通し番号を入れてしまって
いたとすると、ノードをシークするためにO(N)の時間が掛かってしまう。

なので、ノードの識別をポインタにしてしまえば、O(1)で、通し番号に
してしまえばO(N)の時間が掛かる。
だから、リンクリストを使う場合には、通し番号ではなく、ポインタを
使うことが推奨されている。ところが、Rustではそれがほぼ不可能。

**デフォルトの名無しさん** · 2021/11/22(月) 18:14:22.43

へー、Rustってそんなこともできないんだ

**デフォルトの名無しさん** · 2021/11/22(月) 18:15:23.83

>>210
いや、ノードの識別をアドレスで行いさいすれば、
リンクリストと配列のランダムアクセスに掛かる時間はどちらもO(1)だから
リンクリストが劣っていることは無い。

なぜなら、乱数で与えられた位置のノードをアクセスする必要は無いから。
ランダムアクセスする場合でも、アクセスすべき位置は、アドレスで決まっている。
シークの時間は不要。

**デフォルトの名無しさん** · 2021/11/22(月) 18:16:52.13

>>214
次の借用規則に引っかかる。
・1個でも書き込みの参照が有る場合、読み込み参照は1つも持てない。
　書き込み参照も1個しか持てない。

**デフォルトの名無しさん** · 2021/11/22(月) 18:26:59.33

>>214
Rustが次々とC/C++の領域を置き換えていってるように
両者で実現できることは同じ
彼はアルゴリズムとオーダーについてもよく理解できていないだけでなく
Rustについても全く理解していない

**デフォルトの名無しさん** · 2021/11/22(月) 18:28:27.85

なるほど。もうちょっとRust覚えたらそういうデータ構造も自分で実装して試してみるよ

**デフォルトの名無しさん** · 2021/11/22(月) 18:31:34.64

>>217
計算時間のオーダーが全く違ってくる。
データベースなどは速度やメモリー効率を高めるために、さまざまな構造を
駆使して作られていることが有り、Rustでは自由に作ることが難しいことが
有り得る。
100万行のテキストエディタの先頭に1000行のデータをペーストするような
時にもリンクリストが大活躍する。単純な配列では遅すぎて駄目。

**デフォルトの名無しさん** · 2021/11/22(月) 18:34:23.79

>>217
あなたは、データ構造やポインタを深く理解して無いか、
高度な実践的プログラミング経験が浅いかのどちらか。

**デフォルトの名無しさん** · 2021/11/22(月) 18:41:12.00

>>219
やはりプログラミングしたことがないようだな
そこで50万行目に行く場合に配列併用なし実装だとリンクを50万回たどるO(n)
配列併用あり実装だと50万行目へ一気に行けるO(1)が挿入削除時のたびに配列内で大移動O(n)
つまりO(1)になっているのは配列アクセスのみ

**デフォルトの名無しさん** · 2021/11/22(月) 18:45:29.95

>>221
リンクリストAの中のランダムな位置のノードのアドレスを、
別のリンクリストBに入れておいて、Bの先頭から順番にループすれば、
リンクリストAのノードをランダムアクセスできるが、その時の
一個のノードあたりの平均アクセス時間はO(1)だ。
ここに配列は一個も出てこない。

**デフォルトの名無しさん** · 2021/11/22(月) 18:51:10.61

>>222
それ、あるkが与えられたときにk番目のアクセスがO(n)になってる
それがリンクリストの性質
ランダムアクセスすなわちk番目のアクセスはO(1)の配列が圧倒的に有利

**デフォルトの名無しさん** · 2021/11/22(月) 18:54:15.44

>>221
それはテキストエディタでは結構問題になる部分だが、
実際的には、ページ単位の大きな移動は文字挿入や文字削除などの編集操作に比べて時々しか
行わないことと、現在位置から相対的な移動距離は大きくないことが多いことから、
行の記憶は配列ではなくリンクリストにしておく手法を取ると良い。
実際に行の記憶を何も配慮せずに配列でやると、ペーストした時にとても遅くなる。
一方、行の記憶をリンクリストにすると、実際問題はかなり快適になる。
スクロールなども速い。
一気に決め打ちの行番号に移動するのはO(N)の時間が掛かることはかかるが、
決め打ちの番号に移動することは、たまにしか行わないので遅くは感じない。

**デフォルトの名無しさん** · 2021/11/22(月) 18:55:48.29

>>223
どうして、あなたは、いつまでたっても、頑なに番号k からノードを
辿ろうとするんだ。
ポインタだと速いのに。
何のためにポインタが発明されたのか理解して無いな。

**デフォルトの名無しさん** · 2021/11/22(月) 18:59:38.49

>>223
ランダムアクセスとランダムに生成した通し番号 k のノードにアクセスする
ことは別の概念だぞ。

**デフォルトの名無しさん** · 2021/11/22(月) 19:03:37.90

結局Rustで実装できないテキストエディタ向けのデータ構造って具体的にはなんなんだ…
ropeもgap bufferもpiece tableも普通にRust実装あるが

**デフォルトの名無しさん** · 2021/11/22(月) 19:07:47.11

>>227
それは、人の知らないものを出してきて、根本問題から目を背けさせる手法。
どんなcrateがあろうと、根本的に出来無い事がRustには有るという話をしてる。