- 1 名前：デフォルトの名無しさん mailto:sage [2021/04/24(土) 08:04:49.48 ID:nPKzA798.net]
- 競え
- 121 名前：デフォルトの名無しさん mailto:sage [2021/09/17(金) 13:36:25.88 ID:9sB/yeOV.net]
- 任意のM番目に要素を挿入する時間計算量がO(1)の線形リストができないと入院中の妹が苦しむんだわ…
- 122 名前：デフォルトの名無しさん mailto:sage [2021/09/18(土) 16:11:40.95 ID:bNqoSBDr.net]
- どーでも良いですよ
byだいたひかる
- 123 名前：デフォルトの名無しさん [2021/10/05(火) 15:44:11.57 ID:+1Hntkr6.net]
- 素人だからよく分からんけど、実務やってる人からCppだとvoid**とか出てきて難しすぎて狂うって話は聞いたことあるけどラッパークラスを作って分かりやすいメソッドつくればいいんじゃないの
- 124 名前：デフォルトの名無しさん [2021/10/05(火) 18:47:14.74 ID:JbR3YU6O.net]
- void**のどこが難しいのかさっぱり
- 125 名前：デフォルトの名無しさん mailto:sage [2021/10/17(日) 09:40:31.27 ID:6Bvliwnf.net]
- void**は許さない派
- 126 名前：デフォルトの名無しさん mailto:sage [2021/10/24(日) 13:55:43.29 ID:eQqSgpa/.net]
- 任意の言語ができる操作が任意の言語ではできないとほざくやつが数学ができるとかネタか糖質だろう...
チューニングマシンの存在を真っ向から否定したいならここではなく学会で論文を出そうね
- 127 名前：デフォルトの名無しさん mailto:sage [2021/10/24(日) 14:24:43.42 ID:eQqSgpa/.net]
- プロレスごっこを期待して覗いたら、キチガイが占拠していたのは笑う
- 128 名前：デフォルトの名無しさん mailto:sage [2021/10/24(日) 14:57:26.55 ID:dxF2sYGf.net]
- ここ隔離スレなので
- 129 名前：デフォルトの名無しさん mailto:sage [2021/10/24(日) 18:05:52.35 ID:NLtlOSxj.net]
- チューニングマシンて
- 130 名前：デフォルトの名無しさん mailto:sage [2021/10/24(日) 20:19:43.90 ID:IF6Ria+p.net]
- c++とrustってチューニング完全なんですよね。意外にこれ知られてない
- 131 名前：デフォルトの名無しさん mailto:sage [2021/10/24(日) 20:55:50.68 ID:IF6Ria+p.net]
- rustの所有権は所謂、線形型
普通に理論として確立している
数学できるくんの主張は線形型によってチューニングマシンの計算複雑性が変化するってことだろう
証明できたらチューニング賞ものだろう
何十年ぶりじゃないか?記述計算量に新しい概念が導入されるのは
- 132 名前：デフォルトの名無しさん mailto:sage [2021/10/24(日) 22:07:03.33 ID:+peTc5KU.net]
- rustの所有権や借用や、コンパイルが通らずにいらいらきますが、慣れればスラスラというか、ストレスなく書けるようになるのかな
- 133 名前：デフォルトの名無しさん mailto:sage [2021/10/24(日) 22:10:42.59 ID:+peTc5KU.net]
- 日本語がおかしいですが、
所有権や借用が、やりたいことをストレスなく書けるようになる気がしなくて…
- 134 名前：デフォルトの名無しさん mailto:sage [2021/10/24(日) 22:29:10.11 ID:HVo+cqVA.net]
- 慣れみたいなものはあると思う
コンパイル通るようコード直すことを繰り返す内に最初からコンパイル通すことができるようになるかと
- 135 名前：デフォルトの名無しさん mailto:sage [2021/10/24(日) 22:41:32.45 ID:+peTc5KU.net]
- >>133
ありがとうございます
やはり繰り返しと慣れですね…
もう少し分かるまで粘ってみます
取り急ぎお礼まで
- 136 名前：デフォルトの名無しさん mailto:sage [2021/10/25(月) 17:58:05.73 ID:a6PpXdhO.net]
- >>131
細かいことにいちいち煩い姑のようだからね。
別に大したご利益
- 137 名前：もないし。 []
- [ここ壊れてます]
- 138 名前：デフォルトの名無しさん mailto:sage [2021/10/25(月) 20:25:16.68 ID:cubP7NbG.net]
- >>135
ご利益の大小はソフトウェアの種類によって変わるだろうね
OSやブラウザのようなメモリアクセス違反が即致命的な脆弱性に繋がり得る、かつ、巨大でバグを取り除ききるのが難しいソフトではご利益大きい
逆に多少バギーでも困らないソフトならただ煩わしいだけというのは正しいかも
とはいえ慣れればコンパイルが通るようにコードを書くのは多くの場合難しくないので、個人的にはカジュアルユースでもコストよりメリットが多いように感じる
- 139 名前：デフォルトの名無しさん [2021/10/26(火) 18:03:05.91 ID:KgmW7hJW.net]
- >>136
め早口
- 140 名前：デフォルトの名無しさん mailto:sage [2021/10/26(火) 20:06:45.12 ID:OracOvFU.net]
- >>131
「最後に消費するのは誰か？」を明確にするだけでよくて
その人以外に渡す時は借用してもらうだけだよね
あとはmut借用だけ一時的独占でルールおしまい
- 141 名前：デフォルトの名無しさん mailto:sage [2021/10/26(火) 22:54:07.10 ID:XkR6Nv6d.net]
- >>138
コメントありがとうございます
いまはまだおっしゃることにピンとこないのですが、「最終消費者は誰か」は常にこころに留めて進めてみます
まだサンプルコードを写経している段階なので、具体的なテーマを見つけて苦労してみます
>>135 さんもありがとうございます
ホント、小煩い姑状態です
親父の小言は後に効く、といいますが…
haskellでいう型クラスや、代数データ型、パターンマッチなど魅力的な機能があり、はやく馴染みたいです…
- 142 名前：デフォルトの名無しさん [2021/10/26(火) 23:17:46.13 ID:zVG+0sad.net]
- >>29
まさに半年経ってようやくカーネルにアロケーター導入されたわけだが
完璧に君の負けだよね
お疲れ様です
- 143 名前：デフォルトの名無しさん mailto:sage [2021/10/27(水) 08:20:39.13 ID:qg2SY4Q5.net]
- こんな実装するならrust使う意味ないけどねw
https://doc.rust-lang.org/stable/std/alloc/trait.Allocator.html
頭悪いからさらに時間使っちゃいそうでかわいそう。
- 144 名前：デフォルトの名無しさん mailto:sage [2021/10/27(水) 09:20:32.30 ID:2iZWGrmg.net]
- ゴールをずらせば負けたことにならないまで読んだ
- 145 名前：デフォルトの名無しさん [2021/10/27(水) 09:23:36.95 ID:q+lzbSiO.net]
- あちゃちゃｗそれ別のapiじゃんｗ
お馬鹿さんだからメーリス追えないんだねｗｗ
- 146 名前：デフォルトの名無しさん [2021/10/27(水) 09:29:13.91 ID:zfYVqfDQ.net]
- 話追えるようになってから来てくださいね🤗
- 147 名前：デフォルトの名無しさん [2021/10/27(水) 09:30:10.86 ID:zfYVqfDQ.net]
- 頭悪いのどっちかな
- 148 名前：デフォルトの名無しさん mailto:sage [2021/10/27(水) 14:57:34.79 ID:qg2SY4Q5.net]
- は？linuxの方ならここから話全く進んでないんだが。。誤魔化せると思ったのかな。。
https://lkml.org/lkml/2021/7/7/349
- 149 名前：デフォルトの名無しさん mailto:sage [2021/10/27(水) 15:49:20.46 ID:G9Y5/nKM.net]
- だからそれだけ貼られても経緯とかなんもわからんし読む気もおきんって
- 150 名前：デフォルトの名無しさん [2021/10/27(水) 16:58:29.94 ID:Ru0zcXw7.net]
- 顔真っ赤っかで草ｗ
悔しいねえｗ
- 151 名前：デフォルトの名無しさん [2021/10/27(水) 16:59:43.91 ID:3BkIbLo2.net]
- >>146
頭悪いの君だよね？
- 152 名前：デフォルトの名無しさん [2021/10/27(水) 18:36:52.66 ID:zwnES/cK.net]
- あわしろ氏がLinuxをRustで書き直すプロジェクト始めなかったっけ。
- 153 名前：デフォルトの名無しさん mailto:sage [2021/11/21(日) 11:28:03.98 ID:aXP4f2By.net]
- どんなに簡単でも、できることに制限がある言語は流行らない、という経験法則がある。
Rustも使えるアルゴリズムに制限があるのだが。
例えば、C言語で使えていたアルゴリズムは、C++/Java/C#ではそのまま使える。
特に
- 154 名前：C++とC#には、Cから移行するときの制限が少ない。
ところがRustでは、これらのコードからはシンプルには移植できないものが存在
してしまう。
C#やJavaは速度を遅くする代わりに安全性と自由性の両方を確保できているが、
Rustは、速度は余り遅くならないが、自由性を犠牲にしている。
これは大問題となるだろう。 [] - [ここ壊れてます]
- 155 名前：デフォルトの名無しさん mailto:sage [2021/11/21(日) 11:54:39.30 ID:7O4ablWw.net]
- C++に勝てるワケねぇだろ
- 156 名前：デフォルトの名無しさん mailto:sage [2021/11/21(日) 13:31:58.91 ID:kZvTUakz.net]
- unsafeあるくせにできないことあるのか
- 157 名前：デフォルトの名無しさん mailto:sage [2021/11/21(日) 13:33:18.01 ID:vno614JY.net]
- いつもの奴だ
- 158 名前：デフォルトの名無しさん mailto:sage [2021/11/21(日) 14:23:27.74 ID:qwOTZsAN.net]
- >>153
unsafeの中だけに閉じ込めきれないのが問題。
例えば、C言語の場合、アセンブラにしか掛けないことは、アセンブラでコードを書いた
ものをCの関数にして、Cから呼び出すことが出来たので問題なかった。
ところがRustの場合、リンクリストをポインタや参照を使って高速に扱うことが
unsafeの中だけでは完結できないので無理。
結論的には、リンクリストをO(1)でアクセスすることがRustのsafeモードでは
完全に不可能といえる。たとえ unsafe モードを使っても、safeモードに
「しみ出してきて」駄目になる。
- 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覚えたらそういうデータ構造も自分で実装して試してみるよ
|
 |
