C++ vs Rust

■ このスレッドは過去ログ倉庫に格納されています
2021/04/24(土) 08:04:49.48ID:nPKzA798
競え
2021/11/22(月) 23:41:22.24ID:7gi7NmEv
>>291
LinkedListの中のノードへの参照を10個持っている状態で、
その参照を使って1個のノードを削除しようとしてコンパイルは通るか？
2021/11/22(月) 23:42:38.96ID:0LbM6y2O
>>301
safeであるためには必要なコストだと思うけどね
mutabilityが前後のノードに影響するデータ構造だから仕方がない
2021/11/22(月) 23:44:32.43ID:5egSOJea
>>311
それCでもC++でもダングリングポインタ発生の駄目プログラマーパターン
2021/11/22(月) 23:49:43.35ID:7gi7NmEv
>>313
そんなことないぞ。
vectorと勘違いして無いか。
2021/11/22(月) 23:55:11.62ID:4Q+A1yLL
>>311
参照先自体を削除するんじゃなくて、参照先からさらにnextとかprevたどってどっかのノードを削除するってこと？
参照先自体を削除するのはRustに限らず問題でるよね
2021/11/22(月) 23:58:04.28ID:7gi7NmEv
>>315
参照先を削除するのは普通なことで、安全に行えるぞ。
参照とは、つまり、識別番号の代わりに使うものだからな。
参照はオブジェクトに付けられた名前みたいなもんだから、
逆に言えば、参照先を削除できないなら、削除する方法がほぼ無い。
2021/11/23(火) 00:00:50.13ID:1c3aeddQ
何の話についてもまずは具体的なC言語のコードを示すべきじゃないかな
そうすればRustのコードを2種類みんなが出してくれるよ
　・1つは元のC言語と同じ安全度で場合によってはunsafeを用いて実装
　・もう1つはメモリ安全性を保証してunsafeを使わずに実装
つまり「C言語で出来ることはRustで必ず出来る」＋「Rustではメモリ安全性を保証した実装も可能」
明らかにC言語よりもRustの方が能力も高く優れている
2021/11/23(火) 00:00:51.12ID:16zHq7La
>>314
残り9個の参照はそのノードが削除されたことを知る術がないからダングリングポインタになるってことだろ
2021/11/23(火) 00:08:02.67ID:xJBrssBV
>>318
本来は、明らかに別のノードであれば問題ない。
C++では普通に安全にそれが行える。
リンクリストの中に、A, B, C という名前の人のデータが入っていて、
それぞれに対して1つずつそれぞれ、ポインタ pA, pB, pC が存在している時に
ポインタ pA を介してAを削除しても、B, C へのポインタ pB, pC は残っていて、
値も変更されることも絶対に無いから完全に安全。
Aさんのデータを削除する場合にはこのようなことが起きるが、その時には、
delete pA の後、pAを捨ててしまうだけで全く安全。
pB, pC は何事も無くまったく安全に残せるし、何のバグも入らない。
こんな単純なロジック、何の問題も無い。
2021/11/23(火) 00:15:34.94ID:8Ju98kPx
同一のノードに10個の参照って意味ちゃうん？
2021/11/23(火) 00:16:47.17ID:1c3aeddQ
>>319
それだと>>311の条件を満たしていないのでやり直し
　・いずれにせよC/C++で書けるコードはそのままの形でそのままの安全度で必ずRustでもunsafeを用いて書ける
　・更にRustでは安全性を保証する形でunsafeを用いずに実装することもできる
C/C++よりもRustのほうが明白に能力が高い
2021/11/23(火) 00:20:07.35ID:xJBrssBV
>>320
1つのリンクリストの異なる10個のノードに対する10個の参照。
2021/11/23(火) 00:21:41.44ID:/rTkTwIT
>>319
C++でノードへのポインタは実装依存な方法でしか取れないよ
pAその他は本当にポインタ？イテレータではなく？
2021/11/23(火) 00:21:54.64ID:xJBrssBV
>>321
何度もしているが、それはフェイク。
Cできることのうち、Rustでは追加コストを掛けずにはsafeモードで出来ないことはたくさん有る。
unsafeモードを使いまくれば別。
しかしそれではRustを使う意味が無い。
2021/11/23(火) 00:22:40.62ID:xJBrssBV
>>323
C++ではなく、Cのリンクリストで考えよう。C++は別の複雑さを入れ込んだから。
2021/11/23(火) 00:22:46.42ID:s6k3uLQ1
>>324
なぜRustを使う意味がないのですか
2021/11/23(火) 00:25:21.42ID:xJBrssBV
>>326
Rustの売りはゼロコスト+安全性にあるからだよ。
どちらが掛けても意味が無い。
ゼロコストで無いなら既にC#やJavaがある。
安全で無いなら既にC++がある。
2021/11/23(火) 00:26:18.34ID:6/+wazXE
ああ、なるほど
安全性を考慮していないCのLinked Listと、安全性が保証されたRustのLinked Listを比較して、
Rustは遅い、できることが少なくて不便だ、みたいなことを述べてたわけか

