C++ vs Rust

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

競え

**デフォルトの名無しさん** · 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には有るという話をしてる。

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

>>228
だからそのデータ構造をCでもC++でもなんでみいからはよソースコードで示せ

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

>>225
まずCプログラマーには常識だけど
インデックスの番号を持つこととポインタを持つことでオーダーOが変わることはない
次に各々への複数のポインタを持つには配列やリンクリストなどの構造が必ず必要となる
いずれにせよポインタを使うことでオーダーOが変わることはない

>>228
そんなウソをついて何がしたいのかさっぱりわからない

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

>>230
>インデックスの番号を持つこととポインタを持つことでオーダーOが変わることはない
>次に各々への複数のポインタを持つには配列やリンクリストなどの構造が必ず必要となる
>いずれにせよポインタを使うことでオーダーOが変わることはない

なんで、このスレはこんなにレベルが低いの。

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

>>230
>そんなウソをついて何がしたいのかさっぱりわからない
真実だから。

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

>>232
数学の専門家であってプログラミング経験がないからソースコード出せとの指摘には一切答えられないということかな

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

>>194
ここであなたがおっしゃっているのは、以下のような実装のことでしょうか？

Element *array[] = {l0, l1, l2, l3, ...};

lnはリストのn番目の要素

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

>>234
近いが、初期値が、{ &l5, &l1, &l123, &l25, ... };
のようになっているイメージ。
ただし、実際には、
・初期化子リストには書かず、プログラムの途中でリンクリストに挿入した直後に記録するような
　ことが多い。
・ノードの識別を常にポインタで扱うので、& で書くことは無い。
・固定配列ではなく、それもまたリンクリストにすることが多い。
　なぜなら、リンクリストは効率が良いことが多いから。

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

>>233
そうではなく、
・大規模すぎて、こういうところには抽出して書ききれない。
・言葉で書いたほうが理解し易いはずだと思った。
　抽象概念を理解しにくい人がこんなに多いスレだとは思わなかったから。
・しかし、これだけ書いても理解できないと言うことは、具体的に書いても
　ますますそのコードの本質的な意味が理解できないと思われる。

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

中国共産党のお偉いさんって本当に偉いんですね

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

スレ間違えたまいいか

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

>>235
ある要素が複数のリストに所属するイメージでしょうか
例えば全要素が連なっているリストのn番目、特定の要素だけが抽出された別のリストのm番目に属すといったような
要素の削除に当たっては属するすべてのリストについて前後の要素からの参照を外す

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

配列でもリンクリストでも他のコレクションでも全てに言えること
「格納要素が『データ本体でも、ポインタでも、何らかのid番号でも、他のインデックス番号でも、』そこは一切関係なく、様々な操作のオーダーOが変わることはない」
まずこの大原則をID:HWCOZSD4は理解できていないのたろう
だからポインタを使うと魔法のようにオーダーがO(1)になると勘違いしている

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

>>239
今回例としてあげたのはそういうケース。
ただそれは一例であってさまざまなケースがある。

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

>>240
アホか。
俺は現実世界では天才と言われてるのに。

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

>>241
この一例もやはりRustでは実装できないのでしょうか

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

>>243
読み込みオンリーに限定して、一切削除もしないという条件なら可能。
ノードの中に書き込んだり、ノードを削除するなら、不可能。

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

>>244
[補足]
C/C++/Java/C#/JS/Ruby/Python など多くの言語では可能だが、Rust
だけが不可能。
なので、Rustだけが仲間はずれであり、他の言語でできる事ができない。

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

>>243
C言語で可能なことはRustでも可能

>>244
嘘つき

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

>>236
gistでもどこでもいいからコード貼り付けてリンクここに貼ってください
日本語でうだうだ話すより議論が早く終わるでしょうあなたの言うことが正しければ

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

>>245
Rustでプログラミングをしたこともない人がデタラメな妄想を撒き散らしてるなｗ

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

>>246
デタラメ一言ってんじゃないぞ!!

>>247
具体例を書いても、それはレアケースだの、本質的にはリンクリストの速度では
間違った評価が下るだけ。

そもそも、極簡単な話を書いてるのに理解できないのにコードを書いても理解できる
とは思えない。
そもそも、ランダムアクセスの意味すら理解出来て無い、ここの人達は。

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

>>248
うそつきは黙れ。

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

>>246
>>244 は、Rustの借用規則からそうなってる。

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

そもそもRustだって最悪UnsafeCell使えば1変数への多数読み書き参照は保持できるのだが

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

