C++ vs Rust

**デフォルトの名無しさん** · 2021/04/24(土) 08:04:49.48

競え

**デフォルトの名無しさん** · 2021/12/03(金) 19:35:25.25

C10Kというけど、いま使ってるパソコンだってスレッドが数千あるのに、クライアントが1万程度でいまどき問題ある？

**デフォルトの名無しさん** · 2021/12/03(金) 20:15:24.75

有線LAN なら、200Mbps ぐらい出る。
無線にすると、10～20

無線スポットから離れると、1まで落ちる

**デフォルトの名無しさん** · 2021/12/03(金) 20:20:25.08

Elixir では、10万のプロセスを起動できる

これは、OS のプロセス・スレッドじゃないから。
Erlang 内の小プロセスだから出来る

**デフォルトの名無しさん** · 2021/12/03(金) 20:32:10.63

そんなに起動して何に使うの？

**デフォルトの名無しさん** · 2021/12/03(金) 20:45:06.44

ルーチェン

**デフォルトの名無しさん** · 2021/12/03(金) 22:07:37.69

>>751
非同期プログラミングの話をしているだけなのにそんなasync/awaitに限定するのがおかしいのではないかね
さらにいえばasync/awaitの話とpromise/futureの話を同類に捉えているからちゃんと理解していないのでは？
非同期関数をなにか特殊なもののように捉えているのも怪しい

非同期ブログラミングとは同期ブロッキングI/Oによる非効率で無駄な方法を排除するプログラミングであって
昔も今も中心部分にselectやepoll等のシステムコールを核とするループすなわち高度化した時のスケジューラーで成り立っている
そして読み書き可能になったら読み書きをするという極めて自然なプログラミング
もちろんこのスケジューラー部分で割り込みやタイマー含めて共通管理できるため「相性が悪く複雑になる」というのも間違いだ

もちろん読み書き可能になったら教えて！と最初に登録するところから始まるわけだから
読み書き可能になったぜ！と教えてもらう部分がコールバックとなるのは当然の話
だからそれをまとめて包んだ非同期関数は当然コールバックとなりI/O待ちブロックされる同期関数より極めて効率が良い

promise/futureはこの部分のインターフェース部分だけを抽象化しただけに過ぎず
この中身は単なる状態管理だから具体的なI/Oやタイマー等と関係なく共通して使える点もプログラミングの利便性を向上させている
そしてこれ自体はコールバックを無くしているわけではなく例えばクロージャを渡すメソッドなどを用意することでコードの見た目を改善している
これで非同期関数のインタフェースとして(直接)コールバック系と(間接に行う)promise/future系((およびその両対応))に分かれた

以上ここまでの話は生のC言語でも普通にプログラミング可能な話である (メソッド呼び出しを除く)
もちろんスレッドなんか存在しない環境でもシングルスレッドにて並行に動作するの非同期プログラミング
当然ながらマルチスレッドでも同じように動作させられる

**デフォルトの名無しさん** · 2021/12/03(金) 22:08:57.91

>>757の続き

一方でasync/awaitは全く別の話
これだけはプログラミング言語による支援がないと実現できない
そしてこの導入目的は同期プログラミングしか出来ない人たち向けも含めて楽に非同期プログラミングするためであり
asyncと宣言した関数などの中ではawaitを付ければ見かけ上は同期プログラミングと同じ記述ができる！という改革
これによりようやく真にコールバックが利用側からは消えたので「コールバックを無くすため」というのも間違ってはいない

ではasync/await導入で非同期関数側はどう変わったか？
実は全く変わっていない、が正解
そのままpromise/futureを返す非同期関数と全く同じそのままである
つまりasync/awaitは非同期関数を利用する側だけの話という点が重要

以上で>>751氏も非同期プログラミングを正しく理解できるであろうか？

**デフォルトの名無しさん** · 2021/12/03(金) 22:13:40.85

もはやC++もRustも関係無いマウント合戦になってら

**デフォルトの名無しさん** · 2021/12/03(金) 23:22:05.85

もしかしてずーっと同じ人が暴れてんですか？