Cでもメモリリークしないようにして、スレッドセーフにするとかしたら、途端に大変になりそう
2021/11/23(火) 00:26:36.02ID:s6k3uLQ1
>>327
違いますよ
2021/11/23(火) 00:27:06.93ID:8Ju98kPx
>>324
リンクトリスト内のメソッドでunsafeを閉じ込めることできると思うんだけどそれではだめなのか
2021/11/23(火) 00:28:01.20ID:8Ju98kPx
なんなら>>330は「基本的な操作のメソッドは」ってしてもいいけど
2021/11/23(火) 00:31:19.33ID:xJBrssBV
>>330
複数のノードへの読み書き自由なアクセスの速度をO(1)を保ったままで、
RustではunsafeをLinkedListのメソッド内には閉じ込めることが基本的に
出来ない。基本的に、と言ったのは、先ほど彼が示したリンク先の独自
実装の様に、ゼロコストであることを諦めてコストを掛ければできる
ようになるから。ただし、その場合、スパイク的にO(N)の時間でコピー
動作が発生してしまう。
2021/11/23(火) 00:32:59.52ID:xJBrssBV
>>332
[補足]
スパイク的なコピーの発生だけでなく、普段からコスト増加もある。
ベースアドレス + 相対アドレスでアクセスするから。
2021/11/23(火) 00:38:03.01ID:1c3aeddQ
>>262
その人が作ったLinkedList実装がポインタではなく格納配列のインデックスを使っているだけだよ
Rustの標準ライブラリのLinkedList実装ではポインタを使っています
std::collections::LinkedList
https://doc.rust-lang.org/std/collections/struct.LinkedList.html
2021/11/23(火) 00:39:30.31ID:xJBrssBV
>>334
それは分かってる。
で、標準の方は、ノードのアクセス速度に問題がある。
2021/11/23(火) 00:43:10.08ID:qrGqDm2c
>>335
RustはLinkedListでも問題を感じたことがないですが何を根拠に？
2021/11/23(火) 00:49:14.22ID:xJBrssBV
>>336
1つのリンクリストの異なる10個のノードに対する10個のmut参照を同時
に持ち事は出来ないので、O(1)でアクセスできないからだ。
2021/11/23(火) 01:04:38.76ID:qrGqDm2c
>>337
意味がわからないので具体的に意味のあるCコードを書いて
2021/11/23(火) 01:08:49.01ID:8Ju98kPx
Rustだと確かに複数個所のノードへの可変参照を得るのはunsafeメソッドになるだろうね
そのノードが全部別々であることが保証できないから
でもそれは他の言語でも同じで、例えば1のノードに複数の可変参照があって、
1の参照がノード消したらまずことになる

そしてunsafeを許すのなら、内部実装でUnsafe Cell使えばコンパイラからの見た目は不変参照になるから、
オーバーヘッドなしでそういうのは実装可能（ただしstdのLinkedListはそのようにはなっていない）

んで、複数個所のノードへの可変参照を得るというのは相当レアな操作なはずなので、
それはunsafeにしてもAPIの使い勝手としては全然問題はない
2021/11/23(火) 01:37:22.61ID:1c3aeddQ
あるC/C++コードがあった時
(A) 常にRustではC/C++コードと同じ安全度で(必要時はunsafeを用いて)実装できる
(B) ほとんどのケースでRustでは安全なコードを(unsafeを用いずに)実装できる

