C++ vs Rust
■ このスレッドは過去ログ倉庫に格納されています
2021/04/24(土) 08:04:49.48ID:nPKzA798
競え
770デフォルトの名無しさん
2021/12/04(土) 03:52:52.03ID:6dkLKknu771デフォルトの名無しさん
2021/12/04(土) 04:12:46.09ID:aNU60Xul >>770
でもそのコード部分では見て無い場所で、イベントループに戻ってしまって、
別のイベントハンドラが起動してしまう可能性が生まれ、
せっかく通常のシングルスレッドプログラミングでは起きない良い特徴が失われる。
そのため、シングルスレッドなのに排他処理が必要となってしまう。
排他処理は間違うととても危険であって、プログラミングのかなり上級者でも
気を使う必要がある。
でもそのコード部分では見て無い場所で、イベントループに戻ってしまって、
別のイベントハンドラが起動してしまう可能性が生まれ、
せっかく通常のシングルスレッドプログラミングでは起きない良い特徴が失われる。
そのため、シングルスレッドなのに排他処理が必要となってしまう。
排他処理は間違うととても危険であって、プログラミングのかなり上級者でも
気を使う必要がある。
772デフォルトの名無しさん
2021/12/04(土) 04:28:23.02ID:6dkLKknu 見かけ上はどちらも関数処理完了まで待機する形で同じですが
「同期の関数を呼んだ場合」
→関数から戻って来るまでそのスレッドはブロックされる
「非同期の関数を呼んでawaitする場合」
→そのスレッドがブロックされることはなく他にタスクがあれば並行して実行される
>>771
いいえ
その場合はそのタイミングで並行して実行されたら困るタスクを持たなければいいだけです
○ その時は他に並行して実行されるタスクを持たない
○ 並行して実行されてもよいタスクだけを他に持つ
○ 並行して実行されるタスクの動作に制限がかかるようにロック等を持つ
✕ 並行して実行されたら困るタスクを対策なしに他に持つ
選択肢はたくさんあります
これがプログラミングです
「同期の関数を呼んだ場合」
→関数から戻って来るまでそのスレッドはブロックされる
「非同期の関数を呼んでawaitする場合」
→そのスレッドがブロックされることはなく他にタスクがあれば並行して実行される
>>771
いいえ
その場合はそのタイミングで並行して実行されたら困るタスクを持たなければいいだけです
○ その時は他に並行して実行されるタスクを持たない
○ 並行して実行されてもよいタスクだけを他に持つ
○ 並行して実行されるタスクの動作に制限がかかるようにロック等を持つ
✕ 並行して実行されたら困るタスクを対策なしに他に持つ
選択肢はたくさんあります
これがプログラミングです
773デフォルトの名無しさん
2021/12/04(土) 04:34:52.83ID:aNU60Xul >>772
Win32/MFC/WinForms/JavaのSwing/Android/ブラウザのJSで
プログラミングしたこと有る？
イベントループやイベントって自分で定義するものでは無いから
「タスクを持たないようにする」
っていうのは現実には不可能だぞ。
Win32/MFC/WinForms/JavaのSwing/Android/ブラウザのJSで
プログラミングしたこと有る？
イベントループやイベントって自分で定義するものでは無いから
「タスクを持たないようにする」
っていうのは現実には不可能だぞ。
774デフォルトの名無しさん
2021/12/04(土) 05:07:10.24ID:6dkLKknu >>773
もちろんRustでも自分でスケジューラを自作することは滅多になく
selectやpollなど使用のイベントループを自分で書くことはありません
それからここでのイベントとは当然selectやpollなどのイベントですから具体的にはファイルディスクリプタの読み書きOK等がイベントとなります
もちろんこの処理はスケジューラが担当するので自分で書かなくてもいいです
しかし新たなタスクを起こすかどうかはスレッドの時と同様にプログラマーの自由であり必要なら明示的に行います
JavaScriptの場合もイベントループを管轄するスケジューラはブラウザでもNode.jsでもシステムとして持っているため関知しなくてもよいです
ただしJavaScriptでは非同期関数を呼ぶこと自体が自動的にここでいう新たなタスクを起こすことになります
あとは例えばブラウザ自体が暗黙的に動作しているタスクとしてみなすことも出来てそのタスクから新たなタスクを発火することもあります
リスナー登録するタイプの利用時もそのパターンです
もちろんRustでも自分でスケジューラを自作することは滅多になく
selectやpollなど使用のイベントループを自分で書くことはありません
それからここでのイベントとは当然selectやpollなどのイベントですから具体的にはファイルディスクリプタの読み書きOK等がイベントとなります
もちろんこの処理はスケジューラが担当するので自分で書かなくてもいいです
しかし新たなタスクを起こすかどうかはスレッドの時と同様にプログラマーの自由であり必要なら明示的に行います
JavaScriptの場合もイベントループを管轄するスケジューラはブラウザでもNode.jsでもシステムとして持っているため関知しなくてもよいです
ただしJavaScriptでは非同期関数を呼ぶこと自体が自動的にここでいう新たなタスクを起こすことになります
あとは例えばブラウザ自体が暗黙的に動作しているタスクとしてみなすことも出来てそのタスクから新たなタスクを発火することもあります
リスナー登録するタイプの利用時もそのパターンです
775デフォルトの名無しさん
2021/12/04(土) 05:13:43.45ID:aNU60Xul >>774
MFC/WinForms/JavaのSwing/Androidなどでは、マウスイベントやキーボードイベント、
メニューイベントは基本的に常時イネーブル状態になったままにして使うので、await
してしまうと、それぞれのハンドラに普通に入ってしまう。
そうなるとロジックが破綻するので排他処理するか、awaitする直前に、
一々ハンドラを disable にして、awaitの次の行に来た時に enableにする
必要がある。そんなメンドクサイことすべきじゃ無いし、そもそもdisable
にするなら、非同期のメリットも無い。
そもそもGUIスレッドは、イベントハンドラの二重起動は禁止すべきとされている。
MFC/WinForms/JavaのSwing/Androidなどでは、マウスイベントやキーボードイベント、
メニューイベントは基本的に常時イネーブル状態になったままにして使うので、await
してしまうと、それぞれのハンドラに普通に入ってしまう。
そうなるとロジックが破綻するので排他処理するか、awaitする直前に、
一々ハンドラを disable にして、awaitの次の行に来た時に enableにする
必要がある。そんなメンドクサイことすべきじゃ無いし、そもそもdisable
にするなら、非同期のメリットも無い。
そもそもGUIスレッドは、イベントハンドラの二重起動は禁止すべきとされている。
776デフォルトの名無しさん
2021/12/04(土) 06:02:11.33ID:6dkLKknu >>775
プログラミング分野は無数にある中で
なぜそんな特殊な環境だけを唐突に持ち出すのかも含めて分かりません
先ずは適用可能な分野から始めて経験と知識を積んで的確に判断できるようになってから結論づければよいかと
プログラミング分野は無数にある中で
なぜそんな特殊な環境だけを唐突に持ち出すのかも含めて分かりません
先ずは適用可能な分野から始めて経験と知識を積んで的確に判断できるようになってから結論づければよいかと
777デフォルトの名無しさん
2021/12/04(土) 10:01:49.43ID:wGH9SwaY 数学の天才と言い切った手前、後に引けなくなってきたか
自分の触ったことのある範囲でいいから弁解しなくちゃ
もうリンクトリストなんてどうでもいい、無知の印象を払拭するのが第一
自分の触ったことのある範囲でいいから弁解しなくちゃ
もうリンクトリストなんてどうでもいい、無知の印象を払拭するのが第一
778デフォルトの名無しさん
2021/12/04(土) 16:50:56.54ID:Peev2Fa+ 天才と言いつつテスト100点としか言えてない時点で程度は知れて馬鹿にされてるんだから今更取り繕わなくて良いのに
779デフォルトの名無しさん
2021/12/04(土) 16:53:37.05ID:d5QmhWSv リンクリストの話はまだまだお聞きしたいと思っていますのに…
>>738 のリストのソートのご感想とか
>>738 のリストのソートのご感想とか
780デフォルトの名無しさん
2021/12/04(土) 16:55:24.53ID:d5QmhWSv >>778
数学や物理のテストは、B4 の白紙一枚をわたされて、これに回答とか証明を書け、みたいな感じですが、そんなテストで一度でも 100 点をとれるのなら、それはそれですごいとは思いますよ
数学や物理のテストは、B4 の白紙一枚をわたされて、これに回答とか証明を書け、みたいな感じですが、そんなテストで一度でも 100 点をとれるのなら、それはそれですごいとは思いますよ
781デフォルトの名無しさん
2021/12/04(土) 17:09:21.39ID:Peev2Fa+ >>780
引き合いに出してたのがセンター試験だったり東大入試だったりで大学入試の成績を誇るしかない人なんだなって思っていました
引き合いに出してたのがセンター試験だったり東大入試だったりで大学入試の成績を誇るしかない人なんだなって思っていました
782デフォルトの名無しさん
2021/12/04(土) 17:19:28.99ID:2kIdNGW4 RustのLinked Listは遅いからRustはクソ言語
という論理は成立しましたか？
という論理は成立しましたか？
783デフォルトの名無しさん
2021/12/04(土) 17:28:22.69ID:d5QmhWSv >>781
回答用紙の返却のない試験の結果がどうしてわかるのか疑問ですよね
回答用紙の返却のない試験の結果がどうしてわかるのか疑問ですよね
784デフォルトの名無しさん
2021/12/04(土) 17:40:33.98ID:EblMEd3X どっちも中途半端な知識しかないのに他人の指摘は聞かないから救いようがない
隔離スレ立てたやつグッジョブ！
隔離スレ立てたやつグッジョブ！
785デフォルトの名無しさん
2021/12/04(土) 18:40:15.11ID:4fIXFJG6786デフォルトの名無しさん
2021/12/04(土) 18:46:57.96ID:WC3n5yU/787デフォルトの名無しさん
2021/12/04(土) 18:49:24.09ID:d5QmhWSv >>785
Java の awt では、どこにメッセージループが隠れているのか、あわしろ氏に訊いていただけませんか？
Java の awt では、どこにメッセージループが隠れているのか、あわしろ氏に訊いていただけませんか？
788デフォルトの名無しさん
2021/12/04(土) 18:51:13.15ID:d5QmhWSv >>786
私の時代には、そういうのは転部転科でもしようとしない限りわからなかったかと、今は変わったんですね…
私の時代には、そういうのは転部転科でもしようとしない限りわからなかったかと、今は変わったんですね…
789デフォルトの名無しさん
2021/12/04(土) 18:51:48.09ID:4fIXFJG6790デフォルトの名無しさん
2021/12/04(土) 18:53:03.93ID:WC3n5yU/ >>788
そう
そう
791デフォルトの名無しさん
2021/12/04(土) 18:54:08.07ID:wGH9SwaY センター試験や東大入試は数学の天才を黙らせようとした人らが基準を示すため言い出したのであって
当の数学の天才は一度も何の試験かにすら言及していない
高校の定期試験ということもあり得る
当の数学の天才は一度も何の試験かにすら言及していない
高校の定期試験ということもあり得る
792デフォルトの名無しさん
2021/12/04(土) 18:58:45.03ID:d5QmhWSv >>789
師が職場におられるとはうらやましいですね
師が職場におられるとはうらやましいですね
793デフォルトの名無しさん
2021/12/04(土) 19:00:26.50ID:d5QmhWSv >>791
私はしませんが、仮に「自分は数学の天才である」と名乗りたいときに、どういう風に自分の天才性を形容するべきか、はいい演習課題になりますね
あまりマニアックなことをいってもスルーされるだけですし
私はしませんが、仮に「自分は数学の天才である」と名乗りたいときに、どういう風に自分の天才性を形容するべきか、はいい演習課題になりますね
あまりマニアックなことをいってもスルーされるだけですし
794デフォルトの名無しさん
2021/12/04(土) 19:21:42.11ID:5XDM8baS 私は分かりやすく>>621
他には
東大後期模試300点
数学偏差値90
東大数学科卒
など
普通は
論文数/論文引用数/肩書き(教授など)/受賞歴/特許出願数
などが実績ですが
私はその辺の実績はありません
他には
東大後期模試300点
数学偏差値90
東大数学科卒
など
普通は
論文数/論文引用数/肩書き(教授など)/受賞歴/特許出願数
などが実績ですが
私はその辺の実績はありません
795デフォルトの名無しさん
2021/12/04(土) 19:24:17.53ID:5XDM8baS 残念ながら自称数学の天才には効かなかったようです
796デフォルトの名無しさん
2021/12/04(土) 19:27:28.34ID:4fIXFJG6 アカデミー賞受賞最新作はどうでしょうか？
アカデミックな感じで。
アカデミックな感じで。
797デフォルトの名無しさん
2021/12/04(土) 19:28:53.97ID:d5QmhWSv >>794
なんか生々しいんじゃないですか？もっとサラっとした感じでお願いします…
なんか生々しいんじゃないですか？もっとサラっとした感じでお願いします…
798デフォルトの名無しさん
2021/12/04(土) 19:43:56.41ID:mlo2c7Dg 数学の天才っていうとラマヌジャンとかそういう人？
799デフォルトの名無しさん
2021/12/04(土) 19:49:29.22ID:d5QmhWSv >>798
円の体積・表面積を算出したアルキメデスでしょう、ニュートンライプニッツの2000年ほど前の人
円の体積・表面積を算出したアルキメデスでしょう、ニュートンライプニッツの2000年ほど前の人
800デフォルトの名無しさん
2021/12/04(土) 21:07:23.15ID:Peev2Fa+ CSの天才じゃなくて数学の天才名乗るのはなんでなんだろうな
801デフォルトの名無しさん
2021/12/04(土) 22:13:27.18ID:6pcujX+T 自信が無いんだよ
802デフォルトの名無しさん
2021/12/04(土) 22:16:07.33ID:4fIXFJG6 コンビニエンスストアの天才。
803デフォルトの名無しさん
2021/12/04(土) 22:29:30.68ID:d5QmhWSv804デフォルトの名無しさん
2021/12/04(土) 22:41:59.72ID:4fIXFJG6 天才の心は、自分が天才になった時、初めて理解できるのではないでしょうか。
805デフォルトの名無しさん
2021/12/04(土) 23:15:15.65ID:fLZLWJ8o 見上げてErlang夜の星を
806デフォルトの名無しさん
2021/12/04(土) 23:41:44.19ID:4fIXFJG6 美少女の国に行きたいが、美少女じゃないので入れない。
807デフォルトの名無しさん
2021/12/05(日) 10:16:06.18ID:HAXCanWR808デフォルトの名無しさん
2021/12/05(日) 10:27:47.16ID:thYcMvTR 数学100点が自慢の自称天才と
歴史的に有名な超天才を比べる変なスレ
板的にはチューリングが出てこないのは変
歴史的に有名な超天才を比べる変なスレ
板的にはチューリングが出てこないのは変
809デフォルトの名無しさん
2021/12/05(日) 11:52:13.76ID:KOPBFOTo チューリングの話題はLGBT板で。
810デフォルトの名無しさん
2021/12/05(日) 12:45:24.80ID:KOPBFOTo じゃあ、モンティホール問題に納得できない人は、手を上げて。
811デフォルトの名無しさん
2021/12/05(日) 12:47:11.55ID:mf3NqWAC 板違い
812デフォルトの名無しさん
2021/12/05(日) 13:23:53.66ID:KOPBFOTo 良スレ。
アゲ。
アゲ。
813デフォルトの名無しさん
2021/12/05(日) 15:04:30.36ID:RsIoD/ak >>803
>オーダーの話と実時間の話をシレっと往ったり還ったりするところなんかは、私には変だと思いましたね、
>アルゴリズムの評価はオーダーで行うのが普通で他はほとんどみない…
書くのが長くなるからオーダーで書いているだけで、オーダーだけでは正しい特徴を捉えられない
場合がある。
例えば、同じオーダーでも乗算や条件分岐の両方が使われているアルゴリズムとマシン語の
1クロックの命令1個にコンパイルされるものでは全然違う。
また、N個のデータを持っているハッシュ構造は、1回の検索は、数学的に厳密にはO(N)
だが、実験的(実際的)にはO(1)のように振舞うと言われており、厳密に扱うには、
オーダーの記号だけでは表現しきれない。
もし、オーダーだけで評価すればいいのなら、チューリング完全なあらゆる言語は、
同じアルゴリズムを使うことは可能で、同じオーダーの時間で計算できてしまうから、
速度比較には役立たない。
>オーダーの話と実時間の話をシレっと往ったり還ったりするところなんかは、私には変だと思いましたね、
>アルゴリズムの評価はオーダーで行うのが普通で他はほとんどみない…
書くのが長くなるからオーダーで書いているだけで、オーダーだけでは正しい特徴を捉えられない
場合がある。
例えば、同じオーダーでも乗算や条件分岐の両方が使われているアルゴリズムとマシン語の
1クロックの命令1個にコンパイルされるものでは全然違う。
また、N個のデータを持っているハッシュ構造は、1回の検索は、数学的に厳密にはO(N)
だが、実験的(実際的)にはO(1)のように振舞うと言われており、厳密に扱うには、
オーダーの記号だけでは表現しきれない。
もし、オーダーだけで評価すればいいのなら、チューリング完全なあらゆる言語は、
同じアルゴリズムを使うことは可能で、同じオーダーの時間で計算できてしまうから、
速度比較には役立たない。
814デフォルトの名無しさん
2021/12/05(日) 15:19:38.16ID:HAXCanWR >>813
＞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) に近くなるでしょう
ハッシュテーブルには衝突がつき物ですが、そういうところも厳密に評価するのは難しいかもしれませんね
ただし、
＞同じオーダーでも乗算や条件分岐の両方が使われているアルゴリズムとマシン語の
＞1クロックの命令1個にコンパイルされるものでは全然違う。
そのとおりですが、それは所詮 O(f) の f の係数が違うだけでしょう、というか、そういうものはケースバイケースで一般論には載せ難いかと
そもそもあなたは、Σクロック（命令種）、で近似的に評価しようとしてますが、その姿勢は評価しますが、CPU 内の RISC 変換と並列実行、投機実行等までは及んでおらず、ある意味これも粗粗の近似だと思います
CPU 種類やメモリ構成などによって大きく変わるのですから、オーダーでの評価にとどめておくのが妥当なのでは？
＞もし、オーダーだけで評価すればいいのなら、チューリング完全なあらゆる言語は、
＞同じアルゴリズムを使うことは可能で、同じオーダーの時間で計算できてしまうから、
＞速度比較には役立たない。
そりゃそうです、言語間の速度比較にオーダーを使う方が間違っています
総じて評価センスの問題かと
815デフォルトの名無しさん
2021/12/05(日) 15:34:15.66ID:HAXCanWR >>810
高卒の私は、いくら考えても意味がわかりませんでした…
高卒の私は、いくら考えても意味がわかりませんでした…
816デフォルトの名無しさん
2021/12/05(日) 16:04:00.19ID:L/b/spZ8817デフォルトの名無しさん
2021/12/05(日) 16:12:34.15ID:L/b/spZ8 >>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)ではない。
不定積分の等号も集合論的な意味であって、等しいという意味ではないと聞いたことが
あると思うが、それと同じような定義。
ハッシュ構造は、「一回の検索」でも、数学的には、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)ではない。
不定積分の等号も集合論的な意味であって、等しいという意味ではないと聞いたことが
あると思うが、それと同じような定義。
818デフォルトの名無しさん
2021/12/05(日) 16:15:03.84ID:L/b/spZ8819デフォルトの名無しさん
2021/12/05(日) 16:36:22.78ID:5+FKsWbz 実時間が重要なら黙ってベンチ出せや
820デフォルトの名無しさん
2021/12/05(日) 16:50:30.44ID:HAXCanWR >>817
＞しかし、実際問題は、Nが常識の範囲内の大きさではO(1)のように振舞うことが分かっているので
それには理由があるのでしょう？その理由はなんですか？「振舞うことがわかっている」という観測事実のみが根拠とは到底考えられませんね
>>814 が間違っているのであれば、あなたの解釈はなんですか？
＞数学的には、O(f(N))とは、Nを無限に大きくしても、処理時間をf(N)で割るとある
＞上限値未満であるという意味。ハッシュテーブルの検索は、Nを無限に大きくすると、
＞定数的ではないので、O(1)ではない。
そりゃ、衝突が頻繁に発生するようになると、それを連鎖法で処理するか、あるいはオープンハッシュ法＆セカンドハッシュ関数で処理するか、
いずれにしても N がハッシュテーブルサイズに比して大きくなりすぎるとO(1)から程遠くなるでしょう
しかし、今はハッシュテーブルサイズが N に比してそんなに大きくないことが前提だと思っていましたが、そういうハッシュテーブルの重要な性質を無視して N→∞にいきなり振るとか、やはり実装経験が不足しているとしか考えられません
あなたには、オープンハッシュ法でも連鎖法でもいいから、一度実装してみることをお勧めします、そうすれば、そんな無茶な話をふったり出来ないはずです
＞しかし、実際問題は、Nが常識の範囲内の大きさではO(1)のように振舞うことが分かっているので
それには理由があるのでしょう？その理由はなんですか？「振舞うことがわかっている」という観測事実のみが根拠とは到底考えられませんね
>>814 が間違っているのであれば、あなたの解釈はなんですか？
＞数学的には、O(f(N))とは、Nを無限に大きくしても、処理時間をf(N)で割るとある
＞上限値未満であるという意味。ハッシュテーブルの検索は、Nを無限に大きくすると、
＞定数的ではないので、O(1)ではない。
そりゃ、衝突が頻繁に発生するようになると、それを連鎖法で処理するか、あるいはオープンハッシュ法＆セカンドハッシュ関数で処理するか、
いずれにしても N がハッシュテーブルサイズに比して大きくなりすぎるとO(1)から程遠くなるでしょう
しかし、今はハッシュテーブルサイズが N に比してそんなに大きくないことが前提だと思っていましたが、そういうハッシュテーブルの重要な性質を無視して N→∞にいきなり振るとか、やはり実装経験が不足しているとしか考えられません
あなたには、オープンハッシュ法でも連鎖法でもいいから、一度実装してみることをお勧めします、そうすれば、そんな無茶な話をふったり出来ないはずです
821デフォルトの名無しさん
2021/12/05(日) 16:51:42.71ID:HAXCanWR822デフォルトの名無しさん
2021/12/05(日) 18:19:46.95ID:KOPBFOTo INTEL Core N4200。
823デフォルトの名無しさん
2021/12/05(日) 19:15:19.02ID:F58n2Ec9 この数学100点の人はプログラミングできないんだから、ベンチ出せは禁句だよ
824デフォルトの名無しさん
2021/12/05(日) 19:16:59.90ID:3Mcy6QkY825デフォルトの名無しさん
2021/12/05(日) 19:54:51.36ID:HAXCanWR826デフォルトの名無しさん
2021/12/05(日) 22:25:34.77ID:MGzOS3+Z 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回で見つかる
バケット数は、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回で見つかる
827デフォルトの名無しさん
2021/12/05(日) 22:30:23.53ID:GkhJF2sm >>826
Rustのハッシュそうなんだ？
Rustのハッシュそうなんだ？
828デフォルトの名無しさん
2021/12/05(日) 22:55:00.31ID:5+FKsWbz Rubyだぞ
829デフォルトの名無しさん
2021/12/05(日) 23:55:41.03ID:o2Lx+v4j830デフォルトの名無しさん
2021/12/06(月) 00:01:51.71ID:3rXx+R7R ベンチをもっと気楽に行うために単体テストフレームワークを使ってベンチ書いてる。
831デフォルトの名無しさん
2021/12/06(月) 00:03:31.65ID:kjD6KzfX832デフォルトの名無しさん
2021/12/06(月) 00:07:28.71ID:kjD6KzfX なお、ハッシュ値の最大数を動的に増やしていくのならば、本来のハッシュ構造ではない。
本来のハッシュ構造は振り分けられる量は固定サイズ。
だから、ハッシュ値の計算も固定されたアルゴリズムで処理が固定された関数で
行う。
色々と勝手に定義を変えてはいかん。
言葉を勝手に再定義すれば議論になるわけ無い。
本来のハッシュ構造は振り分けられる量は固定サイズ。
だから、ハッシュ値の計算も固定されたアルゴリズムで処理が固定された関数で
行う。
色々と勝手に定義を変えてはいかん。
言葉を勝手に再定義すれば議論になるわけ無い。
833デフォルトの名無しさん
2021/12/06(月) 00:25:08.26ID:3rXx+R7R （キリッ）が抜けてるのでは？
834デフォルトの名無しさん
2021/12/06(月) 00:25:34.03ID:O1qGwT+t リンクリストの次はハッシュテーブルかよ
データ構造スレでやれ
データ構造スレでやれ
835デフォルトの名無しさん
2021/12/06(月) 00:49:48.95ID:3rXx+R7R 良スレ。
アゲ。
アゲ。
836826
2021/12/06(月) 01:37:20.07ID:siDRvkcR >>826
修正
>増え方が、N に比例しなくて、log N に比例するから
>例えば、2^20 = 百万で、2^21 = 2百万では、
>線形探索では毎回、百万回増えるけど、
>ハッシュでは、1回だけ再構築して、その後は、21回で見つかる
これはデータベースで使う、2分探索の事だった。
ハッシュは、バケット数で割った余りで決まるから、O(1)だった
修正
>増え方が、N に比例しなくて、log N に比例するから
>例えば、2^20 = 百万で、2^21 = 2百万では、
>線形探索では毎回、百万回増えるけど、
>ハッシュでは、1回だけ再構築して、その後は、21回で見つかる
これはデータベースで使う、2分探索の事だった。
ハッシュは、バケット数で割った余りで決まるから、O(1)だった
837デフォルトの名無しさん
2021/12/06(月) 01:49:17.06ID:kjD6KzfX >>836
ハッシュの表の様なものが固定サイズであるところの
素朴なハッシュの検索は、Nが大きい時には、O(N)。N が小さい時には、O(1)。
Nが大きくなるに従ってその表を時々大きくしていくようなものは、
考慮の対象にはしない。
ハッシュの表の様なものが固定サイズであるところの
素朴なハッシュの検索は、Nが大きい時には、O(N)。N が小さい時には、O(1)。
Nが大きくなるに従ってその表を時々大きくしていくようなものは、
考慮の対象にはしない。
838デフォルトの名無しさん
2021/12/06(月) 01:53:00.58ID:kjD6KzfX >>837
[補足]
以下、ハッシュの表の様なものが固定サイズであるところの素朴なハッシュの検索
についてだけを考える。
ハッシュの中に入っているデータの個数が N 個の時に、あるキーを持つ
データを1個だけ探すのに掛かる平均時間を g(N)とすると、数学的には
g(N)=O(N)。
しかし、この g(N) は、g(N) = a N + b と近似した場合の a の値が極端に小さい。
なので、N が小さい時には、O(1)であるかのように振舞う。
そういう意味だ。
これで理解できないなら、数学的想像力や理解力が足りてない。
[補足]
以下、ハッシュの表の様なものが固定サイズであるところの素朴なハッシュの検索
についてだけを考える。
ハッシュの中に入っているデータの個数が N 個の時に、あるキーを持つ
データを1個だけ探すのに掛かる平均時間を g(N)とすると、数学的には
g(N)=O(N)。
しかし、この g(N) は、g(N) = a N + b と近似した場合の a の値が極端に小さい。
なので、N が小さい時には、O(1)であるかのように振舞う。
そういう意味だ。
これで理解できないなら、数学的想像力や理解力が足りてない。
839デフォルトの名無しさん
2021/12/06(月) 02:05:17.38ID:McsJgKJD RubyガイジとRustガイジの熱いマッチが今始まる
840デフォルトの名無しさん
2021/12/06(月) 02:22:55.84ID:XuzXkdX2 >>839
この数学100点マンはRustを叩いてる人で常に生ポインタ派のC/C++史上主義な人
ただしコードを出したことがないのでプログラミング能力がないと推定されている
さらにオーダーについても勝手な定義で無茶な主張を繰り返している
この数学100点マンはRustを叩いてる人で常に生ポインタ派のC/C++史上主義な人
ただしコードを出したことがないのでプログラミング能力がないと推定されている
さらにオーダーについても勝手な定義で無茶な主張を繰り返している
841デフォルトの名無しさん
2021/12/06(月) 02:24:44.88ID:McsJgKJD842デフォルトの名無しさん
2021/12/06(月) 02:33:01.01ID:kjD6KzfX >>840
お前もとことん馬鹿だな。
コード書いても抽象理解が出来ない人には、そのコードの本質は分からんし、
こんなところに書ききれるわけでも無いからかけないだけだ。
なお、抽象 = シンボライズ、シンボリック
という意味で、曖昧や玉虫色という意味では無いぞ。
本質的な部分を記号化、定理化、規則化、一般化して理解できるようにしたもの
を「抽象化」と言う。
お前もとことん馬鹿だな。
コード書いても抽象理解が出来ない人には、そのコードの本質は分からんし、
こんなところに書ききれるわけでも無いからかけないだけだ。
なお、抽象 = シンボライズ、シンボリック
という意味で、曖昧や玉虫色という意味では無いぞ。
本質的な部分を記号化、定理化、規則化、一般化して理解できるようにしたもの
を「抽象化」と言う。
843デフォルトの名無しさん
2021/12/06(月) 03:29:12.50ID:rYDKtnCr linkedlistの計算量を勘違いし
平衡二分木とハッシュセットを混同する
数学100点マンがいると聞いて
平衡二分木とハッシュセットを混同する
数学100点マンがいると聞いて
844デフォルトの名無しさん
2021/12/06(月) 05:30:40.66ID:lQ57RfmU845デフォルトの名無しさん
2021/12/06(月) 05:43:24.70ID:4SyL85E7 >>838
＞、g(N) = a N + b と近似した場合の a の値が極端に小さい。…①
なぜですか？
ハッシュテーブルの実装方法から論じてみください
もしかして、あなたは①を数学の公理、みたいに扱っているのですか？そんなことではコンピューターサイエンスは無意味だし面白くないでしょう？
でもC/C++ 至上主義者というのなら、私と気が合いますね
＞、g(N) = a N + b と近似した場合の a の値が極端に小さい。…①
なぜですか？
ハッシュテーブルの実装方法から論じてみください
もしかして、あなたは①を数学の公理、みたいに扱っているのですか？そんなことではコンピューターサイエンスは無意味だし面白くないでしょう？
でもC/C++ 至上主義者というのなら、私と気が合いますね
846デフォルトの名無しさん
2021/12/06(月) 08:46:35.08ID:XZMNlO6i847デフォルトの名無しさん
2021/12/06(月) 10:07:17.08ID:OAOUQrou なんでハッシュテーブルの話になったのかと思えば>>813にいちゃもん付けたいだけか
848デフォルトの名無しさん
2021/12/06(月) 11:16:09.54ID:O1qGwT+t ベンチマークもなしに実時間の話をされてもなぁ
しかも具体的な実装上の問題点の指摘もなく他人のベンチマークは信用できないとか宣われてしまうとこちらとしては会話しても意味がない人なんだと判断せざるを得ないんですよね
しかも具体的な実装上の問題点の指摘もなく他人のベンチマークは信用できないとか宣われてしまうとこちらとしては会話しても意味がない人なんだと判断せざるを得ないんですよね
849デフォルトの名無しさん
2021/12/06(月) 11:52:31.39ID:q0VGOju1 >>845
公理ではなくて、処理時間の平均値を確率論で書いている。
公理ではなくて、処理時間の平均値を確率論で書いている。
850デフォルトの名無しさん
2021/12/06(月) 11:57:28.95ID:q0VGOju1851デフォルトの名無しさん
2021/12/06(月) 12:01:12.30ID:EOOuRFRK852デフォルトの名無しさん
2021/12/06(月) 12:06:08.85ID:q0VGOju1 >>851
確率論では、ランダム性を仮定する。
確率論では、ランダム性を仮定する。
853デフォルトの名無しさん
2021/12/06(月) 12:43:27.37ID:XuzXkdX2 >>842
ここはC++ vs Rustスレなのだからコードを出さなければ何も判定できない
机上の空論ばかり書き綴るよりも現実に使われるCPUと向き合わなければならない
例えばRustの標準ライブラリHashMapでも用いているSwiss Tables法ではハッシュ衝突時の別エントリ探索にSIMD命令を用いている
CPU命令4つで16エントリ同時に探索候補を判別していきメモリキャシュも活かすようこのためのメタデータを連続領域に配置している
ここはC++ vs Rustスレなのだからコードを出さなければ何も判定できない
机上の空論ばかり書き綴るよりも現実に使われるCPUと向き合わなければならない
例えばRustの標準ライブラリHashMapでも用いているSwiss Tables法ではハッシュ衝突時の別エントリ探索にSIMD命令を用いている
CPU命令4つで16エントリ同時に探索候補を判別していきメモリキャシュも活かすようこのためのメタデータを連続領域に配置している
854デフォルトの名無しさん
2021/12/06(月) 13:08:20.11ID:PE/XVSQC855デフォルトの名無しさん
2021/12/06(月) 13:21:52.08ID:iO91q1zt856デフォルトの名無しさん
2021/12/06(月) 13:46:42.22ID:lQ57RfmU >>848
ずっとそんな感じ
計算量ではちゃんとわからない、コストがかかって遅くなる、とか言いつつ、忙しいから実装はできない、お前は馬鹿だから理解できない、みたいなことを数ヶ月に渡って大量に書き込み続けてる
数学でいつも100点取るらしいし、さぞ偉いお方なんでしょうなあ…
ずっとそんな感じ
計算量ではちゃんとわからない、コストがかかって遅くなる、とか言いつつ、忙しいから実装はできない、お前は馬鹿だから理解できない、みたいなことを数ヶ月に渡って大量に書き込み続けてる
数学でいつも100点取るらしいし、さぞ偉いお方なんでしょうなあ…
857デフォルトの名無しさん
2021/12/06(月) 18:09:07.25ID:cGshi4Y2858デフォルトの名無しさん
2021/12/06(月) 19:52:13.50ID:4SyL85E7 >>856
リジェクトされたネタだとか…
リジェクトされたネタだとか…
859デフォルトの名無しさん
2021/12/06(月) 20:04:46.70ID:h+yNZQm8 >>857
意味不明
意味不明
860デフォルトの名無しさん
2021/12/06(月) 21:08:31.14ID:4qQbBrsy ハッシュが衝突しやすいコリジョンデータを使ったDDos攻撃が出来るのでは？
861デフォルトの名無しさん
2021/12/07(火) 13:11:29.70ID:jcfwZSTS >>854
最大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)である。
最大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)である。
862デフォルトの名無しさん
2021/12/07(火) 13:27:33.41ID:pFZAiCY5 Wikipediaでも明記されている
・ハッシュテーブルの検索や追加はO(1)
・ハッシュテーブルの拡張もO(1)
> ハッシュテーブルはキーをもとに生成されたハッシュ値を添え字とした配列である。
> キーを要約する値であるハッシュ値を添え字として値を管理することで、検索や追加を要素数によらず定数時間O(1)で実現する。
>
> 利用率が一定を超えた場合に、より大きいサイズのハッシュテーブルを用意して格納し直す操作が必要となる。これをリハッシュ (rehash) と呼ぶ。
> この操作はすべての要素のハッシュ値を再計算して新たなハッシュテーブルに格納するためO(n)であるが、
> 配列のサイズを指数的に拡張する事で、動的配列の末尾追加操作と同様に償却解析によって計算量をO(1)とみなす事ができる。
・ハッシュテーブルの検索や追加はO(1)
・ハッシュテーブルの拡張もO(1)
> ハッシュテーブルはキーをもとに生成されたハッシュ値を添え字とした配列である。
> キーを要約する値であるハッシュ値を添え字として値を管理することで、検索や追加を要素数によらず定数時間O(1)で実現する。
>
> 利用率が一定を超えた場合に、より大きいサイズのハッシュテーブルを用意して格納し直す操作が必要となる。これをリハッシュ (rehash) と呼ぶ。
> この操作はすべての要素のハッシュ値を再計算して新たなハッシュテーブルに格納するためO(n)であるが、
> 配列のサイズを指数的に拡張する事で、動的配列の末尾追加操作と同様に償却解析によって計算量をO(1)とみなす事ができる。
863デフォルトの名無しさん
2021/12/07(火) 14:35:15.82ID:iH9Jzajc >>862
例えば、M=128で、128種類のハッシュ値に振り分けられるなっている
ハッシュ構造の場合、N=128万にすると、1つのハッシュ値に1万個の
(key, value)のペアが対応している。
そして、1個のkeyを検索する時、平均的には、1万個の半分の5000回
くらいkey値の比較を行うと一致するものが見つかる。
なのでこの場合、1個のkeyに対する検索時間は
5000*(keyの比較に要する時間)
となる。
Nを128億にすると、
5000万*(keyの比較に要する時間)
になる。
例えば、M=128で、128種類のハッシュ値に振り分けられるなっている
ハッシュ構造の場合、N=128万にすると、1つのハッシュ値に1万個の
(key, value)のペアが対応している。
そして、1個のkeyを検索する時、平均的には、1万個の半分の5000回
くらいkey値の比較を行うと一致するものが見つかる。
なのでこの場合、1個のkeyに対する検索時間は
5000*(keyの比較に要する時間)
となる。
Nを128億にすると、
5000万*(keyの比較に要する時間)
になる。
864デフォルトの名無しさん
2021/12/07(火) 14:52:05.46ID:iH9Jzajc >>863
誤:128種類のハッシュ値に振り分けられるなっている
正:128種類のハッシュ値に振り分けられるようになっている
誤:5000*(keyの比較に要する時間)
正:5000*(1回のkeyの比較に要する時間) // ()内は、keyが文字列の場合、1回の文字列比較に掛かる時間。
誤:5000万*(keyの比較に要する時間)
正:5000万*(1回のkeyの比較に要する時間) // ()内は、keyが文字列の場合、1回の文字列比較に掛かる時間。
>>862
> 利用率が一定を超えた場合に、より大きいサイズのハッシュテーブルを用意して格納し直す操作が必要となる。これをリハッシュ (rehash) と呼ぶ。
>>861 の4行目で、リハッシュは行わないと断った。
はっきり、Mを定数とすると書いている。
誤:128種類のハッシュ値に振り分けられるなっている
正:128種類のハッシュ値に振り分けられるようになっている
誤:5000*(keyの比較に要する時間)
正:5000*(1回のkeyの比較に要する時間) // ()内は、keyが文字列の場合、1回の文字列比較に掛かる時間。
誤:5000万*(keyの比較に要する時間)
正:5000万*(1回のkeyの比較に要する時間) // ()内は、keyが文字列の場合、1回の文字列比較に掛かる時間。
>>862
> 利用率が一定を超えた場合に、より大きいサイズのハッシュテーブルを用意して格納し直す操作が必要となる。これをリハッシュ (rehash) と呼ぶ。
>>861 の4行目で、リハッシュは行わないと断った。
はっきり、Mを定数とすると書いている。
865デフォルトの名無しさん
2021/12/07(火) 17:09:08.05ID:Io+x78vq 数学100点マンの机上の空論がさらに輪をかけてるな
>>864
> 最大M個の振り分け能力があるハッシュ構造にN個の(key, value)ペアを書き込んでいる場合を考える。
> M=128で、128種類のハッシュ値に振り分けられるようになっている
> Nを128億にすると、5000万*(keyの比較に要する時間)になる。
つまり128億個のデータを128個のハッシュ値パターンでハッシュテーブルに格納か
現実の世界ではなく一人だけの特殊な妄想世界で空論
>>864
> 最大M個の振り分け能力があるハッシュ構造にN個の(key, value)ペアを書き込んでいる場合を考える。
> M=128で、128種類のハッシュ値に振り分けられるようになっている
> Nを128億にすると、5000万*(keyの比較に要する時間)になる。
つまり128億個のデータを128個のハッシュ値パターンでハッシュテーブルに格納か
現実の世界ではなく一人だけの特殊な妄想世界で空論
866デフォルトの名無しさん
2021/12/07(火) 17:09:50.30ID:q8J3SSC4 worst caseはO(n)って言えば一言で終わる話だった
867デフォルトの名無しさん
2021/12/07(火) 18:11:38.99ID:U30hRDTM 平均もO(n)だろ
868デフォルトの名無しさん
2021/12/07(火) 18:19:10.70ID:j/zIE0U5 でそれにC++やRustとどう関係が？
869デフォルトの名無しさん
2021/12/07(火) 18:22:43.53ID:U30hRDTM さあ
870デフォルトの名無しさん
2021/12/07(火) 18:27:32.38ID:2dc6hCU/ とにかく、この >>813 の書き込みはすごい、ってことだ
このスレの集大成に近い出来だと思う
このスレの集大成に近い出来だと思う
■ このスレッドは過去ログ倉庫に格納されています