**デフォルトの名無しさん** · 2021/12/03(金) 23:31:58.32

どうしようもない二人が残っちゃったね
掃き溜め

**デフォルトの名無しさん** · 2021/12/03(金) 23:40:57.15

Goスレでも同じC#おじさんがRust/Goを学びかけて暴れてたから同じやつ
「真にコールバックが利用側からは消えた」なんてコールバック関数が消えたことはない。お前はHello worldでも
書いて満足してろｗawaitの話とpromiseを同列に語ってんのもお前、「インターフェース部分だけを抽象化」なんて
RustにもC++にも無いしC#おじさん臭さが露骨に出てる

**デフォルトの名無しさん** · 2021/12/03(金) 23:59:21.97

＞当然ながらマルチスレッドでも同じように動作させられる
そんなのはC#のような一部であり、多くのasyncを有する言語ではスレッド境界は越えられないのでそれぞれの
スレッドがイベントループとイベントキューを有する。これはAスレッドで起こったイベントはBスレッドには
伝わらず”同じように動作させられる”なんてことは無い、実行の順序制御も当然バラバラ
C++20でもコルーチェンたるco_return, co_await, co_yieldがあるのに、鬼の首を取ったようにRustなどの
触りだけ触れていて優位性を語ってるアホはまじ市んでほしい

**デフォルトの名無しさん** · 2021/12/04(土) 01:46:20.63

最近は、一度もWindowsプログラミングしたこと無い人が増えてるからな。
Windowsは伝統的に非同期をほとんど使わないことを知らない人が多いらしい。

**デフォルトの名無しさん** · 2021/12/04(土) 01:54:42.66

>>761
もともとrustスレで暴れてた人を隔離するために立てられたスレだから最初から掃きだめ

**デフォルトの名無しさん** · 2021/12/04(土) 03:17:48.45

>>763
＞＞当然ながらマルチスレッドでも同じように動作させられる
＞そんなのはC#のような一部であり、
＞多くのasyncを有する言語ではスレッド境界は越えられない

え？？
Rustでは当然出来ますけど

＞スレッド境界は越えられないので
＞それぞれのスレッドがイベントループとイベントキューを有する。

え？？
Rustではスレッド境界を超えつつ、それぞれのスレッドがイベントループとイベントキューを有することも出来ますけど

＞これはAスレッドで起こったイベントはBスレッドには伝わらず

そこだけは正しいですｗ
しかし暇になったスレッドがいわゆるワークスティーリングすなわち他スレッドからタスクを奪ってからイベント登録しますから、

＞”同じように動作させられる”なんてことは無い

同じように別スレッドで動作を継続できます

＞実行の順序制御も当然バラバラ

え？？
非同期だからバラしたタスク間の実行順序は例えば通信相手次第で変わりますけど
それは単純なワンタスク同期なマルチスレッドの時も同じです
実行の順序制御が必要な部分のみ制御の意味での同期を行うのも同じです
例えば10個のタスクで並行して10ヵ所からデータを取得してその平均を出すならば平均を出す直前で10個全てのタスクの完了を待つだけです

非同期プログラミングしたことがない人は間違った思い込み妄想だらけで大変

**デフォルトの名無しさん** · 2021/12/04(土) 03:24:28.87

Rust使ったこと無いけど健全なマクロはいいなぁと思う。

**デフォルトの名無しさん** · 2021/12/04(土) 03:28:16.65

今言われているasync, awaitの「非同期」ってちょっと違うけど、意味的には擬似スレッドみたいな感じだな。
I/O全般というより、XHRやfetchやsocketのように遅いネットワーク通信を複数同時に待つ時に使う
時に便利な気がする。
nativeのファイルI/Oの場合、処理が完了するまで待つ方が便利だし、余計なことを考えなくて済むので
バグが少なくできるから、伝統的に同期方式を使うことが基本。

**デフォルトの名無しさん** · 2021/12/04(土) 03:36:51.75