つまりRustの能力はC/C++を上回っている

言い換えると
C/C++を捨ててRustを使えば
(B) ほとんどのケースで安全性を保証する形で実装できる
(A) 残りのレアケースでもC/C++と同じ安全度で実装できる

したがってC/C++を用いずにRustを用いたほうがよい
2021/11/23(火) 05:32:01.67ID:RKGfozTd
安全性よりも、
とにかくパフォーマンスや使用リソースが最重要な用途がある
そういう所でC/C++が使われる

C/C++は少なくとも今後20年は使われ続ける
2021/11/23(火) 05:47:19.80ID:qrGqDm2c
>>341
RustはC/C++と同じパフォーマンスを出せます
>>340を読みましょ
C/C++からRustへ移ったほうが誰の目にも得です
2021/11/23(火) 07:27:06.42ID:RKGfozTd
本当に良いことばかりなら
ここで宣伝しなくても自然に広まるはず
344デフォルトの名無しさん
垢版 |
2021/11/23(火) 13:48:55.03ID:VKZug2mU
いや、あわしろ氏もC++は窓から投げ捨てろと言ってる。
2021/11/23(火) 14:00:24.39ID:A++o7U7T
>>344
その、あわしろ氏とやらは、では、なにを推薦しているのでしょうか？
2021/11/23(火) 14:20:23.73ID:BTZW3nye
ほんとRust気持ち悪いなｗ
リンクリストのような単純な構造でSTLでもboostでもそれ自体が「安全でない」ことはめったにない。
バグや脆弱性を作りこんでしまうのは多くは固定長のバッファに対するパース処理などで、確かに各種の
*nixコマンドなんかはRustで書いて貰ったほうが良い場合があるが、C/C++の数msが致命となる世界で
Rustが一般的となることはない。そんな布教をやってるから嫌われるんだよｗ
悔しかったらOpenSSLとか書き直して”安全なコード”で出してみろよ？WebkitにC/C++を排除させて
Rustだけにさせてみろｗ
347デフォルトの名無しさん
垢版 |
2021/11/23(火) 14:29:53.22ID:VKZug2mU
いまさらC++やってるようでは時代についていけない老害という評価しかない。
2021/11/23(火) 14:45:56.12ID:CrSl9z1L
Linusも老害だしChromeコミッターも全部老害、気持ち悪さNo1のRustたちが敵を作りまくる自己評価で
あらゆるスレで暴れてる
2021/11/23(火) 14:49:30.08ID:A++o7U7T
>>348
linus を老害呼ばわりするとは…
2021/11/23(火) 14:56:32.81ID:s6k3uLQ1
>>346
usじゃなくてmsなのか...
2021/11/23(火) 14:57:43.30ID:2khltGI7
twitterでも、RustはHaskell程度にしか発言されて無い。
一方、C 言語 で検索すると一日分でも見ることが不可能なくらい大量に
発言されてることが分かる。
twitterでは「C++」というキーワードでは検索できないので推定するしかないが、
C 言語以上であろう。
2021/11/23(火) 15:54:02.42ID:hMtNqdGd
>>340
>つまりRustの能力はC/C++を上回っている
ダウト。
安全面に置いては上回っているが、効率面では下がるケースがかなりある。
353デフォルトの名無しさん
垢版 |
2021/11/23(火) 16:13:02.54ID:hMtNqdGd
・速度を落として安全性を高めたものは、既にJavaや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++を安全面では余り問題を感じて無い人が多い。
2021/11/23(火) 16:19:09.75ID:hMtNqdGd
>>353
さらに言えば、
・「自動参照外し」は便利だとされるが、逆に勝手に参照が外れることで、
　他人の書いたコードの理解が難しいことがある。明記してるコードと
　省略してるコードが同じことを意味してるのが理解しにくいので。
・&の意味が、let文の左辺ではパターンマッチング、右辺では参照、
　の意味になっているので混乱しやすい。左辺では参照をはずす意味
　になってしまう。
・＆は、reference(参照)演算子と呼ばれるのに、ref という演算子もあるが、
　これは、意味がかなり違うため、混乱し易い。
・nullポインタを代入するポインタは、Option<Box<T>> のように長くなる。
・ライフタイム注釈が発展途上中なのか、特に構造体に関するライフタイム注釈
　のドキュメントが少なく、例で説明されるだけで、根本的な意味を書いた
　ドキュメントが存在して無い。
2021/11/23(火) 16:26:18.07ID:A++o7U7T
>>353
IQの定義は？
356デフォルトの名無しさん
垢版 |
2021/11/23(火) 18:18:27.96ID:VKZug2mU
LinuxはRustを第二言語と位置づけ、カーネル開発に積極利用する計画です。
2021/11/23(火) 18:21:55.09ID:1c3aeddQ
C/C++/Rustをやってきた人ならRustが圧倒的にプログラミングしやすいことで一致している
調査結果でもRustが連続1位を続けていることからも客観的に明白
358デフォルトの名無しさん
垢版 |
2021/11/23(火) 18:23:28.79ID:VKZug2mU
あわしろ氏もC++は終了する言語と言っています。
2021/11/23(火) 19:08:31.54ID:s6k3uLQ1
>>353
例示してるシンタックス全部間違ってるし釣りだろこれ
2021/11/23(火) 19:22:32.43ID:4h9SSBVx
>Rustが圧倒的にプログラミングしやすい
うんこ嘘つき野郎
2021/11/23(火) 19:25:27.46ID:1ymEsXZx
>>359
let mut a : mut &T = mut& b
Box<T>::new( T {・・・} );
だったかも知れんな。
複雑すぎるし、C++との違いが大きすぎて覚えてない。
C++ だと、new クラス名で、Rubyだと確か、クラス名.new。
Rustは、後者に近い書き方だから、書き方だけを見てもRustはC++とはやはり遠い。
362デフォルトの名無しさん
垢版 |
2021/11/23(火) 19:43:48.41ID:VKZug2mU
RustはRubyの影響を受けた言語。
大変使いやすい。
2021/11/23(火) 19:51:13.12ID:1ymEsXZx
>>362
いくつか本を読んだが、スクリプト言語的な範囲で使うならばそうかも知れん。
しかし、C++やCのようにポインタを駆使したリンクリストやツリー構造の様な
ものを効率よく高速に、メモリーも節約しながら扱うには、Rustはとても
複雑になる。訳の分からんCell,RefCellなどと組み合わせる必要があることも多い。
2021/11/23(火) 19:53:12.58ID:/rTkTwIT
訳が分かってから文句垂れてください
365デフォルトの名無しさん
垢版 |
2021/11/23(火) 19:59:41.90ID:VKZug2mU
いまどきC++使ってるのは老害でしょう。
すぐにRustを始めるべきです。
2021/11/23(火) 20:09:04.33ID:A++o7U7T
あわしろ氏って、もしかして馬鹿ぁ？
367デフォルトの名無しさん
垢版 |
2021/11/23(火) 21:01:08.57ID:VKZug2mU
低能が何か申しておりますｗ
2021/11/23(火) 21:24:52.33ID:dif3t6ob
>>364
俺は調査目的で調べてるだけで、実用的に使うつもりはないからな。
2021/11/23(火) 22:01:53.34ID:qrGqDm2c
>>368
たまに見かける使いこなせなくて脱落したケース？
2021/11/23(火) 22:12:56.79ID:WEl5Ae/m
あわしろって誰？調べても出てこない
2021/11/23(火) 23:01:49.38ID:dif3t6ob
>>369
使う必要性を感じない。
2021/11/24(水) 07:30:28.98ID:bRL60DLP
>>368
であれば、批判する資格はないな
2021/11/24(水) 10:47:07.21ID:vbixrgR4
>>372
有る。
2021/11/24(水) 10:49:35.25ID:kXzWnsgO
仮に泡白という人物が実在したとしても
ここで連呼されるのは本人も迷惑してるんじゃないかな
2021/11/24(水) 11:15:10.51ID:vbixrgR4
Ubuntu Linuxや OpenOffice系の洋書の翻訳家に、
「あわしろいくや」という人物がいるようだ。
2021/11/24(水) 11:21:34.63ID:RpLLJ5lb
しかもRustやC++の専門家のようには見えんけども…
2021/11/24(水) 17:09:21.00ID:5wn/1hS5
>>373
CとRustそれぞれでコードを書いてみることをおすすめします
計算量オーダーが変わるアルゴリズムレベルの検討ならともかく
コンパイラの最適化でいくらでも性能が変わりうる実装の詳細についてはまず性能測定するのが常識だと思います
2021/11/24(水) 17:29:56.67ID:mlqzRKjQ
リンクリストで頑張るより配列のほうが色々捗る場面も多々あるよな
キャッシュが効いてるとこ読むときの速度は目を見張るもんがある
ヒープで飛び飛びになったデータ構造はその点で恐ろしく不利
それを知ってる人は実測した結果で語る
379デフォルトの名無しさん
垢版 |
2021/11/24(水) 19:53:47.71ID:6QwWetEE
21世紀にもなってC++使ってるのは頭がおかしい。
380デフォルトの名無しさん
垢版 |
2021/11/24(水) 19:54:39.96ID:6QwWetEE
Linusは20世紀の頃からC++は駄目だと言ってた。
天才。
2021/11/24(水) 22:30:18.26ID:Vyl+UaHe
Rustは言語が汚い。
2021/11/24(水) 22:43:39.16ID:RtLWv5R+
linusのc++否定ってのは当時の実装のバギーさとオブジェクト指向に対する否定だな。
関数型流行ってる今から見ると割と普通のこと言っとるわ。
2021/11/24(水) 23:59:24.30ID:e1u6MioL
>>381
むしろ綺麗な方
2021/11/25(木) 01:15:43.82ID:/vPuyV+m
>>381
言語が汚いってのはよくわからないけど例えばどういうところが汚いと感じたの？
2021/11/25(木) 01:47:48.10ID:pEcDGUra
でもLinkedList版sliceみたいなのって実現できないのかね
2021/11/25(木) 02:58:46.76ID:6PNOZvLH
ここまでのまとめ
(1) ほとんどの用途でLinkedListよりVecの方が有用
(2) Rustの標準ライブラリにはLinkedList型もVec型もどちらもある
(3) もしLinkedListやVecを使っても実現できないならまずはそのRustコードを示すべき
(4) 仮に超レアケースがあったとしてもRustでは自分で自由に必要な型を作ればよい
2021/11/25(木) 07:50:48.33ID:3Rcu7yrD
>>381
アセンブラとチューリングマシン語以外の言語は汚い
2021/11/25(木) 09:50:29.78ID:r5Heuy4P
LLVM最強ですね判ります
2021/11/25(木) 16:04:22.18ID:S6TYxgmH
>>386
嘘を書くな。
2021/11/25(木) 16:33:56.78ID:sK32tKJd
>>389
特に嘘はないと思うけど
stdのLinkedListがちょっと融通利かないところはあるけど
2021/11/25(木) 16:34:58.88ID:ug4Dh0aR
>>386
様々な言語の中でRustだけ linked list の任意の要素にO(1)でアクセスできないというのは嘘だった
も追加で
2021/11/25(木) 20:15:57.40ID:SwFLZgNz
macro記述と言語がまるで別言語、いちいちウザいアトリビュート。letは固定を意味するのではなく式展開
何種類もある「文字列」、それに生えている似たようで意味が違ういっぱいのfn（これはトレイトのせい）
わざと敷居を高くしてるとしか思えん
2021/11/25(木) 20:31:51.42ID:6PNOZvLH
>>392
> letは固定を意味するのではなく式展開

