探検
C++ vs Rust
レス数が1000を超えています。これ以上書き込みはできません。
Rust: 安全ｶﾐｿﾘ
裏方一緒だし
代入やコンストラクタが、moveとcopyのどちらになるかについて、Rustの
方が自動化が進んでいると思いがちだが、実際は、
C++は、関数の戻り値が構造体型/クラス型になっている場合に関しては
RVO(Return Value Optimization)が働き、右辺が
クラス名(実引数列)
の形式の一時オブジェクトである場合には、moveが選ばれるが、それ以外は、
概ねcopyになるので、ある意味では「自動選択」しているのに対し、
Rustでは、x = y と書いた場合、原則的には「デフォルトmove」の規則に
従い、copyしたい場合は、右辺をy.clone()と書くことになっていて、
「手動選択」を採用している。
C++は、どう書いた場合にmoveになり、どう書いた場合にcopyになるかを全て把握するのは
難しくて、C++の仕様が勉強不足だと勘違いや見落としが発生する可能性があるのに対し、
Rust方式は、moveとcopyのどちらになるかが明確なので混乱が少ないと言えるかも知れない。
つまり、このことに関しては、児童選択より手動選択の方が安心感があるかも知れない。
意見を求む。
とはいえc++のそれよりかは分かり易いけど。
xやfunc()の戻り値が CPerson というクラス型の場合、
10. x = y; // copy代入。yの中味はxにコピーされる。yのデータも保存。
11. x = std::move(y) // move代入。yのデータは破棄される。
12. x = func(a); // move代入または、RVOが働いてmove代入以上に速い動作になる。
関数の戻り値だけは特別に処理されている。
[Rust]
(CPerson がCopy traitを実装して無い場合に限定)
20. x = y; // move。以後、y は使用できなくなる。これが故にデフォルトmoveと呼ばれる。
21. x = y.clone(); // copy。以後もyは使用できる。
22. x = func(a); // move。20.と同じ規則に従っているだけで関数の戻り値だから特別では無い。
C++の場合、12.で関数だけは特別処理されているのに対し、Rustの22では
関数でも特別処理されているわけではなく、20.のデフォルトmoveの原則に従っているだけ
のように見える。
C++の場合、11. では、std::move()で修飾すると、なぜか、10. で修飾しなかった場合
より、実行されるCPUの処理が「減る」。ソースコードで関数の様なものを
追加した方が追加しなかったときよりCPUの処理が減ってしまうのは、どことなく直感に
反する。
一方、Rustの21と20を比較すると、.clone()を書いた方が書かなかったときより、
実行されるCPUの処理が増えるので、直感的である。
この場合、.clone()を書いたことで「コピーするためにCPUの処理が追加された」という
直感に沿った感じになるから。
C++の場合、std::move()と書くと「std::move()という関数の様なものを書いたのに、
なぜか、CPUの処理が減る」という違和感を感じるようになる。
って理解がシンプルなのかな
x = y の時、
結果的にはほとんどmemcpy(&x,&y,サイズ)に近い動作になっているかもしれないな。
ただ、右辺yの構造体メンバの中にRc<T>のような複雑なものが入っている場合、
結果は単純コピーのようになったとしても、コンパイラはもっと丁寧に処理
しているのではなかろうか。
move は memcpy だよ
Rc も実体はヒープへのポインタだから memcpy で問題ない
memcpy してはいけない例としては async fn みたいな自己参照構造体などがあるけど
Pin をうまく使うことで変な状態にならないようにしている
rustだってメモリ安全性がなければc++みたいなもんだろ
貶すまではいってないじゃん
C++をあまり好きじゃないところも同じ。
c++にもだいぶ甘くはなってるよ。
ただそれでもrustに対してもそこまで容認的ではない。
試しにドライバー書いてみれば？って言って試させてるが、まだまともには考えてないわ。
https://lkml.org/lkml/2021/4/16/901
むしをrust側に対して例外処理の方法をカーネル内での往来の方法に変更してくれって促しているように見えるんだけど
導入したがってるやんけ
続きを読めば？どういう流れかわかるから。
続きで懐疑的な立場取ってんのlinusじゃなくね？
話の流れは大体予想できてただろうなという受け答えだろ。
んでもって実際、発案者自らmoonshot言うとるわ。
少しは内容を読んでくれ、なんで一から十まで説明しなきゃならんのか。
じゃあレスすんなよカス
moonshotって言ってるの割り込みコンテキストでallocator呼び出すことをコンパイル時にチェックできるようにしたいという話では
現実的には関数ごとにどのコンテキストで呼び出せるものなのかタグ付けしてるとかなんとか
綺麗じゃないけど、まあ動くわなという解決策
つまみ食いしかしてないから読み違えてるかも知れないけど
これをもってlinuxカーネルにrust取り込むのを否定するような話ではないようにみえた
他にもmoonshotって言ってる箇所ある？
あのね。。書けばそうなるってものじゃなくてそれを実装しなきゃならんのよ。。
コンパイラにそういったコンテクストを判断させるのがめちゃくちゃ難しいっていってるでしょ？
なんでそんなに読み取れないの？
当面はdoc commentにannotation書いて済ませておくって言ってるやん
何はともあれ大局的にはrustをlinux kernelに取り込む方向へ進んでいくことには間違いない
だからそのコードじゃpanic捉えきれねーからカーネルに入れるわけねーだろって
言ってんじゃん。。何読んでんだよ。
int *pBuf = new int [n];
だけど、Rustの
let a:Box<i32> = Box::new<x>;
値が x である 32BIT 整数を Heap に 1 つ確保する、という意味だよね？
Heapに n 要素の i32 型の配列を確保したい場合、
let a:Vec<i32> = vec![0; n];
かな？
あ、
let a:Box<i32> = Box::new<x>;
ではなく、
let a:Box<i32> = Box::new(x);
let a:Box<i32> = Box<i32>::new(x);
let a = Box::new(x);
let a = Box<i32>::new(x);
かな。
か
確保した領域の中身を書き換えたい場合は「mut」を付ける必要があり、
値が x である 32BIT 整数を Heap に 1 つ確保するのは：
let mut a:Box<i32> = Box::new(x);
let mut a:Box<i32> = Box<i32>::new(x);
let mut a = Box::new(x);
let mut a = Box<i32>::new(x);
のどれかの書き方で、Heapに n 要素の i32 型の配列を確保するのが、
let mut a:Vec<i32> = vec![0; n];
let mut a = vec![0; n];
のどちらかの書き方かな？
なるほど、そんな書き方があったとは。でも正しくは、
let mut a = Box::new([0; n]);
かな？
って、n 要素のi32配列を確保して0で初期化するという意味らしいけど、
nは実行時に決まらないような変数も指定できるの？
できない
https://stackoverflow.com/questions/41710952/allocate-array-onto-heap-with-size-known-at-runtime
Vec<i32>に相当するのはstd::vector<int>だから、
>>33はstd::unique_ptr<int []>相当のBox<[i32]>型の例を出そうとしたのだろう
そういう値は作れるが、Box::newでは無理
>>244
ポインタは適切に使えばデータ構造やアルゴリズム自体が根本的に変えることが
できるので使わない時と比べて計算オーダー自体が劇的に変化することがあり、
プラシーボではない。
Rustはその点でC/C++に勝てない事がある。
247 デフォルトの名無しさん sage 2021/08/31(火) 14:28:10.16 ID:SlncBcTV
例えば、動的配列であるところのVectorはポインタでアクセスしても余り
効率は良くならないが、LinkedListは構造的にポインタで連結されており、
首尾一貫して添え字アクセスを使わずに必ずポインタでノードを識別する
ようにすれば、Vectorに比べて劇的に効率アップできることがある。
それはRustではほぼ不可能。ベンチマークはこの点が反映されてない。
同じ動作をしてもVectorだとO(N)なのに、LinkedListだとO(1)になるものがある。
これだけでも実験してみなくてもNが大きくなった時に明らかに速度が
違うことはコンピュータ科学では常識。
例えば、コロナの感染者数は、O(exp(aN))になるので、どんだけ頑張っても、
Nが十分大きい時にはO(N^b)が上回ることは出来ない。
そのベンチマークでは使ってる？
Rust は stable で LinkedList も VecDeque (双方向キュー)もありますよ
https://doc.rust-lang.org/std/collections/index.html
ここにそれらのオーダーが O(1) や O(N) になる話もまとまっています
参照局所性の問題もあるから計算量の理論通りにはいかない場合もあるけど、ちゃんと性能測定してデータ構造選定した？
Rust にはポインタがあるから C や C++ のデータ構造はほぼ実現可能なのでは
では赤黒木をひとつやってみて
Rc<RefCell<Node>>のパターン
Safe Rustでも実現可能
ところが、Rustでは借用規則のせいで上手く行かない。
めんどくさいので自分で気づく人だけが理解してくれればいいので、
俺はこれ以上説明しない。
理解できない人は、親切な人が説明してくれるのを待て。
無理。
それはあなたが無知なだけだ
Rustはメモリ安全性を保証する
一方でRustの標準ライブラリではunsafeが多数使われているがこれはメモリ安全性を保証できる操作を効率よく実装するためにある
つまり論理的にメモリ安全性を保証できるならばunsafeを用いてもそれをライブラリやモジュールに閉じ込めることができる
もちろん自作でもこれは同様である
新たな型も当然作ることが可能
標準ライブラリで提供されているリンクドリスト型や双方向リスト型はそのようにして作られている
つまり効率をも落とさない
お前は何も分かってない。
馬鹿は黙ってろ。
その「問題」とやらはCursorじゃ解決されてないのかい
ガイジ
また､その裏方のunsafeなコードをRustで書く意味はRustから扱いやすいこと､Rustプログラマーが慣れたRustの文法で書けることがあると思う
お前の理解は浅くて、間違っている。
お前の様な数学の出来ない人には何を言っても無駄。
Rustはunsafeを局所的に安全に閉じ込めることができます
例えばVec<T>型はその各メソッド実装においてunsafeを用いています
これも『Rustがunsafeを局所的に安全に閉じ込めることができる』具体的な実例です
>>58
C++よりもRustの方が優れています
前半、数学的には間違い。
お前には数学の才能が無い。
お前には数学の才能が無い
unsafeブロック内あるいは関数内でSAFETYが守られるようにしないと安全に閉じ込めることができないって意味？？
そうでなくて、unsafeブロックで閉じ込めようとしても、閉じ込め切れなくて、
O(x)で表される計算時間が、C言語とは同じでは絶対に不可能な場合があるんだ。
Rustのsafeモードでは、コンテナの中のノードに対して書き込み参照と読み込み参照
を持つことが借用規則によって禁じられていることが原因。
C言語ではそれが当たり前に出来るからとても効率の良いプログラムが可能だが
Rustでは、unsafeの外側ではそれが出来ないから不可能だ。
アプリレベルでそれが出来ないから。
これで納得できない人は数学の才能が無い。
俺は数学の天才。
数学の才能が無い人のためにもう少し詳しく書いてやろう。
・Rustのsafeモードでは、LinkedListの中の複数のノードに対して、
読み込み参照と書き込み参照を一度自動時には持てない。
持つと borrow cheker がコンパイル時にエラーを出してしまう。
・C言語ではそれが当たり前に出来る。
・アプリレベルで1つのLinkedListに対して複数の読み込み参照と
書き込み参照を同時に記録し続けることで、やっと、挿入や削除が
O(1)になる。index 値で保持すると O(N)になってしまうから、
vector と同じ速度オーダーしか出ない(つまり、LinkedList本来の性能
が全く出せない。)
・結果、Rustは、Cより遅いプログラムしか出来ない。その遅さは、データが
多いとき、C言語に比べて1万倍でも100万倍でも遅くなる。
コードで書いて
RustとCの知識と、東大数学が簡単に解けるような数学の才能をすべてもっている人
に聴いてみろ。
本当は次のような知識も必要：
・リンクドリストの構造。
・リンクドリストの挿入、削除などの計算オーダーO(x)。
・計算オーダーの記号O(x)の意味。ビッグオー。ランダウの記号。
東大、京大の学部レベルの解析学(微分積分学)の本を見よ。
・index 値 = 基本は配列の添え字。0から割り振られた連番。
リンクドリストでは本来使わないが、Rustではノードの場所を覚えておくために
使わざると得ない。その場合、リンクドリストの先頭のノードを 0 番とし、
次のノードを 1, その次のノードを 2 のように表す。
しかしそうすると、リンクドリスとの M 番目の場所の参照を取得するのに
O(M)の時間が掛かってしまい、リンクドリストの効率の良さが台無しになってしまう。
・このことから、リンクドリストが遅いという誤解を生む状況になってしまっている。
東大数学って何？
高校生が灯台に入学するときに受ける東大の数学の試験のことだよ。
それが簡単に解けるくらいのやつに聞いてみろって事だ。
しかし、受験テクニックやパターン学習によって解ける様になったやつはダメだ。
O(1) で i 番目の要素にアクセスできる safe な LinkedList 実装はある
https://docs.rs/chainlink/0.1.0/chainlink/struct.LinkedList.html
i 番目の要素というと不正確か
ポインタの代わりに Arena 内での index を使うことで LinkedList のノードを O(1) で参照することができる
Repeated 1 time(s), duration = 2.531µs
Repeated 10 time(s), duration = 4.661µs
Repeated 100 time(s), duration = 29.449µs
Repeated 1000 time(s), duration = 256.555µs
Repeated 10000 time(s), duration = 1.800129ms
Repeated 20000 time(s), duration = 3.273489ms
Repeated 50000 time(s), duration = 8.345219ms
Repeated 100000 time(s), duration = 16.454731ms
Repeated 200000 time(s), duration = 32.911471ms
Repeated 500000 time(s), duration = 83.993118ms
Repeated 1000000 time(s), duration = 166.193956ms
結構実行毎にゆれる感じはあるけど、おおむねO(1)じゃないですかね
アホですか？
>>73
Arenaを使った時点で裸のリンクリストじゃ無いし、時間は、O(x)が同じでも
オーバーヘッドが発生する。また、無駄なメモリー領域も食う。
呼んだ？
えっ？
高校数学？
レベル低くないか？
はい、私はアホで数学の才能が無いので数学の天才様の問題意識が分かりません
VecならO(n)になる先頭への挿入がO(1)でできることを示したつもりでしたが見当違いでしたでしょうか
push_front()使ってるから先頭へ挿入してるだけじゃないか。
Cのリンクリストは、どんな非負整数 M に対して、M番目に挿入しても
MにもNにも依存しない定数時間で挿入できる。
それがRustに欠けている。
そのオーバーヘッドは実用上問題になりますか？
例えばmallocの実装もarenaを使っていますが問題はないのですか？
そもそも計算量の議論をしていたのはあなたなのになぜ論点をずらすのですか？
挿入自体が定数時間でも
M番目を探すのが定数じゃない
「M番目」のMをそのまま「通し番号」で表しているならその通りだ、たとえC
であっても。
しかし、Cでは、通し番号ではなくポインタで表現することで1クロックで
辿り付けるので O(1)。
なんで話が進んでるの・・・
自分でM番目に挿入って書いてるわけだが
「M番目に挿入」するが、それをMという数値で識別するとは書いてない。
数学とはそういうものだ。
ポインタ p で表現する場合でも、p が M 番目のノードを指していることがある。
その場合は、M番目に挿入と表現される。
そう表現しないと、O(x)記号で表現しにくいからだ。
それと同じことをRustではポインタの代わりにCursorMutを使って実現できる、という認識ですが
CursorMutには何が欠けていますか？
「M番目に挿入」することと、そのノードを、index = M - 1 で表すこととは
別の話だ。
同じノードを複数のCursor/CursorMutが参照している場合、1つの参照経由
でノードを削除した場合、別の参照がダングリング参照になるのを0コストで
防ぐ方法は無いはずだ。
静的解析が不可能で、時間や記憶域に何らかのオーバヘッドが必要となるはず。
出来ないはず。
その途中が削除された場合にそのポインタは危険なポインタとなる
つまりCで記述しても何らかのコストをかけなければ安全に出来ない
つまりこの問題はどの言語であろうがコストゼロにすることは不可能
いや、数学が得意な人は頭がいいので、それでも至って安全なプログラムが書けるし、
今ままでも書いてきた。
Rustは数学の得意な人間には遥かに及ばない。
屁理屈
と自分で書いている
当然与える情報はMである
各Mに対応するポインタを保持するなら
挿入時にそのテーブルを更新しなきゃならないから
O(1)では出来ない
Mを与える情報とは書いてない。
Mというものを使わないと、LinkedListとVectorで共通した議論が出来なく
なるから書いてるだけ。数学では良く使う論法。
つまり、Mは、議論の中で場所を特定するために用いているだけで、
プログラム中で用いているとは言ってない。
コンテナは、LinkedListやVectorなどどんなアルゴリズムを使っているかは何でも良い。
で、「5番目の場所にノードを追加する」という言葉は、LinkedListにも使えるが、
その場合、プログラム中では5という数値で識別せず使わず、ポインタで識別する
のが C言語での常識。
でも、「5番目の場所に追加する」という言葉は使ってよい事になっている。
その人は数学が得意と言いながらそこすら理解できていない人だからね
Cでもプログラミングしたことあるならすぐわかることだからプログラミング経験も乏しいと推測される
つまりRustを叩きたいだけの人が暴れているだけの構図
理解してる。
お前らが、M番目のノードを数値Mでプログラムでも辿ると勘違いしている
抽象化が理解できない馬鹿だからそう思ってるだけ。
俺は抽象化が得意だから、M番目のノードをポインタで識別すると
考える。お前らは、Mとpを脳内で橋渡しできないだけ。
知能に差が大きすぎる人達とは話が合わない。
君は数学が不得意だな
入力Mに対してM番目を得る関数のコスト(リソースコストなど含む)を考えればいいだけなのにそれができない
抽象的に考えるのが苦手なら具体的な関数のプログラムを考えてもよい
Rustを叩きたいだけだとしてもC言語のプログラミングくらいはできるんだろ？
君の主張が間違っていて実現不可能なことがすぐわかる
そして示せなければ君の完全敗北確定だ
完全に屁理屈
それならわざわざ「どんな非負整数Mに対しても」なんて言う必要は全く無い
任意のノード、任意の箇所
ならまだそういう可能性もある
たまたまMに対応するポインタがキャッシュされてた場合の計算量を言っても何の意味も無い
ちなみに数学的能力はお前よりあると思うよ
実績で勝負するなら付き合う
> 俺は数学の天才。
これみて釣りと判断してるけどマジに受け取ってる人もいるのかな？
議論を続けるなら数学うんぬんの要素を抜きつつアクセス効率だけ語ってほすい
高校数学でここまでイキれるのはもはや才能だと思うわ
数学の天才っていうのは数学の研究してて教科書書いてるような
著名な人をまわりの人が「他称」するときの話で
高校数学の成績で「自称」しちゃうってのは別の才能ｗ
つまり高校レベル
こんなのを東大の数学と言うな
つっこんであげないのが優しさでは
C言語でも他の言語でもそのようなことは実現不可能です
いくらRustを叩きたいとはいえ主張が滅茶苦茶になっていますよ
例:
1. テキストエディタで、10万行のファイルを読み込み、その先頭に
1000行のテキストを挿入するときの速度向上。
2. 言語を自作する時、マクロ展開の時のトークン列へのトークンの挿入
それはどちらの使用例なのかハッキリしてほしいです。
配列にN番目への参照を格納する例として挙げているのか、
そうではなくリンクリストを用いる例として挙げているのか、
どちらですか？
さすが高学歴
1.ってバッファを1個のLinkedListとして持っておいて、カーソルの位置をノードへの&mutで持っておきたいって発想だよね
それよか2個のLinkedListに「カーソル以前の内容」「カーソル以降の内容」を最初から分けて持っておいて、
必要に応じて前者の末尾または後者の先頭を操作するという風にすれば、常に&mut LinkedListつかまれることもなくて都合良いのでは？
workaroundでしかないという批判は認めよう
byだいたひかる
チューニングマシンの存在を真っ向から否定したいならここではなく学会で論文を出そうね
普通に理論として確立している
数学できるくんの主張は線形型によってチューニングマシンの計算複雑性が変化するってことだろう
証明できたらチューニング賞ものだろう
何十年ぶりじゃないか?記述計算量に新しい概念が導入されるのは
所有権や借用が、やりたいことをストレスなく書けるようになる気がしなくて…
コンパイル通るようコード直すことを繰り返す内に最初からコンパイル通すことができるようになるかと
ありがとうございます
やはり繰り返しと慣れですね…
もう少し分かるまで粘ってみます
取り急ぎお礼まで
細かいことにいちいち煩い姑のようだからね。
別に大したご利益もないし。
ご利益の大小はソフトウェアの種類によって変わるだろうね
OSやブラウザのようなメモリアクセス違反が即致命的な脆弱性に繋がり得る、かつ、巨大でバグを取り除ききるのが難しいソフトではご利益大きい
逆に多少バギーでも困らないソフトならただ煩わしいだけというのは正しいかも
とはいえ慣れればコンパイルが通るようにコードを書くのは多くの場合難しくないので、個人的にはカジュアルユースでもコストよりメリットが多いように感じる
め早口
「最後に消費するのは誰か？」を明確にするだけでよくて
その人以外に渡す時は借用してもらうだけだよね
あとはmut借用だけ一時的独占でルールおしまい
コメントありがとうございます
いまはまだおっしゃることにピンとこないのですが、「最終消費者は誰か」は常にこころに留めて進めてみます
まだサンプルコードを写経している段階なので、具体的なテーマを見つけて苦労してみます
>>135 さんもありがとうございます
ホント、小煩い姑状態です
親父の小言は後に効く、といいますが…
haskellでいう型クラスや、代数データ型、パターンマッチなど魅力的な機能があり、はやく馴染みたいです…
まさに半年経ってようやくカーネルにアロケーター導入されたわけだが
完璧に君の負けだよね
お疲れ様です
https://doc.rust-lang.org/stable/std/alloc/trait.Allocator.html
頭悪いからさらに時間使っちゃいそうでかわいそう。
お馬鹿さんだからメーリス追えないんだねｗｗ
https://lkml.org/lkml/2021/7/7/349
悔しいねえｗ
頭悪いの君だよね？
Rustも使えるアルゴリズムに制限があるのだが。
例えば、C言語で使えていたアルゴリズムは、C++/Java/C#ではそのまま使える。
特にC++とC#には、Cから移行するときの制限が少ない。
ところがRustでは、これらのコードからはシンプルには移植できないものが存在
してしまう。
C#やJavaは速度を遅くする代わりに安全性と自由性の両方を確保できているが、
Rustは、速度は余り遅くならないが、自由性を犠牲にしている。
これは大問題となるだろう。
unsafeの中だけに閉じ込めきれないのが問題。
例えば、C言語の場合、アセンブラにしか掛けないことは、アセンブラでコードを書いた
ものをCの関数にして、Cから呼び出すことが出来たので問題なかった。
ところがRustの場合、リンクリストをポインタや参照を使って高速に扱うことが
unsafeの中だけでは完結できないので無理。
結論的には、リンクリストをO(1)でアクセスすることがRustのsafeモードでは
完全に不可能といえる。たとえ unsafe モードを使っても、safeモードに
「しみ出してきて」駄目になる。
・リンクリスト
・ツリー構造(バイナリツリーなども含む)
なんどもいうが、unsafeモードをいくら使っても言語の構造上、
無理なものは無理。
俺は数学の天才。最初から結論が分かる。
Rustでリンクリストやツリー構造をO(1)でsafeモードからランダムアクセス
できないことは数学的に完全に証明できる。
そしてそれは、unsafeモードをいかに工夫して使っても無理。
無理なものは無理。これは絶対。
俺は数学の天才。
それが出来るんだったらもっと普及してるし、もっと真似されてる。
Rustのやり方では不可能だから普及できない。
つまりunsafe使えばできるのね
アプリのあらゆる場所を unsafe にすれば出来る。
unsafeの閉じ込めが出来ない。
また嘘つきがRust叩きをしているのか
＞リンクリストやツリー構造をO(1)でランダムアクセスできない
これは全てのプログラミング言語で不可能
もちろんC言語でも不可能
以前も皆に論破されて逃走したのにまた戻ってきたのか
馬鹿は黙っとれ。
お前は全くリンクリストを理解できてない。
丁寧に説明したのに全く理解を示さないやつばかり。
Stroustrapも馬鹿だからリンクリストを理解できてない。
vectorだけでは人気アプリの速度は達成できてない。
コード例頂けないでしょうか
Cでうまく書けるものがRustでうまく書けない例
https://doc.rust-lang.org/std/collections/struct.LinkedList.html
std::collections::BTreeMap
https://doc.rust-lang.org/std/collections/struct.BTreeMap.html
本来の速度性能が出ない。
CではO(1)で済むところが、O(N)必要になってしまう。
余りにも馬鹿すぎるから、発言者の背景を示すしかなかった。
IQの違いが大きすぎると話が通じないと言われるが、まさに
このスレがそうで、ちゃんと言わないと、正しいことを言ってる
人が馬鹿にされるから。
・Cだとリンクリストやツリーの中のノードを識別するのに、通し番号ではなく
ポインタが使われる。そのポインタは、関数内部にとどまらず、
アプリ全体で大規模に保持され続け、ノードが必要になった場合、それを
介してノードにアクセスする。だから、読み込みも書き込みも自由自在に
行える。一つのツリーの中の有るノードを削除し、あるノードに子ノード
を追加し、あるノードの直後に弟ノードを追加し、あるノードを読み取り、
あるノードに書き込む、などを全く任意のタイミングで行える。
繰り返しになるが、これらのポインタはある関数の内部だけで完結
せずに、関数の外のグローバル変数にアプリの起動時から終了時まで
恒久的に保持され、必要なタイミングで使用される。
・Rustではこのようなことが不可能。ツリーのノードを指す参照を、
グローバル変数に複数保持して、書き込みと読み込みを自由自在に
行うことが不可能だかっら。
[補足]
Cの方で説明したやり方は、C++/C/Javaでも可能。
JSやRuby、Pythonでも可能。
Rustだけが不可能。
つまり、多くの言語が出来る中でRustだけが出来ない。
その結果、数学的な意味での「一般的」には、TreeやLinkedListでまともな性能が出ない。
もちろん、特定のケースでは同等性能が出ることはあるが。
[補足2]
通し番号ではなく、ポインタでノードを識別することで、末尾以外のノードを
削除した時でも、識別番号の書き換えが不要であるメリットもある。
ポインタとはアドレスを保持する変数のことであるが、リンクリストや
ツリー構造の場合、途中のノードを削除しても、別のノードのアドレス
は全く変化しないので、削除したノード以外のポインタ値は全く変更されないので
書き換えも必要ないからである。
一方、初心者がやりがちなのは、リンクリストでも先頭のノードを0番にして、
それ以後のノードを1、2、3 という通し番号で識別しようとする方法。
これだと、5番のノードを削除した時、6番以後のノードは番号の付け替えが
必要になるのでものすごく効率が下がる。
また、k 番のノードをアクセスする際には、O(k)の時間が掛かってしまう。
本来、Cではノードを識別するのは、このような通し番号ではなく、
ポインタ(アドレス)で行うのが伝統であって、アルゴリズムの教科書でも
それが前提になっている。
それがいつからか、リンクリストでも通し番号で識別する流儀を誰かが持ち込み
初めて混乱が生じるようになった。
日本語読めます？
ソースコードをくれって言っている
なるほど、そうなんだ
でも正直、なにを言ってるのかまだよくわからんから、ちょっとベンチマークを投稿して遅さを示してみてくれん？
Linked Listの実装なんてその投稿よりも圧倒的に短く書けるとおもうし、ちょっとやってみせておくれ
This is a nightly-only experimental API. (linked_list_cursors #58533)
CursorMutのStabilisedがまだ来てないことへの批判ってこと？
> Rustでリンクリストやツリー構造をO(1)でsafeモードからランダムアクセスできない
どんな言語で書いてもO(1)でランダムアクセスできないのでRustでも同様にO(1)でできないのは当たり前
一般的にランダムでkが与えられた時にリンクリストでk番目を得るにはO(n)かかる
C言語でもO(n)でありO(1)では不可能
リンクリストとポインタを学び直してから出直せ。
君はプログラムを書いたことがないのかね？
どんな言語でもランダムでkが与えられた時にリンクリストでk番目を得るにはO(n)かかる
O(1)でできると主張するならば実行可能なソースコードを出しなさい
「過去に一度対象となるコンテンツのポインタを確認&記録している場合」じゃなきゃO(1)は無理だろ。
ランダムでkが与えられた時にリンクリストのk番目を常にO(1)で得るためには
全てのk番目の位置を別途ベクターで保持管理しないといけなくなる
そしてリンクリストで挿入削除が行われるたびにk番目がズレるから保持管理ベクターで毎回O(n)の移動が発生する
つまりどんな言語でもO(1)は絶対に不可能
そう思うのは、ランダムアクセスの定義をあなたが誤解してるからだ。
確かに、リンクリストに置いて、何の情報も無く「k番目」のノードに
アクセスするにはO(k)の時間が掛かる。
しかし、そのアクセス方法は、ランダムアクセスする場合に必須ではない。
p1, p2, ..., p_a
というa個のポインタがあって、それをランダムに選び取ってアクセスする場合の
1つあたりに掛かる時間が、O(1)であれば、ランダムアクセスの時間はO(1)
だと言えるから。
連続アクセス以外は、全てランダムアクセスなんだ。
具体的には、最初から100個のノードのアドレスを、100個のポインタに記録していたとしよう。
そのポインタは、リンクリストの中の位置で見ると、連続して並んでいるわけではないとする。
そのポインタを順番に参照してリンクリストのノードをアクセスすれば、連続アクセスでは無いから、
ランダムアクセスに分類される。
もう一度言おう、連続的な位置では無いノードを複数個アクセスすればランダムアクセスだ。
IQが低い人は、こういうトンチのようなものに弱い。
だから、IQの高い人とIQの低い人では誤解が生じ、大変な結果となる。
どうしてあなたは、2つの概念を切り分けられないんだ。
kを任意に与えられてk番目のノードをアクセスするには、確かにO(k)の
時間が掛かるが、ランダムアクセスは、最初からアドレスが分かっている
ノードをa個アクセスした場合の1つ当りのアクセスに掛かる時間でも
いいんだから、必ずしもO(k)ではなく、O(1)になる場合がある。
数学は精密な学問だから、場所をランダムにアクセスすることと、
毎回kという通し番号が与えられて毎回前から順番に辿ることとは
全く別の事象である。
ちなみに俺は、数学は毎回100点とっていたような数学マンだ。
ランダムでkが与えられた時にリンクリストのk番目を常にO(1)で得るためには
全てのk番目の位置を別途ベクターで保持管理しないといけなくなる
そしてリンクリストで挿入削除が行われるたびにk番目がズレるから保持管理ベクターで毎回O(n)を必要とする移動が発生する
つまりどんな言語でどんな手法でもO(1)は絶対に不可能
リンクリストの中に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)で正しい。
だから、それはランダムアクセスの定義では無いんだと何度入ったら分かるんだよ。
どうして、k番目を乱数で与えると思ってるんだ。
ランダムアクセス度は、「ランダム数で与えられたノードでアクセスする」
ことではなく「ランダムな位置のノードをアクセスするためこと」だぞ。
数学的には全く別概念だ。
何でも言うが俺は、数学はほぼ満点だった。
#![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]
}
遅くなる例としては、テープレコーダーがあげられる。
これは、どう頑張っても、長さNに対して、O(N)の時間がかかってしまう。
繰り返しになるのが、リンクリストの場合は、O(1)だ。
ただし、先頭からの通し番号 k を与えられた時に、データが有るアドレスを計算するのに
掛かる時間は、O(k)だ。
しかし、ランダムアクセスに掛かる時間はO(1)だ。
この違いが分からない人は数学が出来なかったことであろう。
C言語では古くから、リンクリストをO(1)の時間でランダムアクセスして
きたからだ。O(k)ではなく、O(1)だ。
この例としては、リンククリストの中の不連続な100個のノードのアドレスを
どこかの配列にいてれておいて順番にアクセスする例がある。
この場合、一個当りの平均アクセス時間はO(1)、全体に掛かる時間はその100倍で済む。
しかし、アドレスではなく、ノードを通し番号で識別した場合、
一個当りの平均アクセス時間は、O(N)、全体に掛かる時間はその100倍になってしまう。
この意味に置いて、アドレス(ポインタ)でノードを識別することに徹すれば、
リンクリストにランダムアクセスする時間は、O(1)である。
しかし、このようなアクセス法は、Rustは一般的には無理。
プログラミングは理屈が重要。
O(1)の記法も実験せずに思考実験で結論を得るためにある。
Rustって参照を持ち回すことがそんなにできないんだ
わからない人はコーディングすればすぐわかる
ランダムでkが与えられた時にリンクリストのk番目を常にO(1)で得るためには
全てのk番目の位置を別の配列で保持管理しないといけない
そしてリンクリストで挿入削除が行われるたびにk番目がズレるから保持管理する配列で毎回O(n)を必要とする移動が発生
どんな言語でどんな手法を用いてもO(1)は絶対に不可能
俺もそう思う
彼の主張にはポインタの配列をケアする時間を含んで無さそうに聞こえたけどｗ
せっかくのリクリストとは別にアクセス用のポインタ配列をケアするってことも
ふしぎなコーディングだけど
そこまでするなら最初から配列だけでやれって思うけどｗ
その別の配列に用意したアドレスに基いてアクセスすれば、立派なランダム
アクセスなんだ。
ランダムアクセスとは、毎回デタラメにアクセスすることでは無いぞ。
テープレコーダーの場合、キメウチで、100, 1, 200, 10, 30, 2, 1000
の位置の7個のデータを取得するには、シーク時間が必要だから、
100+99+199+190+20+28+998 の時間が掛かる。
そしてこの読み取りを2回行ってもまた同じだけの時間が掛かる。
その意味で、ランダムアクセス時間は、テープの長さがNの時、O(N)とされている。
ところが、リンクリストの場合、アドレスが毎回決まっている 7 個のデータ
をアクセスするには、一個当りのノードに掛かる平均時間は O(1)だ。
これを2回行っても同じ。
あなたがおもっているような、シーク時間はリンクリストの場合には不要だから。
そうでなくて、その配列が既に決まっている場合もあるんだということだ。
それを上手く用意することが出来るケースが現実にかなり有る。
挿入削除場所以降のコピーする必要が出るだけで
へー
記録しておけば「シーク時間」が不要だから。
例えば、100個のノードを任意の位置に追加したとしよう。そのアドレスは、
100個分は既知である。そのアドレスをまたどこかのリンクリストの末尾に
でも順番に追加して全て記録しておいたとしよう。
そうすると、元のリンクリストは、立派にO(1)でランダムアクセスできるんだ。
> シーク時間はリンクリストの場合には不要だから。
そら、あらかじめアドレスがわかってればできるだけで、別にLinked Listの性質ではないよね
そこでO(1)とは配列のアクセスのみ
つまりリンクリストは全く関係なく配列のアクセスがO(1)だと主張していることに気付こう
そしてリンクリストで削除や挿入が行われるたびにその配列でO(n)の大移動が行われる
結論: O(1)ではどんな言語でもプログラミングできない
そんなことない。
あなたは、ポインタを使ったプログラミング経験が浅い。
そうでない。
テープレコーダーとリンクリストでは、明らかにランダムアクセスに掛かる時間の
性質が違う。
「アドレスが既知」であるのは、ポインタを全面的に使ったプログラミング法
では当たり前の事だから、リンクリストに置いてシーク時間は不要。
違う。
ツリーの場合でも、番号ではなく、ノードをポインタで識別することで、
0の時間でシークできる。
リンクリストでも同じ。
通し番号を使おうとするから遅くなってるだけ。
ノードの識別をポインタで統一してしまうと、本当に O(1)でいける。
あなたの主張を整理すると
「k番目をO(1)でアクセスできる配列」は「k番目をO(n)でアクセスできるリンクリスト」よりも優れている、となる
O(1)の部分はリンクリストと全く無関係であることに気付かないとね
ここまで壮大な勘違いをしてるのはおそらくプログラミングをしたことがないのだろうけど
テープレコーダーはランダムアクセスできない。これも当然
なんでテープレコーダーと、メモリ上に実装したLinked Listを比較しているのか意味がわからない
何を説明しようとしてるんだろう
なんか話途中から首突っ込んだけど
結局はそういうしょうもないオチっぽいなこれｗ
ポインタの指す先のデータ構造に一切関わらず
アクセス用のポインタを回収して配列にするんならそりゃO(1)だもんな
そしてわざわざそれをしたいという動機もよーわからんかった
個人情報がリンクリストに入っているが、ID番号と個人情報は別に配列の中に
入っていて、ID番号の構造体には、リンクリストのノードのアドレスも
入っているとする。
これだと、ID番号を全て巡って、それぞれの個人情報を巡る時、
個人情報の1個当りのアクセスに掛かる平均時間はO(1)だ。
しかし、ノードのアドレスの変わりに、ノードの通し番号を入れてしまって
いたとすると、ノードをシークするためにO(N)の時間が掛かってしまう。
なので、ノードの識別をポインタにしてしまえば、O(1)で、通し番号に
してしまえばO(N)の時間が掛かる。
だから、リンクリストを使う場合には、通し番号ではなく、ポインタを
使うことが推奨されている。ところが、Rustではそれがほぼ不可能。
いや、ノードの識別をアドレスで行いさいすれば、
リンクリストと配列のランダムアクセスに掛かる時間はどちらもO(1)だから
リンクリストが劣っていることは無い。
なぜなら、乱数で与えられた位置のノードをアクセスする必要は無いから。
ランダムアクセスする場合でも、アクセスすべき位置は、アドレスで決まっている。
シークの時間は不要。
次の借用規則に引っかかる。
・1個でも書き込みの参照が有る場合、読み込み参照は1つも持てない。
書き込み参照も1個しか持てない。
Rustが次々とC/C++の領域を置き換えていってるように
両者で実現できることは同じ
彼はアルゴリズムとオーダーについてもよく理解できていないだけでなく
Rustについても全く理解していない
計算時間のオーダーが全く違ってくる。
データベースなどは速度やメモリー効率を高めるために、さまざまな構造を
駆使して作られていることが有り、Rustでは自由に作ることが難しいことが
有り得る。
100万行のテキストエディタの先頭に1000行のデータをペーストするような
時にもリンクリストが大活躍する。単純な配列では遅すぎて駄目。
あなたは、データ構造やポインタを深く理解して無いか、
高度な実践的プログラミング経験が浅いかのどちらか。
やはりプログラミングしたことがないようだな
そこで50万行目に行く場合に配列併用なし実装だとリンクを50万回たどるO(n)
配列併用あり実装だと50万行目へ一気に行けるO(1)が挿入削除時のたびに配列内で大移動O(n)
つまりO(1)になっているのは配列アクセスのみ
リンクリストAの中のランダムな位置のノードのアドレスを、
別のリンクリストBに入れておいて、Bの先頭から順番にループすれば、
リンクリストAのノードをランダムアクセスできるが、その時の
一個のノードあたりの平均アクセス時間はO(1)だ。
ここに配列は一個も出てこない。
それ、あるkが与えられたときにk番目のアクセスがO(n)になってる
それがリンクリストの性質
ランダムアクセスすなわちk番目のアクセスはO(1)の配列が圧倒的に有利
それはテキストエディタでは結構問題になる部分だが、
実際的には、ページ単位の大きな移動は文字挿入や文字削除などの編集操作に比べて時々しか
行わないことと、現在位置から相対的な移動距離は大きくないことが多いことから、
行の記憶は配列ではなくリンクリストにしておく手法を取ると良い。
実際に行の記憶を何も配慮せずに配列でやると、ペーストした時にとても遅くなる。
一方、行の記憶をリンクリストにすると、実際問題はかなり快適になる。
スクロールなども速い。
一気に決め打ちの行番号に移動するのはO(N)の時間が掛かることはかかるが、
決め打ちの番号に移動することは、たまにしか行わないので遅くは感じない。
どうして、あなたは、いつまでたっても、頑なに番号k からノードを
辿ろうとするんだ。
ポインタだと速いのに。
何のためにポインタが発明されたのか理解して無いな。
ランダムアクセスとランダムに生成した通し番号 k のノードにアクセスする
ことは別の概念だぞ。
ropeもgap bufferもpiece tableも普通にRust実装あるが
それは、人の知らないものを出してきて、根本問題から目を背けさせる手法。
どんなcrateがあろうと、根本的に出来無い事がRustには有るという話をしてる。
だからそのデータ構造をCでもC++でもなんでみいからはよソースコードで示せ
まずCプログラマーには常識だけど
インデックスの番号を持つこととポインタを持つことでオーダーOが変わることはない
次に各々への複数のポインタを持つには配列やリンクリストなどの構造が必ず必要となる
いずれにせよポインタを使うことでオーダーOが変わることはない
>>228
そんなウソをついて何がしたいのかさっぱりわからない
>インデックスの番号を持つこととポインタを持つことでオーダーOが変わることはない
>次に各々への複数のポインタを持つには配列やリンクリストなどの構造が必ず必要となる
>いずれにせよポインタを使うことでオーダーOが変わることはない
なんで、このスレはこんなにレベルが低いの。
>そんなウソをついて何がしたいのかさっぱりわからない
真実だから。
数学の専門家であってプログラミング経験がないからソースコード出せとの指摘には一切答えられないということかな
ここであなたがおっしゃっているのは、以下のような実装のことでしょうか？
Element *array[] = {l0, l1, l2, l3, ...};
lnはリストのn番目の要素
近いが、初期値が、{ &l5, &l1, &l123, &l25, ... };
のようになっているイメージ。
ただし、実際には、
・初期化子リストには書かず、プログラムの途中でリンクリストに挿入した直後に記録するような
ことが多い。
・ノードの識別を常にポインタで扱うので、& で書くことは無い。
・固定配列ではなく、それもまたリンクリストにすることが多い。
なぜなら、リンクリストは効率が良いことが多いから。
そうではなく、
・大規模すぎて、こういうところには抽出して書ききれない。
・言葉で書いたほうが理解し易いはずだと思った。
抽象概念を理解しにくい人がこんなに多いスレだとは思わなかったから。
・しかし、これだけ書いても理解できないと言うことは、具体的に書いても
ますますそのコードの本質的な意味が理解できないと思われる。
ある要素が複数のリストに所属するイメージでしょうか
例えば全要素が連なっているリストのn番目、特定の要素だけが抽出された別のリストのm番目に属すといったような
要素の削除に当たっては属するすべてのリストについて前後の要素からの参照を外す
「格納要素が『データ本体でも、ポインタでも、何らかのid番号でも、他のインデックス番号でも、』そこは一切関係なく、様々な操作のオーダーOが変わることはない」
まずこの大原則をID:HWCOZSD4は理解できていないのたろう
だからポインタを使うと魔法のようにオーダーがO(1)になると勘違いしている
今回例としてあげたのはそういうケース。
ただそれは一例であってさまざまなケースがある。
アホか。
俺は現実世界では天才と言われてるのに。
この一例もやはりRustでは実装できないのでしょうか
読み込みオンリーに限定して、一切削除もしないという条件なら可能。
ノードの中に書き込んだり、ノードを削除するなら、不可能。
[補足]
C/C++/Java/C#/JS/Ruby/Python など多くの言語では可能だが、Rust
だけが不可能。
なので、Rustだけが仲間はずれであり、他の言語でできる事ができない。
C言語で可能なことはRustでも可能
>>244
嘘つき
gistでもどこでもいいからコード貼り付けてリンクここに貼ってください
日本語でうだうだ話すより議論が早く終わるでしょうあなたの言うことが正しければ
Rustでプログラミングをしたこともない人がデタラメな妄想を撒き散らしてるなｗ
デタラメ一言ってんじゃないぞ!!
>>247
具体例を書いても、それはレアケースだの、本質的にはリンクリストの速度では
間違った評価が下るだけ。
そもそも、極簡単な話を書いてるのに理解できないのにコードを書いても理解できる
とは思えない。
そもそも、ランダムアクセスの意味すら理解出来て無い、ここの人達は。
うそつきは黙れ。
>>244 は、Rustの借用規則からそうなってる。
僕はリンクリストの速度がどうこう評価するつもりはあんまりなくて、
他言語で書かれたソースコードが本当にRustでは無理なのかを確認したいだけ
だから、その「Rustでは無理なコード」を見てみたい、と言っている
最悪ソースコードの中身は理解不能なものでもよい
説明するつもりもないのに、お前らはどうせ理解もできないバカだ、俺はいつも数学100点の天才だ、俺を信じろ
とか言ってても狂人扱いされるだけに決まってるじゃん・・・
テキストエディタの例では>>119のアイデアを完全無視
C++では書けてRustでは書けないコード
リソースを無視すればチューリング完全だろうから
書けないなんて事はないはずで
何かしら制限を付けた上での「書けない」なんだろうけど
Rust でも書けるように思えてしまったのですが、以下のコードはどこが間違っているのでしょうか
https://play.rust-lang.org/?version=stable&;mode=debug&edition=2021&gist=7534885705cd5879f536acdf64947870
プログラマを守るためそれをさせないのが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 }]
}
Cursorでも無理だ。
実行結果はこちら
[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 }]
独自の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;
}
ゼロコストが謳いなのに、ゼロコストで無い。
それで実装も動作も良いけど
_bはどちらも不要
_a.0と_a.1はそれぞれprevとnextと書いたほうが読みやすい
_b は単一の要素が複数のリストに属するという要件に対する実装ですね
面倒だったのでメンバーだけ用意して実装はしてないですが
タプル使ってるのも構造体定義が面倒だったため
というかできるできないを実証するための例なので細かいところは適当です
お好きなように修正してください
>>263
>>245 の
> C/C++/Java/C#/JS/Ruby/Python など多くの言語では可能だが、Rust
だけが不可能
> なので、Rustだけが仲間はずれであり、他の言語でできる事ができない。
というのはほかの言語ではゼロコストで実装できることを意味していますか？
それともRustでも実装できることを認めた上でのただの負け惜しみですか？
はたまたこれを書いたのは自分とは別の人と主張されるのでしょうか
ゼロコストを定義してください
後半のあなたの主張、おかしくないか。
Rustの参照では無い独自の参照風の様な構造を添え字番号で実装してしまって、
C言語より速度を落としているのだから、ゼロコスト性に反してる。
参照に関しては、参照がC言語の生ポインタと同じ速度で扱えること。
あらゆる言語の中でRustだけが実装できないという主張は撤回されて
CにRustは劣るという主張へと変更されるのですね？
elements_aはinto_iterにしたらあかんの？と思ったけど
2つ持った時の前半用として用意した意味なのかw
1. データを格納している場所が配列になっているが、動的に長さを長くしようとすれば
動的配列と同様のコピー動作が生じてしまうから、その実装は、本来のLinkedListの
性質とはかなり異なる。リンクリストは速度的に安定である事が重要なのに、
この性質により、動的配列と同様に、時々大規模コピーが生じて、スパイク的に
速度が遅くなる減少を伴うことになってしまう。このようなスパイク的な
速度低下は、twitterかFacebook のどちらか忘れたが、どっかのSNSでも問題
になっていた。
2. アクセスするときに、番号を配列のアドレスに変換する動作を毎回行っている。
[補足]
誤解を招いて議論に混乱を来たしそうなので捕捉しておくと、
271の2で書いた「番号」は、リンクリストの先頭からの通し番号の事ではなく、
今回示されたリンクリスト風のコードで、内部で用いられている配列の添え字番号
のことで、リンクリストの先頭からは、辿っていっても、連続した番号には成ってないもの。
あらゆる言語で実装できないがRustでは実装できない
他の言語だと O(1) だが Rustだと O(N) になる
という主張を撤回されたと理解しました
そういうことでしたら私の方から言うことはなにもありません
またアロケーションについてはVecを実装が工夫されたコンテナ型に変えることで対応できそうですね
実装詳細のないまま議論してもしょうがないトピックなのでこれ以上こちらからレスを重ねることはやめます
ありがとうございました
[追加]
3. そこにさらに削除メソッドを実装したとしよう。
削除したノードに対する番号が、どこかのCursorの中にまだ生きた状態に
なっている場合、ダングリング参照と似た現象が起きる。
削除したノードの中を参照できてしまうのだ。
その主張、Rustの中に超軽量のインタプリタの様なものを載せておいて、
そのインタプリタの中ではランダムアクセスがO(1)のリンクリストが
完全に実装できることを示しただけだね。
しかも、追加すると、時々、大規模なメモリーコピーが生じるし。
newやmallocではそのようなメモリーコピーは生じない。
ノードを追加しても、リンクリスト中の他のノードの本当のマシン語レベルでの
線形アドレスが固定で変化し無いし。
あなたの実装では、それが変化してしまう。相対アドレスは変化しないが。
ベースアドレスが変化している。
generational arenaという手法を利用することでダングリングポインタ的アクセスを検知してハンドリング可能になります
[補足]
実質的なダングリング参照が起きるということは、Rustのもう一つの柱である
ところのメモリー安全性が部分的に壊れてしまってるということだ。
動的コストを掛けていいなら、C++でも安全性の高いものは作れるぞ。
ポインタも正しいメモリーブロックを指していることを動的に確認した後で
実際に参照するようなことは、C++でも出来るから。
Rustも配列の範囲チェックはやっているが、配列以外のアドレスでも、動的に
チェックしようと思えばいろいろなチェック法はある。
その一つの方法が、アドレスではなく、あなたが書いたような配列の中の
番号方式にしてしまうこと。
番号に対する配列要素がNULLになっていれば、動的にエラーを出力して
アプリを停止させる、などの方法が有る。
Rustの zero-cost abstraction はあなたの期待するような物ではありませんでした
残念でしたね
>> C/C++/Java/C#/JS/Ruby/Python など多くの言語では可能だが、Rust
だけが不可能
>> なので、Rustだけが仲間はずれであり、他の言語でできる事ができない。
>というのはほかの言語ではゼロコストで実装できることを意味していますか？
>それともRustでも実装できることを認めた上でのただの負け惜しみですか？
分かった。ゼロコストで無くて良いなら Rustでも実装できるということだね。
なるほど、今回の実装法のような裏技の発想は無かったよ。それは認める。
でも、ゼロコストでなくなるということは、RustがC/C++の代替になるという
説には反することになるね。
それと、C++, Java, C# では最初から標準ライブラリ的なもので最初から実装済み
なのに対して、あなたのやり方は、少なくとも標準のLinkedListではないね。
Cursorも標準のものとは別。
ノードへの参照を持ったままリストを変更したいの？
何がしたいって、C/C++/C#/Javaでは、LinkedListへのアクセスがO(1)で
自由自在に出来るのに、標準のRust実装では出来ないことが問題なんだ。
それに、今回示された実装法では、内部では配列で実装されているから、
ノードを追加してい言って、配列の要素数を超える時には、新しい配列を
コピーして内部でコピー動作が生じる。これは、C++のnewよりも遥かに
遅い動作になってしまうし、スパイク的に時々生じるから速度的な安定性
が求められるソフトでは好ましくない現象。
また、実質的なダングリング参照的が生じることも指摘した。
結論は、このやり方で、C/C++などと同じO(1)にはなったものの、安全性も失われ、
ゼロコスト性も失われ、C/C++の実装に比べて速度的に不安定でありスパイク的に
遅くなるということだ。
「LinkedListへのアクセスがO(1)で自由自在に出来る」
が正確にはどういう意味かと聞いているんだ
>>257の実装は忘れなさい
>ノードへの参照を持ったままリストを変更したいの？
もちろん、それもある。
>「LinkedListへのアクセスがO(1)で自由自在に出来る」
>が正確にはどういう意味かと聞いているんだ
Cの場合、ポインタでアクセスすれば、O(1)でリンクリストの
ノードを参照できるし、削除も出来る。
削除しても、他のノードのアドレスは変化しないから、ポインタも
書き換える必要も無い。
配列だったら、削除するとそれより後ろのノードの番号が全て
変化してしまうので、書き直さなくてはならない。
リンクリストでも、先頭からの通し番号を識別番号に
している場合には、同様にそれ以後のノードの全ての番号を書き換えないといけない。
リンクリストのノードにO(1)でアクセスするというのは、ポインタでアクセスすれば
当たり前の事で、どう説明していいのか分からない。マシン語では、間接参照の
[アドレス]
だけの話だから。
コンピュータの基礎から学び直してもらわないと理解してもらえないかも知れない。
マシン語を学んで欲しい。
Vec::split_at_mutと同様の発想
だからそれだけならCursorMutでできるんだって
でもダメなんだろ？
それはなぜ？
どっちがデマだと思ってるのか知らんが、俺のはデマじゃないぞ。
実際に、今回の実装を示した彼は、俺の言ってることはある程度正しく理解していた。
つまり、基本的にデマじゃないということを理解した人がいるということだ。
ただし、彼は、ゼロコスト安全性である、ということを無視して独自実装したり、
参照を独自に修正したものを勝手に導入した誤魔化しがあったのが残念であった
だけだ。
つまり、俺の主張自体は、彼は本当は理解している。
理解しているが、悔し紛れに詐欺めいた独自実装をしたことだけが残念なだけだ。
1つのリンクリストに対して、書き込み参照や読み込み参照を同時に複数持てない。
デマを流すのはそろそろやめとけよ
RustはRefCellもあるし複数からポインタで指しつつ書き換えもできるぞ
そもそも、RefCellは、動的チェックが入るからゼロコストではない。
C には存在しないコストが新たに導入される。
何を言ってるんだ？
そういうコストかけずにどうやって排他制御するんだよ？
そこはCだとプログラマが気をつけることで排他制御してるんだと思うよ
unsafe Rustでも同じだけど
C++と同じ事が出来るのに「ゼロコスト」で「安全」、と謳ってるのが間違いだと
言ってる。
間違いというより、デマや誇大宣伝。
そうだ、最初からそう言えばよかったんだ
蓋を開けてみればO(1)なんかまるで関係無いじゃないか
でそれに対して>>287という策があるわけだがどう思う？
「排他制御」とは、マルチスレッドプログラミングで使う用語なのだが、
本当にその意味で使ってるか？
ゼロコストって他のことでもそうだけど全くコストがかからないってことではない
必要最低限のことのみでそれ以外はゼロコストってこと
今回のRefCellならば並行プログラミングの時の書き換え競合が起きないことを保証する
RefCellはゼロコスト
ゼロコストでないと主張するならば他の対処方法を述べよ
「策」があるっていうが、どんどん複雑化し、コストも増えているだろ。
俺も正直言うとRefCellとか出てくると複雑すぎてよくわからなくなってくるが、
RefCellは内部可変性に対するものだから、並行プログラミングを使わない時
にも使うことがあるはずだが。
比較するならRubyが妥当。
つまり、CやC++の代替には成りえない。
アプリレベルであってもC/C++の全てをカバーすることは出来ない。
そのコストを払いたくなければunsafe 使って自分で安全性を保証すればいいって話なんだが
それでもリンクリストがどうたらって話じゃなかったっけ・・・？？
シングルスレッドマルチタスクでも競合は起き得る
そのため書き込み権限がある者がある瞬間に複数存在しないことを保証する(排他制御)ためにRefCellがある
マルチスレッドの場合は並列に起き得るからもっと厳しくてRefCellではダメでMutexやRwLockを使う
比較するならVBAが妥当。
貴様のライバルはJavascriptだろ。
LinkedListの中のノードへの参照を10個持っている状態で、
その参照を使って1個のノードを削除しようとしてコンパイルは通るか？
safeであるためには必要なコストだと思うけどね
mutabilityが前後のノードに影響するデータ構造だから仕方がない
それCでもC++でもダングリングポインタ発生の駄目プログラマーパターン
そんなことないぞ。
vectorと勘違いして無いか。
参照先自体を削除するんじゃなくて、参照先からさらにnextとかprevたどってどっかのノードを削除するってこと？
参照先自体を削除するのはRustに限らず問題でるよね
参照先を削除するのは普通なことで、安全に行えるぞ。
参照とは、つまり、識別番号の代わりに使うものだからな。
参照はオブジェクトに付けられた名前みたいなもんだから、
逆に言えば、参照先を削除できないなら、削除する方法がほぼ無い。
そうすればRustのコードを2種類みんなが出してくれるよ
・1つは元のC言語と同じ安全度で場合によってはunsafeを用いて実装
・もう1つはメモリ安全性を保証してunsafeを使わずに実装
つまり「C言語で出来ることはRustで必ず出来る」＋「Rustではメモリ安全性を保証した実装も可能」
明らかにC言語よりもRustの方が能力も高く優れている
残り9個の参照はそのノードが削除されたことを知る術がないからダングリングポインタになるってことだろ
本来は、明らかに別のノードであれば問題ない。
C++では普通に安全にそれが行える。
リンクリストの中に、A, B, C という名前の人のデータが入っていて、
それぞれに対して1つずつそれぞれ、ポインタ pA, pB, pC が存在している時に
ポインタ pA を介してAを削除しても、B, C へのポインタ pB, pC は残っていて、
値も変更されることも絶対に無いから完全に安全。
Aさんのデータを削除する場合にはこのようなことが起きるが、その時には、
delete pA の後、pAを捨ててしまうだけで全く安全。
pB, pC は何事も無くまったく安全に残せるし、何のバグも入らない。
こんな単純なロジック、何の問題も無い。
それだと>>311の条件を満たしていないのでやり直し
・いずれにせよC/C++で書けるコードはそのままの形でそのままの安全度で必ずRustでもunsafeを用いて書ける
・更にRustでは安全性を保証する形でunsafeを用いずに実装することもできる
C/C++よりもRustのほうが明白に能力が高い
1つのリンクリストの異なる10個のノードに対する10個の参照。
C++でノードへのポインタは実装依存な方法でしか取れないよ
pAその他は本当にポインタ？イテレータではなく？
何度もしているが、それはフェイク。
Cできることのうち、Rustでは追加コストを掛けずにはsafeモードで出来ないことはたくさん有る。
unsafeモードを使いまくれば別。
しかしそれではRustを使う意味が無い。
C++ではなく、Cのリンクリストで考えよう。C++は別の複雑さを入れ込んだから。
なぜRustを使う意味がないのですか
Rustの売りはゼロコスト+安全性にあるからだよ。
どちらが掛けても意味が無い。
ゼロコストで無いなら既にC#やJavaがある。
安全で無いなら既にC++がある。
安全性を考慮していないCのLinked Listと、安全性が保証されたRustのLinked Listを比較して、
Rustは遅い、できることが少なくて不便だ、みたいなことを述べてたわけか
Cでもメモリリークしないようにして、スレッドセーフにするとかしたら、途端に大変になりそう
違いますよ
リンクトリスト内のメソッドでunsafeを閉じ込めることできると思うんだけどそれではだめなのか
複数のノードへの読み書き自由なアクセスの速度をO(1)を保ったままで、
RustではunsafeをLinkedListのメソッド内には閉じ込めることが基本的に
出来ない。基本的に、と言ったのは、先ほど彼が示したリンク先の独自
実装の様に、ゼロコストであることを諦めてコストを掛ければできる
ようになるから。ただし、その場合、スパイク的にO(N)の時間でコピー
動作が発生してしまう。
[補足]
スパイク的なコピーの発生だけでなく、普段からコスト増加もある。
ベースアドレス + 相対アドレスでアクセスするから。
その人が作ったLinkedList実装がポインタではなく格納配列のインデックスを使っているだけだよ
Rustの標準ライブラリのLinkedList実装ではポインタを使っています
std::collections::LinkedList
https://doc.rust-lang.org/std/collections/struct.LinkedList.html
それは分かってる。
で、標準の方は、ノードのアクセス速度に問題がある。
RustはLinkedListでも問題を感じたことがないですが何を根拠に？
1つのリンクリストの異なる10個のノードに対する10個のmut参照を同時
に持ち事は出来ないので、O(1)でアクセスできないからだ。
意味がわからないので具体的に意味のあるCコードを書いて
そのノードが全部別々であることが保証できないから
でもそれは他の言語でも同じで、例えば1のノードに複数の可変参照があって、
1の参照がノード消したらまずことになる
そしてunsafeを許すのなら、内部実装でUnsafe Cell使えばコンパイラからの見た目は不変参照になるから、
オーバーヘッドなしでそういうのは実装可能（ただしstdのLinkedListはそのようにはなっていない）
んで、複数個所のノードへの可変参照を得るというのは相当レアな操作なはずなので、
それはunsafeにしてもAPIの使い勝手としては全然問題はない
(A) 常にRustではC/C++コードと同じ安全度で(必要時はunsafeを用いて)実装できる
(B) ほとんどのケースでRustでは安全なコードを(unsafeを用いずに)実装できる
つまりRustの能力はC/C++を上回っている
言い換えると
C/C++を捨ててRustを使えば
(B) ほとんどのケースで安全性を保証する形で実装できる
(A) 残りのレアケースでもC/C++と同じ安全度で実装できる
したがってC/C++を用いずにRustを用いたほうがよい
とにかくパフォーマンスや使用リソースが最重要な用途がある
そういう所でC/C++が使われる
C/C++は少なくとも今後20年は使われ続ける
RustはC/C++と同じパフォーマンスを出せます
>>340を読みましょ
C/C++からRustへ移ったほうが誰の目にも得です
ここで宣伝しなくても自然に広まるはず
その、あわしろ氏とやらは、では、なにを推薦しているのでしょうか？
リンクリストのような単純な構造でSTLでもboostでもそれ自体が「安全でない」ことはめったにない。
バグや脆弱性を作りこんでしまうのは多くは固定長のバッファに対するパース処理などで、確かに各種の
*nixコマンドなんかはRustで書いて貰ったほうが良い場合があるが、C/C++の数msが致命となる世界で
Rustが一般的となることはない。そんな布教をやってるから嫌われるんだよｗ
悔しかったらOpenSSLとか書き直して”安全なコード”で出してみろよ？WebkitにC/C++を排除させて
Rustだけにさせてみろｗ
あらゆるスレで暴れてる
linus を老害呼ばわりするとは…
usじゃなくてmsなのか...
一方、C 言語 で検索すると一日分でも見ることが不可能なくらい大量に
発言されてることが分かる。
twitterでは「C++」というキーワードでは検索できないので推定するしかないが、
C 言語以上であろう。
>つまりRustの能力はC/C++を上回っている
ダウト。
安全面に置いては上回っているが、効率面では下がるケースがかなりある。
・Rustが仮に速度面ではCに比べて余り遅くならないケースが多いと
仮定しても(この仮定には嘘があるのだが)、使いこなすのがJavaやC#
に比べると難しい。
特に参照関連だけでも、Option, Box, Rc, Arc, Cell, RefCell, Cursor, ref, &
の理解が必要な他、mut &'a などの表記、
let mut a : mut &:T = mut& b
や
Option<Rc<RefCell<T>>> a;
new Box<T>( T {・・・} );
のような解読が難しいシンタックスも多い。
このような複雑な表記は、JavaやC#には存在しない。
また、& と * の違いもあれば、& と ref の違いも有る。
let文ですらパターンマッチング方式になっているので Cのポインタの 10倍理解が難しい。
つまり、普通IQ者には理解が難しい。
逆に高IQ者は、C++でも安全に使えるし、C++を安全面では余り問題を感じて無い人が多い。
さらに言えば、
・「自動参照外し」は便利だとされるが、逆に勝手に参照が外れることで、
他人の書いたコードの理解が難しいことがある。明記してるコードと
省略してるコードが同じことを意味してるのが理解しにくいので。
・&の意味が、let文の左辺ではパターンマッチング、右辺では参照、
の意味になっているので混乱しやすい。左辺では参照をはずす意味
になってしまう。
・＆は、reference(参照)演算子と呼ばれるのに、ref という演算子もあるが、
これは、意味がかなり違うため、混乱し易い。
・nullポインタを代入するポインタは、Option<Box<T>> のように長くなる。
・ライフタイム注釈が発展途上中なのか、特に構造体に関するライフタイム注釈
のドキュメントが少なく、例で説明されるだけで、根本的な意味を書いた
ドキュメントが存在して無い。
IQの定義は？
調査結果でもRustが連続1位を続けていることからも客観的に明白
例示してるシンタックス全部間違ってるし釣りだろこれ
うんこ嘘つき野郎
let mut a : mut &T = mut& b
Box<T>::new( T {・・・} );
だったかも知れんな。
複雑すぎるし、C++との違いが大きすぎて覚えてない。
C++ だと、new クラス名で、Rubyだと確か、クラス名.new。
Rustは、後者に近い書き方だから、書き方だけを見てもRustはC++とはやはり遠い。
大変使いやすい。
いくつか本を読んだが、スクリプト言語的な範囲で使うならばそうかも知れん。
しかし、C++やCのようにポインタを駆使したリンクリストやツリー構造の様な
ものを効率よく高速に、メモリーも節約しながら扱うには、Rustはとても
複雑になる。訳の分からんCell,RefCellなどと組み合わせる必要があることも多い。
すぐにRustを始めるべきです。
俺は調査目的で調べてるだけで、実用的に使うつもりはないからな。
たまに見かける使いこなせなくて脱落したケース？
使う必要性を感じない。
であれば、批判する資格はないな
有る。
ここで連呼されるのは本人も迷惑してるんじゃないかな
「あわしろいくや」という人物がいるようだ。
CとRustそれぞれでコードを書いてみることをおすすめします
計算量オーダーが変わるアルゴリズムレベルの検討ならともかく
コンパイラの最適化でいくらでも性能が変わりうる実装の詳細についてはまず性能測定するのが常識だと思います
キャッシュが効いてるとこ読むときの速度は目を見張るもんがある
ヒープで飛び飛びになったデータ構造はその点で恐ろしく不利
それを知ってる人は実測した結果で語る
天才。
関数型流行ってる今から見ると割と普通のこと言っとるわ。
むしろ綺麗な方
言語が汚いってのはよくわからないけど例えばどういうところが汚いと感じたの？
(1) ほとんどの用途でLinkedListよりVecの方が有用
(2) Rustの標準ライブラリにはLinkedList型もVec型もどちらもある
(3) もしLinkedListやVecを使っても実現できないならまずはそのRustコードを示すべき
(4) 仮に超レアケースがあったとしてもRustでは自分で自由に必要な型を作ればよい
アセンブラとチューリングマシン語以外の言語は汚い
嘘を書くな。
特に嘘はないと思うけど
stdのLinkedListがちょっと融通利かないところはあるけど
様々な言語の中でRustだけ linked list の任意の要素にO(1)でアクセスできないというのは嘘だった
も追加で
何種類もある「文字列」、それに生えている似たようで意味が違ういっぱいのfn（これはトレイトのせい）
わざと敷居を高くしてるとしか思えん
> letは固定を意味するのではなく式展開
letは常に成功する構造パターンマッチングにすぎないよ
if letは成功か失敗か不明な構造パターンマッチング
今どきの言語ならば左辺値にパターンが書けるのが普通
> 何種類もある「文字列」
文字列はヒープにあり伸縮可能なStringとそうでないstrの2種類しかないよ
ヒープを意識する言語なら2種類ある
あとは文字列の参照として&strがあってその本体はヒープにあろうがなかろうが同じ扱いできるだけ
CStr
OsString
OsStr
それはRustの文字列ではなく単なるFFI
通常のプログラミングでは登場しない
「任意の」
の定義をしないと無意味な主張
・どの言語でもリンクリストでk番目を得るにはO(n)かかる
・そのk番目を配列で持てばO(1)だがそれはリンクリストではなく配列アクセスのコスト
・リンクリストのk番目を保持する配列を維持するには削除挿入のたびにO(n)の移動が生じる
・これらは言語に依存しない
言語の汚さというよりもOSなどの環境が抱える複雑さをそのまま見せたらそうなったのでは
それを他の言語のせいにするrust野郎はクソってことだよ。
・Rustの通常のプログラミングでCStrやOsStrが出てくることはない
・そこでファイルやディレクトリやソケットを操作してもCStrやOsStrは出てこない
・つまりRustで使う文字列はstrとヒープのStringの2種類しかない
・CStrやOsStrはFFIを書く人のみが用いるのでほとんどの人には無縁
Rustで未だ対応していない未知のものが出現した時にその対応する人だけがCStrやOsStrを用いる
その時のその人を除き、全ての人はCStrやOsStrなんか知らなくてもRustでプログラミング可能
Pathの操作してるとOsStrは普通に出てくるのでFFIでしか出てこないというのは嘘
Rustで標準の文字列をUTF8のバイト配列（ヌル文字終端不採用）としたことによる弊害って側面が割と強い
でも他言語みたいにそこしっかりしないとなるとそれはそれでめんどくさいから結局のところトレードオフ
でもOsStrめんどいわ
WTF-8なる概念必要になったりとにかくWindowsが悪いという気はする
嘘を書くな。
正しくは、Rustは配列を使って独自実装しないとO(1)には出来無い事が明らかに成った。
参照だと借用規則で出来なくて、配列の添え字番号だと単なる整数なので借用規則の
適用範囲外だからできる。添え字番号をポインタの代わりに使って、独自に
リンクトリストを実装することで初めて、O(1)になる。
しかし、O(1)になっても、「係数」が大きくなり、1アクセスに20クロックくらいかかる。
配列の範囲チェックと、配列アクセスのための乗算と加算が追加で必要になるため。
一方、C、C++、C#、Javaではそんなことしなくても最初からO(1)。
お前みたいなやつは、一度殴ってやりたい。
匿名掲示板だからと言って、でたらめを書くな！！
ばか者！
C/C++ のリンクリストがどうして O(1) なんですか？
細かい点が全然分かって無い。
リンクリストでは、「k番目にアクセスする」と言っても、次の二種類ある。
1. (乱数などで)整数 k を与えられて、ノードを探す。
この場合、どうしても、O(N)、O(k)の時間がかかる。
2. 既に追加したノードを、もう一度アクセスする。
これには、C、C++、C#、Javは、O(1)しかかからない。
しかも、C、C++だと 1 クロック。
Rustだと配列と添え字番号を使って独自実装しなければ、
基本的にO(N)、O(k)かかる。独自実装した場合、
O(1)ではあるが、20～50クロックくくらいかかる。
>>411を読め。
俺は正直に言っている。また、数学が昔から良くできるので、間違ってない。
[補足]
実際、>>257 の独自実装は、Rustでも、任意の場所のノードをO(1)で
アクセスできるが、1アクセスあたりに一般的なノードサイズでは
20～50クロック掛かる。
悪いが、QZが出てくると話がややこしくなる。
かわいそうだが、単刀直入にいえば、QZは頭が良くないので、
レベルが全体に下がってしまう。
ようは、レベルが違う人は、教室を分けないとめちゃくちゃに成る。
レベルというのは熟練しているかどうかではなく、生まれつき決まっていて、
直すことが出来ない。
すまん。
>・どの言語でもリンクリストでk番目を得るにはO(n)かかる
これは間違いである事は何でも説明した。例えば>>411。
>・そのk番目を配列で持てばO(1)だがそれはリンクリストではなく配列アクセスのコスト
これも間違いで、C、C++、Java、C#では、配列で持たずに、直接、ポインタや参照
で持っても、O(1)でアクセスできる。
Rustでは、借用規則が邪魔して、複数の読み書き参照を同時に永続的に保持できないので、
「k」のような番号でしか場所を維持できないため、そんな風になってしまうだけ。
だから、配列と番号を組み合わせてやっとO(1)にできる。
C、C++、Java、C#では、ポインタや参照を永続的にいつまでも保持できるので
配列を使わなくても O(1)でアクセスできる。
その際、「シーク」動作は必要ない。つまり、先頭から k 番目までを辿る必要が
なく、いきなり、k番目に 1 クロックでアクセスできる。
Rustでは、それが、一般的には出来ない。Rustでも、
局所的に1個のノードだけに限定すれば出来る。
リンクリストに、
ハンバーガー、りんご、みかん、ドーナツ、パイナップル
の5つを追加したとする。
C、C++、Java、C#では、追加した時に、どこかの5つの変数にこれらの
ポインタを残しておけば、あとから好きなタイミングで、どの
食べ物にも、一瞬でアクセスできる。C、C++では、1クロック。
1番目: ハンバーガー
2番目: りんご
3番目: みかん
4番目: ドーナツ
5番目: パイナップル
3番目のみかんにアクセスするのも、1クロック。
その後に、1番目のハンバーガーにアクセスするのも、1クロック。
その後に、4番目のドーナツにアクセスするのも、1クロック。
例えば、こうだ:
LinkedList ll;
p1 = ll.append("ハンバーガー");
p2 = ll.append("りんご");
p3 = ll.append("みかん");
p4 = ll.append("ドーナツ");
p5 = ll.append("パイナップル");
[続き]
cout << p3->name; // 1 クロックで3番目のノードのみかんにアクセス。
p3->name="orange"; // 名前を英語に直す。アクセスには1クロックしかかからない。
cout << p1->name; // 1 クロックで1番目のノードのハンバーガーにアクセス。
p1->name="hamburger"; // 名前を英語に直す。アクセスには1クロックしかかからない。
cout << p4->name; // 1 クロックで4番目のノードのドーナツにアクセス。
p4->name="donuts"; // 名前を英語に直す。アクセスには1クロックしかかからない。
書き込みも変更も、アクセスには1クロックずつしか掛からない。
これが、Rustでは借用規則に引っかかるために出来ない。
その結果、標準実装では、k番目のノードに「シーク」する必要があるため、
O(k)や、O(N)の時間が掛かってしまう。
例えば:
cout << seek(ll, 3)->name; // O(N)の時間が掛かる!!
seek(ll, 3)->name="orange"; // O(N)の時間が掛かる!!
＞2. 既に追加したノードを、もう一度アクセスする。
これカーソルでO(1)でできるって何度も言われてるやんけ
書き換え可能なカーソルを複数持つコードを書くのがめんどくさいってならわかるが
[補足]
cout << aaa;
は、分かりにくいが、aaa の内容を表示する、という意味だと思って欲しい。
他の言語だと、print aaa; と書くことが多い。この点 C++ は異質であることは
認める。
Rustでは、標準 Cursorでは、読み、書き、削除を出来る参照を同時に持つことは出来ない。
C、C++、Java、C#では、
ll.RemoveAt(p2); // p2 のノードを削除。
もアクセス自体は1クロックで出来るし、今示したコードの好きな場所に
追加しても何の問題も無い。
p2は削除されているからアクセスできなくなるだけで、
他のポインタの値は変更されないので、それ以外は何もしなくても
そのままで良い。
良く確認してくれ。
RustのCursorは、順番に辿ることはできるが、読み込みと書き込みと削除が
出来るタイプの参照を同時に複数記憶することは出来ない。
標準(std)のLinkedListならそれはそう
前にも言ったような気がするが、
自前で作って内部構造にunsafecellを使えば、
不変参照を複数持っている状態でも書き換えが可能になる
例えば要素の追加時にそういうことをするカーソルを返せばよい
実装がめんどくさすぎるのは認める
もっと言えば、C、C++、Java、C#の LinkedListは、
p2 の直後に「じゃがいも」ノードを追加した後、
p4 の直前に「トマト」ノードを追加するなどと言ったことも、
O(1)で出来る。しかも、O(1)と言っても、極限的に速くて、
C、C++の場合は、アクセスには1クロック。
こういうことが、Rustでは、Cursorを使っても出来ない。
>>257のように、遅くするつもりなのか。
1ノードのアクセスに20～50クロックくらい掛かるが。
しかも、ダングリングポインタ、つまり、削除後にアクセスしてしまう
減少を防ぐことが出来なくなってるぞ。
アンセーフ前提だから>>257とは全然違う
ダングリングも当然防げない（でもそれは他言語でもそう
>>257 の実装でもそうだが、まだノードAに対する参照がどこかに残っている状態で、
ノードAの中身を削除できて、ノードAが使っていた要素を新規作成ノードのために
使用されてしまうね。
[RustのCursorの補足]
・書き込み用のCursorを1個でも作ると、読み込み用のCursorは作れない。
はずだ。難しすぎてちゃんと理解して無いことは認める。
std::cell::UnsafeCell なるものがあるのか。
Rustの参照は種類が多すぎ。
学んでも学んでもキリが無い。
しかも、1つずつをちゃんと理解するのが難しい。
Pathといってもこちらから使うだけならAsRef<Path>だからStringと&strでも全く問題なくOsStringの存在すら知らなくていい
したがって出てくるのはDirEntryのみとなる
それも周り全てUTF8環境ばかりなのでinto_string()で全てSome(String)になるため結局OsStringを扱ったことは一度もない
ResultのOk(String)ね
いやいやせっかく標準ライブラリがWindowsでも動くよう苦労してくれてるのにそれを台無しにするなよ
個々のアプリで雑に対処するならともかくRust擁護派がRustの強みを否定してどうする
あと Path::file_name も Option<&OsStr> 返すしこれは利用頻度高い
Rustはちゃんと考えられてるね
ただし自分はWindowsを使うことは100%ないから path.file_name().unwrap().to_str().unwrap() 等でいいし
他にも use std::os::unix::fs::MetadataExt して metadata.uid() 等することもある
リンクリストや広く一般的なデータ構造の空間的・時間的オーダーを語る場合には
ノードの追加
ノードの検索
すでに取得している指定ノードの削除
あたりを考えるのが普通ですが、
「一度取得したノードの再アクセスコスト」を特に取り上げて考えるというのは、確かに rust の特殊性を示しているものといえそうですね…
>>413
生まれてきてすみません…
また、話を混乱させている。
指摘していることが、全く的を外しているから。
ことを言い出す。それが最後に書かれたことによって、このスレに
後から来た人には「まとめ」の様に見えてしまうから、大迷惑。
全くまとめになってない、でたらめなことを書くから。
秀才達が大体理解したのに、「まとめ」として、レベルの人が全く
デタラメなことを話す。それがQZ。
クラスの場合、みんなの雰囲気でQZがレベルが低いことが分かるので呆れられ、
無視され、せせら笑いが聞こえるが、ネットだとそれが分からないから困る。
現実世界では言葉にしなくても、ひそひそ場なしや、せせら笑いなどで分かるが
ねっとではそのような言外のコミュニケーションが出来ないから。
どうせ、QZは、この文書の誤字脱字を発見して馬鹿にするんだろう。
誤字訂正:
誤:レベルの人が全く
正:レベルの低い人が全く
誤:ひそひそ場なしや
正:ひそひそ話や
誤:ねっとでは
正:ネットでは
>>432のまとめが嫌なら、中身のない4レスのうち1レスを使ってご立派なまとめぐらい書き込んだら？
こいつがまとめを書けば話は終わりだな
すみません
>>434-436
生まれてきてすみません…
お二人方どちらでもいいから
具体的に削除でダングリングが発生しないCかC++のO(1)コードを示してよ
それが示せない限り机上の空論
もしコードが示されれば対応するRustのコードを出します
＞具体的に削除でダングリングが発生しないCかC++のO(1)コードを示してよ
>>432
＞「一度取得したノードの再アクセスコスト」を特に取り上げて考える
という、他ではあまり聞いたことのない特殊な話ゆえに筋を深く追えていないのですが、
>>432
＞リンクリストや広く一般的なデータ構造の空間的・時間的オーダーを語る
において
①
＞すでに取得している指定ノードの削除
でいいですか？
②
データ構造は一方向リストでいいですか？
一方向だと削除がO(1)じゃないから双方向が良いのでは
それは末尾または冒頭ノードの削除の話ですね
何が与えられていて、何を削除するのか、きちんと定義していただきたいです
失礼、あるいは特定ノードの上流ノードの探索の話もありますね
確かに双方向の方が楽チンですが、「ダブルポインタ」を使えば単方向でも処理できないわけではないです
当然でしょう
>>432
＞リンクリストや広く一般的なデータ構造の空間的・時間的オーダーを語る場合には
＞ノードの追加
＞ノードの検索
＞すでに取得している指定ノードの削除
＞
＞あたりを考えるのが普通
なのに、
>>445
＞＞「一度取得したノードの再アクセスコスト」を特に取り上げて考える
＞という、他ではあまり聞いたことのない特殊な話
を延々とやっていることに噛み付いているのですから
さて実装実装…
リファレンスカウンタは必須になるな
重要な点としては
コンストラクタやデストラクタやスマートポインタに隠れて曖昧にならないように
それらを使わずに実装すべきだ
そもそもC言語でもO(1)という話なのだから
まずはC言語かつ標準ライブラリのみ使用が今回のコード条件
ん？アンカーで示してください
今回はリファレンスカウンタは実装に含めないつもりです、まあ C で書くつもりですけど
配列に格納し直すのが彼のアイデアの全てなんだから、つついても面白い話は出てこないよ
O(1)で追加・削除できる配列も作れる！って言い出したら、多分リンクリストを使うってことだよ
https://mevius.5ch.net/test/read.cgi/tech/1434079972/105
これでいかがでしょうか？
C/C++では、ダングリングが発生するのを防ぐのはプログラマーの仕事だ。
引き続いて双方向リストの場合
https://mevius.5ch.net/test/read.cgi/tech/1434079972/106
これでいかがでしょうか？
>>444
＞オブジェクトのアドレスをハッシュテーブルで持たせて、双方向リストで実装。
では C で実装願いますね
私は宿題を片付けましたので 、ちゃんちゃん
>>432では、あなた、そういうこと書いてなかったよね。
こういう議論でははっきり言わないと分からないよ。
でも、あなたの観点は間違ってる。
C/C++/Java/C# においては、リンクリストで、一度作成したノードのアドレスは
ずっと保存するのが基本で、「先頭からの通し番号」で「辿る」ということは効率
が悪すぎて特殊なケース以外ではしないから。
もうリンクリストなんか不要で、最初からハッシュテーブル一本でやっていくべきなのでは？
なんでリンクリストとハッシュテーブルを両方使うのですか？
ハッシュテーブルなんて全く使って無いぞ。
あなたはポインタの仕組みを理解して無いのか？
のではないか。
アドレスさえ分かっていれば、1クロックであらゆるオブジェクトにたどり着けるぞ。
基本的にハッシュ構造とは全く関係無い。
失礼、>>444 とは別の方なんですね
でも、
＞C/C++/Java/C# においては、リンクリストで、一度作成したノードのアドレスは
＞ずっと保存するのが基本で、「先頭からの通し番号」で「辿る」ということは効率
＞が悪すぎて特殊なケース以外ではしないから。
それはそうです、リンクリストを頭から舐めるのは効率がイマイチなのはおっしゃるとおり、単純な構造だからそれはしかたがない
しかし、
＞リンクリストで、一度作成したノードのアドレスはずっと保存する
って、どこにどういう形で保存するのです？
＞QZは、ポインタが 1 クロックでどんな場所にもたどり着けることを理解出来て無い
＞のではないか。
>>456, >>458 で示した程度には理解しているつもりです
＞アドレスさえ分かっていれば、1クロックであらゆるオブジェクトにたどり着けるぞ。
で、そのアドレスをどのように管理するのですか？どのような形でどのようなデータ構造に格納するのですか？C/C++ で説明いただくと助かります
>＞リンクリストで、一度作成したノードのアドレスはずっと保存する
>って、どこにどういう形で保存するのです？
・リンクリスト全体のノードを辿ればいい場合には保存する必要が無い。
なお、その場合、1ノード右側のノードのアドレスを取得するのは1～2クロック
しかかからない。
・例えば、1000個のノードが入っている場合の、特定の 2 個のポインタを
保存したい場合には、グローバル変数の2つのポインタにそれぞれの
アドレスを代入しておけばよい。
それは丁度、ArrayList(vector)の場合であれば、添え字番号を2つの整数
変数に代入しておくのと全く同じこと。
・要は、ノードを識別するための数値が、配列では整数型の添え字番号であったところが、
リンクリストでは、ポインタ型のアドレスになるというだけのこと。
決して後者に置いては、通し番号を使ってはいけない。
数学的には、次のような双対関係の様なものが存在していると考えられる:
（配列, 添え字) <---> (リンクリスト, アドレス)
QZを含めて、この双対関係を理解できておらず、
（配列, 添え字) <---> (リンクリスト, 添え字)
と間違って理解してしまっている人が多いことから、リンクリストでのランダムアクセス
が O(N)などと謝った認識に至ってしまう人が多いと考えられる。
しかし、正しく双対関係を理解すれば、O(1)であることが理解できよう。
結論から申し上げれば、ここはプログラム板だから、適切なお題を設定してプログラムで例示いただけませんか？
＞リンクリストでのランダムアクセス が O(N)などと謝った認識
いいえ、リンクリストの各ノードのアドレスは、リンクリスト内で調達するのならば、O(N) でしか取得できないものですよ
あなたはリンクリスト以外の何か別のデータ構造を使ってリンクリストのアドレスを管理しようとしているようですが、
ならば、もうリンクリストなんか最初から止めちまえばいいのじゃないでしょうか？
あなたはやはり馬鹿だな。
それをいうなら、配列も同じ。
配列の添え字番号を覚えておくのに、別の配列が必要になる。
お分かりかな？
あなたは、双対を全く理解出来て無い。
それってリンクリストの意味ある？
なんのためにリンクリストにするんだ？
あらゆるデータ構造がランダムアクセス性を持つということになってしまうな
Qちゃんお疲れ
> あなたはリンクリスト以外の何か別のデータ構造を使って
> リンクリストのアドレスを管理しようとしているようですが、
> ならば、もうリンクリストなんか最初から止めちまえばいいのじゃないでしょうか？
それは色んな人がわりと最初のころから既にツッコミ済みなのだよ…
ようやく議論に追いついたねキミは
実際、C言語などから高級言語にポインタの概念が入ってからはそうなった。
ただ、Rustはそうなって無いから問題なんだよ。
ポインタの指す領域に1クロックでアクセスできるCPUなんてあるんですか？
ポインタの指す先がメモリにあるかキャッシュにあるかで異なりますがL1キャッシュにあっても数クロックかかるのではないかと思います
数クロックを争うような話をするなら実装がないと話にならないと思うので、まずは比較したい書く言語の実装を用意しましょうよ
既存のコードへのリンクで良いので
双対という言葉の意味が分からなくても、生まれつき頭のいい人なら、
俺の言っている意味がわかるはずだ。
キャッシュに載っていたらの話だ。
任意のアドレスへのアクセスは本質的にunsafeだと思うのですが、safe rustでそれができないことにどのような問題があるのですか
リンクリストは参照局所性が悪いのでキャッシュに載っていない確率が大きいのですが、本当に高速なのですか？
双対性にもいろいろありますよね…論理学上の双対命題（∩と∪、∀と∃の入れ替え）ならばその否定が証明できますが、そういう意味ですか？
それとも正十二面体と正二十面体の双対性ですか？
適当にペアにして双対と呼んでいるだけなのでは？
そうなんですね…
いや、突っ込みどころはそこではなくて、
「あるときは O(f) ランダウのオミクロンで話をしたかと思うと、次の瞬間、クロック数を問題にする」というバラバラな論理展開でしょう
ランダウでやるんだったら最後までランダウで統一してほしいのですが…
ランダウ記号は、大まかな分類しか示せない。例えば、
O(N)は、N→∞ の時に、
O(N)/N < α (alpha)
のように有る正の実数αによって、「抑えられる」という意味しか示せないし、
O(1) < α (alpha)
であることしか意味しない。
だから、O(1)であることよりも、1クロックであることの方がずっと意味が強い。
なので、ちゃんと1クロックであると分かっているなら1クロックと書いた方がいい。
ある数量に対応する空間的・時間的コストの依存状況を滔々と語っていたかと思うと、次の瞬間は実時間に関する話に都合のいいように鞍替えするのは論理的でない、といっているのです
実時間なら実時間、依存関係なら依存関係できっちり話をわけてほしいですね
悪いが、お前が馬鹿なだけだ。
数学的には、O(1)と書くこともあれば、実クロックで書くこともあり、
混ぜたらいけないなんてことは無い。
ちゃんと理解していれば、混ぜても問題ない。
「数学的」の定義を伺いたいものですが、それはさておき、実クロックなんて「おま環」な話をしても仕方がない場合も多いのですよ
今はキャッシュのヒット率で処理速度も大きく変わるから、実クロックによる考察なんてほとんど無意味です
しかしデータ数等の「ある数量」に対する時間的・空間的コストの評価ならば、それは、どの環境にもっていっても通用する、すなわち適用範囲が広いのです
何か評価をしたいのなら、広い環境で通用する評価方法の方が有用でしょう
あなたは、その二つの評価方法の意義の違い（「どちらが有意義か」）を知らないから「混ぜたらいけないなんてことはない」などとシレっといえるのですよ
そうじゃないんだ。実際のクロック数の事ではなくて、マシン語で書いたときに
1命令だということなんだ。
邪魔になる。
まず、それは横に置いておいて、基本を理解しないといけない。
キャッシュの影響についてはその次。
また、なら、最初から「1命令」と書いておけば良かったのに、という突っ込み
が予想されるが、1命令でも乗算命令なんかは13クロック(レイテンシ)以上かかるから
それとは区別するために1クロックと書いた。
キャッシュは複雑すぎて話が混乱するだけ。
ポインタを介してのアクセスが1～2クロックなのは、今のx86系だとアーキテクチャに
依存せず必ず言えることだから、そう書いた。
命令数なんてもっと当てにならないですよ、内部で別形態に変換され並列に実行されたりするわけで、人手で最適化することは不可能なしろもの
そんな制御できないものを評価対象にしてもしかたがないのでは？
＞ポインタを介してのアクセスが1～2クロックなのは、今のx86系だとアーキテクチャに
＞依存せず必ず言えることだから、そう書いた。
残念ですがキャッシュにヒットするかしないかで大きく実行時間は変わりますね、キャッシュにヒットせず、RAM 空間上から引っ張ってくる場合は数十クロックは必要でしょうね…
そんな「お前の環境でしか通用しない話だろう」的な曖昧な評価方法よりも、どの環境でも通用するランダウのO記号による評価の方が有意義でしょう
どちらの方が有効範囲が広い有意義な評価法なのかを知らないから、ちゃんぽんにして話をしても不自然さを感じないじゃないですか、あなたは？
そうでなくて、Rustでも、O(1)というものだけなら、作ろうと思えば作れるから
1クロックと書かざるを得なくなったんだよ。
Rustの場合は、O(1)でも、単なるポインタでは無く、配列を介すので、
乗算、足し算、境界チェックが入ってしまうのでトータルで20～50クロック
くらい掛かる。このうち、境界チェックだけは外せるかも知れないが。
>>489 を見ろ。
「なぜあなたは文脈を考えて書かないんだ」
と はちみつ餃子にも指摘されてただろ。
＞乗算、足し算、境界チェックが入ってしまう
C/C++ の配列とても乗算・足し算は入りますよ…
そんな瑣末な話とO(1), O(N) の話をちゃんぽんにしても不自然さを感じない感性に私は大いに疑問を感じます
よくご存知ですね…
まあ、今日は基本的なデータ構造を基本的な言語を使用して白紙からコーディングする機会を下さったあなたには感謝してますよ、久々に脳細胞を使ったのでちょっといい気分です
mov ebx,ptr
mov eax,[ebx]
ので済む。配列の場合は、
mov ebx,index ;添え字番号
mov eax,[ebp+ebx+32] ;32はスタックの中での位置
だから、配列とポインタで速度が変わらない。むしろこの例だとリンクリスト
の方が僅かに速いくらい。
Rustの場合、借用規則で禁止されてしまうため、以下のようになってしまう。
このスレである人が実装を示した独自Cursorをrustcでマシン語に直したものを
アセンブリ言語で書いた場合、次のように成る:
mov ebx,pseudo_ptr ;Cursorの中味はポインタの変わりに配列の番号になってしまう。
cmp ebx,配列要素数 ;safeモードの配列の境界チェック(これと次の命令はオプションで外せるかも)
jae 境界チェックエラーのラベル ;条件ジャンプ命令は遅くなる原因になりやすい。
imul ebx,要素のバイト数 ;13～35クロック位。CPUによってこの限りではない。
add ebx,配列の先頭アドレス ;Cursorの実装の内部で用いられていた配列の先頭アドレス
mov eax,[ebx] ;間接アドレッシングによって実際にアドレスebxにアクセスする。
これは、O(1)ではあるが、20～50クロック位かかり、先に示したCの場合とは
雲泥の差である。
Rust で insert, remove 操作を O(1) で実装可能かどうかが論点ですよね？
リストの要素数に関わらず insert, remove 操作を固定計算量で実行可能であればそれは O(1) です。
https://wandbox.org/permlink/AHWR4LIjkMCvWuZE
insert, remove 実装のコードだけここに貼ります。全てのコードは上記で確認願います。
--------------------------------
node *insert(node *target, int value) // ノードを target の直後へ挿入
{
node *n = new node;
n->value = value;
n->prev = target;
n->next = (target != nullptr) ? target->next : nullptr;
if (n->prev != nullptr) n->prev->next = n;
if (n->next != nullptr) n->next->prev = n;
if (head == nullptr) head = n;
if (tail == target) tail = n;
return n;
}
void remove(node *n) // 指定ノードを削除
{
if (n->next != nullptr) n->next->prev = n->prev;
if (n->prev != nullptr) n->prev->next = n->next;
delete n;
}
お前はアホか。
リンクリストの場合は、乗算が入らないんだよ。
>>493
ミス訂正:
配列の場合は、
mov ebx,index ;添え字番号
imul ebx,配列のバイト数
mov eax,[ebp+ebx+32] ;32はスタックの中での位置
従って、リンクリストの方が一般的にはアクセスが速い。
リンクリストは、1クロック位、配列の場合は、要素が一般のバイト数の場合は、
14～36クロック位。
>Rust で insert, remove 操作を O(1) で実装可能かどうかが論点ですよね？
そうじゃない。
Rustでも、insert, remove 自体は、標準実装でも O(1)で行える。
ところが、アクセスが、標準実装では、借用規則のために複数の
読み書きポインタを永続的に保持することが出来ないので、ノードの位置を
先頭からの通し番号で覚えておいて、アクセスするたびに毎回先頭から
辿る必要があるため、O(N)かかる。
特殊な独自実装をすると、アクセスがオーダー的にはO(1)で出来るが、
特殊実装な故に、>>493 の後半のようになってしまい、
20～50クロック位かかる。
読みました
私の場合は双方向リストを循環させ、始点のみをポイントすることとしましたが、結果として記述はあまり簡単にはならなかったですね、うーむ
疲れるだけだということが分かった。
疲れるだけだということが分かった。
疲れるだけだということが分かった。
https://wandbox.org/permlink/GlDCsezlcix3aJvi
>>496
なるほど。アクセス時に通し番号的な物が必要になるのであれば
insert, remove 操作時にもその通し番号を振り直す必要があるので、O(1) では実現できない気がします。
>>497
双方向リンクリストは始点と終了をペアで持つという固定観念があったので、その発想はなかったです。
>なるほど。アクセス時に通し番号的な物が必要になるのであれば
>insert, remove 操作時にもその通し番号を振り直す必要があるので、O(1) では実現できない気がします。
先頭や末尾では無い途中のinsert、removeであれば、あなたの言うとおり。
追加する直前のノードにたどり付くまでに一般的にはO(N)の時間が掛かる。
ただまあ、末尾追加や先頭追加と、末尾削除、先頭削除なら、RustでもO(1)で
出来るだろう。
なお、Cursorを使えば、よくあるケースだけは高速に行えるようになっているかも知れないが。
あくまでも良くあるケースだけは、unsafeを使って特別対応しているだけ。
複雑な一般的なケースでは、やはり、O(N)かかってしまう。
その意味で、あなたの言っていることは正しい。
こだわっているというか、あれは、オーダー的にはCと同じく、ほとんど全ての
動作をO(1)で出来てしまうリンクトリストをRustでも出来ているから、
注目に値する。
ただし、O(1)と言っても、実際には遅い。
また、Read After Delete、ダングリングポインタに相当するものがRustでも
生じる。たとえ、safeモードで書いても。
要素追加でバッファ超えると配列全体をコピーするけどO(1)なんだ？
いいのかそれで？
Rustはそれを売りにしてるからだよ。
C/C++は最初から諦めてる。
>>506
その指摘は正しい。
平均的にはO(1)だが、スパイク状に(不定期に)O(N)のコピー動作が入ってしまう。
私のやり方でよかったことは、prev/next の無矛盾性のチェックが簡単に書けることくらいでした、他は複雑になってしまった…
売りにしてるいうても結構厳しい制限だからデータ構造に直結するようなコードはsafeのみじゃ無茶だぞ
連結リストのようにユーザ側もダングリングとか多重参照とか気をつけなきゃいけないタイプのものは、
safeの範囲じゃ回りくどいことやるハメになるか、そもそも本当に無理になるかだ
>ところが、アクセスが、標準実装では、借用規則のために複数の
>読み書きポインタを永続的に保持することが出来ないので、ノードの位置を
>先頭からの通し番号で覚えておいて、アクセスするたびに毎回先頭から
>辿る必要があるため、O(N)かかる。
そうなんだ
でもこれってC/C++でもメモリ安全で、スレッドセーフとかにしたら同じにならん？
そうなると一度間違った考え(リンクドリストの任意の要素にO(1)でアクセスできる)を持ってもそれを間違った考えとは気づかずにその間違いを補強するようなチグハグな考え方をするようになる。
反ワクチンのようなトンデモ科学にはまっちゃう人に周囲の人がいくら正しい科学知識で説得しても自分の考えに疑問を持つどころか、自分の考えは絶対に正しい、周りのやつらは頭がおかしいと思いこんでしまう。
自分の考えが間違うこともあるのではないかと謙虚になることも重要だということだね。
今後はクロックという言葉を使うのはやめなさい
次にポインタで持てばリンクリストはO(1)も明らかにおかしい
例えばハッシュテーブルもバイナリツリーもO(1)になってしまう
Cの場合、リンクリストは経験的に言えば、簡単に扱えるので結構安全。
すっきり分かり易いので安全になる。動作が素直だし。
むしろ、途中削除、途中挿入した場合、配列の方が扱いが難しい。
リンクリストは他のノードのアドレスが変わらないのでポインタの値は
変化させなくて良いが、配列の場合は操作をしたノードより後ろに
有るノードの添え字番号がずれてしまうため、そのたびに
管理番号を付け替えるようなことが必要になってしまい、
データ構造が複雑な時に管理がとても大変になる。
リンクリストだとそのような手間が要らないので便利。
ただし、(配列, 添え字) <--> (リンクリスト, アドレス) の双対関係
は常に念頭に置いておく必要がある。後者は基本的には決して
添え字(通し番号)を使ってはいけない。なぜなら、それは後者においては、
ID値としては使えないから。
ただそもそも配列は、添え字はID値としては不十分というか、配列には絶対不変の
ID値が存在しない。リンクリストはアドレスが絶対不変のID値として使える。
まずは、
(配列, 添え字) <--> (リンクリスト, アドレス)
の双対関係を理解しよう。
これが理解出来て無い人は、リンクリストの本来の性能も、本来の使い方も
出来ない。
俺は頑張って勉強したから数学が得意だったのではない。
テキトーにやってただけで、出来た。
[補足]
要は、「配列の世界」と「リンクリストの世界」では、世界自体が別物なので、
要素/ノードを識別する手段も違い、前者は添え字番号、後者はアドレスが基本量となる。
従って、リンクリストでは、ノードを識別するには、必ずアドレスを使うことが基本。
それが最も自然であり、高速であるから。
いつまでも、添え字番号で識別する方法しか理解できない人には、言っている意味が理解できない
だろう。
電気と磁気にもさまざまな双対関係がある。世界がある種の対称になっているから、
その際に、正確に対応する量を入れ替えてやら無ければならない。リンクリストでは
通し番号ではなくアドレスを使う。
そうしないと公平ではない。
双対の定義は、独自に決めてよい。
はあ？
ハッシュテーブルは、実質的にO(1)にとても近い速度で検索できるから
使われているんだが。
それは嘘だと誰でもわかる
リンクリストの個別要素のアドレスに対応するものは配列の個別要素のアドレスでありハッシュマップの個別要素のアドレスである
そしてアドレスを持てばO(1)とトンデモを言い出すならば全てのデータ構造がO(1)となる
つまりリンクリストのO(1)は嘘
>Cの場合、リンクリストは経験的に言えば、簡単に扱えるので結構安全。
>すっきり分かり易いので安全になる。動作が素直だし。
そんなに簡単だとかいうなら、試しに実装を見せてほし・・・
お前が生徒だったら0点つけてやる。
そもそも、動的配列は要素数が内部容量を超える時にアドレスが時々変わって
しまうから、ID番号として基本的にアドレスは使えない。
それをすると、末尾追加するだけでも、定期的にID番号が変わってしまうので
その際にID番号として使っているアドレスを全部修正しないといけなくなるから。
しかし、アプリ内のID番号を全部修正するのは、効率免で良くない。
だから、配列だと要素の一番ましなID番号は添え字番号。
一方、リンクリストで最も効率の良いID番号は、アドレス。
しかも、リンクリストの場合、任意の場所への挿入、任意のノードの削除を
行っても、他のノードのアドレスは変わらないので、アドレスをID番号
として用いている限り、どんな操作をしてもID番号の修正が不要となる。
こんなによいID番号はないわけで、敢えて添え字番号をID番号に使うのは
不適切。
Cの入門書で、リンクリストについて書いてあるもの読んで理解して、
頭が悪くなければ、そう自然に解釈できる。
根本的に馬鹿な人には無理かも。
Cでは生ポインタ一個に対して、Rustは参照関連だけでも、20種類は下らないほど
色々な複雑な仕組みがあるのは、全て safe のためであるのに、safeでなくなったら
それこそCの圧勝になるが。
コーディングはゲロのようにめんどくさくなるが、
速度面では別にCにそう負けるもんではない
多分最適化しきれなくてほんのちょっと遅くなる部分はありそうだが
それは、実はリンクリストも十分に局所性が有る。
というのは、追加するときには、リンクリスト全体のごく一部にバースト的に
挿入することが多いからだ。
そしてその時、ノードのアドレスは等間隔に並ぶ傾向が有るから。
いや、今回の例では劇的に遅くなるケースがあるといってるんだ。
今回の例が何のことか把握してないが（QZが絡んでいるレスは読みづらすぎる）、
配列がどうたらとかの話なら別に配列なんていらんよ
＞まとめ
＞・C/C++で記述できることは同じ安全度合いで常にRustでも記述できる
＞・そのうちほとんどのケースではRustだとメモリ安全性を保証する形で記述できる
＞・つまり言語としてC/C++よりもRustの方が優れている
デタラメを何度も書くな。
もし反論があるならしてみたら？
shared XOR mutableルールぶち破れるから、
C/C++でできることはコーディングめんどくさくなるし安全性が結構悲しいことになるけど（でもCとかと同程度）
Rustでも不可能ってことはない
なんならCコードをRustコードに自動変換するやつすらあったような
成熟度は知らんが
全て書いてるのに理解力が無いから理解できないだけ。
Rust信者は馬鹿ばかり。
>Rustはそれを売りにしてるからだよ。
>C/C++は最初から諦めてる。
自分で C/C++ は安全じゃないから、って書いてるじゃん
それが結論でしょ
同じ安全性にしたら、同じになるだろ
同じ安全性にする必要がない。
リンクドリストとは別に配列を用意してリンクドリストの要素へのアドレスを保持するからリンクドリストの任意の要素にはO(1)でアクセスできる
と主張しているが
そのリンクドリストに追加または削除するたびに配列の要素も追加か削除しないといけなくなる。
リンクドリストの任意の位置に追加/削除するのはO(1)だけど、配列の任意の位置に要素を追加/削除するのはO(1)じゃない。
だからリンクドリストと配列を組み合わせて使うとリンクドリストのメリット(任意の位置への追加/削除がO(1))が無くなってしまう。
その配列に静的配列を使うならリンクドリストの最大サイズを予想してあらかじめ大きな配列を用意しないといけない。
動的配列を使うな要素を追加したときにときどきヒープの再確保がおきる。
実際のメモリレイアウトがどうなるかは言語処理系のランタイムやlibcに依存すると思うのですが
例えばどの言語のどの処理系のどのランタイムを使使えばそうなることが確認されているのですか
配列 + リンクリストの代わりに、リンクリスト + リンクリストにすれば解決するぞ。
malloc()の仕組みから言ってそう考えられる。
Rustはもっと単純
生ポインタを使えばC言語と全く同じ状態となる
fn main() {
let mut a: i32 = 123;
let raw_pointer = &mut a as *mut i32; // aの生ポインタを得る (unsafe不要)
let b = &a; // bがaの参照を借用
// a = 456; // これは借用ルールによりコンパイルエラーとなり書き換えできない
unsafe { *raw_pointer = 456; } // 生ポインタを使えば自由自在に書き換え可能
assert_eq!(a, 456); // 借用ルールを逸脱して書き換わっている
assert_eq!(*b, 456); // 借用している参照bから見ても当然書き換わっている
}
じゃあUnsafeCellなどはいつ使うの？と思うだろうけど
それはRustで安全な型を提供するための部品として用いる
例えばRefCellやOnceCellなどの安全な型は部品としてUnsafeCellを用いている
最初の初期化時に（あまりフラグメンテーションが発生していない状態で）複数要素追加する以外に追加がほとんど発生しないっていう前提ならそうかもね
でも一般にそうじゃないから連結リスト使うんじゃないの？
参照局所性高めたいなら個々の要素ごとにmallocするのではなくarena的に割り当てすべきなのでは
>>543の言うとおり、フラグメンテーション発生してると何も保証できなくなる
C/C++で記述できることは同じ安全度合いで常にRustでも記述できる
したがって以下の合意事項は正しい
＞まとめ
＞・C/C++で記述できることは同じ安全度合いで常にRustでも記述できる
＞・そのうちほとんどのケースではRustだとメモリ安全性を保証する形で記述できる
＞・つまり言語としてC/C++よりもRustの方が優れている
発生するから、キャッシュが大規模に乱れてしまうがな。
その点、リンクリストは乱れたとしてもそこまででは無い。
unsafe付けたら全体の安全性も失われるが。
メモリーの間違いには局所性がなくて原因箇所が分かりにくいからこそ、
Rustはメモリー安全に固執しているんだが。
逆にCはそもそもそれをユニットテストなどで徐々にテストしながら開発を進める
ことで確保する方針を採っている。
必ずしもペナルティーが増えるわけでは無いぞ。
例えば、2つの大幅にアドレスが異なるノードを交互にアクセスする程度では
キャッシュの読み込み直しは通常の連続アドレスにアクセスした場合に比べて
特に追加発生はしない。
キャッシュメモリ1種類の連続メモリブロックしか収められないわけでは無いからな。
限界はあるが、いくつかのメモリブロックなら同時に収めることが出来るからな。
逆にキャッシュ制御せずにmemcpy()みたいなもので大きなメモリーをコピーした
場合、キャッシュが全フラッシュしてしまう可能性も有る。
動的配列の場合はそこに注意が必要。
図を書いておこう。2つのメモリー領域A, B があったとして、
リンクリストが
AAAAAAAAAAA
の状態の途中にノードを5つ追加して、
AAAAABBBBBAAAAAA
のようになっていてもそれほどキャッシュミスは起きない。
さらに、もし、
AABCBBACDBBAABBDBCCC
みたいになっている程度でも、そんなにキャッシュミスは起きない。
なぜなら、A,B,C,D の4箇所くらいならキャッシュにどれも収まるから。
それはウソ
Rustは標準ライブラリの内部に至るところに多数のunsafeがあるのは事実だが
それにより全体の安全性に影響を与えることはない形でのみ提供している
まずunsafeの使用方法は大きく2つに分けられる
(1)影響が局所的に限定される場合
(2)影響が大域的に起き得る場合
つまりunsafeを用いたRustの様々な型やその操作インタフェース等は(1)が満たされている
つまりそれらを利用するプログラムには内部がどう実装されていようと影響をもたらさない
したがってRustのプログラム自体がコンパイラによって安全性を保証することが可能となっている
あとVecに対するLinkedListの優位性の話されても誰もそんなことは問題にしてないぞ？
それはそうかもしれないが、リンクリストの場合、ノードの識別に
アドレスを使うのが、双対原理によって標準なので、その標準手法を
Rustで使おうとすると、unsafeをアプリ本体で使う必要が出てくる。
つまり、ライブラリの中にunsafeを閉じ込めることが不可能。
これは間違いないはずで譲れない。
ほとんどのケースではLinkedListよりもVecを用いた方が有利
だから使用する言語に関わらず特殊なケースを除けばリンクリストではなくベクターが使われている
それが間違いなんだって。
そんな思想だから、ChromeではHTMLもtextareaへの文字列の末尾追加ですら遅いんだな。
計算量が理解出来て無い。
VisualStudioも異常に遅いし。
それに比べて日本人の作るVzEditor, WzEditor は速い。
それはなぜかというと、LinkedListも使っているから。
https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
insert/removeはO(1)なlistの方が速そうなものなのに要素サイズが小さいと10万要素でもvecの方が速いんだね
Push Front を見たら圧倒的に list が速い。
それにC++のライブラリの list はへたくそな実装になっている。
deque無視しないでよ
先頭への追加削除が高速なvectorだよ
クラフをログスケールにするとわかるけどlistより速い
を使ってる。
ベンチマークは、ベンチマークを作る人が正しく理解してなければ、正しい
テストプログラムを書けないから、正しい結果が出ない。
CPUのベンチマークも実際の体感速度に比例しているとは限らないのと同様。
何度も言ってるように、listは、双対原理から言って、添え字番号ではなく
アドレスを用いなければ成らないことをベンチマークプログラムを作ってる
人が理解出来て無いから、遅く出てることが多い。
https://baptiste-wicht.com/posts/2017/05/cpp-containers-benchmark-vector-list-deque-plf-colony.html
>>563
あなたのワークロードではそうなんですね、なるほど
ついにGoogleとMicrosoftを批判しだしたのか
>>561
C++擁護派なのにC++のライブラリまで批判しだしたのか
君が間違っているとは考えないのね？
要素サイズが128バイトや4096バイトの時には、listの方がvectorより速い。
それに、NonTrivialの時こそ list が効率がいいはずなのに結果が逆になって
いたり、listは、安定なはずなのに、trivial 128 で list のグラフが
途中で直線になってないこともおかしい。
listは、どんなときでも速度が変化しにくい性質があるはず。
何かそのテストはおかしい。
俺はCと言っていたが。
C++のSTLには設計に問題が有ると行っているぞ、昔から。
実際に一般的なケースでは、vectorとlistでは、listの方が速いことが多い。
ほとんどの用途でベクターが速い
だからほとんどのケースではリンクリストではなくベクターが使われている
数理に弱いアメリカ人。
だから、VisualStudioも激オソなんだな。
アメリカ人の作るものは何でもでかくて速度が遅い。
車もでかくて燃費が悪い。
NonTrivialはMovableな要素だから追加削除時には要素あたりポインタ数個分のデータがコピーされるだけで小サイズと同じ特性になるのは不思議ではないのでは
listについては要素サイズの変化に対して他のコンテナよりも安定的に見えるけど
さすがに要素のコピー分のコストはかかるから要素サイズ変わっても全く同じという訳ではないけど
今までネットのこういう変な結果のベンチマークを見てきたが、
ソースを見てみると変なことをしてることが多かった。
多かったというより、結果がおかしいと思って調べてみたら全て変なことしてた。
秀才以外が行ったベンチマークは信用できない。
まだ、雑誌は信用できることが多いが、ネットのベンチマークはおかしい。
少なくともこのスレでやることではない
https://github.com/wichtounet/articles/blob/master/src/vector_list_update_1/bench.cpp
こっちはボランティアに馬鹿に説明してやってるだけなんだから。
ソースを出せ、と言ってくるのは抽象的理解が出来ないから。
とても簡単なことを言ってるだけなのに、少しでも抽象的(symbolic)
な言葉で語ると全然理解できない。
数学とは抽象性(symbolic)な学問であるから、数学が出来ない人は
コードを示さないと理解できないらしい。
CだろうがRustだろうが実装可能って話にしか見えん
これな。
結局のところ実体へのポインタの配列であればリンクトリストになってなくても話は同じなんじゃないかな。
それで実体にはすべて到達できるもんｗ
ある実体の次も、前も、それも両方分かるしｗ
違う。
リンクトリスト + 配列だと >>538 が指摘している現象が生じてしまうが、
リンクトリスト + リンクリスト だと生じない。
こういっても、数学力の無い人は理解できないだろうな。
数学力は数学という学問だけの能力ではなくて、脳内のワーキングエリアや
イマジネーションなどに関係しているから、生まれつきの影響が大きい。
[補足]
抽象的理解が難しい人に具体的に書いておいてやろう。
LinkedList ll;
ArrayList al; //自動伸張方式の動的配列だと仮定する
al[0] = ll.append("りんご");
al[1] = ll.append("みかん");
al[2] = ll.append("バナナ");
だと >>538 が指摘しているような不具合が起きる。しかし、
LinkedList ll;
LinkedList ll2;
ll2.append( ll.append("りんご") );
ll2.append( ll.append("みかん") );
ll2.append( ll.append("バナナ") );
だと起きない。
中身が同じリストを二個用意しても意味がないのでもう少し実践的な例の方が理解のためにはよろしいのでは
スキップリストみたいな構造とは違うのですか？
もっと具体的に書いてやろう。
リンクリストの中の追加した6つの果物の内、4つを他の配列やリンクリストの
中から参照する例を示しておこう。
これの応用としてリンクリスト内の1000個の品物の内、何らかの条件で選び取った10個を
別の配列やリンクリストから参照することが出来る。
1. リンクリスト + 配列
LinkedList ll;
ArrayList al; //自動伸張方式の動的配列だと仮定する
al[0] = ll.append("りんご");
ll.append("みかん");
al[1] = ll.append("バナナ");
ll.append("すいか");
al[2] = ll.append("パイナップル");
al[3] = ll.append("ブドウ");
2. リンクリスト + リンクリスト
LinkedList ll;
LinkedList ll2;
ll2.append( ll.append("りんご") );
ll.append("みかん");
ll2.append( ll.append("バナナ") );
ll.append("すいか");
ll2.append( ll.append("パイナップル") );
ll2.append( ll.append("ブドウ") );
>>585 を見ろ。
これがどういう時に起きるかといえば、最初に1000個の品物の入った
リンクリスト ll がある時、条件に合う品物を1つ探してリンクリスト ll2
の末尾に参照を追加する。
それを10回繰り返した後に、実質的に生じる。
queryに対する抽出結果をリストとして保持しておいて元のリストの更新に応じてquery結果も適宜更新されるイメージですか？
正確にはll2のサイズN_ll2の半分に近づくね。
ll2のサイズが大きくなるなら、大きめに初期化するのが無難。スカスカならバランス木のmapかね。
様々な分類が生じるうち今回関係するノードの参照については以下の4種類あるようだ
(A) データを挿入しても作られたノード自体は返さない方式
実際にこの仕様でも困らない用途も多いようでこの方式も普通に使われている
もちろん問題は何も生じない
(B) データを挿入して作られたノードのポインタを直接返す方式
これは危険で最も推奨されない方式
ポインタを握っていても使う時にそのノードは削除されているかもしれない
削除で開放されてヒープに戻され更に再利用されているとデータの中身もnext辿りも滅茶苦茶になりうる
そしてデータの扱い次第で実際に削除は起き得るしUI人間や通信相手から発動ルーチンでの削除も有り得る
(C) データを挿入して作られたノードの(一般的な)スマートポインタを返す方式
これはshared_ptrなど安全とされているスマートポインタを返すためメモリ使用上は安全
しかしポインタ先がヒープへ戻されていないことしか保証がない
つまり(B)と同様にリンクリスト自体からの削除が起きている可能性がありそれを知る方法がない
(D) データを挿入して作られたノードを管理しているリンクリスト内部の何らかを返す方式
リスクの高い(B)や(C)と異なりこの方式は安全かつ整合性が維持される
もしノードがリンクリストから削除されていればそれに対して対応ができる
この返されたデータを用いて新たなデータをその位置に挿入する時に元ノードが削除されていた場合
(D)-1. 挿入はされず既に元ノードが削除されていると知らせる
(D)-2. 知らせずに削除された元ノードの次に有効なノードの位置に挿入する
などリンクリストの仕様や用意されたメソッドにより異なるようだ
以上まとめると現実的に安全に使える方式は(A)もしくは(D)となっている
例えばC++の標準リンクリストstd::listでもこの(D)方式を採用しており
insert()はリンクリスト上をその位置から順に辿っていくイテレータを返す
Rustでも作れると思うんですけど
Unsafe全振りにはなると思うけど
rustだけはsafeじゃないとだめらしいですよ
それだとさあ
最初から主張してるO(1)ランダムアクセスできないけどいいのｗ
配列だからこそi番目が定数時間でa[i]でアクセスできるんでしょ
やはりポインタを直接返さないんだな
ポインタだけもらって保持していてもそのノードがリンクリスト上でアクティブかどうかすらわからないもんな
Debug ビルドだと二重 erase は検出してくれるけど、Release ビルドだとセグフォで落ちる。
リンクリストの先頭挿入か最後挿入かあるいは何らかのデータ順になっていてその位置に挿入だよな
可能性があるのはエディターくらいだけどそれならばカレントポジションをエディター用リンクリストの中で保持した方が便利
ポインタの代わりにインデックス使ってればそのままシリアライズできるけど
途中への挿入・削除が頻繁に発生するようなら std::list の使用も検討するべき。
ノードが既に分かっているとして、当該ノードの保持する値へのアクセスが O(1) で
行えるのは当たり前の話で、これが出来ないコンテナって存在するのか？
リンクリストは（既に分かっている）ノードの削除、
（既に分かっているノードの前後への）挿入が O(1) で行えることに意味がある。
C でも rust でもいいから動くソースを出してもらえませんか？ここ、確かプログラム板でしょ？
多くのケースではシリアライザ手書きしないから気にならないのでは
例えばrustならserdeがLinkedList対応してるからVecと同じ手軽さでシリアライズ・デシリアライズできると思われる
その中の切れ端へのポインタをもらってどうするの？って話だから話がずれてる
リンクリストはポインタだからO(1)で速い！とナゾ主張する勘違い君がさらに暴走した結果
普通にVec相当の構造に変換された上でシリアライズされてデシリアライズ時にlistに変換されるよ
それ怪しいな
LinkedList型はser/de定義されていて先頭保持してるところから順にたどって全体を巡るとして
途中ノードのポインタを渡されてもまずそのノードだけ対象になるのかそれとも次をたどるのか曖昧
もし同じように順にたどるとしてもLinkedListの一部分が出来上がりそれに意味があるのか疑問
CursorではなくてLinkedListのシリアライズに対応してるから必ずリストの先頭からのシリアライズ
>>608
なぜ？
safeを売りにするという言葉をどのように解釈しているの？
ダングリングポインタは諸悪の根源と言える。
ll2にllの検索条件に合うノードのポインタを順に入れて言った場合、
llのノードが順序がバラバラで入っていることになり、
ll2を先頭から順にシーケンシャルアクセスすると
llはランダムアクセスされることになる。
なお、ランダムアクセスとはシーケンシャルアクセス以外のアクセスを全て指す
言葉。
もちろん、O(1)だ。
> ll2にllの検索条件に合うノードのポインタを順に入れて言った場合
なぜポインタを辿って遅くて不便なリンクリストを使うの？
順に入れるならベクタを使えば速くてメモリも食わないのに
そこをベクタにしてしまうと、せっかくのリンクリストの特性であるところの
O(1)性が完全な意味では維持できなくなるからだよ。
配列は、ちょっとしたことで使うには良いが、
一見得してるようだが、複雑なことをやる場合には損することが多い。
リンクリストはランダムアクセスO(n)で遅いから特殊な用途でしか使われていない
ほとんどのケースではランダムアクセスO(1)のベクタが使われている
シーケンシャルアクセスだけならどちらも同じだけどポインタをたどるリンクリストは遅くてメモリも余分に使って結果不利
アホは黙っててくれないかな。
俺は数学100点マンなんだぞ。
お前は完全に間違ってる。
そうでないと、まともな議論にならない。
IQ130以上限定。
今までの論争？についてどうですか？
細かくは読んで無いけど
限定がなければ当然同じ計算オーダーの構造は作れるはず
いずれもリソースを限定しなければチューリング完全な言語であるわけだから
あとは限定次第
特定のコンテナを使う場合とか安全性とか
各言語での流儀とか
2文目は取り消しでお願い
>限定がなければ当然同じ計算オーダーの構造は作れるはず
>いずれもリソースを限定しなければチューリング完全な言語であるわけだから
確かに同じ計算オーダーの構造は作れるが、制限を回避するためにかなり遅くなる。
例として、参照もポインタも無いBASIC言語で、配列だけを使ってポインタを
模倣することも可能ではあり、実際にポインタと同じような計算オーダーを
持つものをそれでも実現可能ではあるが、「速度係数」が大きくなる。
Rustの場合、safeモードでは、1つのリンクリストに対して、読み書きが出来る
参照を複数同時にはマシン語レベルの生アドレスとしては持つことが出来ない。
その制約を回避するため、別の配列をわざわざよういして、アドレスの代わりに
配列の添え字番号を持つ整数型を参照型の代替として用いるやり方が、
提示されていた。
Rustでも生ポインタを使えば制約は一切ない
ソースコード>>542
さらにリンクリストで生ポインタを返すのは危険なので一般的にもっと安全な形が取られている
リンクリスト分類まとめ>>592
あなたは、秀才じゃないでしょ。
分かるから。
言ってること的外してるし。
C言語だろうとC++だろうと排他機構が必要になって、実行時コストを払わずに行うことは不可能
C++は、プログラマが自分の頭で考えて、安全性を確保する思想だから、
あなたの言ってるコストは元々必要ないという思想。
聞いたことないが誰の言葉？
[補足]
なお、マルチスレッドにおける、排他制御はCやC++では必ず必要。
それはプログラマが頭で考えても省略できない。
なお、シングルスレッドにおける Rustの借用規則のような仕組みを
に「排他制御」という言葉は通常は使わない。
あなたも秀才じゃないでしょ。
書いてあることで分かる。
なぜC++で説明しないのかといえば、std::listは、std::vectorなどの
他のコンテナと同じ使い勝手にするために、リンクトリスト本来の
アルゴリズムとは異なって実装されてしまっている可能性があるから。
シングルスレッド内のマルチタスク(いわゆるグリーンスレッド)でも競合は起きます
例えばポインタを得た後にファイルや通信の読み書きを行えばシングルスレッド内の別タスクに切り替わります
その別タスクが人間UIから指示でリンクリストの一部削除も起き得ます
元のタスクに切り替わった時に保持してるポインタの先は既に削除されて存在しないかもしれません
したがってシングルスレッドでも競合対策は必要です
そもそも Chromeが根本的にバグったりダウンした経験が無いので
そういわれても分からない。
でもそのことを通常、「排他機構」とは言わないハズ。
独自定義の言葉は混乱するので使うべきでない。
クレジットカードやパスワードが既に。
ではそのシングルスレッドでの競合状況>>636を避けるための排他的な制御をあなたは何と呼ぶのですか？
言葉は知らない。
ただし、MicrosoftのWinFormsやMFC、Win32だと、メッセージキューを
上手く使うことができていて、1つのメッセージ(イベント)を処理中は、他のメッセージを
受け付けないようにする仕組みになっているので、自分のアプリのイベントハンドラに
二重に入ってくることがない。だから、あなたの言っているような状況は絶対に起きないように
なっているため、心配要らないし、それを一般プログラマがコードで避けることも
通常は必要ない。
JSだとメッセージキューを上手く操れないためにイベントが二重に入ってくる
ことを一般プログラマが手作業で避ける必要がある場合が出てくるが。
JSは、二重にイベントが呼び出されることがあるから必要になるだけ。
マイクロソフトのMFCやWinFormsではそもそも起きない。
[補足]
正しくは「JS」ではなくて、ブラウザ上でJSで使ったイベント処理の話。
onclick="func()" みたいに書くやり方のこと。
イベントキューは有ることはあるが、一般プログラマが細かく制御できない。
Win32やMFCでは細かく制御できる。
Microsoftは全く使うことがないので知らないのですがそんなダメ仕様なの？
さすがに通信I/O待ちになったら別タスクに切り替わると思いますよ
少なくとも他のまともなシステムならば別タスクへと切り替わります
ずっと通信I/Oを待ち続けるのは明らかに時間の無駄ですから
は？何言ってんの？
プロセス対プロセスでも競合が発生するなら排他制御すると表現するのに
「タスク」って言うのが、他のアプリのプロセスやスレッドに切り替わるというの
なら、その通りだが、自分のアプリのイベント中に、自分のアプリの別にイベントが
発生するのはプログラムが複雑になるので、MicrosoftのGUIではわざと避けられて
いる。でも、そのおかげでGUIプログラムが簡単に書けるようになっている。
そんな効率の悪いお子様向けメニューがあるのですね
あなたはそんな効率悪いダメ環境でしかプログラミングしたことないのですか？
ドローツールで、メニューからファイル保存ハンドラを起動して、
ファイル保存処理中に、マウスをクリックして、マウスイベントを起動して、
データを変更する必要は無いよね。
だから、マイクロソフトのMFCやWinFormsでは、最初から、メニューハンドラを
実行中は、マウスイベントが起動しないように設計されている。
同様に、あらゆるイベントは、必ず1つずつ順番に実行される設計になっている。
それだとウェブブラウザすら実装できませんね
そういうお子様向けメニューがあると勉強になりました
ありがとう
二重にイベントが呼び出されるとはどういう現象を指しているのでしょうか
またJSはシングルスレッドなのでデータ競合は発生しないと思うのですが
そもそもなぜ突然JSの話が出てきたのですか
シグナルハンドラとイベントハンドラを混同していませんか
JSは、ファイルI/Oを非同期でやりたがる人が居て、例えば、
Unixの write() は、書き終わるまでその場で停止して、書き終わってから
次の行から実行が再開される。
ところが、JSの場合は、書いている間に、イベントキューの読み取りに戻って
別のイベントが起動される可能性が生まれる。
だから、メニューからファイル保存を選んで、write() 文に相当する関数を
呼び出すと、まだ保存が終了して無いのに、別のメニューをもう一回起動
できるようなアホな状況が生まれる可能性が出てくる。
それはJS限定の場合ではなく
まともなシングルスレッド並列プログラミングならどれも同じで他へ切り替わります
通信I/Oで止まってしまい他へ切り替わらない方がおかしい
あなたは、テキストエディタで保存中に、別の処理をしてしまう人？
そんなことではなくて
そのMS仕様？ではウェブブラウザを作れませんよね
そりゃノンブロッキングなAPIを使ったらそうなるでしょ
処理が先に進んで困るならブロッキングなAPIを使うかawaitなりすれば良いのでは
なにを問題に感じているのかがわかりません
いや、作れる。
>>636のようなデタラメを書く人が居たからだ。
グリーンスレッドの話にMFCやWinFormsの描画スレッドの話を持ち出すのはなんの反論にもなってないと思うのですが...
そもそも >>628 のいう排他は rust の aliasing xor mutability の意味での排他なので論点がすれてます
通信やI/O待ちしたままシングルスレッド内で他へ切り替わらないと主張しているのですからウェブブラウザを実装するのは無理でしょ
JavaScriptを含むまともなシステムのように通信やI/O待ちの時はシングルスレッド内の他のタスクへ切り替わるのが普通であってそれだと実装できます
の構造を理解しなくては。基本は、MFCとWinForms。
あなたは、ゲームで、それぞれのキャラクターが同時に動いて見えるのは、
非同期に動いていると思ってる人？
マイクロソフトには興味ないのでどうでもいいです
シングルスレッドである限りは通信やI/O待ちで他へ切り替わらずに全体が止まってしまってはどうしようもありません
通信やI/O待ちになるところで他のタスクへ切り替わるのが普通のシステムです
伝統的な理解では、その場合の、タスクというのは、JSのasyncのタスクの事
ではなくて、別のアプリの「プロセス」のことである事は分かってる？
JSのような意味でのタスクだと切り替えた瞬間にアプリがおかしくなってしまう。
だから、あなた自身が分かっているような「排他処理」が必要だと考えに至る。
ところが、MSが採用している標準的なGUIシステムでは、最初からそうならない
ようになっているから、その心配が無い。
いいえ
ここでタスクと呼んでいるのはそのJSだけでなくRustでも同じで
シングルOSスレッドの中でも複数が動くタスクのことであって
別名グリーンスレッドと呼ばれる並行プログラミングでの単位のことです
シングルスレッド内のタスクの中でI/Oや通信待ちとなる時は他のタスクへスケジューラーが切り替えます
別タスクへ切り替えないとI/Oや通信待ちのままプログラムが動かなくなるからです
その仕組みはどれくらい採用されているの。
世界標準は、マイクロソフトの MFCとWinFormsなんだが、それはそんな
仕組みは採用して無いぞ。
マイクロソフトには興味がないので知りませんが並行プログラミングの常識ですよ
少なくともウェブブラウザで動くJavaScriptは通信I/O待ちで止まったままにはなりませんね
その間も例えば人間が操作すると反応するように他のタスクが並行して動いています
JavaScriptはスクリプト言語だし、ブラウザのセキュリティー的にもあえてそう設計されているから、
C++やRustのようなコンパイル言語とは比較出来ないのでは？
Rustでも普通にasync-stdやtokioを用いてシングルスレッドでマルチタスクの普通のプログラムを組むと全く同じですよ
もちろん通信やI/O待ちになると別のタスクへ切り替わります
結局の所、Rustって基本は非同期で、プログラマが await-std や tokio を使って
明示的に非同期プログラミングするってことですよね。
それだったら C++ や Windows の WinForms/WPF アプリでも非同期プログラミングのフレームワークを使えば同じ事。
あなたのこれまでの投稿内容を見て、JavaScript では全てが勝手に非同期で動くと私は受け取りました。
つまりWindowsのシングルスレッドのプログラミングでも通信I/O待ちになると他のタスクへ切り替わるわけですね
そうすると元々の話
シングルスレッド内でもマルチタスクならば競合を避けるために何らかの排他的な制御が必要、と合意できますよね
そしてその排他的な制御が無ければ他のタスクにより書き換えや削除も起き得るということがわかっていただけましたでしょうか？
リンクリストか否かに関わらず全てのデータ構造で。
>つまりWindowsのシングルスレッドのプログラミングでも通信I/O待ちになると他のタスクへ切り替わるわけですね
Win32の場合、ファイルI/Oは、通常は同期式だが、特殊な場合には非同期に
することも出来ることは出来る。
しかし、その場合、プログラミングが難しくなるので上級者向きで、
初心者はやるべきではない。
その場合、もちろん、何らかのフラグで危険な状態になるのを防ぐ必要がある。
このスレで初心者用のお子様向けメニューの話をしても仕方ないでしょ
現在プログラミング界ではasync/awaitが普通となっている現状で非同期プログラミングは当たり前のことなので
プログラムが難しくなるから同期だけ使う、というケースだけを前提に考えては駄目ですよ
>現在プログラミング界ではasync/awaitが普通となっている現状で非同期プログラミングは当たり前のことなので
JS業界では耳にするが、C++業界では耳にしないな。
と思ってる人も、「非同期I/Oを使わなければ成らない」と思い込んでる人が
多いのかもね。
実際は、非同期I/Oは高度なので避けることが賢明と考えられている。
同期I/Oでもほとんどの場合は十分に機能を果たし、十分に高速なプログラムになる。
イバラの道を避けることで安全なプログラムが簡単に書けるようになる。
async/awaitはJavaScriptだけだと思い込んでるの？？
PythonからC#まで幅広くサポートされている
もちろんRustもね
>>675
非同期が難しいって、初心者なのにこのスレにいるの？
あとawaitは同期するので初心者でも使うよ
JSがある程度以上高度なプログラミングができないのは、非同期を使おうと
する人が多いからも有るかも。しかも、それを推奨したりする人が多くて。
簡単な方法で十分なのに、敢えてロジックがこんがらがる方法を使う必要は無い。
昔から言われていることとして、初心者ほど、マルチスレッドや、高度な
メッセージ通信、Mutexやセマフォなどの同期処理に興味を持ちやすい、
ということがある。
そして、上級者ほど、ほとんどの目的ではそれらを使わなくても
十分に良いプログラミングできることを知っている。
初心者ほど独特の複雑な記法を好み、一行で何もかも書こうとし、
関数に分けずにラムダ式で書こうとする。
上級者ほど、単純で平易な書き方をしようとし、複雑な記法や難しい
仕組みは避ける。
あなたが全く理解できていないから
このスレに無関係なJavaScriptをデタラメに叩いている
メジャーな言語の多くでasync/awaitや類するものが導入されている
時代遅れのC++ですらC++20で半分だけ導入するらしいぜ
同期プログラミングしか出来ない初心者だと判明したことが大きいな
全く理解出来て無いわけではなくて、Promise や then() や await も
使ったことは有ることはあって、色々テストしてみたが、理解が難しい部分が
残るなとは思った。
で、俺は馬鹿だと思うかも知れないが、これでも数学100点連続マンだったからね。
少なくともそれ位は数学が出来たのに、Promiseが易しい概念だとは思わない。
e.responseWith()や、e.waitUntil()も未だにちゃんと理解出来てる自信が無い。
async関数をthenの中に入れているような場合も、ちゃんとは理解出来て無い。
CやC++には、基本的にそのようなタイプの非同期システムは無いからね。
＞上級者ほど、ほとんどの目的ではそれらを使わなくても
＞十分に良いプログラミングできることを知っている。
金子氏も Windows を信用せず自前で並行処理を記述していたというし、しかし本当なのでしょうか？誰か解析してください…
std::future
Promise(言語によってはFuture)が難しいって数学も苦手なんだな
Promiseは単なる先物であって内部はpending/ok/error(言語によって名称など異なる)の状態を持つだけ
async関数はPromiseを返すだけだしawaitはpendingじゃなくなるのを待つだけ
thenの引数はokとなったら呼ばれるだけ
一方でresponseWithやwaitUntilは上述のような言語の基本構成ではなく
ブラウザのWeb APIに過ぎないからそこをまず区別できないと
関数の最後に○○をreturnするとPromiseでラップされるとか、qiitaなどでは
見つけられたんだが、公式サイトで見つけられなかった。
それと実際色々実験して見ると、単にコールバック関数を登録していると
すれば予想される順序とは異なった順序でconsole.log()文が呼び出されて
いたりした。
その順序はとても独特だった。
また、Proimseを解説する記事において、Aを解決するBなどという言葉が
多用されていたが、その定義を見つけられなかった。
推定は出来るが。しかし、定義が無いと分かりにくい。
公式を見なさい
RustではPromiseはFuture traitでゼロコスト設計
https://doc.rust-lang.org/std/future/trait.Future.html
Futureはpoll()を持ち呼ばれると以下の2状態いずれかを返す
・Poll::Pending
・Poll::Ready(val) 【Rustではエラー状態はなくResult<正常値,エラー値>で返す】
https://doc.rust-lang.org/std/keyword.async.html
asyncはFutureを返す
JavaScriptがそんなに好きならこちら
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Promise
Promiseは以下の3状態を持つ
・pending
・fulfilled 【正常値が得られた時】
・rejected 【エラー値が得られた時】
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/async_function
asyncはPromiseを返す
このように概念は全く同じ
ただしJavaScriptはPromise作れば自動的にスケジューラーに登録されてタスク切り替え実行されるが
Rustはゼロコスト設計だからFuture作ったら自分で好みのスケジューラーに登録してタスク切り替え実行される
もし非同期プログラミングが不得意ならば数学も不得意だろう
というか、Promiseは自分では使いたくないから興味が沸かないし、
実験する時間も取りたくないのに、サンプルなどでは大量に使われてる
場合が多いからもある。
意味が無いものには興味が沸かないというか。
超不得意になるだろうな。
意味無いから
O(1)やリンクリストの話は、イマジネーションの世界だから生まれつきの
頭の良さの影響が大きい。
Promiseを知らないことを馬鹿にされても、俺の意見が間違っていることには成らない。
博士課程などにも馬鹿が多いからかもな。
どうみても生まれつきの頭は大したことが無いのに、大学に残ってるような
人が多い分野。
それで馬鹿なのに勘違いして、明らかに間違ったことをいつまでも信じ続ける
人が居る。
さらに悪いのは間違ったことを流布してしまう。
c++ の future とかコルーチンってその辺どうなんですか？
複数のクライアントから同時接続されるサーバだとあるクライアントと通信している間に別のクライアントからの要求を処理しないと効率悪いだろうし。
ネットからファイルを一つダウンロードして解凍して中のファイルを読み込むだけのプログラムだったら前の処理が終わらないと何もできないから同期処理で十分。
知るか知らないかではなく
理解できるか理解できないかの違い
もし非同期プログラミングが出来ないならば数学も弱いとわかる
>>693
後者の初心者向けプログラミングだけしか理解できずに終わるか
それとも前者の普通のプログラミングもできるようになるかの違い
需要が無いのに知っていることを自慢するって、真空管技術を知っていて
偉いと思ってるのと同じようなことだと思うが。
通信の場合、マルチスレッドプログラミングなら意味はあることもあるな。
しかし、単一スレッドで非同期にすることにどれだけ意味があることか。
需要があるから使われているし
さらに利便性を高めるためにどの言語もasync/await導入したり導入検討している
>>696
例えば1000か所から通信でデータを取ってくる場合
(1)順番に同期的に一つずつ順に1000回処理するの？
(2)マルチスレッド1000個生成するの？
(3)普通はシングルスレッドかCPUスレッド数(2個とか4個とか8個とか)分までのマルチスレッドにてスレッド内マルチタスクをして実行します
このようにマルチスレッドでも各スレッド内では複数のタスクが非同期に多数動きます
使用用途は、通信に限られるような気がするな。
余り一般化して欲しくない。
面倒だから。
それになんかわかりにくい。
このネット時代では通信しないアプリの方が例外的な特殊な存在
そして通信だけでなくヒューマンインタフェースも非同期に発生
その『それになんかわかりにくい。』から数学が苦手だと予想します
GUIなアプリは非同期プログラミングが避けられないと思うぞ
でないと、何か処理するごとにユーザーに待たせることになる
シングルスレッドでも工夫次第で待たせなくは出来るが、かえって実装が複雑になってしまう
ブラウザ上で動いているJavaScriptはシングルスレッドですが
スレッド内で非同期に複数のタスクが動くのでGUIに対応出来ています
例えばマウスが動いたりクリックされたりするたびに次々と新たなスレッドが起動したら重すぎて困ります
プロセス起動よりは軽いとはいえスレッド起動はかなりのコストがかかります
だからマルチスレッドではなくシングルスレッドで動いています
このようにシングルスレッド内で並行プログラミングできるところが非同期プログラミングの良いところです
今どきサーバーは数万のクライアント接続が同時に来ても捌けますが
これを数万のスレッド起動で実装したらリソースが足りず動きません
実際にサーバーが使用するスレッド数は最大でも使用CPUが同時実行できるスレッド数で8個とか16個などだけです
したがってそのスレッド各々が何千や何万のクライアントを相手に並行して非同期に処理しています
Wixdowsアプリ(イベントドリブン)はイベントのキャッチはシングルスレッドでやっているのでイベントの実行から終了は全て同期処理。
ただし、イベントの実処理(中身)は非同期で実行する(しているケースが多い)からイベントの実処理が終わらずとも次のイベントが実行されているってことなんじゃない？
イベントドリブンの認識間違ってたらごめんね
同期プログラムと同じ書き方で非同期になるよ
同期プログラムと同じ書き方といっても局所的な表面上だけだからgoroutine間のやり取りや制御で理解できなくなると思われる
そして同期プログラムと同じ書き方という点ならばasync/awaitサポートする任意の言語でawaitを付ければ同期的にプログラミングできるわけだけどこれも彼には厳しいかも
そんな...
数学100点なのに比較的学習が容易とされているgoも使えないなんて悲しすぎる
非同期やデータ構造に対する理解を求めるのが酷だったか
イベントではなく、シングルスレッドでメッセージキューに溜まったメッセージを
1つづつ取りだして処理するので、1つのメッセージ処理実行中、同時に別のメッ
セージ処理が実行されることはないので、排他処理が要らない。
ところが、メッセージ処理の中で受信待ちとか発生するコードだと、タイムアウト等で
抜けるまでメッセージ処理が終了しないので、ウィンドウ再描画などのメッセージも
処理されず、見かけ上GUIが固まったようになる。
だから、通信とかは、マルチスレッド化する必要がある。 C/C++はOSが走ってない
ワンチップマイコンのソフト開発にも使われるので、言語仕様にスレッドを持ち込む
必要はないと思う。
auto = automaticだろ
名前負けしてんじゃねーよ
クソ言語か
仕様で明確に定義されている以上、そんなアホな勘違いするやつが悪い。
さすがにこの理解はないわ
もうちょっと勉強したほうがいいぞ
合っとるよ
そのへんはC10K問題などで知見が広まりプロセスやスレッドを増やすのではダメだと結論出ている
それ以降はスレッドの中で非同期にどれだけ多数のタスクをこなすかが勝負となった
C++のauto
本来の仕様は一緒のはずなのに使われ方が違ってて笑う
そんな事で笑ってたらC/C++を覚えるまでに笑いすぎて死ぬぞ
>>583 アクセス用にArrayListを使う例
この辺↑の話題のやつを実装してみた
Rc<RefCell>をまず共有しておいて、中身へのborrow()や
borrow_mut()は最小限の時間で行えば十分じゃないかな？ ダメ？
実行時にうまく中身を借用できているかは使う人次第ってことになる
https://ideone.com/bd0cFx
・注意：双方向リストだけど循環参照は未解決のまま
・注意：要素への参照を使っての操作はリスト側には未反映
（front, backを正しく再設定し直したりはしないということ）
（両端の要素の外側に追加したときとかおかしくなるはず）
・手元の1.8.0で主に動作チェック
・基本的によく分かってないので妙な箇所があるはず
・イテレータを提供したかったがよく分からなかったので諦めた
・fmt::Debug for LinkedList<T>は本来はもっとスッキリ書けるはず
・push_prev(&self, h)などが何も返さないのは、selfを返すかhを返すか
どっちを返すのが自然なのかという判断に迷って決め切れなかったため
クライアントの話なのにC10K持ち出して
しかも無知晒しただけやんw
5chのページとか見ると多数の広告やら何やら大量にコネクション貼りに行くけど非同期で並行にシングルスレッドでも余裕で可能
これが同期プログラミングしかできない人が作ると数十のコネクションに数十のスレッドを無駄に使うか
もしくはシングルスレッドで1つずつ順に時間をかけるかのどちらかとなる
今時のブラウザは非同期処理の塊だろうからもっと良い例あるのでは
そんな中でもAjaxでイベントによる非同期処理は要求されたし
ブラウザjsに関して言えばマルチスレッドのオーバーヘッドに耐えられず必要に駆られてっていう理由ではなく
従来のイベント非同期をPromiseで簡便に書けて、async/awaitでもっと簡便に書けて喜ばれた、というのが正しい理由でしょうね
それブラウザがマルチプロセス・マルチスレッドで仕事をこなしてるからGUIアプリとして使いものになるんだぞ
まさかJavaScriptだけで実現できてると思ってたのか？
https://ideone.com/IY3aFj
・イテレータを提供
・impl Debug for LinkedListも若干スッキリ
リスト構造ってほとんど使わんなぁ。 C++だとインスタンスの配列じゃなくて、
インスタンスへのポインタ配列を使えば、配列サイズの拡張に伴う領域確保とコピー
が行われるのは、配列要素であるポインタだけなので、要素数が増えようが、複雑な
オブジェクトだろうが、処理時間は最小限で済む。
リスト構造の欠点はソートに弱いこと。 オブジェクトインスタンスへのポインタ配列
ならソートの場合でも、ソート対象はポインタの並び替えだけで、ポインタが指す
オブジェクトのインスタンスには一切触らない(コピーや再配置は行わない)で済む。
「100日後に退職する47歳」に出てくる「クイックソートの計算量」なんて質問をする
面接官は、記憶力が全ての学力試験が産んだ馬鹿でしかない。 現実問題としては、
ソートする必要がある時はソートしなければならない。 聞くべきは『効率的にソート
するには、どんなデータ構造を採用すべきか』である。
GUIスレッドの裏で動く、通信専用のワーカスレッドを1つ作成して、順番に1000個
のサーバヘアクセスに行くのが簡単かつ現実的じゃないかな。
むろんコア数を調べてワーカスレッド数の上限を可変にしてもいいが、アクセス先
リストの消し込みやエラー処理とか自動リトライとか面倒になるし、そこらを頑張っ
たところで、実際のところほとんどの場合は回線速度で頭打ちになる。
それと、たとえスレッドが1000個作れても、実際の環境では、経由するルータや
相手サーバ側の制限などで、同じIPアドレスから、同時に1000個の通信セッション
が張れないことの方が多い。
配列だとポインタの読み込み2回、書き換え2回で済むのに対し
単方向リンクリストだと読み込みmax(n, m)+4回、書き換え4回必要になるからこれだけでかなりの差が生じる
配列と違って、リスト構造を構成する各要素は、メモリ空間上に隣接して配置されて
いないのでqsort()ではソートできない。 あと、リスト内に循環参照がないとしても、
リストをバラす際にコストが掛かる。
まあメモリが安く大容量になりましたからね…
QZちーす
リストのソートにはコムソートが容易に適用できたと記憶しています、ほぼO(NlogN)
https://mevius.5ch.net/test/read.cgi/tech/1434079972/107
前者はその通り
後者は違ってJavaScriptだけでもGUIアプリは普通に作れる
例えばNode.jsでQtベースの物は軽くて便利
> 通信専用のワーカスレッドを1つ作成して、
> 順番に1000個のサーバヘアクセスに行くのが簡単かつ現実的じゃないかな。
それは昔の同期プログラミングのマズいやり方でとてつもなく遅くなってしまう
> 経由するルータや相手サーバ側の制限などで、
> 同じIPアドレスから、同時に1000個の通信セッションが張れないことの方が多い。
経由する普通のルータにそんな制限はないです
1000ヶ所へ取りに行くという話だから相手サーバー側には各々1つのコネクションしか貼られないため
通信セッションが張れないということもありません
> そこらを頑張ったところで、実際のところほとんどの場合は回線速度で頭打ちになる。
たった1000個でそんなことは起きません
数KBの1000倍は数MBですから
それって、Qtライブラリ(JavaScriptではなく、CやC++で書かれている)が、マルチ
スレッド機能を持ってるだけでは？
そりゃC++だから軽いわな
でもってシングルスレッドかマルチスレッドかの話には基本的に関係ないわな
JSのシングルスレット非同期モデルで対応できるのは
I/O待ち等でCPUがidleになる場合か
ホスト環境が提供する別のプロセスやスレッドに処理をオフローディングできる場合だけ
デスクトップアプリでそこそこ重いSQLiteへの読み書きなんかをJS実行スレッドでやれば非同期だろうがGUIに顕著な影響がでる
だからJS使ってても当然マルチスレッド化する
> それは昔の同期プログラミングのマズいやり方でとてつもなく遅くなってしまう
実際、書いたことある？ Webサイトの複数ページを移動しながらスクレイピング
して、ダウンロードファイルのURLを取得し、HTTPまたはHTTPSでファイルを順次
自動ダウンロードする自分専用ソフトを書いて使ってるけど、ダウンロード中に
GUIのプログレスバーや転送量/速度などの更新や、キャンセルボタン等の関係から、
GUIスレッドと通信スレッドに分けてるけど、速度はほぼ回線速度と相手サーバーの
応答に依存だよ。
> 経由する普通のルータにそんな制限はないです
> 1000ヶ所へ取りに行くという話だから相手サーバー側には各々1つのコネクション
> しか貼られないため通信セッションが張れないということもありません
確かに1000個のファイル取得先が別々なら、相手サーバーのコネクションは1つだけ
でセッション数も制限を受けないけど、2000を超えると安物や古いルーターだとNAT
テーブルの制限に引っ掛かる気がする。
> たった1000個でそんなことは起きません
> 数KBの1000倍は数MBですから
そんな制約あったっけ？
ちなみに自分が書いたアプリでダウンロードしているファイルは、小さいもので数百KB
大きいと＋数MBくらいで、1000個(総容量約3.5～3.7GB)ダウンロードすると2時間～
3時間くらいかな。
回線はSoftbank Air(非5G)で、今の時間帯だとGoogleのSpeedtestで、ダウンロードが
20Mbpsくらい。
分割パート毎にマルチセッションで同時ダウンロードして連結する方法もあるが、
ダウンロード先が同じサーバーで、アクセス遮断されないようにというのもあって
1セッションでのダウンロードにしてる。
本当はロボットであることを覚られないよう、ファイル単位のダウンロード完了後に
ランダムな秒数の待ち時間をいれるべきだろうが、今のところやってない。
> 20Mbpsくらい。
ということは、毎秒2MBくらいのダウンロード能力があり、1分あたりでは120MB、1時間あたり7GBくらいはダウンロードできるということになる
> 1000個(総容量約3.5～3.7GB)ダウンロードすると2時間～
> 3時間くらいかな。
めちゃくちゃ遅くね？
専売特許じゃない、むしろ後発でC10k、promise、async/awaitだとかいってるアホは市んでほしい…
C/C++では現状コールバック関数でしかない。もちろんC++22とか出てきてないものは除く
callback hell をなんとかするために生まれてきた promise や async/await にはそれはそれで価値を認めるべき
時間帯によって速度は変わる。 MicrosoftからWindows 10のISOファイルを1つ
(ほぼ容量同じ)をWebブラウザで落としても、30分強で終わるどころか、ほぼ同じ
くらい掛かる。
いや、それってMSのサーバ能力で律速されてるってことでしょ
そもそも
>> 通信専用のワーカスレッドを1つ作成して、
>> 順番に1000個のサーバヘアクセスに行くのが簡単かつ現実的じゃないかな。
>
> それは昔の同期プログラミングのマズいやり方でとてつもなく遅くなってしまう
に対する反論を試みようとしてるんだから、相手側の能力で律速するのなら「じゃやっぱマズいやり方だよね」ってことになるだろ
同期関数という普通の関数と、見た目上は同様に見えるように考えられただけで価値なんてほんの少ししかない。
むしろこのキーワードの導入によりコードの汚染が酷く、さらに言うならI/Oバウンドや*nix割り込みベースや
そしてCPUバウンドな非同期（≒スレッド）と統一的に扱えないために複雑なフレームワークを導入する羽目になる。
一般的には、I/Oバウンドなブロック単位のI/O読み書き待ちでコールバックされることだけを主眼に置いて設計されて
しまったがために多くの言語で採用されているが、スレッドや軽量ルーチェンとは互換性ない場合が多い。
ただ副次的にコールバック関数のネストが解決されているように見えるだけに過ぎない。
無線にすると、10～20
無線スポットから離れると、1まで落ちる
これは、OS のプロセス・スレッドじゃないから。
Erlang 内の小プロセスだから出来る
非同期プログラミングの話をしているだけなのにそんなasync/awaitに限定するのがおかしいのではないかね
さらにいえばasync/awaitの話とpromise/futureの話を同類に捉えているからちゃんと理解していないのでは？
非同期関数をなにか特殊なもののように捉えているのも怪しい
非同期ブログラミングとは同期ブロッキングI/Oによる非効率で無駄な方法を排除するプログラミングであって
昔も今も中心部分にselectやepoll等のシステムコールを核とするループすなわち高度化した時のスケジューラーで成り立っている
そして読み書き可能になったら読み書きをするという極めて自然なプログラミング
もちろんこのスケジューラー部分で割り込みやタイマー含めて共通管理できるため「相性が悪く複雑になる」というのも間違いだ
もちろん読み書き可能になったら教えて！と最初に登録するところから始まるわけだから
読み書き可能になったぜ！と教えてもらう部分がコールバックとなるのは当然の話
だからそれをまとめて包んだ非同期関数は当然コールバックとなりI/O待ちブロックされる同期関数より極めて効率が良い
promise/futureはこの部分のインターフェース部分だけを抽象化しただけに過ぎず
この中身は単なる状態管理だから具体的なI/Oやタイマー等と関係なく共通して使える点もプログラミングの利便性を向上させている
そしてこれ自体はコールバックを無くしているわけではなく例えばクロージャを渡すメソッドなどを用意することでコードの見た目を改善している
これで非同期関数のインタフェースとして(直接)コールバック系と(間接に行う)promise/future系((およびその両対応))に分かれた
以上ここまでの話は生のC言語でも普通にプログラミング可能な話である (メソッド呼び出しを除く)
もちろんスレッドなんか存在しない環境でもシングルスレッドにて並行に動作するの非同期プログラミング
当然ながらマルチスレッドでも同じように動作させられる
一方でasync/awaitは全く別の話
これだけはプログラミング言語による支援がないと実現できない
そしてこの導入目的は同期プログラミングしか出来ない人たち向けも含めて楽に非同期プログラミングするためであり
asyncと宣言した関数などの中ではawaitを付ければ見かけ上は同期プログラミングと同じ記述ができる！という改革
これによりようやく真にコールバックが利用側からは消えたので「コールバックを無くすため」というのも間違ってはいない
ではasync/await導入で非同期関数側はどう変わったか？
実は全く変わっていない、が正解
そのままpromise/futureを返す非同期関数と全く同じそのままである
つまりasync/awaitは非同期関数を利用する側だけの話という点が重要
以上で>>751氏も非同期プログラミングを正しく理解できるであろうか？
掃き溜め
「真にコールバックが利用側からは消えた」なんてコールバック関数が消えたことはない。お前はHello worldでも
書いて満足してろｗawaitの話とpromiseを同列に語ってんのもお前、「インターフェース部分だけを抽象化」なんて
RustにもC++にも無いしC#おじさん臭さが露骨に出てる
そんなのはC#のような一部であり、多くのasyncを有する言語ではスレッド境界は越えられないのでそれぞれの
スレッドがイベントループとイベントキューを有する。これはAスレッドで起こったイベントはBスレッドには
伝わらず”同じように動作させられる”なんてことは無い、実行の順序制御も当然バラバラ
C++20でもコルーチェンたるco_return, co_await, co_yieldがあるのに、鬼の首を取ったようにRustなどの
触りだけ触れていて優位性を語ってるアホはまじ市んでほしい
Windowsは伝統的に非同期をほとんど使わないことを知らない人が多いらしい。
もともとrustスレで暴れてた人を隔離するために立てられたスレだから最初から掃きだめ
＞＞当然ながらマルチスレッドでも同じように動作させられる
＞そんなのはC#のような一部であり、
＞多くのasyncを有する言語ではスレッド境界は越えられない
え？？
Rustでは当然出来ますけど
＞スレッド境界は越えられないので
＞それぞれのスレッドがイベントループとイベントキューを有する。
え？？
Rustではスレッド境界を超えつつ、それぞれのスレッドがイベントループとイベントキューを有することも出来ますけど
＞これはAスレッドで起こったイベントはBスレッドには伝わらず
そこだけは正しいですｗ
しかし暇になったスレッドがいわゆるワークスティーリングすなわち他スレッドからタスクを奪ってからイベント登録しますから、
＞”同じように動作させられる”なんてことは無い
同じように別スレッドで動作を継続できます
＞実行の順序制御も当然バラバラ
え？？
非同期だからバラしたタスク間の実行順序は例えば通信相手次第で変わりますけど
それは単純なワンタスク同期なマルチスレッドの時も同じです
実行の順序制御が必要な部分のみ制御の意味での同期を行うのも同じです
例えば10個のタスクで並行して10ヵ所からデータを取得してその平均を出すならば平均を出す直前で10個全てのタスクの完了を待つだけです
非同期プログラミングしたことがない人は間違った思い込み妄想だらけで大変
I/O全般というより、XHRやfetchやsocketのように遅いネットワーク通信を複数同時に待つ時に使う
時に便利な気がする。
nativeのファイルI/Oの場合、処理が完了するまで待つ方が便利だし、余計なことを考えなくて済むので
バグが少なくできるから、伝統的に同期方式を使うことが基本。
と書いた場合に、print文は端末(terminal)などの別プロセスでの処理が
完了するまで待つことが多く、実行完了するには時間が掛かるが、
これを一々非同期にして、print 文が完了するまでに別の処理をする、
というようなことはすべきじゃない。
一番いいのは、print 文が完了するまではそこで待機して、ちゃんと
それが完了してから次の文を実行すること。
つまり、同期的処理。
え？？
awaitはその待機という同期的処理をするためにあります
したがって非同期のprint関数を呼んでも問題は起きずにその書かれてる通りになります
でもそのコード部分では見て無い場所で、イベントループに戻ってしまって、
別のイベントハンドラが起動してしまう可能性が生まれ、
せっかく通常のシングルスレッドプログラミングでは起きない良い特徴が失われる。
そのため、シングルスレッドなのに排他処理が必要となってしまう。
排他処理は間違うととても危険であって、プログラミングのかなり上級者でも
気を使う必要がある。
「同期の関数を呼んだ場合」
→関数から戻って来るまでそのスレッドはブロックされる
「非同期の関数を呼んでawaitする場合」
→そのスレッドがブロックされることはなく他にタスクがあれば並行して実行される
>>771
いいえ
その場合はそのタイミングで並行して実行されたら困るタスクを持たなければいいだけです
○ その時は他に並行して実行されるタスクを持たない
○ 並行して実行されてもよいタスクだけを他に持つ
○ 並行して実行されるタスクの動作に制限がかかるようにロック等を持つ
✕ 並行して実行されたら困るタスクを対策なしに他に持つ
選択肢はたくさんあります
これがプログラミングです
Win32/MFC/WinForms/JavaのSwing/Android/ブラウザのJSで
プログラミングしたこと有る？
イベントループやイベントって自分で定義するものでは無いから
「タスクを持たないようにする」
っていうのは現実には不可能だぞ。
もちろんRustでも自分でスケジューラを自作することは滅多になく
selectやpollなど使用のイベントループを自分で書くことはありません
それからここでのイベントとは当然selectやpollなどのイベントですから具体的にはファイルディスクリプタの読み書きOK等がイベントとなります
もちろんこの処理はスケジューラが担当するので自分で書かなくてもいいです
しかし新たなタスクを起こすかどうかはスレッドの時と同様にプログラマーの自由であり必要なら明示的に行います
JavaScriptの場合もイベントループを管轄するスケジューラはブラウザでもNode.jsでもシステムとして持っているため関知しなくてもよいです
ただしJavaScriptでは非同期関数を呼ぶこと自体が自動的にここでいう新たなタスクを起こすことになります
あとは例えばブラウザ自体が暗黙的に動作しているタスクとしてみなすことも出来てそのタスクから新たなタスクを発火することもあります
リスナー登録するタイプの利用時もそのパターンです
MFC/WinForms/JavaのSwing/Androidなどでは、マウスイベントやキーボードイベント、
メニューイベントは基本的に常時イネーブル状態になったままにして使うので、await
してしまうと、それぞれのハンドラに普通に入ってしまう。
そうなるとロジックが破綻するので排他処理するか、awaitする直前に、
一々ハンドラを disable にして、awaitの次の行に来た時に enableにする
必要がある。そんなメンドクサイことすべきじゃ無いし、そもそもdisable
にするなら、非同期のメリットも無い。
そもそもGUIスレッドは、イベントハンドラの二重起動は禁止すべきとされている。
プログラミング分野は無数にある中で
なぜそんな特殊な環境だけを唐突に持ち出すのかも含めて分かりません
先ずは適用可能な分野から始めて経験と知識を積んで的確に判断できるようになってから結論づければよいかと
自分の触ったことのある範囲でいいから弁解しなくちゃ
もうリンクトリストなんてどうでもいい、無知の印象を払拭するのが第一
>>738 のリストのソートのご感想とか
数学や物理のテストは、B4 の白紙一枚をわたされて、これに回答とか証明を書け、みたいな感じですが、そんなテストで一度でも 100 点をとれるのなら、それはそれですごいとは思いますよ
引き合いに出してたのがセンター試験だったり東大入試だったりで大学入試の成績を誇るしかない人なんだなって思っていました
という論理は成立しましたか？
回答用紙の返却のない試験の結果がどうしてわかるのか疑問ですよね
隔離スレ立てたやつグッジョブ！
あわしろ氏が言ってたけど、Win32ではメッセージループを自分で作るらしいですよ。
まあ、配送はDispatchMessage()でやってもらうんですが。
マジレスすると
点数はわかる
Java の awt では、どこにメッセージループが隠れているのか、あわしろ氏に訊いていただけませんか？
私の時代には、そういうのは転部転科でもしようとしない限りわからなかったかと、今は変わったんですね…
了解です。
来週、職場で会うと思うので、聞いておきます。
そう
当の数学の天才は一度も何の試験かにすら言及していない
高校の定期試験ということもあり得る
師が職場におられるとはうらやましいですね
私はしませんが、仮に「自分は数学の天才である」と名乗りたいときに、どういう風に自分の天才性を形容するべきか、はいい演習課題になりますね
あまりマニアックなことをいってもスルーされるだけですし
他には
東大後期模試300点
数学偏差値90
東大数学科卒
など
普通は
論文数/論文引用数/肩書き(教授など)/受賞歴/特許出願数
などが実績ですが
私はその辺の実績はありません
アカデミックな感じで。
なんか生々しいんじゃないですか？もっとサラっとした感じでお願いします…
円の体積・表面積を算出したアルキメデスでしょう、ニュートンライプニッツの2000年ほど前の人
鋭い視点ですね
オーダーの話と実時間の話をシレっと往ったり還ったりするところなんかは、私には変だと思いましたね、アルゴリズムの評価はオーダーで行うのが普通で他はほとんどみない…
>>799
× 円
○ 球
>>799 の人は1000年以上も登場する時代を間違えた人だから、その孤独感たるや想像を絶するでしょうね…
歴史的に有名な超天才を比べる変なスレ
板的にはチューリングが出てこないのは変
アゲ。
>オーダーの話と実時間の話をシレっと往ったり還ったりするところなんかは、私には変だと思いましたね、
>アルゴリズムの評価はオーダーで行うのが普通で他はほとんどみない…
書くのが長くなるからオーダーで書いているだけで、オーダーだけでは正しい特徴を捉えられない
場合がある。
例えば、同じオーダーでも乗算や条件分岐の両方が使われているアルゴリズムとマシン語の
1クロックの命令1個にコンパイルされるものでは全然違う。
また、N個のデータを持っているハッシュ構造は、1回の検索は、数学的に厳密にはO(N)
だが、実験的(実際的)にはO(1)のように振舞うと言われており、厳密に扱うには、
オーダーの記号だけでは表現しきれない。
もし、オーダーだけで評価すればいいのなら、チューリング完全なあらゆる言語は、
同じアルゴリズムを使うことは可能で、同じオーダーの時間で計算できてしまうから、
速度比較には役立たない。
＞1回の検索は、数学的に厳密にはO(N)だが、実験的(実際的)にはO(1)のように振舞う
ハッシュテーブルの構築は O(N) ですが、既存のデータをハッシュで引く割合が多ければ多いほど O(1) に近くなるでしょう
ハッシュテーブルには衝突がつき物ですが、そういうところも厳密に評価するのは難しいかもしれませんね
ただし、
＞同じオーダーでも乗算や条件分岐の両方が使われているアルゴリズムとマシン語の
＞1クロックの命令1個にコンパイルされるものでは全然違う。
そのとおりですが、それは所詮 O(f) の f の係数が違うだけでしょう、というか、そういうものはケースバイケースで一般論には載せ難いかと
そもそもあなたは、Σクロック（命令種）、で近似的に評価しようとしてますが、その姿勢は評価しますが、CPU 内の RISC 変換と並列実行、投機実行等までは及んでおらず、ある意味これも粗粗の近似だと思います
CPU 種類やメモリ構成などによって大きく変わるのですから、オーダーでの評価にとどめておくのが妥当なのでは？
＞もし、オーダーだけで評価すればいいのなら、チューリング完全なあらゆる言語は、
＞同じアルゴリズムを使うことは可能で、同じオーダーの時間で計算できてしまうから、
＞速度比較には役立たない。
そりゃそうです、言語間の速度比較にオーダーを使う方が間違っています
総じて評価センスの問題かと
高卒の私は、いくら考えても意味がわかりませんでした…
>＞1回の検索は、数学的に厳密にはO(N)だが、実験的(実際的)にはO(1)のように振舞う
>ハッシュテーブルの構築は O(N) ですが、既存のデータをハッシュで引く割合が多ければ多いほど O(1) に近くなるでしょう
あなたは、>>813で
「また、N個のデータを持っているハッシュ構造は、1回の検索は、数学的に厳密にはO(N)
だが、実験的(実際的)にはO(1)のように振舞うと言われており、厳密に扱うには、
オーダーの記号だけでは表現しきれない。」
と書いてあることの意味が全く分かって無い。
秀才以上で無いと発言禁止だ。
ハッシュ構造は、「一回の検索」でも、数学的には、O(N)の時間が掛かる。
ハッシュ構造へのデータの書き込みとは全く関係無い。
検索自体が、数学的にはO(N)なのだ。
しかし、実際問題は、Nが常識の範囲内の大きさではO(1)のように振舞うことが
分かっているので、とても高速。
数学的には、O(f(N))とは、Nを無限に大きくしても、処理時間をf(N)で割るとある
上限値未満であるという意味。ハッシュテーブルの検索は、Nを無限に大きくすると、
定数的ではないので、O(1)ではない。
なお、g(N)=O(f(N))のように書いた時の意味で定義されているが、左辺は関数で、
右辺は集合のようなもので、両辺が等しいという意味ではない。なので、記法として
O(1)=O(N)であるが、O(N)=O(1)ではない。
不定積分の等号も集合論的な意味であって、等しいという意味ではないと聞いたことが
あると思うが、それと同じような定義。
[さらに補足]
なお、そもそも、等号 = の左辺に O(xxx)の記号は書くべきではないという説もある。
＞しかし、実際問題は、Nが常識の範囲内の大きさではO(1)のように振舞うことが分かっているので
それには理由があるのでしょう？その理由はなんですか？「振舞うことがわかっている」という観測事実のみが根拠とは到底考えられませんね
>>814 が間違っているのであれば、あなたの解釈はなんですか？
＞数学的には、O(f(N))とは、Nを無限に大きくしても、処理時間をf(N)で割るとある
＞上限値未満であるという意味。ハッシュテーブルの検索は、Nを無限に大きくすると、
＞定数的ではないので、O(1)ではない。
そりゃ、衝突が頻繁に発生するようになると、それを連鎖法で処理するか、あるいはオープンハッシュ法＆セカンドハッシュ関数で処理するか、
いずれにしても N がハッシュテーブルサイズに比して大きくなりすぎるとO(1)から程遠くなるでしょう
しかし、今はハッシュテーブルサイズが N に比してそんなに大きくないことが前提だと思っていましたが、そういうハッシュテーブルの重要な性質を無視して N→∞にいきなり振るとか、やはり実装経験が不足しているとしか考えられません
あなたには、オープンハッシュ法でも連鎖法でもいいから、一度実装してみることをお勧めします、そうすれば、そんな無茶な話をふったり出来ないはずです
×今はハッシュテーブルサイズが N に比してそんなに大きくないことが前提だ
○今は N がハッシュテーブルサイズに比してそんなに大きくないことが前提だ
あなたは馬鹿すぎて議論が成立しない。
勉強しろ、とも言えない。
なぜなら、勉強しても無駄だと思うから。
話が噛み合いませんね、やっぱり私が馬鹿だからなんでしょうかね…
でも、仮にも計算機科学方面から解析を行っていただくのでしたら、C でいいから例示してほしいですよね
>>824
生まれてきてすみません…
バケット数は、2 の累乗の次に現れる素数。
2^n + a, 2 <= n <= 30
8 + 3 = 11
16 + 3 = 19
32 + 5 = 37
64 + 3 = 67
128 + 3 = 131
256 + 27 = 283
512 + 9 = 521
データ数が、バケット数の5倍を超えると、ハッシュが再構成される。
再構成時には、極端に遅くなる
11 * 5 = 55 だから、データ数が56 個になると、バケット数が19 になる。
19 * 5 = 95 だから、データ数が96 個になると、バケット数が37 になる
バケット数は、2 の累乗で大きくなっていくから、
大きいほど、線形(全)探索に比べて、ハッシュが有利
増え方が、N に比例しなくて、log N に比例するから
例えば、2^20 = 百万で、2^21 = 2百万では、
線形探索では毎回、百万回増えるけど、
ハッシュでは、1回だけ再構築して、その後は、21回で見つかる
Rustのハッシュそうなんだ？
> ハッシュ構造は、「一回の検索」でも、数学的には、O(N)の時間が掛かる。
ホントですか？
>>826がO(logN)ですよ
O(N)の定義は、Nを無限に大きくしていった時に、処理時間を N で割った時に
ある固定された上限値の定数未満になる、という意味だぞ。
O(log N)のハッシュは有り得ない。
本来のハッシュ構造は振り分けられる量は固定サイズ。
だから、ハッシュ値の計算も固定されたアルゴリズムで処理が固定された関数で
行う。
色々と勝手に定義を変えてはいかん。
言葉を勝手に再定義すれば議論になるわけ無い。
データ構造スレでやれ
アゲ。
修正
>増え方が、N に比例しなくて、log N に比例するから
>例えば、2^20 = 百万で、2^21 = 2百万では、
>線形探索では毎回、百万回増えるけど、
>ハッシュでは、1回だけ再構築して、その後は、21回で見つかる
これはデータベースで使う、2分探索の事だった。
ハッシュは、バケット数で割った余りで決まるから、O(1)だった
ハッシュの表の様なものが固定サイズであるところの
素朴なハッシュの検索は、Nが大きい時には、O(N)。N が小さい時には、O(1)。
Nが大きくなるに従ってその表を時々大きくしていくようなものは、
考慮の対象にはしない。
[補足]
以下、ハッシュの表の様なものが固定サイズであるところの素朴なハッシュの検索
についてだけを考える。
ハッシュの中に入っているデータの個数が N 個の時に、あるキーを持つ
データを1個だけ探すのに掛かる平均時間を g(N)とすると、数学的には
g(N)=O(N)。
しかし、この g(N) は、g(N) = a N + b と近似した場合の a の値が極端に小さい。
なので、N が小さい時には、O(1)であるかのように振舞う。
そういう意味だ。
これで理解できないなら、数学的想像力や理解力が足りてない。
この数学100点マンはRustを叩いてる人で常に生ポインタ派のC/C++史上主義な人
ただしコードを出したことがないのでプログラミング能力がないと推定されている
さらにオーダーについても勝手な定義で無茶な主張を繰り返している
分かっとるわ
語呂がいいからRustガイジって言っただけ
お前もとことん馬鹿だな。
コード書いても抽象理解が出来ない人には、そのコードの本質は分からんし、
こんなところに書ききれるわけでも無いからかけないだけだ。
なお、抽象 = シンボライズ、シンボリック
という意味で、曖昧や玉虫色という意味では無いぞ。
本質的な部分を記号化、定理化、規則化、一般化して理解できるようにしたもの
を「抽象化」と言う。
平衡二分木とハッシュセットを混同する
数学100点マンがいると聞いて
>こんなところに書ききれるわけでも無いからかけないだけだ。
スレじゃなくて、IdeoneとかGihubのgistに書いてもらえれば大丈夫ですよ
＞、g(N) = a N + b と近似した場合の a の値が極端に小さい。…①
なぜですか？
ハッシュテーブルの実装方法から論じてみください
もしかして、あなたは①を数学の公理、みたいに扱っているのですか？そんなことではコンピューターサイエンスは無意味だし面白くないでしょう？
でもC/C++ 至上主義者というのなら、私と気が合いますね
MFC(Win32)に関しては、メッセージキューとイベントは別物だぞ。 イベントは、
イベント処理中でも降って来る。
しかも具体的な実装上の問題点の指摘もなく他人のベンチマークは信用できないとか宣われてしまうとこちらとしては会話しても意味がない人なんだと判断せざるを得ないんですよね
公理ではなくて、処理時間の平均値を確率論で書いている。
[補足]
確率論で証明することが出来るが、とてもめんどくさいので割愛する。
失礼だが、質問者のレベルから推測すると、ちゃんと書いても理解できない。
最悪値が重要な用途もある
また、確率はデータの分布が決まってはじめて決まるもの
分布次第ではあなたの想定通りにはならない
確率論では、ランダム性を仮定する。
ここはC++ vs Rustスレなのだからコードを出さなければ何も判定できない
机上の空論ばかり書き綴るよりも現実に使われるCPUと向き合わなければならない
例えばRustの標準ライブラリHashMapでも用いているSwiss Tables法ではハッシュ衝突時の別エントリ探索にSIMD命令を用いている
CPU命令4つで16エントリ同時に探索候補を判別していきメモリキャシュも活かすようこのためのメタデータを連続領域に配置している
値がガウス分布に従うとかなんらかの仮定をおいていると思うのですがあなたの言うランダム性とはなんですか
あらゆる分布を想定しているのですか
> O(N)の定義は、Nを無限に大きくしていった時に、
コンピュータサイエンスでアルゴリズムの評価をするときは、Nを無限にするなんて考えません
ハッシュアルゴリズムはO(1)でFA
ずっとそんな感じ
計算量ではちゃんとわからない、コストがかかって遅くなる、とか言いつつ、忙しいから実装はできない、お前は馬鹿だから理解できない、みたいなことを数ヶ月に渡って大量に書き込み続けてる
数学でいつも100点取るらしいし、さぞ偉いお方なんでしょうなあ…
いまの場合で言えば、N個のキーに対するハッシュ値が、可能な限り重ならずに
分布すること。
リジェクトされたネタだとか…
意味不明
最大M個の振り分け能力があるハッシュ構造にN個の(key, value)ペアを
書き込んでいる場合を考える。
ただし、Mは 定数とし、N が大きくなっても拡張していかないものとする。
このとき、一回の検索に掛かる平均時間をg(N,M)とすると、
ほぼ、
g(N,M)=b・(ceil(N/(2M))
ただし、
・b は、一回の文字列比較に掛かる時間。
・ceil(x)は、xを越えない最小整数。
と書ける。これは、ほぼ、
g(N,M)=b・((int)(N/(2M) + 1)
=(int)(N/(2M))*b + b
と書ける。Nが大きい時には、
g(N,M)=a*N + b
a = b / (2M)
と書ける。
Mが大きい時、aは、小さいが0ではないので、処理時間は、O(1)ではなく、O(N)である。
・ハッシュテーブルの検索や追加はO(1)
・ハッシュテーブルの拡張もO(1)
> ハッシュテーブルはキーをもとに生成されたハッシュ値を添え字とした配列である。
> キーを要約する値であるハッシュ値を添え字として値を管理することで、検索や追加を要素数によらず定数時間O(1)で実現する。
>
> 利用率が一定を超えた場合に、より大きいサイズのハッシュテーブルを用意して格納し直す操作が必要となる。これをリハッシュ (rehash) と呼ぶ。
> この操作はすべての要素のハッシュ値を再計算して新たなハッシュテーブルに格納するためO(n)であるが、
> 配列のサイズを指数的に拡張する事で、動的配列の末尾追加操作と同様に償却解析によって計算量をO(1)とみなす事ができる。
例えば、M=128で、128種類のハッシュ値に振り分けられるなっている
ハッシュ構造の場合、N=128万にすると、1つのハッシュ値に1万個の
(key, value)のペアが対応している。
そして、1個のkeyを検索する時、平均的には、1万個の半分の5000回
くらいkey値の比較を行うと一致するものが見つかる。
なのでこの場合、1個のkeyに対する検索時間は
5000*(keyの比較に要する時間)
となる。
Nを128億にすると、
5000万*(keyの比較に要する時間)
になる。
誤:128種類のハッシュ値に振り分けられるなっている
正:128種類のハッシュ値に振り分けられるようになっている
誤:5000*(keyの比較に要する時間)
正:5000*(1回のkeyの比較に要する時間) // ()内は、keyが文字列の場合、1回の文字列比較に掛かる時間。
誤:5000万*(keyの比較に要する時間)
正:5000万*(1回のkeyの比較に要する時間) // ()内は、keyが文字列の場合、1回の文字列比較に掛かる時間。
>>862
> 利用率が一定を超えた場合に、より大きいサイズのハッシュテーブルを用意して格納し直す操作が必要となる。これをリハッシュ (rehash) と呼ぶ。
>>861 の4行目で、リハッシュは行わないと断った。
はっきり、Mを定数とすると書いている。
>>864
> 最大M個の振り分け能力があるハッシュ構造にN個の(key, value)ペアを書き込んでいる場合を考える。
> M=128で、128種類のハッシュ値に振り分けられるようになっている
> Nを128億にすると、5000万*(keyの比較に要する時間)になる。
つまり128億個のデータを128個のハッシュ値パターンでハッシュテーブルに格納か
現実の世界ではなく一人だけの特殊な妄想世界で空論
このスレの集大成に近い出来だと思う
>>624 はスルーで
混ぜるな危険
あなたの言うランダム性の定義を伺いたかったのですが
挿入されるkeyはどのような分布に従う仮定なのですか
衝突が起きるとしても、5chのIDが被る程度の稀な確率となる程度のランダム性を想定しています。
分布については特に何も想定してないということですね
データに合わせてハッシュアルゴリズムを変更する、アダプティブ・ハッシュ・テクノロジー™をご提案いたします。
その理由として、同一の計算オーダーを持つアルゴリズム、あるいは同一のアルゴリズムから、どちらが優れたバイナリを生成できるか論じているので、それはベンチでしか判明しない、と挙げていると思うのです。
全く意味がない事はない
異なるキーに対するハッシュ値が、可能な限り異なるランダム性。
処理時間を g(N)とすると、worst case ではなく、平均が、g(N) = O(N)。
O(N)という記号を使わずに、詳細に書くと、
g(N) = a * N + b
だが、利用されるハッシュ値の振り分け数が M 個の場合、
a = b / M
程度となり、M = 1024 の場合、a は、0.001 * b 程度の小さな値になる。
横軸を N、縦軸を g(N) とするグラフを書くと、一次関数となり、y 切片が b、
傾きが 0.001 * b 程度となり、ほぼ水平であるが、僅かに右肩上がりとなる。
もしこれが完全に水平なら O(1)。
今回の場合、非常に水平に近いが確実に単調増加であるので、O(1)のように
見えるが本当は O(N)。
O(1)とO(N)の間にはO(logN)やO(√N)など無数にある
もちろん、それは当然。
それは全く否定していない。
[補足]
「グラフが水平なら O(1)」とは書いたが、「O(1)ならグラフが水平」とは
書いてない。
つまり、グラフが水平である事はO(1)であることの十分条件であるが、
必要条件ではない。
「グラフが水平 ⇒ O(1)」とは述べているが、その逆の
「O(1) ⇒ グラフが水平」とは述べて無いことに注意。
それがworst caseの話なんだってw
amortized average caseがO(1)とみなせる前提をガン無視して
「ほらO(n)だろ」とか言ってても誰も相手にしてくれない
いや、違う。
平均は、
g(N) = b * (N/M + 1)
程度。
worst は、
g(N) = b * N
どちらも O(N)ではあるが。
なお、数学の秀才なら気付くと思うが、この平均の式は、本当は正しくない。
ただし、大体は合ってる。
[補足]
何が正しくないかというと、本当は、ある箇所を2 で割る必要があるから。
例えば次のように :
g(N) = b * (N/(2M) + 1)
しかし、これでも、まだ少し正しくない。
説明の内容からしても多分中高生か啓蒙書を読みかじったおじさんなんだろ
だから、プログラマが馬鹿にされる。
でないとどうにもならん。
それ以前の問題。
正直さだ。
自説を主張するために正しい主張を否定してはいけない。
結果は一時式でも、それを求めるには確率論以前に、イマジネーションが必要。
どこかに書いてある知識の組み合わせでは導出できない。
確率論は、自分の想像力が重要に成るので、計算力だけでは無理な分野。
書いてある定理を組合すだけでも導けない。
数学は、基礎の部分はイマジネーションで作られているから、頭の良い
人以外には作れない。
いくら勉強しても無駄。
誰でも後から客観的に検証できる性質が数学含む科学の特徴ですよ
イマジネーションって言い換えればあなたの妄想ってことですよね
それで100点君は何を主張したいんだっけ？
>また、N個のデータを持っているハッシュ構造は、1回の検索は、数学的に厳密にはO(N)
>だが、実験的(実際的)にはO(1)のように振舞うと言われており、厳密に扱うには、
>オーダーの記号だけでは表現しきれない。
「1回の検索は、数学的に厳密にはO(N)」になるのは
一般的なハッシュテーブルの実装とは関係ない架空の条件下の話だね
つかBig O記法が何の目的で使われるのか把握してなかったのか・・・
長々とお疲れさんでした
>>861
> 最大M個の振り分け能力があるハッシュ構造にN個の(key, value)ペアを
> 書き込んでいる場合を考える。
> ただし、Mは 定数とし、N が大きくなっても拡張していかないものとする。
> このとき、一回の検索に掛かる平均時間をg(N,M)とすると、
> ほぼ、
> g(N,M)=b・(ceil(N/(2M))
いや、全然違うし
一体何をあらわしてる式なんだ？
Rust: c++くらいの性能はほしいけど、間抜けがメモリリークをエンバグするのを防ぎたい
Rustの狙いはc++＆コーティング規約＆lintでけっこうカバーできるけど、Rustは言語仕様としてコーダー全員に規約遵守を強制しているのが強み。
Rustが本当に普及してきたら、Rust対抗としてC++と連携できるSmartC++が出てくるんじゃないのかね。
＞Rust: c++くらいの性能はほしいけど、間抜けがメモリリークをエンバグするのを防ぎたい
これが重要だな。
楽をしなければ
実際にはコードベースが大きくなると間抜けなミスをする確率が高まるので
自分はミスをしないと思い込むのではなくミスした場合も検出できるようにすべき
静的解析やrustの真価はそういうところにあると思う
ここの人には理解できないようだがな。
そのためのコーディング規約＆lintだろ。
極端な話、Rustみたいに
基本unique_ptrにして共有する部分だけshared_ptrを使用＆生ポインタ禁止、
3rdパーティライブラリはunsafeなラッパークラスで閉じ込めた使用のみ可、
といったコーディング規約にして設計すりゃポカミスぐらいは防げる。
何もrustに限った話ではないというのはその通りで
静的解析やrustと書いたのはそういう規約やlintで補うことも可能という意図
ただrustのshared mutabilityを原則禁じるルールなど、lintで同等のチェックするのは難しい気がする
その規約を遵守させる工数がバカにならないんだよなぁ
人数が増えるとさらに倍になるし
lintやコンパイラみたいな機械的なチェック以外は基本信用できない
Rustの問題点が顕在化してきたくらいのタイミングで、RustアンチテーゼとしてSmartC++とか出てくるんじゃない？
c++のバットノウハウを禁止できればRust使う必要性はずいぶん薄れるな。
「SmartC++のスコープ内では生ポインタ変数禁止」「nullのスマートポインタの生成禁止」くらいでも十分な気がしてきた。
機能的にも未熟だし標準的に使われるレベルになるかどうかも現段階では怪しい
そんな夢見てるくらいならRust使ったほうが堅いし現実的
Rustの問題点てなんですか？
揶揄してるわけじゃなくてまだ入門の勉強中なのでいろいろ興味あります
よく言われるのが学習コストの高さ。
c++もいいかげん複雑すぎる言語と言われているけど、Rustはそれに輪をかけて難しい。
特に他の言語を勉強した初級・中級者は変数の挙動から何から違う(＆他の言語のようにやるときのためのガイドラインも無い)ので地獄を見るかと。
そんなことはないと思う
Rustはわかりやすかったぜ
しかも他より書きやすく便利になった
https://www.tohoho-web.com/www.htm
ちょっとは「何がわかりやすかったか」ぐらいは書こうぜ。
変に他言語の流儀を持ち込もうとするとハマりやすいというのはありそう
あといきなりWebアプリ作りたいとか思うとasyncで死ぬってのは多分ある
https://lkml.org/lkml/2021/12/6/461
ついに正式に第二言語としてとりこまれましたとさ
完璧にお前の負けやな
いいか？自分の間違えを完璧に認めて
土下座するんだぞ？
写真上げろよガイジ
Windows C++
Linux Rust
structとenumだけでナンでもできてわかりやすかったです
クラスや継承ピラミッドがないのも嬉しかったです
あと&selfやらderefやらその他のimpl&のおかげらしくポインタか否かを気にせず使えるのも便利ですね
ArmとGoogleとMicrosoftとRed Hatの後押しのおかげで
RustがLinuxの第二言語の地位を確立したのね
他にどういう問題があるの？
少し前進したな。このまま着実に進めて行って欲しい。
C++書いてる時点でライフタイム周りは分かってるわけだし、結構複雑な言語機能もバリバリ使いこなせるタイプなんだからRustが合う可能性は比較的高いと思う
derefじゃ循環参照作れないと思うが
高い効率と抽象性をRustでも実現できるの？
だったらRust使うが
一般的に洗脳されていると難しいけれど色んなレベルでの意識改革ができると今後に役立つよ
例えばC++自体の限界のためにテンプレートメタプログラミングでやらざるを得なかったケースがRustでは使わずに出来てしまうケースもあるし
C++ではこうやるべきだと思えていたお決まりの手法が発想を転換するとRustでは別の手法によりもっと自然に出来てしまうケースもある
一方で失敗する人たちはそういった意識改革が出来ずにC++では当たり前に思えていた方法でそのまま突き進もうとしてしまい本来は簡単に出来ることを複雑にしてしまう
もちろん能力がある人たちならばこの意識改革が出来るため必要に応じて発想の転換など臨機応変に対応することが出来ますから大丈夫
> 例えばC++自体の限界のためにテンプレートメタプログラミングでやらざるを得なかったケースがRustでは使わずに出来てしまうケースもある
> C++ではこうやるべきだと思えていたお決まりの手法が発想を転換するとRustでは別の手法によりもっと自然に出来てしまうケースもある
ふむふむ。例えばどういう具体例がありますか？
例えばRustにはclassすらないしtry/catch/throwすらない
C++の視点から見るとそんなのでまともなプログラミングできるの？？となる
しかし現実にRustではそれらがなくとも普通に問題なく便利にプログラミングが出来ている
そして発想の転換が出来るようになるとclassやtry/catch/throwはプログラミングする上で必須なものではなかったんだなと真の理解が進む
まずはこういう基礎的なところからスタートするのがよいでしょう
type traitベースでenable_ifするのはtrait boundで
テンプレートメタプロそこまで詰めてやったことないから逆にRustでできなさそうなの挙げて欲しいかも
それか両方詳しいひとカモン
典型的なのはSFINAEを駆使してた部分がtraitで解決できるとかかな
まぁconceptと同じようなもんだけど、conceptは正直まだ発展途上だと思う
Rustのジェネリクスはそういうのは許容しないからちょっと表現範囲は狭いね
ジェネリクスの範囲外は手続きマクロでカバーする感じ
こっちは任意のコード生成だから、テンプレートより遥かに自由度が高い（が、当然乱用するとやばい）
こういうの見るとどんどんRustが嫌いになっていく…
Rustコミュニティーは若いからな。
説明ノウハウ無い＆自浄作用無いので、アホがクズみたいなレスでマウント取ろうとするのは仕方ないよ。
テンプレート機能はC++の一部だしテンプレートメタプログラミングはその機能を使ったプログラミングに過ぎない
言語自体の限界とはまったく関係ないしやらざるを得ないという表現はなにを指しているのかわからない
>>944
そんなことを言ったらRustにもプログラミング上必須でない機能が無数にあるだろう
言語間に差があることは前提で言語ごとに設計の仕方が異なるからRustの話を聞いただけだ
あなたのコンプレックスを刺激してしまってのならばごめんなさい
嫌いになるかどうかはあなたが損するだけなのでご自由にどうぞｗ
>>949
単なるアドバイスがマウントに見えてしまうのは一種の病気なので
普段の生活でもマウントがどうとかそんなくだらないとこは一切気にせずに穏やかに暮らしたほうが精神面にも良いでしょう
> そんなことを言ったらRustにもプログラミング上必須でない機能が無数にあるだろう
無数？？
具体的にプログラミング上必須でない機能を挙げていただけますか？
> 言語間に差があることは前提で言語ごとに設計の仕方が異なるからRustの話を聞いただけだ
前提はおっしゃる通り同意です
具体的にどういうことをしたい時に設計の仕方でお困りですか？
>>944がアドバイスに見えるとしたら、コーチング・ティーチング技術を勉強した方がいいよ。
>>941の「テンプレートメタプログラミング……」という問いかけには答えず、「そういう気付きや意識改革を自分で出来ない人たち」と相手を否定するだけのアホな言葉をアドバイスと言うのは無能すぎる。
こういうのはRustの害にしかならないから、>>952はアドバイスしないほうがいいよ。
気付けない人たちへのアドバイスをしてはダメなのでしょうか？
アホな言葉とか無能とか言い出すあなたの人格を疑いますｗ
> こういうのはRustの害にしかならないから
こちらはRustに対して何の利害関係もなく中立なのでどうでもよいですｗ
むしろ害にしかならないと思い込みで決め付けることに呆れました
枯れ木も山の賑わい
健全なマクロはいいなぁと思った。
>>954でアドバイス「技術」の話をしているのに、アドバイス「可否」の話をするのは無能の証。わかってやっているなら邪悪だし、どちらにしても>>955には他人にアドバイスする資格が無い。
やっぱりRustの害にしかならないから、>>955はアドバイスしないほうがいいよ。
なんかテンプレに書くべきことある？
最近あっちは大人しいし、変なの湧き始めてからでもいいかね？
単発のネタスレだよここは
LinkedList ランダムアクセス でググれば一発で分かるようなことを延々とやってたからな
本スレがノイズだらけになるから隔離スレは継続すべき
証明されたスレだ。
言ってることは全く正しいけど
promise/futureの存在によってasync/awaitが成立していることをもっと強調すべきかな
このまえGoスレでそれすら理解できないやつが延々と暴れていた
さらに「async/awaitがあればpromise/futureは不要！」とまで主張して暴れていた
非同期プログラミングをかじっただけの人にありがちなのかもしれない
例えば「複数のpromise/futureに対して任意の一つが解決されたら」とか「解決順に」とかawaitだけでは表現不可能なのにな
むしろ暴れてるのはお前だろ、思想的に必要無い言語にそれを持ち込んで優位性を語るなんてアホちゃうか？
非同期をawaitという限られた同期パターンだけでなくfutureを直接扱うことも可能だし
Goのようにコルーチンをすぐ動かせるしそれに対して同様にchannel通信もいけるしfutureとして扱うことも可能
実験的にRFC 2033: experimental coroutinesとかやってるけど、N:Mスレッドスケジューラーが標準搭載される未来はない。
Rustでは一昨年からasync blockが既にstackless symmetric coroutineとして動いています
zero costでlazyなのでasync blockを作るとそれだけだとfutureが出来るのみ
それをm:n含め好きなスケジューラがいくらでもあるのでそれに対してspawnするだけで起動します
そのasync block内では全てawaitしまくればgoroutineと同じ状況になります
もちろんチャネルも使えます
tokioとasync-stdはどっちがデファクトスタンダードです？
所詮spawnするということはasync/awaitがepollベースであり、更には「全てawaitしまくれば」なんてGoと同じ状況じゃないでしょｗ
標準搭載と書いてるのに「好きなスケジューラがいくらでもある」とほざく
ゼロコスト、ゼロコスト言うやつがいる限りウザがられるし、英文で書けば相手を丸め込む事ができると思い込んでると
ホントに爪弾きにされるぞ、Rust推しは分かるけどもう少し顔真っ赤にしてくる態度改めようぜ？
C++でもco_await、co_yieldはゼロコストでスタック消費しないし、コンパイラ型で非同期にコスト掛かる言語って何？
2022年版が必要です
貴方のほうが色々とおかしい。
＞所詮spawnするということはasync/awaitがepollベースであり、Goと同じ状況じゃないでしょｗ
まずepollを貴方が理解できていない。epollはLinuxでのpoll/select系システムコールのAPI。
厳密にするのも的外れなので、仮にここではselect/poll等の意味合いで受け取っておく。
Goのgoroutineも当然ながらこのselect/poll等を用いて実現しているので全く同じ状況。
当然select/poll等を用いなければgoroutineのような軽量スレッド(グリーンスレッド)は実現できない。
＞所詮spawnするということはasync/awaitがepollベースであり、
引用再掲するが、貴方は更なる誤解もしている。
まず、awaitはfutureを解決する単なる一つの手段にすぎず、貴方が言及しているspawnする対象はfurureである。
そしてGoでの「go func」がRustでの「spawn(future)」に相当。
これらが為されないとどちらもスケジューラに登録されず両者は同じ状況であると言える。
＞更には「全てawaitしまくれば」なんてGoと同じ状況じゃないでしょ
Goroutineでは明記しなくても暗黙的にawaitを付けたのと同じ同期的な記述で非同期を記述できる。
したがって、Rustにおいては「全てawaitしまくれば」Goと同じ状況といっても過言ではないと言えよう。
いずれにしても「go func」と「spawn(future)」の場合と同じで記述面での些細な相違だけにすぎない。
＞標準搭載と書いてるのに「好きなスケジューラがいくらでもある」とほざく
Rustの標準には不可欠なものしか無いから標準搭載されていないのは当たり前。
よく例に出されるが、C言語でstdlibにあるrand()のような乱数ですらRustの標準ライブラリにはない。
貴方の無茶な理論だとRustは乱数もサポートしていない言語、となる。
OSや組み込みにも用いられる状況で、何か単一のスケジューラが標準搭載であればよい、わけがない。
むしろ様々なスケジューラを選ぶことができるRustの状況こそ、明らかに有利である。
顔真っ赤で草
個人的には名の通りstdをasync化しているasync-stdが好みです
>>987
よくわかっていらっしゃらないようなのでどの言語でもいいから実際にプログラミングしてみることをおすすめします
epollでもselectでもいいからI/Oイベントループを自分で書いてみればそれがディスパッチャでありスケジューラの核心だとわかりますよ
C言語で大丈夫ですから
Goではできないこと辛いことが多すぎてGo2でRustの後追いしようとしているがGo2は期待外れで盛り下がっている
そこをパズルのように組み合わせてある程度のことは出来る楽しさがいいのよ
ただしそれが飽きられてきていたり楽しいと思う人たちより外に広まらなかったり
自然じゃない組み合わせで実装や冗長な記述などせざるをえなかったり
だからGoはこのまま狭い適用範囲だけで使われる形になりそう
完走しても建ってなかったらワイが建てるで
納得できない
じゃあきみはGoにGenericsとか実装されても使いたくないの？
Goの良いところはそういうとこじゃないでしょ
新しいスレッドを立ててください。
life time: 235日 4時間 30分 6秒
運営にご協力お願いいたします。
───────────────────
《プレミアム会員の主な特典》
★ 5ちゃんねる専用ブラウザからの広告除去
★ 5ちゃんねるの過去ログを取得
★ 書き込み規制の緩和
───────────────────
会員登録には個人情報は一切必要ありません。
月300円から匿名でご購入いただけます。
▼ プレミアム会員登録はこちら ▼
https://premium.5ch.net/
▼ 浪人ログインはこちら ▼
https://login.5ch.net/login.php
レス数が1000を超えています。これ以上書き込みはできません。
ニュース
- 【文春】M-1王者コンビ「ウエストランド」河本太、タクシー運転手に暴行トラブル「腕に噛みつき、前歯が欠け…」 [Anonymous★]
- 政府、コロナワクチン啓発に「YouTuber起用動画9本・３２００万円支出」認める「接種の重要性など、正しい情報を知っていただくために」 [Hitzeschleier★]
- 【鉄道】女性「電車で隣に座ってくる男キモい」SNS“炎上”…男女で《賛否》真っ二つ、それぞれの言い分とは ★2 [ぐれ★]
- 【三重】保健室に来た男子中学生を抱きしめたりキスをしたり…２７歳女性養護教諭を懲戒免職 [シャチ★]
- 『平和堂』公式X、いなり寿司誤認逮捕事件「いなりずしを渡した知人もダメ」投稿2件に「いいね」 「誤った操作」と陳謝 [Hitzeschleier★]
- 【文春】「相合い傘で自宅マンションへ…」内田理央と人気YouTuberヒカルの寿司デート＆お泊まり愛“スクープ撮 [Ailuropoda melanoleuca★]
- 【実況】博衣こよりと周防パトラのドキドキたこパ🧪 ★2
- 【実況】博衣こよりと周防パトラのドキドキたこパ🧪 ★4
- 【実況】博衣こよりと周防パトラのドキドキたこパ🧪 ★3
- それも程度問題であるわけですよ、誰か焼き肉ビーガン開業してますよ
- いーつのーことーだかーおもいだしてごーらんーwwwwwwwwwwwwwwwwwwwwwwwww
- 【悲報】１５歳～１９歳のバカまんこ、スマホ２台持ちのバカばっかだったwwwwwwwwwwwwwwwwwwwwwwwww [207516352]