C++ vs Rust

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

競え

**デフォルトの名無しさん** · 2021/09/10(金) 17:58:29.87

もっと知能レベルが合った人が集う場所にいきな

**デフォルトの名無しさん** · 2021/09/10(金) 18:15:44.49

>>100
君は数学が不得意だな
入力Mに対してM番目を得る関数のコスト(リソースコストなど含む)を考えればいいだけなのにそれができない
抽象的に考えるのが苦手なら具体的な関数のプログラムを考えてもよい
Rustを叩きたいだけだとしてもC言語のプログラミングくらいはできるんだろ？
君の主張が間違っていて実現不可能なことがすぐわかる
そして示せなければ君の完全敗北確定だ

**デフォルトの名無しさん** · 2021/09/10(金) 18:22:19.32

>>98
完全に屁理屈
それならわざわざ「どんな非負整数Mに対しても」なんて言う必要は全く無い
任意のノード、任意の箇所
ならまだそういう可能性もある

たまたまMに対応するポインタがキャッシュされてた場合の計算量を言っても何の意味も無い

ちなみに数学的能力はお前よりあると思うよ
実績で勝負するなら付き合う

**デフォルトの名無しさん** · 2021/09/10(金) 18:33:25.73

>>65
> 俺は数学の天才。

これみて釣りと判断してるけどマジに受け取ってる人もいるのかな？
議論を続けるなら数学うんぬんの要素を抜きつつアクセス効率だけ語ってほすい

**デフォルトの名無しさん** · 2021/09/10(金) 20:54:06.22

まあここ隔離スレなんで

**デフォルトの名無しさん** · 2021/09/10(金) 22:29:30.98

自分は数学できないからできる人の相場感覚は分からないが、数学の天才って◯◯予想を証明したとか、定理に自分の名前が付いているとか、そういうレベルの人のことじゃない？　東大数学程度で数学の天才を名乗られても……。

**デフォルトの名無しさん** · 2021/09/10(金) 23:03:29.47

> 高校生が灯台に入学するときに受ける東大の数学の試験のことだよ。

高校数学でここまでイキれるのはもはや才能だと思うわ
数学の天才っていうのは数学の研究してて教科書書いてるような
著名な人をまわりの人が「他称」するときの話で
高校数学の成績で「自称」しちゃうってのは別の才能ｗ

**デフォルトの名無しさん** · 2021/09/10(金) 23:04:20.56

東大でやる数学じゃなくて入試でしょ？
つまり高校レベル
こんなのを東大の数学と言うな

**デフォルトの名無しさん** · 2021/09/11(土) 01:22:42.58

知ってる一番難しい数学がそれだったんでしょ
つっこんであげないのが優しさでは

**デフォルトの名無しさん** · 2021/09/11(土) 01:40:01.24

>>80
C言語でも他の言語でもそのようなことは実現不可能です
いくらRustを叩きたいとはいえ主張が滅茶苦茶になっていますよ

**デフォルトの名無しさん** · 2021/09/11(土) 10:36:57.99

馬鹿ばっか。

**デフォルトの名無しさん** · 2021/09/11(土) 11:20:17.45

実際連結リストのノードに対する参照を保持しておくってどういうユースケースで現れるんだろうか

**デフォルトの名無しさん** · 2021/09/11(土) 11:40:09.41

掲示板で算数自慢するときに使う

**デフォルトの名無しさん** · 2021/09/11(土) 11:42:49.15

>>113
例:

1. テキストエディタで、10万行のファイルを読み込み、その先頭に
1000行のテキストを挿入するときの速度向上。

2. 言語を自作する時、マクロ展開の時のトークン列へのトークンの挿入

**デフォルトの名無しさん** · 2021/09/11(土) 16:43:18.56

>>115
それはどちらの使用例なのかハッキリしてほしいです。
配列にN番目への参照を格納する例として挙げているのか、
そうではなくリンクリストを用いる例として挙げているのか、
どちらですか？

**デフォルトの名無しさん** · 2021/09/11(土) 23:33:36.29

>>112

**デフォルトの名無しさん** · 2021/09/12(日) 00:21:25.00

相手をバカと貶めることで何もしなくても自分わ相対的に高めることができるという高等な議論テクだ
さすが高学歴

**デフォルトの名無しさん** · 2021/09/12(日) 02:54:54.78

>>115
1.ってバッファを1個のLinkedListとして持っておいて、カーソルの位置をノードへの&mutで持っておきたいって発想だよね
それよか2個のLinkedListに「カーソル以前の内容」「カーソル以降の内容」を最初から分けて持っておいて、
必要に応じて前者の末尾または後者の先頭を操作するという風にすれば、常に&mut LinkedListつかまれることもなくて都合良いのでは？

workaroundでしかないという批判は認めよう

**デフォルトの名無しさん** · 2021/09/17(金) 13:36:25.88

任意のM番目に要素を挿入する時間計算量がO(1)の線形リストができないと入院中の妹が苦しむんだわ…

**デフォルトの名無しさん** · 2021/09/18(土) 16:11:40.95

どーでも良いですよ

byだいたひかる

**デフォルトの名無しさん** · 2021/10/05(火) 15:44:11.57

素人だからよく分からんけど、実務やってる人からCppだとvoid**とか出てきて難しすぎて狂うって話は聞いたことあるけどラッパークラスを作って分かりやすいメソッドつくればいいんじゃないの

**デフォルトの名無しさん** · 2021/10/05(火) 18:47:14.74

void**のどこが難しいのかさっぱり

**デフォルトの名無しさん** · 2021/10/17(日) 09:40:31.27

void**は許さない派

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

任意の言語ができる操作が任意の言語ではできないとほざくやつが数学ができるとかネタか糖質だろう...
チューニングマシンの存在を真っ向から否定したいならここではなく学会で論文を出そうね

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

プロレスごっこを期待して覗いたら、キチガイが占拠していたのは笑う

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

ここ隔離スレなので

**デフォルトの名無しさん** · 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
そうでなくて、その配列が既に決まっている場合もあるんだということだ。
それを上手く用意することが出来るケースが現実にかなり有る。