print "hello\n";
と書いた場合に、print文は端末(terminal)などの別プロセスでの処理が
完了するまで待つことが多く、実行完了するには時間が掛かるが、
これを一々非同期にして、print 文が完了するまでに別の処理をする、
というようなことはすべきじゃない。
一番いいのは、print 文が完了するまではそこで待機して、ちゃんと
それが完了してから次の文を実行すること。
つまり、同期的処理。

**デフォルトの名無しさん** · 2021/12/04(土) 03:52:52.03

>>769
え？？
awaitはその待機という同期的処理をするためにあります
したがって非同期のprint関数を呼んでも問題は起きずにその書かれてる通りになります

**デフォルトの名無しさん** · 2021/12/04(土) 04:12:46.09

>>770
でもそのコード部分では見て無い場所で、イベントループに戻ってしまって、
別のイベントハンドラが起動してしまう可能性が生まれ、
せっかく通常のシングルスレッドプログラミングでは起きない良い特徴が失われる。
そのため、シングルスレッドなのに排他処理が必要となってしまう。
排他処理は間違うととても危険であって、プログラミングのかなり上級者でも
気を使う必要がある。

**デフォルトの名無しさん** · 2021/12/04(土) 04:28:23.02

見かけ上はどちらも関数処理完了まで待機する形で同じですが

「同期の関数を呼んだ場合」
　　→関数から戻って来るまでそのスレッドはブロックされる

「非同期の関数を呼んでawaitする場合」
　　→そのスレッドがブロックされることはなく他にタスクがあれば並行して実行される

>>771
いいえ
その場合はそのタイミングで並行して実行されたら困るタスクを持たなければいいだけです

○ その時は他に並行して実行されるタスクを持たない
○ 並行して実行されてもよいタスクだけを他に持つ
○ 並行して実行されるタスクの動作に制限がかかるようにロック等を持つ
✕ 並行して実行されたら困るタスクを対策なしに他に持つ

選択肢はたくさんあります
これがプログラミングです

**デフォルトの名無しさん** · 2021/12/04(土) 04:34:52.83

>>772
Win32/MFC/WinForms/JavaのSwing/Android/ブラウザのJSで
プログラミングしたこと有る？
イベントループやイベントって自分で定義するものでは無いから
「タスクを持たないようにする」
っていうのは現実には不可能だぞ。

**デフォルトの名無しさん** · 2021/12/04(土) 05:07:10.24

>>773
もちろんRustでも自分でスケジューラを自作することは滅多になく
selectやpollなど使用のイベントループを自分で書くことはありません
それからここでのイベントとは当然selectやpollなどのイベントですから具体的にはファイルディスクリプタの読み書きOK等がイベントとなります
もちろんこの処理はスケジューラが担当するので自分で書かなくてもいいです
しかし新たなタスクを起こすかどうかはスレッドの時と同様にプログラマーの自由であり必要なら明示的に行います

JavaScriptの場合もイベントループを管轄するスケジューラはブラウザでもNode.jsでもシステムとして持っているため関知しなくてもよいです
ただしJavaScriptでは非同期関数を呼ぶこと自体が自動的にここでいう新たなタスクを起こすことになります
あとは例えばブラウザ自体が暗黙的に動作しているタスクとしてみなすことも出来てそのタスクから新たなタスクを発火することもあります
リスナー登録するタイプの利用時もそのパターンです

**デフォルトの名無しさん** · 2021/12/04(土) 05:13:43.45

>>774
MFC/WinForms/JavaのSwing/Androidなどでは、マウスイベントやキーボードイベント、
メニューイベントは基本的に常時イネーブル状態になったままにして使うので、await
してしまうと、それぞれのハンドラに普通に入ってしまう。
そうなるとロジックが破綻するので排他処理するか、awaitする直前に、
一々ハンドラを disable にして、awaitの次の行に来た時に enableにする
必要がある。そんなメンドクサイことすべきじゃ無いし、そもそもdisable
にするなら、非同期のメリットも無い。
そもそもGUIスレッドは、イベントハンドラの二重起動は禁止すべきとされている。

**デフォルトの名無しさん** · 2021/12/04(土) 06:02:11.33

>>775
プログラミング分野は無数にある中で
なぜそんな特殊な環境だけを唐突に持ち出すのかも含めて分かりません
先ずは適用可能な分野から始めて経験と知識を積んで的確に判断できるようになってから結論づければよいかと