>>249
僕はリンクリストの速度がどうこう評価するつもりはあんまりなくて、
他言語で書かれたソースコードが本当にRustでは無理なのかを確認したいだけ

だから、その「Rustでは無理なコード」を見てみたい、と言っている
最悪ソースコードの中身は理解不能なものでもよい

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

>>249
説明するつもりもないのに、お前らはどうせ理解もできないバカだ、俺はいつも数学100点の天才だ、俺を信じろ

とか言ってても狂人扱いされるだけに決まってるじゃん・・・

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

Cursorを使えと何回言っても聞かない
テキストエディタの例では>>119のアイデアを完全無視

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

おれも興味があるな
C++では書けてRustでは書けないコード

リソースを無視すればチューリング完全だろうから
書けないなんて事はないはずで
何かしら制限を付けた上での「書けない」なんだろうけど

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

>>245
Rust でも書けるように思えてしまったのですが、以下のコードはどこが間違っているのでしょうか

https://play.rust-lang.org/?version=stable&;mode=debug&edition=2021&gist=7534885705cd5879f536acdf64947870

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

>>216
プログラマを守るためそれをさせないのがRustっていう言語ではｗ
Rc<RefCell>ではいかんの？

https://play.rust-lang.org/?version=stable&;mode=debug&edition=2021&gist=50e9fc65e69dd1859478ee62dde963aa
fn main() {
use std::collections::LinkedList;
use std::rc::Rc;
use std::cell::RefCell;
let mut list: LinkedList<Rc<RefCell<i32>>> = LinkedList::new();
list.push_back(Rc::new(RefCell::new(1)));
list.push_back(Rc::new(RefCell::new(2)));
list.push_back(Rc::new(RefCell::new(3)));
println!("{:?}", list); // [RefCell { value: 1 }, RefCell { value: 2 }, RefCell { value: 3 }]
let mut vec: Vec<Rc<RefCell<i32>>> = Vec::new();
let mut it = list.iter();
vec.push(Rc::clone(it.next().unwrap()));
vec.push(Rc::clone(it.next().unwrap()));
vec.push(Rc::clone(it.next().unwrap()));
println!("{:?}", vec); // [RefCell { value: 1 }, RefCell { value: 2 }, RefCell { value: 3 }]
println!("{:?}", vec[1]); // RefCell { value: 2 }
*vec[1].borrow_mut() = 22;
println!("{:?}", vec[1]); // RefCell { value: 22 }
println!("{:?}", list); // [RefCell { value: 1 }, RefCell { value: 2 }, RefCell { value: 3 }]
println!("{:?}", vec); // [RefCell { value: 1 }, RefCell { value: 2 }, RefCell { value: 3 }]
}

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

>>255
Cursorでも無理だ。

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

あっコメントはミスってる
実行結果はこちら
[RefCell { value: 1 }, RefCell { value: 2 }, RefCell { value: 3 }]
[RefCell { value: 1 }, RefCell { value: 2 }, RefCell { value: 3 }]
RefCell { value: 2 }
RefCell { value: 22 }
[RefCell { value: 1 }, RefCell { value: 22 }, RefCell { value: 3 }]
[RefCell { value: 1 }, RefCell { value: 22 }, RefCell { value: 3 }]

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

Rustの実装 (>>257) はポインタでの直接アクセスではなく配列への添え字アクセスだからオーバーヘッドが大きいとか言い出したらみんなで笑ってあげましょう

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

>>257
独自のLinkedListで、実装としては配列を持っていて、
ノード間が参照でリンクされておらず、添え字番号でリンクしており、
get(), set()が添え字番号を返して配列要素を返しているので
ゼロコストではないね。

struct LinkedList<T> {
　first_idx_a: Option<usize>,
　first_idx_b: Option<usize>,
　elems: Vec<Elem<T>>,
}
struct Cursor {
　a_idx: usize,
}
fn get(&self, elem: Cursor) -> &T {
　&self.elems[elem.a_idx].data
}
fn set(&mut self, elem: Cursor, data: T) {
　self.elems[elem.a_idx].data = data;
}

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

>>261
ゼロコストが謳いなのに、ゼロコストで無い。

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

>>257
それで実装も動作も良いけど
_bはどちらも不要
_a.0と_a.1はそれぞれprevとnextと書いたほうが読みやすい

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

>>264
_b は単一の要素が複数のリストに属するという要件に対する実装ですね
面倒だったのでメンバーだけ用意して実装はしてないですが
タプル使ってるのも構造体定義が面倒だったため
というかできるできないを実証するための例なので細かいところは適当です
お好きなように修正してください