letは常に成功する構造パターンマッチングにすぎないよ
if letは成功か失敗か不明な構造パターンマッチング
今どきの言語ならば左辺値にパターンが書けるのが普通

> 何種類もある「文字列」

文字列はヒープにあり伸縮可能なStringとそうでないstrの2種類しかないよ
ヒープを意識する言語なら2種類ある
あとは文字列の参照として&strがあってその本体はヒープにあろうがなかろうが同じ扱いできるだけ
2021/11/25(木) 20:38:50.41ID:pEcDGUra
CString
CStr
OsString
OsStr
2021/11/25(木) 20:58:33.97ID:88pS2ZzI
>>394
それはRustの文字列ではなく単なるFFI
通常のプログラミングでは登場しない
2021/11/25(木) 21:05:41.06ID:NJM+Y62L
>>391
「任意の」
の定義をしないと無意味な主張
2021/11/25(木) 21:16:25.34ID:vljrMlfk
じゃあ何種類もあるじゃない、全部が汚いことへの言い訳にしか聞こえない
2021/11/25(木) 21:25:33.18ID:88pS2ZzI
まとめ
・どの言語でもリンクリストでk番目を得るにはO(n)かかる
・そのk番目を配列で持てばO(1)だがそれはリンクリストではなく配列アクセスのコスト
・リンクリストのk番目を保持する配列を維持するには削除挿入のたびにO(n)の移動が生じる
・これらは言語に依存しない
2021/11/25(木) 21:33:37.11ID:/vPuyV+m
>>397
言語の汚さというよりもOSなどの環境が抱える複雑さをそのまま見せたらそうなったのでは
2021/11/25(木) 21:38:29.78ID:beDf3C1p
それが低いレイヤーをやるってことだわな。
それを他の言語のせいにするrust野郎はクソってことだよ。
2021/11/25(木) 22:13:10.27ID:88pS2ZzI
誤解している人が居るようなので正しい情報
・Rustの通常のプログラミングでCStrやOsStrが出てくることはない
・そこでファイルやディレクトリやソケットを操作してもCStrやOsStrは出てこない
・つまりRustで使う文字列はstrとヒープのStringの2種類しかない
・CStrやOsStrはFFIを書く人のみが用いるのでほとんどの人には無縁
2021/11/25(木) 22:18:29.72ID:3Rcu7yrD
「通常」の定義は？
2021/11/25(木) 22:30:32.62ID:6PNOZvLH
>>402
Rustで未だ対応していない未知のものが出現した時にその対応する人だけがCStrやOsStrを用いる
その時のその人を除き、全ての人はCStrやOsStrなんか知らなくてもRustでプログラミング可能
2021/11/25(木) 23:14:44.56ID:/vPuyV+m
>>401
Pathの操作してるとOsStrは普通に出てくるのでFFIでしか出てこないというのは嘘
2021/11/25(木) 23:16:52.42ID:/vPuyV+m
他の言語がごまかしている箇所を正確に扱えるのがrustの強みでもありめんどくさいところでもある
2021/11/25(木) 23:45:28.39ID:sK32tKJd
Rust擁護マンでも標準の文字列（String/str）以外がFFIのみというのはさすがに筋悪に見える
Rustで標準の文字列をUTF8のバイト配列（ヌル文字終端不採用）としたことによる弊害って側面が割と強い
でも他言語みたいにそこしっかりしないとなるとそれはそれでめんどくさいから結局のところトレードオフ