**デフォルトの名無しさん** · 2021/12/04(土) 10:01:49.43

数学の天才と言い切った手前、後に引けなくなってきたか
自分の触ったことのある範囲でいいから弁解しなくちゃ
もうリンクトリストなんてどうでもいい、無知の印象を払拭するのが第一

**デフォルトの名無しさん** · 2021/12/04(土) 16:50:56.54

天才と言いつつテスト100点としか言えてない時点で程度は知れて馬鹿にされてるんだから今更取り繕わなくて良いのに

**デフォルトの名無しさん** · 2021/12/04(土) 16:53:37.05

リンクリストの話はまだまだお聞きしたいと思っていますのに…
>>738 のリストのソートのご感想とか

**デフォルトの名無しさん** · 2021/12/04(土) 16:55:24.53

>>778
数学や物理のテストは、B4 の白紙一枚をわたされて、これに回答とか証明を書け、みたいな感じですが、そんなテストで一度でも 100 点をとれるのなら、それはそれですごいとは思いますよ

**デフォルトの名無しさん** · 2021/12/04(土) 17:09:21.39

>>780
引き合いに出してたのがセンター試験だったり東大入試だったりで大学入試の成績を誇るしかない人なんだなって思っていました

**デフォルトの名無しさん** · 2021/12/04(土) 17:19:28.99

RustのLinked Listは遅いからRustはクソ言語

という論理は成立しましたか？

**デフォルトの名無しさん** · 2021/12/04(土) 17:28:22.69

>>781
回答用紙の返却のない試験の結果がどうしてわかるのか疑問ですよね

**デフォルトの名無しさん** · 2021/12/04(土) 17:40:33.98

どっちも中途半端な知識しかないのに他人の指摘は聞かないから救いようがない

隔離スレ立てたやつグッジョブ！

**デフォルトの名無しさん** · 2021/12/04(土) 18:40:15.11

>>773
あわしろ氏が言ってたけど、Win32ではメッセージループを自分で作るらしいですよ。
まあ、配送はDispatchMessage()でやってもらうんですが。

**デフォルトの名無しさん** · 2021/12/04(土) 18:46:57.96

>>783
マジレスすると
点数はわかる

**デフォルトの名無しさん** · 2021/12/04(土) 18:49:24.09

>>785
Java の awt では、どこにメッセージループが隠れているのか、あわしろ氏に訊いていただけませんか？

**デフォルトの名無しさん** · 2021/12/04(土) 18:51:13.15

>>786
私の時代には、そういうのは転部転科でもしようとしない限りわからなかったかと、今は変わったんですね…

**デフォルトの名無しさん** · 2021/12/04(土) 18:51:48.09

>>787
了解です。
来週、職場で会うと思うので、聞いておきます。

**デフォルトの名無しさん** · 2021/12/04(土) 18:53:03.93

>>788
そう

**デフォルトの名無しさん** · 2021/12/04(土) 18:54:08.07

センター試験や東大入試は数学の天才を黙らせようとした人らが基準を示すため言い出したのであって
当の数学の天才は一度も何の試験かにすら言及していない
高校の定期試験ということもあり得る

**デフォルトの名無しさん** · 2021/12/04(土) 18:58:45.03

>>789
師が職場におられるとはうらやましいですね

**デフォルトの名無しさん** · 2021/12/04(土) 19:00:26.50

>>791
私はしませんが、仮に「自分は数学の天才である」と名乗りたいときに、どういう風に自分の天才性を形容するべきか、はいい演習課題になりますね
あまりマニアックなことをいってもスルーされるだけですし

**デフォルトの名無しさん** · 2021/12/04(土) 19:21:42.11

私は分かりやすく>>621
他には
東大後期模試300点
数学偏差値90
東大数学科卒
など

普通は
論文数/論文引用数/肩書き(教授など)/受賞歴/特許出願数
などが実績ですが
私はその辺の実績はありません

**デフォルトの名無しさん** · 2021/12/04(土) 19:24:17.53