>>263
>>245 の
> C/C++/Java/C#/JS/Ruby/Python など多くの言語では可能だが、Rust
だけが不可能
> なので、Rustだけが仲間はずれであり、他の言語でできる事ができない。

というのはほかの言語ではゼロコストで実装できることを意味していますか？
それともRustでも実装できることを認めた上でのただの負け惜しみですか？
はたまたこれを書いたのは自分とは別の人と主張されるのでしょうか

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

>>262
ゼロコストを定義してください

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

>>265
後半のあなたの主張、おかしくないか。
Rustの参照では無い独自の参照風の様な構造を添え字番号で実装してしまって、
C言語より速度を落としているのだから、ゼロコスト性に反してる。

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

>>266
参照に関しては、参照がC言語の生ポインタと同じ速度で扱えること。

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

>>267
あらゆる言語の中でRustだけが実装できないという主張は撤回されて
CにRustは劣るという主張へと変更されるのですね？

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

>>257
elements_aはinto_iterにしたらあかんの？と思ったけど
2つ持った時の前半用として用意した意味なのかw

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

>>269
1. データを格納している場所が配列になっているが、動的に長さを長くしようとすれば
　動的配列と同様のコピー動作が生じてしまうから、その実装は、本来のLinkedListの
　性質とはかなり異なる。リンクリストは速度的に安定である事が重要なのに、
　この性質により、動的配列と同様に、時々大規模コピーが生じて、スパイク的に
　速度が遅くなる減少を伴うことになってしまう。このようなスパイク的な
　速度低下は、twitterかFacebook のどちらか忘れたが、どっかのSNSでも問題
　になっていた。
2. アクセスするときに、番号を配列のアドレスに変換する動作を毎回行っている。

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

>>271
[補足]
誤解を招いて議論に混乱を来たしそうなので捕捉しておくと、
271の2で書いた「番号」は、リンクリストの先頭からの通し番号の事ではなく、
今回示されたリンクリスト風のコードで、内部で用いられている配列の添え字番号
のことで、リンクリストの先頭からは、辿っていっても、連続した番号には成ってないもの。

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

>>271
あらゆる言語で実装できないがRustでは実装できない
他の言語だと O(1) だが Rustだと O(N) になる
という主張を撤回されたと理解しました

そういうことでしたら私の方から言うことはなにもありません

またアロケーションについてはVecを実装が工夫されたコンテナ型に変えることで対応できそうですね
実装詳細のないまま議論してもしょうがないトピックなのでこれ以上こちらからレスを重ねることはやめます
ありがとうございました

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

>>271
[追加]
3. そこにさらに削除メソッドを実装したとしよう。
　削除したノードに対する番号が、どこかのCursorの中にまだ生きた状態に
　なっている場合、ダングリング参照と似た現象が起きる。
　削除したノードの中を参照できてしまうのだ。

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

>>273
その主張、Rustの中に超軽量のインタプリタの様なものを載せておいて、
そのインタプリタの中ではランダムアクセスがO(1)のリンクリストが
完全に実装できることを示しただけだね。
しかも、追加すると、時々、大規模なメモリーコピーが生じるし。
newやmallocではそのようなメモリーコピーは生じない。
ノードを追加しても、リンクリスト中の他のノードの本当のマシン語レベルでの
線形アドレスが固定で変化し無いし。
あなたの実装では、それが変化してしまう。相対アドレスは変化しないが。
ベースアドレスが変化している。

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

>>274
generational arenaという手法を利用することでダングリングポインタ的アクセスを検知してハンドリング可能になります

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

>>274
[補足]
実質的なダングリング参照が起きるということは、Rustのもう一つの柱である
ところのメモリー安全性が部分的に壊れてしまってるということだ。

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

>>276
動的コストを掛けていいなら、C++でも安全性の高いものは作れるぞ。
ポインタも正しいメモリーブロックを指していることを動的に確認した後で
実際に参照するようなことは、C++でも出来るから。
Rustも配列の範囲チェックはやっているが、配列以外のアドレスでも、動的に
チェックしようと思えばいろいろなチェック法はある。
その一つの方法が、アドレスではなく、あなたが書いたような配列の中の
番号方式にしてしまうこと。
番号に対する配列要素がNULLになっていれば、動的にエラーを出力して
アプリを停止させる、などの方法が有る。

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

>>278
Rustの zero-cost abstraction はあなたの期待するような物ではありませんでした
残念でしたね