でもOsStrめんどいわ
2021/11/26(金) 00:54:57.87ID:Ye0bskEh
文字列エンコードを規定しないとそれはそれで移植性に問題あるし難しいところ
WTF-8なる概念必要になったりとにかくWindowsが悪いという気はする
2021/11/26(金) 03:23:02.14ID:FqYYA0QW
>>391
嘘を書くな。
正しくは、Rustは配列を使って独自実装しないとO(1)には出来無い事が明らかに成った。
参照だと借用規則で出来なくて、配列の添え字番号だと単なる整数なので借用規則の
適用範囲外だからできる。添え字番号をポインタの代わりに使って、独自に
リンクトリストを実装することで初めて、O(1)になる。
しかし、O(1)になっても、「係数」が大きくなり、1アクセスに20クロックくらいかかる。
配列の範囲チェックと、配列アクセスのための乗算と加算が追加で必要になるため。

一方、C、C++、C#、Javaではそんなことしなくても最初からO(1)。
2021/11/26(金) 03:24:19.18ID:FqYYA0QW
>>398
お前みたいなやつは、一度殴ってやりたい。
匿名掲示板だからと言って、でたらめを書くな！！
ばか者！
2021/11/26(金) 03:25:10.11ID:xSrpn+m5
>>408
C/C++ のリンクリストがどうして O(1) なんですか？
2021/11/26(金) 03:33:50.05ID:FqYYA0QW
>>398は、数学できない。
細かい点が全然分かって無い。
リンクリストでは、「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クロックくくらいかかる。
　
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。