残念ながら自称数学の天才には効かなかったようです

**デフォルトの名無しさん** · 2021/12/04(土) 19:27:28.34

アカデミー賞受賞最新作はどうでしょうか？
アカデミックな感じで。

**デフォルトの名無しさん** · 2021/12/04(土) 19:28:53.97

>>794
なんか生々しいんじゃないですか？もっとサラっとした感じでお願いします…

**デフォルトの名無しさん** · 2021/12/04(土) 19:43:56.41

数学の天才っていうとラマヌジャンとかそういう人？

**デフォルトの名無しさん** · 2021/12/04(土) 19:49:29.22

>>798
円の体積・表面積を算出したアルキメデスでしょう、ニュートンライプニッツの2000年ほど前の人

**デフォルトの名無しさん** · 2021/12/04(土) 21:07:23.15

CSの天才じゃなくて数学の天才名乗るのはなんでなんだろうな

**デフォルトの名無しさん** · 2021/12/04(土) 22:13:27.18

自信が無いんだよ

**デフォルトの名無しさん** · 2021/12/04(土) 22:16:07.33

コンビニエンスストアの天才。

**デフォルトの名無しさん** · 2021/12/04(土) 22:29:30.68

>>800
鋭い視点ですね
オーダーの話と実時間の話をシレっと往ったり還ったりするところなんかは、私には変だと思いましたね、アルゴリズムの評価はオーダーで行うのが普通で他はほとんどみない…

>>799
×　円
○　球

**デフォルトの名無しさん** · 2021/12/04(土) 22:41:59.72

天才の心は、自分が天才になった時、初めて理解できるのではないでしょうか。

**デフォルトの名無しさん** · 2021/12/04(土) 23:15:15.65

見上げてErlang夜の星を

**デフォルトの名無しさん** · 2021/12/04(土) 23:41:44.19

美少女の国に行きたいが、美少女じゃないので入れない。

**デフォルトの名無しさん** · 2021/12/05(日) 10:16:06.18

>>804
>>799 の人は1000年以上も登場する時代を間違えた人だから、その孤独感たるや想像を絶するでしょうね…

**デフォルトの名無しさん** · 2021/12/05(日) 10:27:47.16

数学100点が自慢の自称天才と
歴史的に有名な超天才を比べる変なスレ

板的にはチューリングが出てこないのは変

**デフォルトの名無しさん** · 2021/12/05(日) 11:52:13.76

チューリングの話題はLGBT板で。

**デフォルトの名無しさん** · 2021/12/05(日) 12:45:24.80

じゃあ、モンティホール問題に納得できない人は、手を上げて。

**デフォルトの名無しさん** · 2021/12/05(日) 12:47:11.55

板違い

**デフォルトの名無しさん** · 2021/12/05(日) 13:23:53.66

良スレ。
アゲ。

**デフォルトの名無しさん** · 2021/12/05(日) 15:04:30.36

>>803
>オーダーの話と実時間の話をシレっと往ったり還ったりするところなんかは、私には変だと思いましたね、
>アルゴリズムの評価はオーダーで行うのが普通で他はほとんどみない…
書くのが長くなるからオーダーで書いているだけで、オーダーだけでは正しい特徴を捉えられない
場合がある。
例えば、同じオーダーでも乗算や条件分岐の両方が使われているアルゴリズムとマシン語の
1クロックの命令1個にコンパイルされるものでは全然違う。
また、N個のデータを持っているハッシュ構造は、1回の検索は、数学的に厳密にはO(N)
だが、実験的(実際的)にはO(1)のように振舞うと言われており、厳密に扱うには、
オーダーの記号だけでは表現しきれない。
もし、オーダーだけで評価すればいいのなら、チューリング完全なあらゆる言語は、
同じアルゴリズムを使うことは可能で、同じオーダーの時間で計算できてしまうから、
速度比較には役立たない。

**デフォルトの名無しさん** · 2021/12/05(日) 15:19:38.16

