21/11/23 19:51:13.12 1ymEsXZx.net
>>362
いくつか本を読んだが、スクリプト言語的な範囲で使うならばそうかも知れん。
しかし、C++やCのようにポインタを駆使したリンクリストやツリー構造の様な
ものを効率よく高速に、メモリーも節約しながら扱うには、Rustはとても
複雑になる。訳の分からんCell,RefCellなどと組み合わせる必要があることも多い。
370:デフォルトの名無しさん
21/11/23 19:53:12.58 /rTkTwIT.net
訳が分かってから文句垂れてください
371:デフォルトの名無しさん
21/11/23 19:59:41.90 VKZug2mU.net
いまどきC++使ってるのは老害でしょう。
すぐにRustを始めるべきです。
372:ハノン
21/11/23 20:09:04.33 A++o7U7T.net
あわしろ氏って、もしかして馬鹿ぁ？
373:デフォルトの名無しさん
21/11/23 21:01:08.57 VKZug2mU.net
低能が何か申しておりますｗ
374:デフォルトの名無しさん
21/11/23 21:24:52.33 dif3t6ob.net
>>364
俺は調査目的で調べてるだけで、実用的に使うつもりはないからな。
375:デフォルトの名無しさん
21/11/23 22:01:53.34 qrGqDm2c.net
>>368
たまに見かける使いこなせなくて脱落したケース？
376:デフォルトの名無しさん
21/11/23 22:12:56.79 WEl5Ae/m.net
あわしろって誰？調べても出てこない
377:デフォルトの名無しさん
21/11/23 23:01:49.38 dif3t6ob.net
>>369
使う必要性を感じない。
378:デフォルトの名無しさん
21/11/24 07:30:28.98 bRL60DLP.net
>>368
であれば、批判する資格はないな
379:デフォルトの名無しさん
21/11/24 10:47:07.21 vbixrgR4.net
>>372
有る。
380:デフォルトの名無しさん
21/11/24 10:49:35.25 kXzWnsgO.net
仮に泡白という人物が実在したとしても
ここで連呼されるのは本人も迷惑してるんじゃないかな
381:デフォルトの名無しさん
21/11/24 11:15:10.51 vbixrgR4.net
Ubuntu Linuxや OpenOffice系の洋書の翻訳家に、
「あわしろいくや」という人物がいるようだ。
382:デフォルトの名無しさん
21/11/24 11:21:34.63 RpLLJ5lb.net
しかもRustやC++の専門家のようには見えんけども…
383:デフォルトの名無しさん
21/11/24 17:09:21.00 5wn/1hS5.net
>>373
CとRustそれぞれでコードを書いてみることをおすすめします
計算量オーダーが変わるアルゴリズムレベルの検討ならともかく
コンパイラの最適化でいくらでも性能が変わりうる実装の詳細についてはまず性能測定するのが常識だと思います
384:デフォルトの名無しさん
21/11/24 17:29:56.67 mlqzRK
385:jQ.net
386:デフォルトの名無しさん
21/11/24 19:53:47.71 6QwWetEE.net
21世紀にもなってC++使ってるのは頭がおかしい。
387:デフォルトの名無しさん
21/11/24 19:54:39.96 6QwWetEE.net
Linusは20世紀の頃からC++は駄目だと言ってた。
天才。
388:デフォルトの名無しさん
21/11/24 22:30:18.26 Vyl+UaHe.net
Rustは言語が汚い。
389:デフォルトの名無しさん
21/11/24 22:43:39.16 RtLWv5R+.net
linusのc++否定ってのは当時の実装のバギーさとオブジェクト指向に対する否定だな。
関数型流行ってる今から見ると割と普通のこと言っとるわ。
390:デフォルトの名無しさん
21/11/24 23:59:24.30 e1u6MioL.net
>>381
むしろ綺麗な方
391:デフォルトの名無しさん
21/11/25 01:15:43.82 /vPuyV+m.net
>>381
言語が汚いってのはよくわからないけど例えばどういうところが汚いと感じたの？
392:デフォルトの名無しさん
21/11/25 01:47:48.10 pEcDGUra.net
でもLinkedList版sliceみたいなのって実現できないのかね
393:デフォルトの名無しさん
21/11/25 02:58:46.76 6PNOZvLH.net
ここまでのまとめ
(1) ほとんどの用途でLinkedListよりVecの方が有用
(2) Rustの標準ライブラリにはLinkedList型もVec型もどちらもある
(3) もしLinkedListやVecを使っても実現できないならまずはそのRustコードを示すべき
(4) 仮に超レアケースがあったとしてもRustでは自分で自由に必要な型を作ればよい
394:デフォルトの名無しさん
21/11/25 07:50:48.33 3Rcu7yrD.net
>>381
アセンブラとチューリングマシン語以外の言語は汚い
395:デフォルトの名無しさん
21/11/25 09:50:29.78 r5Heuy4P.net
LLVM最強ですね判ります
396:デフォルトの名無しさん
21/11/25 16:04:22.18 S6TYxgmH.net
>>386
嘘を書くな。
397:デフォルトの名無しさん
21/11/25 16:33:56.78 sK32tKJd.net
>>389
特に嘘はないと思うけど
stdのLinkedListがちょっと融通利かないところはあるけど
398:デフォルトの名無しさん
21/11/25 16:34:58.88 ug4Dh0aR.net
>>386
様々な言語の中でRustだけ linked list の任意の要素にO(1)でアクセスできないというのは嘘だった
も追加で
399:デフォルトの名無しさん
21/11/25 20:15:57.40 SwFLZgNz.net
macro記述と言語がまるで別言語、いちいちウザいアトリビュート。letは固定を意味するのではなく式展開
何種類もある「文字列」、それに生えている似たようで意味が違ういっぱいのfn（これはトレイトのせい）
わざと敷居を高くしてるとしか思えん
400:デフォルトの名無しさん
21/11/25 20:31:51.42 6PNOZvLH.net
>>392
> letは固定を意味するのではなく式展開
letは常に成功する構造パターンマッチングにすぎないよ
if letは成功か失敗か不明な構造パターンマッチング
今どきの言語ならば左辺値にパターンが書けるのが普通
> 何種類もある「文字列」
文字列はヒープにあり伸縮可能なStringとそうでないstrの2種類しかないよ
ヒープを意識する言語なら2種類ある
あとは文字列の参照として&strがあってその本体はヒープにあろうがなかろうが同じ扱いできるだけ
401:デフォルトの名無しさん
21/11/25 20:38:50.41 pEcDGUra.net
CString
CStr
OsString
OsStr
402:デフォルトの名無しさん
21/11/25 20:58:33.97 88pS2ZzI.net
>>394
それはRustの文字列ではなく単なるFFI
通常のプログラミングでは登場しない
403:デフォルトの名無しさん
21/11/25 21:05:41.06 NJM+Y62L.net
>>391
「任意の」
の定義をしないと無意味な主張
404:デフォルトの名無しさん
21/11/25 21:16:25.34 vljrMlfk.net
じゃあ何種類もあるじゃない、全部が汚いことへの言い訳にしか聞こえない
405:デフォルトの名無しさん
21/11/25 21:25:33.18 88pS2ZzI.net
まとめ
・どの言語でもリンクリストでk番目を得るにはO(n)かかる
・そのk番目を配列で持てばO(1)だがそれはリンクリストではなく配列アクセスのコスト
・リンクリストのk番目を保持する配列を維持するには削除挿入のたびにO(n)の移動が生じる
・これらは言語に依存しない
406:デフォルトの名無しさん
21/11/25 21:33:37.11 /vPuyV+m.net
>>397
言語の汚さというよりもOSなどの環境が抱える複雑さをそのまま見せたらそうなったのでは
407:デフォルトの名無しさん
21/11/25 21:38:29.78 beDf3C1p.net
それが低いレイヤーをやるってことだわな。
それを他の言語のせいにするrust野郎はクソってことだよ。
408:デフォルトの名無しさん
21/11/25 22:13:10.27 88pS2ZzI.net
誤解している人が居るようなので正しい情報
・Rustの通常のプログラミングでCStrやOsStrが出てくることはない
・そこでファイルやディレクトリやソケットを操作してもCStrやOsStrは出てこない
・つまりRustで使う文字列はstrとヒープのStringの2種類しかない
・CStrやOsStrはFFIを書く人のみが用いるのでほとんどの人には無縁
409:デフォルトの名無しさん
21/11/25 22:18:29.72 3Rcu7yrD.net
「通常」の定義は？
410:デフォルトの名無しさん
21/11/25 22:30:32.62 6PNOZvLH.net
>>402
Rustで未だ対応していない未知のものが出現した時にその対応する人だけがCStrやOsStrを用いる
その時のその人を除き、全ての人はCStrやOsStrなんか知らなくてもRustでプログラミング可能
411:デフォルトの名無しさん
21/11/25 23:14:44.56 /vPuyV+m.net
>>401
Pathの操作してるとOsStrは普通に出てくるのでFFIでしか出てこないというのは嘘
412:デフォルトの名無しさん
21/11/25 23:16:52.42 /vPuyV+m.net
他の言語がごまかしている箇所を正確に扱えるのがrustの強みでもありめんどくさいところでもある
413:デフォルトの名無しさん
21/11/25 23:45:28.39 sK32tKJd.net
Rust擁護マンでも標準の文字列（String/str）以外がFFIのみというのはさすがに筋悪に見える
Rustで標準の文字列をUTF8のバイト配列（ヌル文字終端不採用）としたことによる弊害って側面が割と強い
でも他言語みたいにそこしっかりしないとなるとそれはそれでめんどくさいから結局のところトレードオフ
でもOsStrめんどいわ
414:デフォルトの名無しさん
21/11/26 00:54:57.87 Ye0bskEh.net
文字列エンコードを規定しないとそれはそれで移植性に問題あるし難しいところ
WTF-8なる概念必要になったりとにかくWindowsが悪いという気はする
415:デフォルトの名無しさん
21/11/26 03:23:02.14 FqYYA0QW.net
>>391
嘘を書くな。
正しくは、Rustは配列を使って独自実装しないとO(1)には出来無い事が明らかに成った。
参照だと借用規則で出来なくて、配列の添え字番号だと単なる整数なので借用規則の
適用範囲外だからできる。添え字番号をポインタの代わりに使って、独自に
リンクトリストを実装することで初めて、O(1)になる。
しかし、O(1)になっても、「係数」が大きくなり、1アクセスに20クロックくらいかかる。
配列の範囲チェックと、配列アクセスのための乗算と加算が追加で必要になるため。
一方、C、C++、C#、Javaではそんなことしなくても最初からO(1)。
416:デフォルトの名無しさん
21/11/26 03:24:19.18 FqYYA0QW.net
>>398
お前みたいなやつは、一度殴ってやりたい。
匿名掲示板だからと言って、でたらめを書くな！！
ばか者！
417:ハノン
21/11/26 03:25:10.11 xSrpn+m5.net
>>408
C/C++ のリンクリストがどうして O(1) なんですか？
418:デフォルトの名無しさん
21/11/26 03:33:50.05 FqYYA0QW.net
>>398は、数学できない。
細かい点が全然分かって無い。
リンクリストでは、「k番目にアクセスする」と言っても、次の二種類ある。
1. (乱数などで)整数 k
419:を与えられて、ノードを探す。 この場合、どうしても、O(N)、O(k)の時間がかかる。 2. 既に追加したノードを、もう一度アクセスする。 これには、C、C++、C#、Javは、O(1)しかかからない。 しかも、C、C++だと 1 クロック。 Rustだと配列と添え字番号を使って独自実装しなければ、 基本的にO(N)、O(k)かかる。独自実装した場合、 O(1)ではあるが、20～50クロックくくらいかかる。
420:デフォルトの名無しさん
21/11/26 03:34:37.06 FqYYA0QW.net
>>410
>>411を読め。
俺は正直に言っている。また、数学が昔から良くできるので、間違ってない。
421:デフォルトの名無しさん
21/11/26 03:40:28.33 FqYYA0QW.net
>>411
[補足]
実際、>>257 の独自実装は、Rustでも、任意の場所のノードをO(1)で
アクセスできるが、1アクセスあたりに一般的なノードサイズでは
20～50クロック掛かる。
悪いが、QZが出てくると話がややこしくなる。
かわいそうだが、単刀直入にいえば、QZは頭が良くないので、
レベルが全体に下がってしまう。
ようは、レベルが違う人は、教室を分けないとめちゃくちゃに成る。
レベルというのは熟練しているかどうかではなく、生まれつき決まっていて、
直すことが出来ない。
すまん。
422:デフォルトの名無しさん
21/11/26 03:46:37.90 FqYYA0QW.net
>>398
>・どの言語でもリンクリストで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個のノードだけに限定すれば出来る。
423:デフォルトの名無しさん
21/11/26 04:02:58.56 FqYYA0QW.net
例えばこういうことだ。
リンクリストに、
ハンバーガー、りんご、みかん、ドーナツ、パイナップル
の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("パイナップル");
424:デフォルトの名無しさん
21/11/26 04:03:19.69 FqYYA0QW.net
>>415
[続き]
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)の時間が掛かる!!
425:デフォルトの名無しさん
21/11/26 04:10:09.81 r6ugNRE0.net
>>411
＞2. 既に追加したノードを、もう一度アクセスする。
これカーソルでO(1)でできるって何度も言われてるやんけ
書き換え可能なカーソルを複数持つコードを書くのがめんどくさいってならわかるが
426:デフォルトの名無しさん
21/11/26 04:12:10.51 FqYYA0QW.net
>>
427:416 [補足] cout << aaa; は、分かりにくいが、aaa の内容を表示する、という意味だと思って欲しい。 他の言語だと、print aaa; と書くことが多い。この点 C++ は異質であることは 認める。
428:デフォルトの名無しさん
21/11/26 04:15:36.11 FqYYA0QW.net
>>417
Rustでは、標準 Cursorでは、読み、書き、削除を出来る参照を同時に持つことは出来ない。
C、C++、Java、C#では、
ll.RemoveAt(p2); // p2 のノードを削除。
もアクセス自体は1クロックで出来るし、今示したコードの好きな場所に
追加しても何の問題も無い。
p2は削除されているからアクセスできなくなるだけで、
他のポインタの値は変更されないので、それ以外は何もしなくても
そのままで良い。
429:デフォルトの名無しさん
21/11/26 04:16:36.76 FqYYA0QW.net
>>417
良く確認してくれ。
RustのCursorは、順番に辿ることはできるが、読み込みと書き込みと削除が
出来るタイプの参照を同時に複数記憶することは出来ない。
430:デフォルトの名無しさん
21/11/26 04:18:59.29 r6ugNRE0.net
>>419
標準(std)のLinkedListならそれはそう
前にも言ったような気がするが、
自前で作って内部構造にunsafecellを使えば、
不変参照を複数持っている状態でも書き換えが可能になる
例えば要素の追加時にそういうことをするカーソルを返せばよい
実装がめんどくさすぎるのは認める
431:デフォルトの名無しさん
21/11/26 04:19:23.54 FqYYA0QW.net
>>420
もっと言えば、C、C++、Java、C#の LinkedListは、
p2 の直後に「じゃがいも」ノードを追加した後、
p4 の直前に「トマト」ノードを追加するなどと言ったことも、
O(1)で出来る。しかも、O(1)と言っても、極限的に速くて、
C、C++の場合は、アクセスには1クロック。
こういうことが、Rustでは、Cursorを使っても出来ない。
432:デフォルトの名無しさん
21/11/26 04:23:10.27 FqYYA0QW.net
>>421
>>257のように、遅くするつもりなのか。
1ノードのアクセスに20～50クロックくらい掛かるが。
しかも、ダングリングポインタ、つまり、削除後にアクセスしてしまう
減少を防ぐことが出来なくなってるぞ。
433:デフォルトの名無しさん
21/11/26 04:25:26.12 r6ugNRE0.net
>>423
アンセーフ前提だから>>257とは全然違う
ダングリングも当然防げない（でもそれは他言語でもそう
434:デフォルトの名無しさん
21/11/26 04:29:37.41 FqYYA0QW.net
>>424
>>257 の実装でもそうだが、まだノードAに対する参照がどこかに残っている状態で、
ノードAの中身を削除できて、ノードAが使っていた要素を新規作成ノードのために
使用されてしまうね。
435:デフォルトの名無しさん
21/11/26 04:42:30.98 FqYYA0QW.net
>>420
[RustのCursorの補足]
・書き込み用のCursorを1個でも作ると、読み込み用のCursorは作れない。
はずだ。難しすぎてちゃんと理解して無いことは認める。
436:デフォルトの名無しさん
21/11/26 04:49:17.40 FqYYA0QW.net
>>421
std::cell::UnsafeCell なるものがあるのか。
Rustの参照は種類が多すぎ。
学んでも学んでもキリが無い。
しかも、1つずつをちゃんと理解するのが難しい。
437:デフォルトの名無しさん
21/11/26 09:55:21.11 5+U4u14D.net
>>404
Pathといってもこちらから使うだけならAsRef<Path>だからStringと&strでも全く問題なくOsStringの存在すら知らなくていい
したがって出てくるのはDirEntryのみとなる
それも周り全てUTF8環境ばかりなのでinto_string()で全てSome(String)になるため結局OsStringを扱ったことは一度もない
438:デフォルトの名無しさん
21/11/26 10:08:20.18 5+U4u14D.net
ミスったｗ
ResultのOk(String)ね
439:デフォルトの名無しさん
21/11/26 12:12:39.51 Ye0bskEh.net
>>428
いやいやせっかく標準ライブラリがWindowsでも動くよう苦労してくれてるのにそれを台無しにするなよ
個々のアプリで雑に対処するならともかくRust擁護派がRustの強みを否定してどうする
あと Path::file_name も Option<&OsStr> 返すしこれは利用頻度高い
440:デフォルトの名無しさん
21/11/26 20:45:27.01 MbvsChzk.net
>>430
Rustはちゃんと考えられてるね
ただし自分はWindowsを使うことは100%ないから path.file_name().unwrap().to_str().unwrap() 等でいいし
他にも use std::os::unix::fs::MetadataExt して metadata.uid() 等することもある
441:ハノン
21/11/26 21:02:52.31 xSrpn+m5.net
>>411
リンクリストや広く一般的なデータ構造の空間的・時間的オーダーを語る場合には
ノードの追加
ノードの検索
すでに取得している指定ノードの削除
あたりを考えるのが普通ですが、
「一度取得したノードの再アクセスコスト」を特に取り上げて考えるというのは、確かに rust の特殊性を示しているものといえそうですね…
>>413
生まれてきてすみません…
442:デフォルトの名無しさん
21/11/27 13:14:46.65 Y9o/DNQu.net
>>432
また、話を混乱させている。
指摘していることが、全く的を外しているから。
443:デフォルトの名無しさん
21/11/27 13:16:38.57 Y9o/DNQu.net
ちゃんと正確に議論されているのに、最後の最後でQZがめちゃくちゃな
ことを言い出す。それが最後に書かれたことによって、このスレに
後から来た人には「まとめ」の様に見えてしまうから、大迷惑。
全くまとめになってない、でたらめなことを書くから。
444:デフォルトの名無しさん
21/11/27 13:19:47.46 Y9o/DNQu.net
ようは、秀才達が集まっているクラスで、一人だけレベルの低い人がいて、
秀才達が大体理解したのに、「まとめ」として、レベルの人が全く
デタラメなことを話す。それがQZ。
クラスの場合、みんなの雰囲気でQZがレベルが低いことが分かるので呆れられ、
無視され、せせら笑いが聞こえるが、ネットだとそれが分からないから困る。
現実世界では言葉にしなくても、ひそひそ場なしや、せせら笑いなどで分かるが
ねっとではそのような言外のコミュニケーションが出来ないから。
445:デフォルトの名無しさん
21/11/27 13:22:32.48 Y9o/DNQu.net
>>435
どうせ、QZは、この文書の誤字脱字を発見して馬鹿にするんだろう。
誤字訂正:
誤:レベルの人が全く
正:レベルの低い人が全く
誤:ひそひそ場なしや
正:ひそひそ話や
誤:ねっとでは
正:ネットでは
446:デフォルトの名無しさん
21/11/27 17:31:40.13 v9cw8FEl.net
4レスも使って成果物も作れない評論家様はそびえ立つクソだからなぁ。
>>432のまとめが嫌なら、中身のない4レスのうち1レスを使ってご立派なまとめぐらい書き込んだら？
447:デフォルトの名無しさん
21/11/27 17:48:27.29 d/xEnnZB.net
たしかに4レスも使って人格批判しかしてね～
448:デフォルトの名無しさん
21/11/27 19:00:17.29 tDXnKU/S.net
ID:Y9o/DNQu
こいつがまとめを書けば話は終わりだな
449:デフォルトの名無しさん
21/11/27 19:39:40.61 SLaQ3CeJ.net
あわしろ氏はC++は使わないほうが良いと言ってる。
450:デフォルトの名無しさん
21/11/27 20:00:10.09 WDqbhltk.net
C++をあまり使用してなさそうなよくわからないあわしろ氏でなく自分の意見出しなよ
451:ハノン
21/11/27 20:25:46.13 bCVlBsXA.net
>>433
すみません
>>434-436
生まれてきてすみません…
452:デフォルトの名無しさん
21/11/27 21:09:50.54 riEP2Tv6.net
>>434 >>442
お二人方どちらでもいいから
具体的に削除でダングリングが発生しないCかC++のO(1)コードを示してよ
それが示せない限り机上の空論
もしコードが示されれば対応するRustのコードを出します
453:デフォルトの名無しさん
21/11/27 22:07:53.33 kID5mUHa.net
オブジェクトのアドレスをハッシュテーブルで持たせて、双方向リストで実装。
454:ハノン
21/11/27 22:11:02.52 bCVlBsXA.net
>>443
＞具体的に削除でダングリングが発生しないCかC++のO(1)コードを示してよ
>>432
＞「一度取得したノードの再アクセスコスト」を特に取り上げて考える
という、他ではあまり聞いたことのない特殊な話ゆえに筋を深く追えていないのですが、
>>432
＞
455:リンクリストや広く一般的なデータ構造の空間的・時間的オーダーを語る において ① ＞すでに取得している指定ノードの削除 でいいですか？ ② データ構造は一方向リストでいいですか？
456:デフォルトの名無しさん
21/11/27 22:20:41.20 g2vJAoph.net
>>445
一方向だと削除がO(1)じゃないから双方向が良いのでは
457:ハノン
21/11/27 23:03:04.21 bCVlBsXA.net
>>446
それは末尾または冒頭ノードの削除の話ですね
何が与えられていて、何を削除するのか、きちんと定義していただきたいです
458:ハノン
21/11/27 23:04:36.52 bCVlBsXA.net
>>446
失礼、あるいは特定ノードの上流ノードの探索の話もありますね
確かに双方向の方が楽チンですが、「ダブルポインタ」を使えば単方向でも処理できないわけではないです
459:デフォルトの名無しさん
21/11/27 23:42:34.01 +ONNbmgV.net
スマンが、余り言いたくないことだが、QZが出てくると話がとてもややこしくなる。
460:デフォルトの名無しさん
21/11/28 00:05:23.91 L/jojvYG.net
まだやってたのか
461:ハノン
21/11/28 02:32:25.17 DhOI6JvL.net
>>449
当然でしょう
>>432
＞リンクリストや広く一般的なデータ構造の空間的・時間的オーダーを語る場合には
＞ノードの追加
＞ノードの検索
＞すでに取得している指定ノードの削除
＞
＞あたりを考えるのが普通
なのに、
>>445
＞＞「一度取得したノードの再アクセスコスト」を特に取り上げて考える
＞という、他ではあまり聞いたことのない特殊な話
を延々とやっていることに噛み付いているのですから
さて実装実装…
462:デフォルトの名無しさん
21/11/28 02:39:16.73 Fw4ypgsa.net
それがこのスレの目的ですから
463:デフォルトの名無しさん
21/11/28 03:42:41.88 sDAG0wCq.net
ある特定のエントリーを持つ変数はプログラム中に複数存在しうると議論中にも出ていたから
リファレンスカウンタは必須になるな
重要な点としては
コンストラクタやデストラクタやスマートポインタに隠れて曖昧にならないように
それらを使わずに実装すべきだ
そもそもC言語でもO(1)という話なのだから
まずはC言語かつ標準ライブラリのみ使用が今回のコード条件
464:ハノン
21/11/28 04:07:17.98 DhOI6JvL.net
>>453
ん？アンカーで示してください
今回はリファレンスカウンタは実装に含めないつもりです、まあ C で書くつもりですけど
465:デフォルトの名無しさん
21/11/28 10:45:19.29 tHJVymxJ.net
もうソース出せって意地悪言わないで、無視しときなよ
配列に格納し直すのが彼のアイデアの全てなんだから、つついても面白い話は出てこないよ
O(1)で追加・削除できる配列も作れる！って言い出したら、多分リンクリストを使うってことだよ
466:ハノン
21/11/28 14:56:23.04 DhOI6JvL.net
>>443
ｽﾚﾘﾝｸ(tech板:105番)
これでいかがでしょうか？
467:デフォルトの名無しさん
21/11/28 17:32:59.07 4++rc1oJ.net
>>443
C/C++では、ダングリングが発生するのを防ぐのはプログラマーの仕事だ。
468:ハノン
21/11/28 17:39:38.36 DhOI6JvL.net
>>443
引き続いて双方向リストの場合
ｽﾚﾘﾝｸ(tech板:106番)
これでいかがでしょうか？
>>444
＞オブジェクトのアドレスをハッシュテーブルで持たせて、双方向リストで実装。
では C で実装願いますね
私は宿題を片付けましたので 、ちゃんちゃん
469:デフォルトの名無しさん
21/11/28 17:42:46.59 4++rc1oJ.net
>>451
>>432では、あなた、そういうこと書いてなかったよね。
こういう議論でははっきり言わないと分からないよ。
でも、あなたの観点は間違ってる。
C/C++/Java/C# においては、リンクリストで、一度作成したノードのアドレスは
ずっと保存するのが基本で、「先頭からの通し番号」で「辿る」ということは効率
が悪すぎて特殊なケース以外ではしないから。
470:ハノン
21/11/28 17:47:22.55 DhOI6JvL.net
>>459
もうリンクリストなんか不要で、最初からハッシュテーブル一本でやっていくべきなのでは？
なんでリンクリストとハッシュテーブルを両方使うのですか？
471:デフォルトの名無しさん
21/11/28 17:51:06.30 4++rc1oJ.net
>>460
ハッシュテーブルなんて全く使って無いぞ。
あなたはポインタの仕組みを理解して無いのか？
472:デフォルトの名無しさん
21/11/28 17:54:05.88 4++rc1oJ.net
QZは、ポインタが 1 クロックでどんな場所にもたどり着けることを理解出来て無い
のではないか。
アドレスさえ分かっていれば、1クロックであらゆるオブジェクトにたどり着けるぞ。
基本的にハッシュ構造とは全く関係無い。
473:ハノン
21/11/28 17:58:02.00 DhOI6JvL.net
>>461
失礼、>>444 とは別の方なんですね
でも、
＞C/C++/Java/C# においては、リンクリストで、一度作成したノードのアドレスは
＞ずっと保存するのが基本で、「先頭からの通し番号」で「辿る」ということは効率
＞が悪すぎて特殊なケース以外ではしないから。
それはそうです、リンクリストを頭から舐めるのは効率がイマイチなのはおっしゃるとおり、単純な構造だからそれはしかたがない
しかし、
＞リンクリストで、一度作成したノードのアドレスはずっと保存する
って、どこにどういう形で保存するのです？
474:ハノン
21/11/28 17:59:56.44 DhOI6JvL.net
>>462
＞QZは、ポインタが 1 クロックでどんな場所にもたどり着けることを理解出来て無い
＞のではないか。
>>456, >>458 で示した程度には理解しているつもりです
＞アドレスさえ分かっていれば、1クロックであらゆるオブジェクトにたどり着けるぞ。
で、そのアドレスをどのように管理するのですか？どのような形でどのようなデータ構造に格納するのですか？C/C++ で説明いただくと助かります
475:デフォルトの名無しさん
21/11/28 18:32:54.89 Izo/gJUY.net
>>463
>＞リンクリストで、一度作成したノードのアドレスはずっと保存する
>って、どこにどういう形で保存するのです？
・リンクリスト全体のノードを辿ればいい場合には保存する必要が無い。
なお、その場合、1ノード右側のノードのアドレスを取得するのは1～2クロック
しかかからない。
・例えば、1000個のノードが入っている場合の、特定の 2 個のポインタを
保存したい場合には、グローバル変数の2つのポインタにそれぞれの
アドレスを代入しておけばよい。
それは丁度、ArrayList(vector)の場合であれば、添え字番号を2つの整数
変数に代入しておくのと全く同じこと。
・要は、ノードを識別するための数値が、配列では整数型の添え字番号であったところが、
リンクリストでは、ポインタ型のアドレスになるというだけのこと。
決して後者に置いては、通し番号を使ってはいけない。
数学的には、次のような双対関係の様なものが存在していると考えられる:
（配列, 添え字) <---> (リンクリスト, アドレス)
QZを含めて、この双対関係を理解できておらず、
（配列, 添え字) <---> (リンクリスト, 添え字)
と間違って理解してしまっている人が多いことから、リンクリストでのランダムアクセス
が O(N)などと謝った認識に至ってしまう人が多いと考えられる。
しかし、正しく双対関係を理解すれば、O(1)であることが理解できよう。
476:ハノン
21/11/28 18:40:36.55 DhOI6JvL.net
>>465
結論から申し上げれば、ここはプログラム板だから、適切なお題を設定してプログラムで例示いただけませんか？
＞リンクリストでのランダムアクセス が O(N)などと謝った認識
いいえ、リンクリストの各ノードのアドレスは、リンクリスト内で調達するのならば、O(N) でしか取得できないものですよ
あなたはリンクリスト以外の何か別のデータ構造を使ってリンクリストのアドレスを管理しようとしているようですが、
ならば、もうリンクリストなんか最初から止めちまえばいいのじゃないでしょうか？
477:デフォルトの名無しさん
21/11/28 18:50:25.63 Izo/gJUY.net
>>466
あなたはやはり馬鹿だな。
それをいうなら、配列も同じ。
配列の添え字番号を覚えておくのに、別の配列が必要になる。
お分かりかな？
あなたは、双対を全く理解出来て無い。
478:デフォルトの名無しさん
21/11/28 18:53:09.31 uSmUEadq.net
>>465
それってリンクリストの意味ある？
なんのためにリンクリストにするんだ？
479:デフォルトの名無しさん
21/11/28 18:57:11.39 pGvlrRKC.net
Linked Listを使っているのにLinkを辿りたくないらしい
480:デフォルトの名無しさん
21/11/28 18:58:57.15 uSmUEadq.net
アドレス保持してればなんでもランダムアクセスできるっていうなら
あらゆるデータ構造がランダムアクセス性を持つということになってしまうな
481:デフォルトの名無しさん
21/11/28 19:16:56.34 /zln3poJ.net
>>466
Qちゃんお疲れ
> あなたはリンクリスト以外の何か別のデータ構造を使って
> リンクリストのアドレスを管理しようとしているようですが、
> ならば、もうリンクリストなんか最初から止めちまえばいいのじゃないでしょうか？
それは色んな人がわりと最初のころから既にツッコミ済みなのだよ…
ようやく議論に追いついたねキミは
482:デフォルトの名無しさん
21/11/28 19:42:21.78 1e4/tv+M.net
>>470
実際、C言語などから高級言語にポインタの概念が入ってからはそうなった。
ただ、Rustはそうなって無いから問題なんだよ。
483:デフォルトの名無しさん
21/11/28 19:42:59.18 ZOlCZyFx.net
>>462
ポインタの指す領域に1クロックでアクセスできるCPUなんてあるんですか？
ポインタの指す先がメモリにあるかキャッシュにあるかで異なりますがL1キャッシュにあっても数クロックかかるのではないかと思います
数クロックを争うような話をするなら実装がないと話にならないと思うので、まずは比較したい書く言語の実装を用意しましょうよ
既存のコードへのリンクで良いので
484:デフォルトの名無しさん
21/11/28 19:43:39.06 1e4/tv+M.net
やっぱり、数学が出来ない人は、双対の概念に脳が追いついてこないらしい。
双対という言葉の意味が分からなくても、生まれつき頭のいい人なら、
俺の言っている意味がわかるはずだ。
485:デフォルトの名無しさん
21/11/28 19:44:13.37 1e4/tv+M.net
>>473
キャッシュに載っていたらの話だ。
486:デフォルトの名無しさん
21/11/28 19:44:50.23 ZOlCZyFx.net
>>472
任意のアドレスへのアクセスは本質的にunsafeだと思うのですが、safe rustでそれができないことにどのような問題があるのですか
487:デフォルトの名無しさん
21/11/28 19:45:41.68 ZOlCZyFx.net
>>475
リンクリストは参照局所性が悪いのでキャッシュに載っていない確率が大きいのですが、本当に高速なのですか？
488:ハノン
21/11/28 19:59:16.91 DhOI6JvL.net
>>474
双対性にもいろいろありますよね…論理学上の双対命題（∩と∪、∀と∃の入れ替え）ならばその否定が証明できますが、そういう意味ですか？
それとも正十二面体と正二十面体の双対性ですか？
適当にペアにして双対と呼んでいるだけなのでは？
489:ハノン
21/11/28 20:01:48.12 DhOI6JvL.net
>>471
そうなんですね…
490:ハノン
21/11/28 20:10:07.08 DhOI6JvL.net
>>473
いや、突っ込みどころはそこではなくて、
「あるときは O(f) ランダウのオミクロンで話をしたかと思うと、次の瞬間、クロック数を問題にする」というバラバラな論理展開でしょう
ランダウでやるんだったら最後までランダウで統一してほしいのですが…
491:デフォルトの名無しさん
21/11/28 20:33:56.21 tN4i8A7m.net
>>480
ランダウ記号は、大まかな分類しか示せない。例えば、
O(N)は、N→∞ の時に、
O(N)/N < α (alpha)
のように有る正の実数αによって、「抑えられる」という意味しか示せないし、
O(1) < α (alpha)
であることしか意味しない。
だから、O(1)であることよりも、1クロックであることの方がずっと意味が強い。
なので、ちゃんと1クロックであると分かっているなら1クロックと書いた方がいい。
492:ハノン
21/11/28 20:51:47.55 DhOI6JvL.net
>>481
ある数量に対応する空間的・時間的コストの依存状況を滔々と語っていたかと思うと、次の瞬間は実時間に関する話に都合のいいように鞍替えするのは論理的でない、といっているのです
実時間なら実時間、依存関係なら依存関係できっちり話をわけてほしいですね
493:デフォルトの名無しさん
21/11/28 20:59:23.99 tN4i8A7m.net
>>482
悪いが、お前が馬鹿なだけだ。
数学的には、O(1)と書くこともあれば、実クロックで書くこともあり、
混ぜたらいけないなんてことは無い。
ちゃんと理解していれば、混ぜても問題ない。
494:ハノン
21/11/28 21:06:52.79 DhOI6JvL.net
>>483
「数学的」の定義を伺いたいものですが、それはさておき、実クロックなんて「おま環」な話をしても仕方がない場合も多いのですよ
今はキャッシュのヒット率で処理速度も大きく変わるから、実クロックによる考察なんてほとんど無意味です
しかしデータ数等の「ある数量」に対する時間的・空間的コストの評価ならば、それは、どの環境にもっていっても通用する、すなわち適用範囲が広いのです
何か評価をしたいのなら、広い環境で通用する評価方法の方が有用でしょう
あなたは、その二つの評価方法の意義の違い（「どちらが有意義か」）を知らないから「混ぜたらいけないなんてことはない」などとシレっといえるのですよ
495:デフォルトの名無しさん
21/11/28 21:14:34.22 tN4i8A7m.net
>>484
そうじゃないんだ。実際のクロック数の事ではなくて、マシン語で書いたときに
1命令だということなんだ。
496:デフォルトの名無しさん
21/11/28 21:17:54.80 tN4i8A7m.net
キャッシュの話なんかは状況が複雑すぎて議論を複雑にするだけで、本質を理解する
邪魔になる。
まず、それは横に置いておいて、基本を理解しないといけない。
キャッシュの影響についてはその次。
また、なら、最初から「1命令」と書いておけば良かったのに、という突っ込み
が予想されるが、1命令でも乗算命令なんかは13クロック(レイテンシ)以上かかるから
それとは区別するために1クロックと書いた。
キャッシュは複雑すぎて話が混乱するだけ。
ポインタを介してのアクセスが1～2クロックなのは、今のx86系だとアーキテクチャに
依存せず必ず言えることだから、そう書いた。
497:ハノン
21/11/28 21:20:07.26 DhOI6JvL.net
>>485
命令数なんてもっと当てにならないですよ、内部で別形態に変換され並列に実行されたりするわけで、人手で最適化することは不可能なしろもの
そんな制御できないものを評価対象にしてもしかたがないのでは？
498:ハノン
21/11/28 21:25:24.33 DhOI6JvL.net
>>486
＞ポインタを介してのアクセスが1～2クロックなのは、今のx86系だとアーキテクチャに
＞依存せず必ず言えることだから、そう書いた。
残念ですがキャッシュにヒットするかしないかで大きく実行時間は変わりますね、キャッシュにヒットせず、RAM 空間上から引っ張ってくる場合は数十クロックは必要でしょうね…
そんな「お前の環境でしか通用しない話だろう」的な曖昧な評価方法よりも、どの環境でも通用するランダウのO記号による評価の方が有意義でしょう
どちらの方が有効範囲が広い有意義な評価法なのかを知らないから、ちゃんぽんにして話をしても不自然さを感じないじゃないですか、あなたは？
499:デフォルトの名無しさん
21/11/28 21:26:27.36 tN4i8A7m.net
>>487
そうでなくて、Rustでも、O(1)というものだけなら、作ろうと思えば作れるから
1クロックと書かざるを得なくなったんだよ。
Rustの場合は、O(1)でも、単なるポインタでは無く、配列を介すので、
乗算、足し算、境界チェックが入ってしまうのでトータルで20～50クロック
くらい掛かる。このうち、境界チェックだけは外せるかも知れないが。
500:デフォルトの名無しさん
21/11/28 21:27:53.03 tN4i8A7m.net
>>488
>>489 を見ろ。
「なぜあなたは文脈を考えて書かないんだ」
と はちみつ餃子にも指摘されてただろ。
501:ハノン
21/11/28 21:30:30.36 DhOI6JvL.net
>>489
＞乗算、足し算、境界チェックが入ってしまう
C/C++ の配列とても乗算・足し算は入りますよ…
そんな瑣末な話とO(1), O(N) の話をちゃんぽんにしても不自然さを感じない感性に私は大いに疑問を感じます
502:ハノン
21/11/28 21:34:48.65 DhOI6JvL.net
>>490
よくご存知ですね…
まあ、今日は基本的なデータ構造を基本的な言語を使用して白紙からコーディングする機会を下さったあなたには感謝してますよ、久々に脳細胞を使ったのでちょっといい気分です
503:デフォルトの名無しさん
21/11/28 21:40:43.94 tN4i8A7m.net
Cの場合のリンクリストのポインタを介してのアクセスは、
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の場合とは
雲泥の差である。
504:デフォルトの名無しさん
21/11/28 21:42:26.92 8j2GjV45.net
俺は Rust 書けない C++ マンだけど、双方向リンクリストのサンプルコードを書いてみた。
Rust で insert, remove 操作を O(1) で実装可能かどうかが論点ですよね？
リストの要素数に関わらず insert, remove 操作を固定計算量で実行可能であればそれは O(1) です。
URLﾘﾝｸ(wandbox.org)
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;
}
505:デフォルトの名無しさん
21/11/28 21:43:21.57 tN4i8A7m.net
>>491
お前はアホか。
リンクリストの場合は、乗算が入らないんだよ。
>>493
ミス訂正:
配列の場合は、
mov ebx,index ;添え字番号
imul ebx,配列のバイト数
mov eax,[ebp+ebx+32] ;32はスタックの中での位置
従って、リンクリストの方が一般的にはアクセスが速い。
リンクリストは、1クロック位、配列の場合は、要素が一般のバイト数の場合は、
14～36クロック位。
506:デフォルトの名無しさん
21/11/28 21:47:47.53 tN4i8A7m.net
>>494
>Rust で insert, remove 操作を O(1) で実装可能かどうかが論点ですよね？
そうじゃない。
Rustでも、insert, remove 自体は、標準実装でも O(1)で行える。
ところが、アクセスが、標準実装では、借用規則のために複数の
読み書きポインタを永続的に保持することが出来ないので、ノードの位置を
先頭からの通し番号で覚えておいて、アクセスするたびに毎回先頭から
辿る必要があるため、O(N)かかる。
特殊な独自実装をすると、アクセスがオーダー的にはO(1)で出来るが、
特殊実装な故に、>>493 の後半のようになってしまい、
20～50クロック位かかる。
507:ハノン
21/11/28 21:49:24.66 DhOI6JvL.net
>>494
読みました
私の場合は双方向リストを循環させ、始点のみをポイントすることとしましたが、結果として記述はあまり簡単にはならなかったですね、うーむ
508:デフォルトの名無しさん
21/11/28 21:56:03.25 tN4i8A7m.net
すまんが、馬鹿に何言っても理解されない。
疲れるだけだということが分かった。
509:デフォルトの名無しさん
21/11/28 21:56:11.42 tN4i8A7m.net
すまんが、馬鹿に何言っても理解されない。
疲れるだけだということが分かった。
510:デフォルトの名無しさん
21/11/28 21:56:13.54 tN4i8A7m.net
すまんが、馬鹿に何言っても理解されない。
疲れるだけだということが分かった。
511:デフォルトの名無しさん
21/11/28 21:57:51.47 8j2GjV45.net
remove メソッドにバグがあった (head, tail を更新していなかった) ので一応修正。
URLﾘﾝｸ(wandbox.org)
>>496
なるほど。アクセス時に通し番号的な物が必要になるのであれば
insert, remove 操作時にもその通し番号を振り直す必要があるので、O(1) では実現できない気がします。
>>497
双方向リンクリストは始点と終了をペアで持つという固定観念があったので、その発想はなかったです。
512:デフォルトの名無しさん
21/11/28 22:02:54.87 tN4i8A7m.net
>>501
>なるほど。アクセス時に通し番号的な物が必要になるのであれば
>insert, remove 操作時にもその通し番号を振り直す必要があるので、O(1) では実現できない気がします。
先頭や末尾では無い途中のinsert、removeであれば、あなたの言うとおり。
追加する直前のノードにたどり付くまでに一般的にはO(N)の時間が掛かる。
ただまあ、末尾追加や先頭追加と、末尾削除、先頭削除なら、RustでもO(1)で
出来るだろう。
なお、Cursorを使えば、よくあるケースだけは高速に行えるようになっているかも知れないが。
あくまでも良くあるケースだけは、unsafeを使って特別対応しているだけ。
複雑な一般的なケースでは、やはり、O(N)かかってしまう。
その意味で、あなたの言っていることは正しい。
513:デフォルトの名無しさん
21/11/28 22:13:58.18 uBLcCIA8.net
いつまで例のVecを使った謎LinkedList実装にこだわっているのだろう
514:デフォルトの名無しさん
21/11/28 22:17:12.75 tN4i8A7m.net
>>503
こだわっているというか、あれは、オーダー的にはCと同じく、ほとんど全ての
動作をO(1)で出来てしまうリンクトリストをRustでも出来ているから、
注目に値する。
ただし、O(1)と言っても、実際には遅い。
また、Read After Delete、ダングリングポインタに相当するものがRustでも
生じる。たとえ、safeモードで書いても。
515:デフォルトの名無しさん
21/11/28 22:20:39.78 qezuw3R9.net
なんでRustだけsafe前提なんすか？
516:デフォルトの名無しさん
21/11/28 22:21:32.31 uBLcCIA8.net
>>504
要素追加でバッファ超えると配列全体をコピーするけどO(1)なんだ？
いいのかそれで？
517:デフォルトの名無しさん
21/11/28 22:26:36.40 tN4i8A7m.net
>>505
Rustはそれを売りにしてるからだよ。
C/C++は最初から諦めてる。
>>506
その指摘は正しい。
平均的にはO(1)だが、スパイク状に(不定期に)O(N)のコピー動作が入ってしまう。
518:ハノン
21/11/28 22:29:15.25 DhOI6JvL.net
>>501
私のやり方でよかったことは、prev/next の無矛盾性のチェックが簡単に書けることくらいでした、他は複雑になってしまった…
519:デフォルトの名無しさん
21/11/28 22:50:50.98 qezuw3R9.net
>>507
売りにしてるいうても結構厳しい制限だからデータ構造に直結するようなコードはsafeのみじゃ無茶だぞ
連結リストのようにユーザ側もダングリングとか多重参照とか気をつけなきゃいけないタイプのものは、
safeの範囲じゃ回りくどいことやるハメになるか、そもそも本当に無理になるかだ
520:デフォルトの名無しさん
21/11/28 22:53:17.54 Z9Xk/5kf.net
>>496
>ところが、アクセスが、標準実装では、借用規則のために複数の
>読み書きポインタを永続的に保持することが出来ないので、ノードの位置を
>先頭からの通し番号で覚えておいて、アクセスするたびに毎回先頭から
>辿る必要があるため、O(N)かかる。
そうなんだ
でもこれってC/C++でもメモリ安全で、スレッドセーフとかにしたら同じにならん？
521:デフォルトの名無しさん
21/11/28 22:59:54.62 hrke4Ba5.net
自分はがんばって数学の勉強をしてきたので自分の考えは絶対に正しい、間違うはずがないと思いこむ。
そうなると一度間違った考え(リンクドリストの任意の要素にO(1)でアクセスできる)を持ってもそれを間違った考えとは気づかずにその間違いを補強するようなチグハグな考え方をするようになる。
反ワクチンのようなトンデモ科学にはまっちゃう人に周囲の人がいくら正しい科学知識で説得しても自分の考えに疑問を持つどころか、自分の考えは絶対に正しい、周りのやつらは頭がおかしいと思いこんでしまう。
自分の考えが間違うこともあるのではないかと謙虚になることも重要だということだね。
522:デフォルトの名無しさん
21/11/28 23:00:17.08 j8Nrs0jp.net
まずポインタで持てば1クロックは明らかに嘘
今後はクロックという言葉を使うのはやめなさい
次にポインタで持てばリンクリストはO(1)も明らかにおかしい
例えばハッシュテーブルもバイナリツリーもO(1)になってしまう
523:デフォルトの名無しさん
21/11/28 23:03:08.30 tN4i8A7m.net
>>510
Cの場合、リンクリストは経験的に言えば、簡単に扱えるので結構安全。
すっきり分かり易いので安全になる。動作が素直だし。
むしろ、途中削除、途中挿入した場合、配列の方が扱いが難しい。
リンクリストは他のノードのアドレスが変わらないのでポインタの値は
変化させなくて良いが、配列の場合は操作をしたノードより後ろに
有るノードの添え字番号がずれてしまうため、そのたびに
管理番号を付け替えるようなことが必要になってしまい、
データ構造が複雑な時に管理がとても大変になる。
リンクリストだとそのような手間が要らないので便利。
ただし、(配列, 添え字) <--> (リンクリスト, アドレス) の双対関係
は常に念頭に置いておく必要がある。後者は基本的には決して
添え字(通し番号)を使ってはいけない。なぜなら、それは後者においては、
ID値としては使えないから。
ただそもそも配列は、添え字はID値としては不十分というか、配列には絶対不変の
ID値が存在しない。リンクリストはアドレスが絶対不変のID値として使える。
524:デフォルトの名無しさん
21/11/28 23:04:35.17 tN4i8A7m.net
>>511 >>512
まずは、
525:r> (配列, 添え字) <--> (リンクリスト, アドレス) の双対関係を理解しよう。 これが理解出来て無い人は、リンクリストの本来の性能も、本来の使い方も 出来ない。
526:デフォルトの名無しさん
21/11/28 23:05:48.98 tN4i8A7m.net
>>511
俺は頑張って勉強したから数学が得意だったのではない。
テキトーにやってただけで、出来た。
527:デフォルトの名無しさん
21/11/28 23:05:52.69 Fw4ypgsa.net
そういうの双対って言わないから……
528:デフォルトの名無しさん
21/11/28 23:08:15.36 j8Nrs0jp.net
じゃあハッシュテーブルもエントリーアドレスでアクセスできるからO(1)と言い出す気か？
529:デフォルトの名無しさん
21/11/28 23:11:15.41 tN4i8A7m.net
>>514
[補足]
要は、「配列の世界」と「リンクリストの世界」では、世界自体が別物なので、
要素/ノードを識別する手段も違い、前者は添え字番号、後者はアドレスが基本量となる。
従って、リンクリストでは、ノードを識別するには、必ずアドレスを使うことが基本。
それが最も自然であり、高速であるから。
いつまでも、添え字番号で識別する方法しか理解できない人には、言っている意味が理解できない
だろう。
電気と磁気にもさまざまな双対関係がある。世界がある種の対称になっているから、
その際に、正確に対応する量を入れ替えてやら無ければならない。リンクリストでは
通し番号ではなくアドレスを使う。
そうしないと公平ではない。
530:デフォルトの名無しさん
21/11/28 23:11:50.99 tN4i8A7m.net
>>516
双対の定義は、独自に決めてよい。
531:デフォルトの名無しさん
21/11/28 23:13:05.79 tN4i8A7m.net
>>517
はあ？
ハッシュテーブルは、実質的にO(1)にとても近い速度で検索できるから
使われているんだが。
532:デフォルトの名無しさん
21/11/28 23:16:38.50 sDAG0wCq.net
>>514
それは嘘だと誰でもわかる
リンクリストの個別要素のアドレスに対応するものは配列の個別要素のアドレスでありハッシュマップの個別要素のアドレスである
そしてアドレスを持てばO(1)とトンデモを言い出すならば全てのデータ構造がO(1)となる
つまりリンクリストのO(1)は嘘
533:デフォルトの名無しさん
21/11/28 23:18:09.73 Z9Xk/5kf.net
>>513
>Cの場合、リンクリストは経験的に言えば、簡単に扱えるので結構安全。
>すっきり分かり易いので安全になる。動作が素直だし。
そんなに簡単だとかいうなら、試しに実装を見せてほし・・・
534:デフォルトの名無しさん
21/11/28 23:25:05.70 tN4i8A7m.net
>>521
お前が生徒だったら0点つけてやる。
そもそも、動的配列は要素数が内部容量を超える時にアドレスが時々変わって
しまうから、ID番号として基本的にアドレスは使えない。
それをすると、末尾追加するだけでも、定期的にID番号が変わってしまうので
その際にID番号として使っているアドレスを全部修正しないといけなくなるから。
しかし、アプリ内のID番号を全部修正するのは、効率免で良くない。
だから、配列だと要素の一番ましなID番号は添え字番号。
一方、リンクリストで最も効率の良いID番号は、アドレス。
しかも、リンクリストの場合、任意の場所への挿入、任意のノードの削除を
行っても、他のノードのアドレスは変わらないので、アドレスをID番号
として用いている限り、どんな操作をしてもID番号の修正が不要となる。
こんなによいID番号はないわけで、敢えて添え字番号をID番号に使うのは
不適切。
535:デフォルトの名無しさん
21/11/28 23:26:21.97 tN4i8A7m.net
>>522
Cの入門書で、リンクリストについて書いてあるもの読んで理解して、
頭が悪くなければ、そう自然に解釈できる。
根本的に馬鹿な人には無理かも。
536:デフォルトの名無しさん
21/11/28 23:38:14.43 ZOlCZyFx.net
rust は safe じゃなきゃ意味がない論者の人かな
537:デフォルトの名無しさん
21/11/28 23:43:54.48 tN4i8A7m.net
>>525
Cでは生ポインタ一個に対して、Rustは参照関連だけでも、20種類は下らないほど
色々な複雑な仕組みがあるのは、全て safe のためであるのに、safeでなくなったら
それこそCの圧勝になるが。
538:デフォルトの名無しさん
21/11/28 23:48:12.68 qezuw3R9.net
>>526
コーディングはゲロのようにめんどくさくなるが、
速度面では別にCにそう負けるもんではない
多分最適化しきれなくてほんのちょっと遅くなる部分はありそうだが
539:デフォルトの名無しさん
21/11/28 23:48:45.22 tN4i8A7m.net
>>477
それは、実はリンクリストも十分に局所性が有る。
というのは、追加するときには、リンクリスト全体のごく一部にバースト的に
挿入することが多いからだ。
そしてその時、ノードのアドレスは等間隔に並ぶ傾向が有るから。
540:デフォルトの名無しさん
21/11/28 23:49:16.38 tN4i8A7m.net
>>527
いや、今回の例では劇的に遅くなるケースがあるといってるんだ。
541:デフォルトの名無しさん
21/11/28 23:51:28.85 qezuw3R9.net
>>529
今回の例が何のことか把握してないが（QZが絡んでいるレスは読みづらすぎる）、
配列がどうたらとかの話なら別に配列なんていらんよ
542:デフォルトの名無しさん
21/11/28 23:52:03.44 j8Nrs0jp.net
結局この全員の合意とは無関係な些末な話ばかりだな
＞まとめ
＞・C/C++で記述できることは同じ安全度合いで常にRustでも記述できる
＞・そのうちほとんどのケースではRustだとメモリ安全性を保証する形で記述できる
＞・つまり言語としてC/C++よりもRustの方が優れている
543:デフォルトの名無しさん
21/11/28 23:53:36.07 tN4i8A7m.net
>>531
デタラメを何度も書くな。
544:デフォルトの名無しさん
21/11/28 23:55:06.43 j8Nrs0jp.net
>>532
もし反論があるならしてみたら？
545:デフォルトの名無しさん
21/11/28 23:58:27.96 qezuw3R9.net
極論だけど各メンバをUnsafeCellにしてunsafe使いまくれば、
shared XOR mutableルールぶち破れるから、
C/C++でできることはコーディングめんどくさくなるし安全性が結構悲しいことになるけど（でもCとかと同程度）
Rustでも不可能ってことはない
なんならCコードをRustコードに自動変換するやつすらあったような
成熟度は知らんが
546:デフォルトの名無しさん
21/11/28 23:58:30.48 tN4i8A7m.net
>>533
全て書いてるのに理解力が無いから理解できないだけ。
Rust信者は馬鹿ばかり。
547:デフォルトの名無しさん
21/11/29 00:02:50.56 g6qk7DwE.net
>>507
>Rustはそれを売りにしてるからだよ。
>C/C++は最初から諦めてる。
自分で C/C++ は安全じゃないから、って書いてるじゃん
それが結論でしょ
同じ安全性にしたら、同じになるだろ
548:デフォルトの名無しさん
21/11/29 00:05:09.36 HgRvzIV4.net
>>536
同じ安全性にする必要がない。
549:デフォルトの名無しさん
21/11/29 00:15:16.20 uM27l7Qv.net
前から別の人が指摘しているけど、
リンクドリストとは別に配列を用意してリンクドリストの要素へのアドレスを保持するからリンクドリストの任意の要素にはO(1)でアクセスできる
と主張しているが
そのリンクドリストに追加または削除するたびに配列の要素も追加か削除しないといけなくなる。
リンクドリストの任意の位置に追加/削除するのはO(1)だけど、配列の任意の位置に要素を追加/削除するのはO(1)じゃない。
だからリンクドリストと配列を組み合わせて使うとリンクドリストのメリット(任意の位置への追加/削除がO(1))が無くなってしまう。
その配列に静的配列を使うならリンクドリストの最大サイズを予想してあらかじめ大きな配列を用意しないといけない。
動的配列を使うな要素を追加したときにときどきヒープの再確保がおきる。
550:デフォルトの名無しさん
21/11/29 00:21:59.31 uYqg1Oz6.net
>>528
実際のメモリレイアウトがどうなるかは言語処理系のランタイムやlibcに依存すると思うのですが
例えば
551:どの言語のどの処理系のどのランタイムを使使えばそうなることが確認されているのですか
552:デフォルトの名無しさん
21/11/29 00:23:38.13 HgRvzIV4.net
>>538
配列 + リンクリストの代わりに、リンクリスト + リンクリストにすれば解決するぞ。
553:デフォルトの名無しさん
21/11/29 00:24:11.08 HgRvzIV4.net
>>539
malloc()の仕組みから言ってそう考えられる。
554:デフォルトの名無しさん
21/11/29 00:30:08.36 4MgUQE5v.net
>>534
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を用いている
555:デフォルトの名無しさん
21/11/29 00:39:59.63 zo5XubVi.net
>>541
最初の初期化時に（あまりフラグメンテーションが発生していない状態で）複数要素追加する以外に追加がほとんど発生しないっていう前提ならそうかもね
でも一般にそうじゃないから連結リスト使うんじゃないの？
556:デフォルトの名無しさん
21/11/29 00:42:22.65 xTtlotpf.net
さすがにおちょくって遊ぶのを見るのも飽きてきたが
557:デフォルトの名無しさん
21/11/29 00:45:55.70 DszBoyLu.net
あわしろ氏もC++は危険と言ってる。
558:デフォルトの名無しさん
21/11/29 00:55:31.86 27e/xIh/.net
>>541
参照局所性高めたいなら個々の要素ごとにmallocするのではなくarena的に割り当てすべきなのでは
>>543の言うとおり、フラグメンテーション発生してると何も保証できなくなる
559:デフォルトの名無しさん
21/11/29 00:59:52.29 4MgUQE5v.net
>>542でコードを示したように
C/C++で記述できることは同じ安全度合いで常にRustでも記述できる
したがって以下の合意事項は正しい
＞まとめ
＞・C/C++で記述できることは同じ安全度合いで常にRustでも記述できる
＞・そのうちほとんどのケースではRustだとメモリ安全性を保証する形で記述できる
＞・つまり言語としてC/C++よりもRustの方が優れている
560:デフォルトの名無しさん
21/11/29 01:00:10.18 HgRvzIV4.net
しかし、配列の場合は、内部バッファのサイズが拡張される時には全コピーが
発生するから、キャッシュが大規模に乱れてしまうがな。
その点、リンクリストは乱れたとしてもそこまででは無い。
561:デフォルトの名無しさん
21/11/29 01:03:19.07 HgRvzIV4.net
>>547
unsafe付けたら全体の安全性も失われるが。
メモリーの間違いには局所性がなくて原因箇所が分かりにくいからこそ、
Rustはメモリー安全に固執しているんだが。
逆にCはそもそもそれをユニットテストなどで徐々にテストしながら開発を進める
ことで確保する方針を採っている。
562:デフォルトの名無しさん
21/11/29 01:10:35.89 HgRvzIV4.net
リンクリストでのキャッシュの乱れと言っても、アドレスが大幅に異なるものが入り混じっても、
必ずしもペナルティーが増えるわけでは無いぞ。
例えば、2つの大幅にアドレスが異なるノードを交互にアクセスする程度では
キャッシュの読み込み直しは通常の連続アドレスにアクセスした場合に比べて
特に追加発生はしない。
キャッシュメモリ1種類の連続メモリブロックしか収められないわけでは無いからな。
限界はあるが、いくつかのメモリブロックなら同時に収めることが出来るからな。
563:デフォルトの名無しさん
21/11/29 01:12:27.10 HgRvzIV4.net
>>550
逆にキャッシュ制御せずにmemcpy()みたいなもので大きなメモリーをコピーした
場合、キャッシュが全フラッシュしてしまう可能性も有る。
動的配列の場合はそこに注意が必要。
564:デフォルトの名無しさん
21/11/29 01:17:45.41 HgRvzIV4.net
>>550
図を書いておこう。2つのメモリー領域A, B があったとして、
リンクリストが
AAAAAAAAAAA
の状態の途中にノードを5つ追加して、
AAAAABBBBBAAAAAA
のようになっていてもそれほどキャッシュミスは起きない。
さらに、もし、
AABCBBACDBBAABBDBCCC
みたいになっている程度でも、そんなにキャッシュミスは起きない。
なぜなら、A,B,C,D の4箇所くらいならキャッシュにどれも収まるから。
565:デフォルトの名無しさん
21/11/29 01:20:38.16 tPktcSTu.net
>>549
それはウソ
Rustは標準ライブラリの内部に至るところに多数のunsafeがあるのは事実だが
それにより全体の安全性に影響を与えることはない形でのみ提供している
まずunsafeの使用方法は大きく2つに分けられる
(1)影響が局所的に限定される場合
(2)影響が大域的に起き得る場合
つまりunsafeを用いたRustの様々な型やその操作インタフェース等は(1)が満たされている
つまりそれらを利用するプログラムには内部がどう実装されていようと影響をもたらさない
したがってRustのプログラム自体がコンパイラによって安全性を保証することが可能となっている
566:デフォルトの名無しさん
21/11/29 01:21:24.40 zo5XubVi.net
ベンチも取らずにキャッシュヒット率の話するの時間の無駄すぎない？
あとVecに対するLinkedListの優位性の話されても誰もそんなことは問題にしてないぞ？
567:デフォルトの名無しさん
21/11/29 01:26:01.98 HgRvzIV4.net
>>553
それはそうかもしれないが、リンクリストの場合、ノードの識別に
アドレスを使うのが、双対原理によって標準なので、その標準手法を
Rustで使おうとすると、unsafeをアプリ本体で使う必要が出てくる。
つまり、ライブラリの中にunsafeを閉じ込めることが不可能。
これは間違いないはずで譲れない。
568:デフォルトの名無しさん
21/11/29 01:26:35.85 tPktcSTu.net
>>554
ほとんどのケースではLinkedListよりもVecを用いた方が有利
だから使用する言語に関わらず特殊なケースを除けばリンクリストではなくベクターが使われている
569:デフォルトの名無しさん
21/11/29 01:32:54.07 HgRvzIV4.net
>>556
それが間違いなんだって。
そんな思想だから、ChromeではHTMLもtextareaへの文字列の末尾追加ですら遅いんだな。
計算量が理解出来て無い。
VisualStudioも異常に遅いし。
それに比べて日本人の作るVzEditor, WzEditor は速い。
それはなぜかというと、LinkedListも使っているから。
570:デフォルトの名無しさん
21/11/29 01:44:20.89 DszBoyLu.net
LinusもC++は糞言語と言ってる。
571:デフォルトの名無しさん
21/11/29 01:44:27.36 27e/xIh/.net
古いけどこんなのみつけた
URLﾘﾝｸ(baptiste-wicht.com)
insert/removeはO(1)なlistの方が速そうなものなのに要素サイズが小さいと10万要素でもvecの方が速いんだね
572:デフォルトの名無しさん
21/11/29 01:47:20.54 DszBoyLu.net
システムコールの実装によるのでは？
573:デフォルトの名無しさん
21/11/29 01:50:31.36 HgRvzIV4.net
>>559
Push Front を見たら圧倒的に list が速い。
それにC++のライブラリの list はへたくそな実装になっている。
574:デフォルトの名無しさん
21/11/29 01:52:56.70 27e/xIh/.net
>>561
deque無視しないでよ
先頭への追加削除が高速なvectorだよ
クラフをログスケールにするとわかるけどlistより速い
575:デフォルトの名無しさん
21/11/29 01:53:14.65 HgRvzIV4.net
沢山実験して、LinkedListの方が性能がいいことが分かってるからLinkedList
を使ってる。
ベンチマークは、ベンチマークを作る人が正しく理解してなければ、正しい
テストプログラムを書けないから、正しい結果が出ない。
CPUのベンチマークも実際の体感速度に比例しているとは限らないのと同様。
576:デフォルトの名無しさん
21/11/29 01:54:51.63 HgRvzIV4.net
list の実装の仕方や使い方に問題があるだけだ。
何度も言ってるように、listは、双対原理から言って、添え字番号ではなく
アドレスを用いなければ成らないことをベンチマークプログラムを作ってる
人が理解出来て無いから、遅く出てることが多い。
577:デフォルトの名無しさん
21/11/29 01:56:39.58 27e/xIh/.net
2017年版あったからこっち見た方がよさそう
URLﾘﾝｸ(baptiste-wicht.com)
>>563
あなたのワークロードではそうなんですね、なるほど
578:デフォルトの名無しさん
21/11/29 01:57:29.30 tPktcSTu.net
>>557
ついにGoogleとMicrosoftを批判しだしたのか
>>561
C++擁護派なのにC++のライブラリまで批判しだしたのか
君が間違っているとは考えないのね？
579:デフォルトの名無しさん
21/11/29 02:04:18.84 HgRvzIV4.net
>>565
要素サイズが128バイトや4096バイトの時には、listの方がvectorより速い。
それに、NonTrivialの時こそ list が効率がいいはずなのに結果が逆になって
いたり、listは、安定なはずなのに、trivial 128 で list のグラフが
途中で直線になってないこともおかしい。
listは、どんなときでも速度が変化しにくい性質があるはず。
何かそのテストはおかしい。
580:デフォルトの名無しさん
21/11/29 02:05:00.82 HgRvzIV4.net
>>566
俺はCと言っていたが。
C++のSTLには設計に問題が有ると行っているぞ、昔から。
581:デフォルトの名無しさん
21/11/29 02:07:29.41 HgRvzIV4.net
実際に自分で実験したこそが無いのに、誰かが実験したものを信じるな。
実際に一般的なケースでは、vectorとlistでは、listの方が速いことが多い。
582:デフォルトの名無しさん
21/11/29 02:09:04.94 tPktcSTu.net
>>569
ほとんどの用途でベクターが速い
だからほとんどのケースではリンクリストではなくベクターが使われている
583:デフォルトの名無しさん
21/11/29 02:12:28.28 HgRvzIV4.net
>>570
数理に弱いアメリカ人。
だから、VisualStudioも激オソなんだな。
アメリカ人の作るものは何でもでかくて速度が遅い。
車もでかくて燃費が悪い。
584:デフォルトの名無しさん
21/11/29 02:15:22.14 27e/xIh/.net
>>567
NonTrivialはMovableな要素だから追加削除時には要素あたりポインタ数個分のデータがコピーされるだけで小サイズと同じ特性になるのは不思議ではないのでは
listについては要素サイズの変化に対して他のコンテナよりも安定的に見えるけど
さすがに要素のコピー分のコストはかかるから要素サイズ変わっても全く同じという訳ではないけど
585:デフォルトの名無しさん
21/11/29 02:21:21.41 HgRvzIV4.net
こういうベンチマークには、ファクトチェックが必要だ。
今までネットのこういう変な結果のベンチマークを見てきたが、
ソースを見てみると変なことをしてることが多かった。
多かったというより、結果がおかしいと思って調べてみたら全て変なことしてた。
秀才以外が行ったベンチマークは信用できない。
まだ、雑誌は信用できることが多いが、ネットのベンチマークはおかしい。
586:デフォルトの名無しさん
21/11/29 02:23:11.00 tPktcSTu.net
『リンクリスト vs. ベクター』のスレ立ててそこでやったら？
少なくともこのスレでやることではない
587:デフォルトの名無しさん
21/11/29 02:25:44.21 zo5XubVi.net
ではどうぞ、ファクトチェックしてくださいまし
URLﾘﾝｸ(github.com)
588:デフォルトの名無しさん
21/11/29 02:29:42.73 27e/xIh/.net
誰かこのベンチマークをRustに移植してみてよ
589:デフォルトの名無しさん
21/11/29 02:44:22.88 HgRvzIV4.net
作業時間が発生するものを持ち込まないで欲しい。
こっちはボランティアに馬鹿に説明してやってるだけなんだから。
ソースを出せ、と言ってくるのは抽象的理解が出来ないから。
とても簡単なことを言ってるだけなのに、少しでも抽象的(symbolic)
な言葉で語ると全然理解できない。
数学とは抽象性(symbolic)な学問であるから、数学が出来ない人は
コードを示さないと理解できないらしい。
590:デフォルトの名無しさん
21/11/29 02:59:57.67 qK4xTYr2.net
ベンチマークとかはどうでもいいが、
CだろうがRustだろうが実装可能って話にしか見えん
591:デフォルトの名無しさん
21/11/29 07:57:57.28 cydEy5/m.net
>>538
これな。
結局のところ実体へのポインタの配列であればリンクトリストになってなくても話は同じなんじゃないかな。
592:デフォルトの名無しさん
21/11/29 08:02:08.66 LzdsKRC
593:S.net
594:デフォルトの名無しさん
21/11/29 10:19:47.16 zFB6Wt84.net
抽象はabstract
595:デフォルトの名無しさん
21/11/29 11:26:03.41 ynhRtjt2.net
>>579
違う。
リンクトリスト + 配列だと >>538 が指摘している現象が生じてしまうが、
リンクトリスト + リンクリスト だと生じない。
こういっても、数学力の無い人は理解できないだろうな。
数学力は数学という学問だけの能力ではなくて、脳内のワーキングエリアや
イマジネーションなどに関係しているから、生まれつきの影響が大きい。
596:デフォルトの名無しさん
21/11/29 11:29:51.75 ynhRtjt2.net
>>582
[補足]
抽象的理解が難しい人に具体的に書いておいてやろう。
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("バナナ") );
だと起きない。
597:デフォルトの名無しさん
21/11/29 11:36:08.77 27e/xIh/.net
>>583
中身が同じリストを二個用意しても意味がないのでもう少し実践的な例の方が理解のためにはよろしいのでは
スキップリストみたいな構造とは違うのですか？
598:デフォルトの名無しさん
21/11/29 11:36:25.33 ynhRtjt2.net
>>583
もっと具体的に書いてやろう。
リンクリストの中の追加した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("ブドウ") );
599:デフォルトの名無しさん
21/11/29 11:36:55.60 ynhRtjt2.net
>>584
>>585 を見ろ。
600:デフォルトの名無しさん
21/11/29 11:39:40.44 ynhRtjt2.net
>>585
これがどういう時に起きるかといえば、最初に1000個の品物の入った
リンクリスト ll がある時、条件に合う品物を1つ探してリンクリスト ll2
の末尾に参照を追加する。
それを10回繰り返した後に、実質的に生じる。
601:デフォルトの名無しさん
21/11/29 12:08:42.24 27e/xIh/.net
>>587
queryに対する抽出結果をリストとして保持しておいて元のリストの更新に応じてquery結果も適宜更新されるイメージですか？
602:デフォルトの名無しさん
21/11/29 12:10:54.78 qK4xTYr2.net
一部のノードが2つのリストで共有されてんのこれ？
603:デフォルトの名無しさん
21/11/29 12:15:46.59 V8SeceOD.net
l2のリストに入れる数によって変わるので結局O(N)の操作じゃね？
604:デフォルトの名無しさん
21/11/29 12:42:23.24 G+erg93y.net
>>590
正確にはll2のサイズN_ll2の半分に近づくね。
ll2のサイズが大きくなるなら、大きめに初期化するのが無難。スカスカならバランス木のmapかね。
605:デフォルトの名無しさん
21/11/29 12:43:56.81 4MgUQE5v.net
リンクリストを少し調べたところ様々な種類のものが使われているようで
様々な分類が生じるうち今回関係するノードの参照については以下の4種類あるようだ
(A) データを挿入しても作られたノード自体は返さない方式
実際にこの仕様でも困らない用途も多いようでこの方式も普通に使われている
もちろん問題は何も生じない
(B) データを挿入して作られたノードのポインタを直接返す方式
これは危険で最も推奨されない方式
ポインタを握っていても使う時にそのノードは削除されているかもしれない
削除で開放されてヒープに戻され更に再利用されているとデータの中身もnext辿りも滅茶苦茶になりうる
そしてデータの扱い次第で実際に削除は起き得るしUI人間や通信相手から発動ルーチンでの削除も有り得る
(C) データを挿入して作られたノードの(一般的な)スマートポインタを返す方式
これはshared_ptrなど安全とされているスマートポインタを返すためメモリ使用上は安全
しかしポインタ先がヒープへ戻されていないことしか保証がない
つまり(B)と同様にリンクリスト自体からの削除が起きている可能性がありそれを知る方法がない
(D) データを挿入して作られたノードを管理しているリンクリスト内部の何らかを返す方式
リスクの高い(B)や(C)と異なりこの方式は安全かつ整合性が維持される
もしノードがリンクリストから削除されていればそれに対して対応ができる
この返されたデータを用いて新たなデータをその位置に挿入する時に元ノードが削除されていた場合
(D)-1. 挿入はされず既に元ノードが削除されていると知らせる
(D)-2. 知らせずに削除された元ノードの次に有効なノードの位置に挿入する
などリンクリストの仕様や用意されたメソッドにより異なるようだ
以上まとめると現実的に安全に使える方式は(A)もしくは(D)となっている
例えばC++の標準リンクリストstd::listでもこの(D)方式を採用しており
insert()はリンクリスト上をその位置から順に辿っていくイテレータを返す
606:デフォルトの名無しさん
21/11/29 12:52:17.03 qK4xTYr2.net
>>585みたいなことできる連結リストって、
Rustでも作れると思うんですけど
Unsafe全振りにはなると思うけど