- 1 名前：デフォルトの名無しさん mailto:sage [2021/04/24(土) 08:04:49.48 ID:nPKzA798.net]
- 競え
- 83 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 12:30:48.00 ID:Ga+Uz44a.net]
- >>80
挿入自体が定数時間でも
M番目を探すのが定数じゃない
- 84 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 12:41:50.91 ID:4cVpX4oe.net]
- >>82
「M番目」のMをそのまま「通し番号」で表しているならその通りだ、たとえC
であっても。
しかし、Cでは、通し番号ではなくポインタで表現することで1クロックで
辿り付けるので O(1)。
- 85 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 12:42:38.21 ID:XIGB6bHM.net]
- >>65が何言ってるのか1行たりとも理解できなくて日本語の見た目した何かにしか見えないんだけど、
なんで話が進んでるの・・・
- 86 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 13:08:34.28 ID:Ga+Uz44a.net]
- >>83
自分でM番目に挿入って書いてるわけだが
- 87 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 13:34:07.88 ID:4cVpX4oe.net]
- >>85
「M番目に挿入」するが、それをMという数値で識別するとは書いてない。
数学とはそういうものだ。
ポインタ p で表現する場合でも、p が M 番目のノードを指していることがある。
その場合は、M番目に挿入と表現される。
そう表現しないと、O(x)記号で表現しにくいからだ。
- 88 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 13:35:00.70 ID:FsmeH+FF.net]
- >>83
それと同じことをRustではポインタの代わりにCursorMutを使って実現できる、という認識ですが
CursorMutには何が欠けていますか？
- 89 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 13:35:29.31 ID:4cVpX4oe.net]
- 数学での言葉の表現と日常の言葉の表現は異なる。
「M番目に挿入」することと、そのノードを、index = M - 1 で表すこととは
別の話だ。
- 90 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 13:47:35.86 ID:4cVpX4oe.net]
- >>87
同じノードを複数のCursor/CursorMutが参照している場合、1つの参照経由
でノードを削除した場合、別の参照がダングリング参照になるのを0コストで
防ぐ方法は無いはずだ。
静的解析が不可能で、時間や記憶域に何らかのオーバヘッドが必要となるはず。
- 91 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 14:16:45.03 ID:4cVpX4oe.net]
- さらに、1つの LinkedListに対して、同時に2個以上の CursorMut を作ることは
出来ないはず。
- 92 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 14:18:55.00 ID:iOAXb/4V.net]
- Cでリンクドリストの途中を直接ポインタで持っていると速いが
その途中が削除された場合にそのポインタは危険なポインタとなる
つまりCで記述しても何らかのコストをかけなければ安全に出来ない
つまりこの問題はどの言語であろうがコストゼロにすることは不可能
- 93 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 15:27:02.65 ID:I2sJLr90.net]
- >>91
いや、数学が得意な人は頭がいいので、それでも至って安全なプログラムが書けるし、
今ままでも書いてきた。
Rustは数学の得意な人間には遥かに及ばない。
- 94 名前：デフォルトの名無しさん [2021/09/10(金) 15:44:47.65 ID:EyQ85oMr.net]
- すげぇバカ
- 95 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 15:45:34.73 ID:XIGB6bHM.net]
- よくわからないけどこんなスレよりqiitaとかzennとかで記事書いたほうがいいと思う
- 96 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 17:06:16.82 ID:lpjuAWj9.net]
- >>86
屁理屈
- 97 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 17:11:54.58 ID:lpjuAWj9.net]
- どんな非負整数Mに対して
と自分で書いている
当然与える情報はMである
各Mに対応するポインタを保持するなら
挿入時にそのテーブルを更新しなきゃならないから
O(1)では出来ない
- 98 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 17:38:39.28 ID:dS7angqs.net]
- >>96
Mを与える情報とは書いてない。
Mというものを使わないと、LinkedListとVectorで共通した議論が出来なく
なるから書いてるだけ。数学では良く使う論法。
つまり、Mは、議論の中で場所を特定するために用いているだけで、
プログラム中で用いているとは言ってない。
- 99 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 17:41:20.99 ID:dS7angqs.net]
- 例えば、コンテナに100個のノードが入っていたとする。
コンテナは、LinkedListやVectorなどどんなアルゴリズムを使っているかは何でも良い。
で、「5番目の場所にノードを追加する」という言葉は、LinkedListにも使えるが、
その場合、プログラム中では5という数値で識別せず使わず、ポインタで識別する
のが C言語での常識。
でも、「5番目の場所に追加する」という言葉は使ってよい事になっている。
- 100 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 17:43:19.62 ID:iOAXb/4V.net]
- >>96
その人は数学が得意と言いながらそこすら理解できていない人だからね
Cでもプログラミングしたことあるならすぐわかることだからプログラミング経験も乏しいと推測される
つまりRustを叩きたいだけの人が暴れているだけの構図
- 101 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 17:48:47.41 ID:dS7angqs.net]
- >>99
理解してる。
お前らが、M番目のノードを数値Mでプログラムでも辿ると勘違いしている
抽象化が理解できない馬鹿だからそう思ってるだけ。
俺は抽象化が得意だから、M番目のノードをポインタで識別すると
考える。お前らは、Mとpを脳内で橋渡しできないだけ。
- 102 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 17:49:37.61 ID:dS7angqs.net]
- 数学的才能の無い人とは話が合わない。
知能に差が大きすぎる人達とは話が合わない。
- 103 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 17:58:29.87 ID:9JzLMDXF.net]
- もっと知能レベルが合った人が集う場所にいきな
- 104 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 18:15:44.49 ID:ae9TKcqK.net]
- >>100
君は数学が不得意だな
入力Mに対してM番目を得る関数のコスト(リソースコストなど含む)を考えればいいだけなのにそれができない
抽象的に考えるのが苦手なら具体的な関数のプログラムを考えてもよい
Rustを叩きたいだけだとしてもC言語のプログラミングくらいはできるんだろ？
君の主張が間違っていて実現不可能なことがすぐわかる
そして示せなければ君の完全敗北確定だ
- 105 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 18:22:19.32 ID:uQqwzIiF.net]
- >>98
完全に屁理屈
それならわざわざ「どんな非負整数Mに対しても」なんて言う必要は全く無い
任意のノード、任意の箇所
ならまだそういう可能性もある
たまたまMに対応するポインタがキャッシュされてた場合の計算量を言っても何の意味も無い
ちなみに数学的能力はお前よりあると思うよ
実績で勝負するなら付き合う
- 106 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 18:33:25.73 ID:HO5HNd+Q.net]
- >>65
> 俺は数学の天才。
これみて釣りと判断してるけどマジに受け取ってる人もいるのかな？
議論を続けるなら数学うんぬんの要素を抜きつつアクセス効率だけ語ってほすい
- 107 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 20:54:06.22 ID:2Djs9W2b.net]
- まあここ隔離スレなんで
- 108 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 22:29:30.98 ID:S72cPfGI.net]
- 自分は数学できないからできる人の相場感覚は分からないが、数学の天才って◯◯予想を証明したとか、定理に自分の名前が付いているとか、そういうレベルの人のことじゃない？ 東大数学程度で数学の天才を名乗られても……。
- 109 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 23:03:29.47 ID:G/i8H+xj.net]
- > 高校生が灯台に入学するときに受ける東大の数学の試験のことだよ。
高校数学でここまでイキれるのはもはや才能だと思うわ
数学の天才っていうのは数学の研究してて教科書書いてるような
著名な人をまわりの人が「他称」するときの話で
高校数学の成績で「自称」しちゃうってのは別の才能ｗ
- 110 名前：デフォルトの名無しさん mailto:sage [2021/09/10(金) 23:04:20.56 ID:uQqwzIiF.net]
- 東大でやる数学じゃなくて入試でしょ？
つまり高校レベル
こんなのを東大の数学と言うな
- 111 名前：デフォルトの名無しさん mailto:sage [2021/09/11(土) 01:22:42.58 ID:Q/hQI3Xf.net]
- 知ってる一番難しい数学がそれだったんでしょ
つっこんであげないのが優しさでは
- 112 名前：デフォルトの名無しさん mailto:sage [2021/09/11(土) 01:40:01.24 ID:PRM8i6LA.net]
- >>80
C言語でも他の言語でもそのようなことは実現不可能です
いくらRustを叩きたいとはいえ主張が滅茶苦茶になっていますよ
- 113 名前：デフォルトの名無しさん mailto:sage [2021/09/11(土) 10:36:57.99 ID:kQXQH3+b.net]
- 馬鹿ばっか。
- 114 名前：デフォルトの名無しさん mailto:sage [2021/09/11(土) 11:20:17.45 ID:PFLibieQ.net]
- 実際連結リストのノードに対する参照を保持しておくってどういうユースケースで現れるんだろうか
- 115 名前：デフォルトの名無しさん [2021/09/11(土) 11:40:09.41 ID:tSun79KI.net]
- 掲示板で算数自慢するときに使う
- 116 名前：デフォルトの名無しさん mailto:sage [2021/09/11(土) 11:42:49.15 ID:kQXQH3+b.net]
- >>113
例:
1. テキストエディタで、10万行のファイルを読み込み、その先頭に
1000行のテキストを挿入するときの速度向上。
2. 言語を自作する時、マクロ展開の時のトークン列へのトークンの挿入
- 117 名前：デフォルトの名無しさん mailto:sage [2021/09/11(土) 16:43:18.56 ID:zUj2TAiQ.net]
- >>115
それはどちらの使用例なのかハッキリしてほしいです。
配列にN番目への参照を格納する例として挙げているのか、
そうではなくリンクリストを用いる例として挙げているのか、
どちらですか？
- 118 名前：デフォルトの名無しさん [2021/09/11(土) 23:33:36.29 ID:EO9owr6G.net]
- >>112
- 119 名前：デフォルトの名無しさん mailto:sage [2021/09/12(日) 00:21:25.00 ID:CFIv5O+a.net]
- 相手をバカと貶めることで何もしなくても自分わ相対的に高めることができるという高等な議論テクだ
さすが高学歴
- 120 名前：デフォルトの名無しさん mailto:sage [2021/09/12(日) 02:54:54.78 ID:x/1IPUIX.net]
- >>115
1.ってバッファを1個のLinkedListとして持っておいて、カーソルの位置をノードへの&mutで持っておきたいって発想だよね
それよか2個のLinkedListに「カーソル以前の内容」「カーソル以降の内容」を最初から分けて持っておいて、
必要に応じて前者の末尾または後者の先頭を操作するという風にすれば、常に&mut LinkedListつかまれることもなくて都合良いのでは？
workaroundでしかないという批判は認めよう
- 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って言えばいいんですか？
|
 |