>>813
＞1回の検索は、数学的に厳密にはO(N)だが、実験的(実際的)にはO(1)のように振舞う
ハッシュテーブルの構築は O(N) ですが、既存のデータをハッシュで引く割合が多ければ多いほど O(1) に近くなるでしょう
ハッシュテーブルには衝突がつき物ですが、そういうところも厳密に評価するのは難しいかもしれませんね

ただし、

＞同じオーダーでも乗算や条件分岐の両方が使われているアルゴリズムとマシン語の
＞1クロックの命令1個にコンパイルされるものでは全然違う。

そのとおりですが、それは所詮 O(f) の f の係数が違うだけでしょう、というか、そういうものはケースバイケースで一般論には載せ難いかと
そもそもあなたは、Σクロック（命令種）、で近似的に評価しようとしてますが、その姿勢は評価しますが、CPU 内の RISC 変換と並列実行、投機実行等までは及んでおらず、ある意味これも粗粗の近似だと思います
CPU 種類やメモリ構成などによって大きく変わるのですから、オーダーでの評価にとどめておくのが妥当なのでは？

＞もし、オーダーだけで評価すればいいのなら、チューリング完全なあらゆる言語は、
＞同じアルゴリズムを使うことは可能で、同じオーダーの時間で計算できてしまうから、
＞速度比較には役立たない。

そりゃそうです、言語間の速度比較にオーダーを使う方が間違っています
総じて評価センスの問題かと

**デフォルトの名無しさん** · 2021/12/05(日) 15:34:15.66

>>810
高卒の私は、いくら考えても意味がわかりませんでした…

**デフォルトの名無しさん** · 2021/12/05(日) 16:04:00.19

>>814
>＞1回の検索は、数学的に厳密にはO(N)だが、実験的(実際的)にはO(1)のように振舞う
>ハッシュテーブルの構築は O(N) ですが、既存のデータをハッシュで引く割合が多ければ多いほど O(1) に近くなるでしょう

あなたは、>>813で
「また、N個のデータを持っているハッシュ構造は、1回の検索は、数学的に厳密にはO(N)
　だが、実験的(実際的)にはO(1)のように振舞うと言われており、厳密に扱うには、
　オーダーの記号だけでは表現しきれない。」
と書いてあることの意味が全く分かって無い。

秀才以上で無いと発言禁止だ。

**デフォルトの名無しさん** · 2021/12/05(日) 16:12:34.15

>>816
ハッシュ構造は、「一回の検索」でも、数学的には、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)ではない。

不定積分の等号も集合論的な意味であって、等しいという意味ではないと聞いたことが
あると思うが、それと同じような定義。

**デフォルトの名無しさん** · 2021/12/05(日) 16:15:03.84

>>817
[さらに補足]
なお、そもそも、等号 = の左辺に O(xxx)の記号は書くべきではないという説もある。

**デフォルトの名無しさん** · 2021/12/05(日) 16:36:22.78

実時間が重要なら黙ってベンチ出せや

**デフォルトの名無しさん** · 2021/12/05(日) 16:50:30.44

>>817
＞しかし、実際問題は、Nが常識の範囲内の大きさではO(1)のように振舞うことが分かっているので

それには理由があるのでしょう？その理由はなんですか？「振舞うことがわかっている」という観測事実のみが根拠とは到底考えられませんね
>>814 が間違っているのであれば、あなたの解釈はなんですか？

＞数学的には、O(f(N))とは、Nを無限に大きくしても、処理時間をf(N)で割るとある
＞上限値未満であるという意味。ハッシュテーブルの検索は、Nを無限に大きくすると、
＞定数的ではないので、O(1)ではない。

そりゃ、衝突が頻繁に発生するようになると、それを連鎖法で処理するか、あるいはオープンハッシュ法＆セカンドハッシュ関数で処理するか、
いずれにしても N がハッシュテーブルサイズに比して大きくなりすぎるとO(1)から程遠くなるでしょう
しかし、今はハッシュテーブルサイズが N に比してそんなに大きくないことが前提だと思っていましたが、そういうハッシュテーブルの重要な性質を無視して N→∞にいきなり振るとか、やはり実装経験が不足しているとしか考えられません

あなたには、オープンハッシュ法でも連鎖法でもいいから、一度実装してみることをお勧めします、そうすれば、そんな無茶な話をふったり出来ないはずです

**デフォルトの名無しさん** · 2021/12/05(日) 16:51:42.71

>>820
×今はハッシュテーブルサイズが N に比してそんなに大きくないことが前提だ
○今は N がハッシュテーブルサイズに比してそんなに大きくないことが前提だ

**デフォルトの名無しさん** · 2021/12/05(日) 18:19:46.95

INTEL Core N4200。

**デフォルトの名無しさん** · 2021/12/05(日) 19:15:19.02

この数学100点の人はプログラミングできないんだから、ベンチ出せは禁句だよ

**デフォルトの名無しさん** · 2021/12/05(日) 19:16:59.90

>>820
あなたは馬鹿すぎて議論が成立しない。
勉強しろ、とも言えない。
なぜなら、勉強しても無駄だと思うから。

**デフォルトの名無しさん** · 2021/12/05(日) 19:54:51.36

>>823
話が噛み合いませんね、やっぱり私が馬鹿だからなんでしょうかね…
でも、仮にも計算機科学方面から解析を行っていただくのでしたら、C でいいから例示してほしいですよね

>>824
生まれてきてすみません…

**デフォルトの名無しさん** · 2021/12/05(日) 22:25:34.77

Ruby のハッシュでは、データ数と共に、バケット数を増やしていく。
バケット数は、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回で見つかる

**デフォルトの名無しさん** · 2021/12/05(日) 22:30:23.53

>>826
Rustのハッシュそうなんだ？

**デフォルトの名無しさん** · 2021/12/05(日) 22:55:00.31

Rubyだぞ

**デフォルトの名無しさん** · 2021/12/05(日) 23:55:41.03

>>817
> ハッシュ構造は、「一回の検索」でも、数学的には、O(N)の時間が掛かる。

ホントですか？
>>826がO(logN)ですよ

**デフォルトの名無しさん** · 2021/12/06(月) 00:01:51.71

ベンチをもっと気楽に行うために単体テストフレームワークを使ってベンチ書いてる。

**デフォルトの名無しさん** · 2021/12/06(月) 00:03:31.65

>>829
O(N)の定義は、Nを無限に大きくしていった時に、処理時間を N で割った時に
ある固定された上限値の定数未満になる、という意味だぞ。
O(log N)のハッシュは有り得ない。

**デフォルトの名無しさん** · 2021/12/06(月) 00:07:28.71

なお、ハッシュ値の最大数を動的に増やしていくのならば、本来のハッシュ構造ではない。
本来のハッシュ構造は振り分けられる量は固定サイズ。
だから、ハッシュ値の計算も固定されたアルゴリズムで処理が固定された関数で
行う。
色々と勝手に定義を変えてはいかん。
言葉を勝手に再定義すれば議論になるわけ無い。

**デフォルトの名無しさん** · 2021/12/06(月) 00:25:08.26

（キリッ）が抜けてるのでは？

**デフォルトの名無しさん** · 2021/12/06(月) 00:25:34.03

リンクリストの次はハッシュテーブルかよ
データ構造スレでやれ

**デフォルトの名無しさん** · 2021/12/06(月) 00:49:48.95

良スレ。
アゲ。

**826** · 2021/12/06(月) 01:37:20.07

>>826
修正

>増え方が、N に比例しなくて、log N に比例するから

>例えば、2^20 = 百万で、2^21 = 2百万では、
>線形探索では毎回、百万回増えるけど、
>ハッシュでは、1回だけ再構築して、その後は、21回で見つかる

これはデータベースで使う、2分探索の事だった。
ハッシュは、バケット数で割った余りで決まるから、O(1)だった

**デフォルトの名無しさん** · 2021/12/06(月) 01:49:17.06

>>836
ハッシュの表の様なものが固定サイズであるところの
素朴なハッシュの検索は、Nが大きい時には、O(N)。N が小さい時には、O(1)。

Nが大きくなるに従ってその表を時々大きくしていくようなものは、
考慮の対象にはしない。

**デフォルトの名無しさん** · 2021/12/06(月) 01:53:00.58

>>837
[補足]
以下、ハッシュの表の様なものが固定サイズであるところの素朴なハッシュの検索
についてだけを考える。
ハッシュの中に入っているデータの個数が N 個の時に、あるキーを持つ
データを1個だけ探すのに掛かる平均時間を g(N)とすると、数学的には
g(N)=O(N)。
しかし、この g(N) は、g(N) = a N + b と近似した場合の a の値が極端に小さい。
なので、N が小さい時には、O(1)であるかのように振舞う。
そういう意味だ。
これで理解できないなら、数学的想像力や理解力が足りてない。

**デフォルトの名無しさん** · 2021/12/06(月) 02:05:17.38

RubyガイジとRustガイジの熱いマッチが今始まる

**デフォルトの名無しさん** · 2021/12/06(月) 02:22:55.84

>>839
この数学100点マンはRustを叩いてる人で常に生ポインタ派のC/C++史上主義な人
ただしコードを出したことがないのでプログラミング能力がないと推定されている
さらにオーダーについても勝手な定義で無茶な主張を繰り返している

**デフォルトの名無しさん** · 2021/12/06(月) 02:24:44.88

>>840
分かっとるわ
語呂がいいからRustガイジって言っただけ

**デフォルトの名無しさん** · 2021/12/06(月) 02:33:01.01

>>840
お前もとことん馬鹿だな。
コード書いても抽象理解が出来ない人には、そのコードの本質は分からんし、
こんなところに書ききれるわけでも無いからかけないだけだ。
なお、抽象 = シンボライズ、シンボリック
という意味で、曖昧や玉虫色という意味では無いぞ。
本質的な部分を記号化、定理化、規則化、一般化して理解できるようにしたもの
を「抽象化」と言う。

**デフォルトの名無しさん** · 2021/12/06(月) 03:29:12.50

linkedlistの計算量を勘違いし
平衡二分木とハッシュセットを混同する
数学100点マンがいると聞いて

**デフォルトの名無しさん** · 2021/12/06(月) 05:30:40.66

>>842
>こんなところに書ききれるわけでも無いからかけないだけだ。
スレじゃなくて、IdeoneとかGihubのgistに書いてもらえれば大丈夫ですよ

**デフォルトの名無しさん** · 2021/12/06(月) 05:43:24.70

>>838
＞、g(N) = a N + b と近似した場合の a の値が極端に小さい。…①
なぜですか？
ハッシュテーブルの実装方法から論じてみください
もしかして、あなたは①を数学の公理、みたいに扱っているのですか？そんなことではコンピューターサイエンスは無意味だし面白くないでしょう？
でもC/C++ 至上主義者というのなら、私と気が合いますね

**デフォルトの名無しさん** · 2021/12/06(月) 08:46:35.08

>>775
MFC(Win32)に関しては、メッセージキューとイベントは別物だぞ。　イベントは、
イベント処理中でも降って来る。

**デフォルトの名無しさん** · 2021/12/06(月) 10:07:17.08

なんでハッシュテーブルの話になったのかと思えば>>813にいちゃもん付けたいだけか

**デフォルトの名無しさん** · 2021/12/06(月) 11:16:09.54

ベンチマークもなしに実時間の話をされてもなぁ
しかも具体的な実装上の問題点の指摘もなく他人のベンチマークは信用できないとか宣われてしまうとこちらとしては会話しても意味がない人なんだと判断せざるを得ないんですよね

**デフォルトの名無しさん** · 2021/12/06(月) 11:52:31.39

>>845
公理ではなくて、処理時間の平均値を確率論で書いている。

**デフォルトの名無しさん** · 2021/12/06(月) 11:57:28.95

>>849
[補足]
確率論で証明することが出来るが、とてもめんどくさいので割愛する。
失礼だが、質問者のレベルから推測すると、ちゃんと書いても理解できない。

**デフォルトの名無しさん** · 2021/12/06(月) 12:01:12.30

>>845じゃないけど
最悪値が重要な用途もある
また、確率はデータの分布が決まってはじめて決まるもの
分布次第ではあなたの想定通りにはならない