C++ vs Rust

1 名前：デフォルトの名無しさん mailto:sage [2021/04/24(土) 08:04:49.48 ID:nPKzA798.net] 競え 802 名前：デフォルトの名無しさん mailto:sage [2021/12/04(土) 17:40:33.98 ID:EblMEd3X.net] どっちも中途半端な知識しかないのに他人の指摘は聞かないから救いようがない 隔離スレ立てたやつグッジョブ！ 803 名前：デフォルトの名無しさん [2021/12/04(土) 18:40:15.11 ID:4fIXFJG6.net] >>773 あわしろ氏が言ってたけど、Win32ではメッセージループを自分で作るらしいですよ。 まあ、配送はDispatchMessage()でやってもらうんですが。 804 名前：デフォルトの名無しさん mailto:sage [2021/12/04(土) 18:46:57.96 ID:WC3n5yU/.net] >>783 マジレスすると 点数はわかる 805 名前：デフォルトの名無しさん mailto:sage [2021/12/04(土) 18:49:24.09 ID:d5QmhWSv.net] >>785 Java の awt では、どこにメッセージループが隠れているのか、あわしろ氏に訊いていただけませんか？ 806 名前：デフォルトの名無しさん mailto:sage [2021/12/04(土) 18:51:13.15 ID:d5QmhWSv.net] >>786 私の時代には、そういうのは転部転科でもしようとしない限りわからなかったかと、今は変わったんですね… 807 名前：デフォルトの名無しさん [2021/12/04(土) 18:51:48.09 ID:4fIXFJG6.net] >>787 了解です。 来週、職場で会うと思うので、聞いておきます。 808 名前：デフォルトの名無しさん mailto:sage [2021/12/04(土) 18:53:03.93 ID:WC3n5yU/.net] >>788 そう 809 名前：デフォルトの名無しさん mailto:sage [2021/12/04(土) 18:54:08.07 ID:wGH9SwaY.net] センター試験や東大入試は数学の天才を黙らせようとした人らが基準を示すため言い出したのであって 当の数学の天才は一度も何の試験かにすら言及していない 高校の定期試験ということもあり得る 810 名前：デフォルトの名無しさん mailto:sage [2021/12/04(土) 18:58:45.03 ID:d5QmhWSv.net] >>789 師が職場におられるとはうらやましいですね 811 名前：デフォルトの名無しさん mailto:sage [2021/12/04(土) 19:00:26.50 ID:d5QmhWSv.net] >>791 私はしませんが、仮に「自分は数学の天才である」と名乗りたいときに、どういう風に自分の天才性を形容するべきか、はいい演習課題になりますね あまりマニアックなことをいってもスルーされるだけですし 812 名前：デフォルトの名無しさん mailto:sage [2021/12/04(土) 19:21:42.11 ID:5XDM8baS.net] 私は分かりやすく>>621 他には 東大後期模試300点 数学偏差値90 東大数学科卒 など 普通は 論文数/論文引用数/肩書き(教授など)/受賞歴/特許出願数 などが実績ですが 私はその辺の実績はありません 813 名前：デフォルトの名無しさん mailto:sage [2021/12/04(土) 19:24:17.53 ID:5XDM8baS.net] 残念ながら自称数学の天才には効かなかったようです 814 名前：デフォルトの名無しさん [2021/12/04(土) 19:27:28.34 ID:4fIXFJG6.net] アカデミー賞受賞最新作はどうでしょうか？ アカデミックな感じで。 815 名前：デフォルトの名無しさん mailto:sage [2021/12/04(土) 19:28:53.97 ID:d5QmhWSv.net] >>794 なんか生々しいんじゃないですか？もっとサラっとした感じでお願いします… 816 名前：デフォルトの名無しさん mailto:sage [2021/12/04(土) 19:43:56.41 ID:mlo2c7Dg.net] 数学の天才っていうとラマヌジャンとかそういう人？ 817 名前：デフォルトの名無しさん mailto:sage [2021/12/04(土) 19:49:29.22 ID:d5QmhWSv.net] >>798 円の体積・表面積を算出したアルキメデスでしょう、ニュートンライプニッツの2000年ほど前の人 818 名前：デフォルトの名無しさん mailto:sage [2021/12/04(土) 21:07:23.15 ID:Peev2Fa+.net] CSの天才じゃなくて数学の天才名乗るのはなんでなんだろうな 819 名前：デフォルトの名無しさん mailto:sage [2021/12/04(土) 22:13:27.18 ID:6pcujX+T.net] 自信が無いんだよ 820 名前：デフォルトの名無しさん [2021/12/04(土) 22:16:07.33 ID:4fIXFJG6.net] コンビニエンスストアの天才。 821 名前：デフォルトの名無しさん mailto:sage [2021/12/04(土) 22:29:30.68 ID:d5QmhWSv.net] >>800 鋭い視点ですね オーダーの話と実時間の話をシレっと往ったり還ったりするところなんかは、私には変だと思いましたね、アルゴリズムの評価はオーダーで行うのが普通で他はほとんどみない… >>799 ×　円 ○　球 822 名前：デフォルトの名無しさん [2021/12/04(土) 22:41:59.72 ID:4fIXFJG6.net] 天才の心は、自分が天才になった時、初めて理解できるのではないでしょうか。 823 名前：デフォルトの名無しさん mailto:sage [2021/12/04(土) 23:15:15.65 ID:fLZLWJ8o.net] 見上げてErlang夜の星を 824 名前：デフォルトの名無しさん [2021/12/04(土) 23:41:44.19 ID:4fIXFJG6.net] 美少女の国に行きたいが、美少女じゃないので入れない。 825 名前：デフォルトの名無しさん mailto:sage [2021/12/05(日) 10:16:06.18 ID:HAXCanWR.net] >>804 >>799 の人は1000年以上も登場する時代を間違えた人だから、その孤独感たるや想像を絶するでしょうね… 826 名前：デフォルトの名無しさん mailto:sage [2021/12/05(日) 10:27:47.16 ID:thYcMvTR.net] 数学100点が自慢の自称天才と 歴史的に有名な超天才を比べる変なスレ 板的にはチューリングが出てこないのは変 827 名前：デフォルトの名無しさん [2021/12/05(日) 11:52:13.76 ID:KOPBFOTo.net] チューリングの話題はLGBT板で。 828 名前：デフォルトの名無しさん [2021/12/05(日) 12:45:24.80 ID:KOPBFOTo.net] じゃあ、モンティホール問題に納得できない人は、手を上げて。 829 名前：デフォルトの名無しさん mailto:sage [2021/12/05(日) 12:47:11.55 ID:mf3NqWAC.net] 板違い 830 名前：デフォルトの名無しさん [2021/12/05(日) 13:23:53.66 ID:KOPBFOTo.net] 良スレ。 アゲ。 831 名前：デフォルトの名無しさん mailto:sage [2021/12/05(日) 15:04:30.36 ID:RsIoD/ak.net] >>803 >オーダーの話と実時間の話をシレっと往ったり還ったりするところなんかは、私には変だと思いましたね、 >アルゴリズムの評価はオーダーで行うのが普通で他はほとんどみない… 書くのが長くなるからオーダーで書いているだけで、オーダーだけでは正しい特徴を捉えられない 場合がある。 例えば、同じオーダーでも乗算や条件分岐の両方が使われているアルゴリズムとマシン語の 1クロックの命令1個にコンパイルされるものでは全然違う。 また、N個のデータを持っているハッシュ構造は、1回の検索は、数学的に厳密にはO(N) だが、実験的(実際的)にはO(1)のように振舞うと言われており、厳密に扱うには、 オーダーの記号だけでは表現しきれない。 もし、オーダーだけで評価すればいいのなら、チューリング完全なあらゆる言語は、 同じアルゴリズムを使うことは可能で、同じオーダーの時間で計算できてしまうから、 速度比較には役立たない。 832 名前：デフォルトの名無しさん mailto:sage [2021/12/05(日) 15:19:38.16 ID:HAXCanWR.net] >>813 ＞1回の検索は、数学的に厳密にはO(N)だが、実験的(実際的)にはO(1)のように振舞う ハッシュテーブルの構築は O(N) ですが、既存のデータをハッシュで引く割合が多ければ多いほど O(1) に近くなるでしょう ハッシュテーブルには衝突がつき物ですが、そういうところも厳密に評価するのは難しいかもしれませんね ただし、 ＞同じオーダーでも乗算や条件分岐の両方が使われているアルゴリズムとマシン語の ＞1クロックの命令1個にコンパイルされるものでは全然違う。 そのとおりですが、それは所詮 O(f) の f の係数が違うだけでしょう、というか、そういうものはケースバイケースで一般論には載せ難いかと そもそもあなたは、Σクロック（命令種）、で近似的に評価しようとしてますが、その姿勢は評価しますが、CPU 内の RISC 変換と並列実行、投機実行等までは及んでおらず、ある意味これも粗粗の近似だと思います CPU 種類やメモリ構成などによって大きく変わるのですから、オーダーでの評価にとどめておくのが妥当なのでは？ ＞もし、オーダーだけで評価すればいいのなら、チューリング完全なあらゆる言語は、 833 名前：＞同じアルゴリズムを使うことは可能で、同じオーダーの時間で計算できてしまうから、 ＞速度比較には役立たない。 そりゃそうです、言語間の速度比較にオーダーを使う方が間違っています 総じて評価センスの問題かと [] [ここ壊れてます] 834 名前：デフォルトの名無しさん mailto:sage [2021/12/05(日) 15:34:15.66 ID:HAXCanWR.net] >>810 高卒の私は、いくら考えても意味がわかりませんでした… 835 名前：デフォルトの名無しさん mailto:sage [2021/12/05(日) 16:04:00.19 ID:L/b/spZ8.net] >>814 >＞1回の検索は、数学的に厳密にはO(N)だが、実験的(実際的)にはO(1)のように振舞う >ハッシュテーブルの構築は O(N) ですが、既存のデータをハッシュで引く割合が多ければ多いほど O(1) に近くなるでしょう あなたは、>>813で 「また、N個のデータを持っているハッシュ構造は、1回の検索は、数学的に厳密にはO(N) 　だが、実験的(実際的)にはO(1)のように振舞うと言われており、厳密に扱うには、 　オーダーの記号だけでは表現しきれない。」 と書いてあることの意味が全く分かって無い。 秀才以上で無いと発言禁止だ。 836 名前：デフォルトの名無しさん [2021/12/05(日) 16:12:34.15 ID:L/b/spZ8.net] >>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)ではない。 不定積分の等号も集合論的な意味であって、等しいという意味ではないと聞いたことが あると思うが、それと同じような定義。 837 名前：デフォルトの名無しさん mailto:sage [2021/12/05(日) 16:15:03.84 ID:L/b/spZ8.net] >>817 [さらに補足] なお、そもそも、等号 = の左辺に O(xxx)の記号は書くべきではないという説もある。 838 名前：デフォルトの名無しさん mailto:sage [2021/12/05(日) 16:36:22.78 ID:5+FKsWbz.net] 実時間が重要なら黙ってベンチ出せや 839 名前：デフォルトの名無しさん mailto:sage [2021/12/05(日) 16:50:30.44 ID:HAXCanWR.net] >>817 ＞しかし、実際問題は、Nが常識の範囲内の大きさではO(1)のように振舞うことが分かっているので それには理由があるのでしょう？その理由はなんですか？「振舞うことがわかっている」という観測事実のみが根拠とは到底考えられませんね >>814 が間違っているのであれば、あなたの解釈はなんですか？ ＞数学的には、O(f(N))とは、Nを無限に大きくしても、処理時間をf(N)で割るとある ＞上限値未満であるという意味。ハッシュテーブルの検索は、Nを無限に大きくすると、 ＞定数的ではないので、O(1)ではない。 そりゃ、衝突が頻繁に発生するようになると、それを連鎖法で処理するか、あるいはオープンハッシュ法＆セカンドハッシュ関数で処理するか、 いずれにしても N がハッシュテーブルサイズに比して大きくなりすぎるとO(1)から程遠くなるでしょう しかし、今はハッシュテーブルサイズが N に比してそんなに大きくないことが前提だと思っていましたが、そういうハッシュテーブルの重要な性質を無視して N→∞にいきなり振るとか、やはり実装経験が不足しているとしか考えられません あなたには、オープンハッシュ法でも連鎖法でもいいから、一度実装してみることをお勧めします、そうすれば、そんな無茶な話をふったり出来ないはずです 840 名前：デフォルトの名無しさん mailto:sage [2021/12/05(日) 16:51:42.71 ID:HAXCanWR.net] >>820 ×今はハッシュテーブルサイズが N に比してそんなに大きくないことが前提だ ○今は N がハッシュテーブルサイズに比してそんなに大きくないことが前提だ 841 名前：デフォルトの名無しさん [2021/12/05(日) 18:19:46.95 ID:KOPBFOTo.net] INTEL Core N4200。 842 名前：デフォルトの名無しさん mailto:sage [2021/12/05(日) 19:15:19.02 ID:F58n2Ec9.net] この数学100点の人はプログラミングできないんだから、ベンチ出せは禁句だよ 843 名前：デフォルトの名無しさん mailto:sage [2021/12/05(日) 19:16:59.90 ID:3Mcy6QkY.net] >>820 あなたは馬鹿すぎて議論が成立しない。 勉強しろ、とも言えない。 なぜなら、勉強しても無駄だと思うから。 844 名前：デフォルトの名無しさん mailto:sage [2021/12/05(日) 19:54:51.36 ID:HAXCanWR.net] >>823 話が噛み合いませんね、やっぱり私が馬鹿だからなんでしょうかね… でも、仮にも計算機科学方面から解析を行っていただくのでしたら、C でいいから例示してほしいですよね >>824 生まれてきてすみません… 845 名前：デフォルトの名無しさん mailto:sage [2021/12/05(日) 22:25:34.77 ID:MGzOS3+Z.net] 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回で見つかる 846 名前：デフォルトの名無しさん mailto:sage [2021/12/05(日) 22:30:23.53 ID:GkhJF2sm.net] >>826 Rustのハッシュそうなんだ？ 847 名前：デフォルトの名無しさん mailto:sage [2021/12/05(日) 22:55:00.31 ID:5+FKsWbz.net] Rubyだぞ 848 名前：デフォルトの名無しさん mailto:sage [2021/12/05(日) 23:55:41.03 ID:o2Lx+v4j.net] >>817 > ハッシュ構造は、「一回の検索」でも、数学的には、O(N)の時間が掛かる。 ホントですか？ >>826がO(logN)ですよ 849 名前：デフォルトの名無しさん [2021/12/06(月) 00:01:51.71 ID:3rXx+R7R.net] ベンチをもっと気楽に行うために単体テストフレームワークを使ってベンチ書いてる。 850 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 00:03:31.65 ID:kjD6KzfX.net] >>829 O(N)の定義は、Nを無限に大きくしていった時に、処理時間を N で割った時に ある固定された上限値の定数未満になる、という意味だぞ。 O(log N)のハッシュは有り得ない。 851 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 00:07:28.71 ID:kjD6KzfX.net] なお、ハッシュ値の最大数を動的に増やしていくのならば、本来のハッシュ構造ではない。 本来のハッシュ構造は振り分けられる量は固定サイズ。 だから、ハッシュ値の計算も固定されたアルゴリズムで処理が固定された関数で 行う。 色々と勝手に定義を変えてはいかん。 言葉を勝手に再定義すれば議論になるわけ無い。 852 名前：デフォルトの名無しさん [2021/12/06(月) 00:25:08.26 ID:3rXx+R7R.net] （キリッ）が抜けてるのでは？ 853 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 00:25:34.03 ID:O1qGwT+t.net] リンクリストの次はハッシュテーブルかよ データ構造スレでやれ 854 名前：デフォルトの名無しさん [2021/12/06(月) 00:49:48.95 ID:3rXx+R7R.net] 良スレ。 アゲ。 855 名前：826 mailto:sage [2021/12/06(月) 01:37:20.07 ID:siDRvkcR.net] >>826 修正 >増え方が、N に比例しなくて、log N に比例するから >例えば、2^20 = 百万で、2^21 = 2百万では、 >線形探索では毎回、百万回増えるけど、 >ハッシュでは、1回だけ再構築して、その後は、21回で見つかる これはデータベースで使う、2分探索の事だった。 ハッシュは、バケット数で割った余りで決まるから、O(1)だった 856 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 01:49:17.06 ID:kjD6KzfX.net] >>836 ハッシュの表の様なものが固定サイズであるところの 素朴なハッシュの検索は、Nが大きい時には、O(N)。N が小さい時には、O(1)。 Nが大きくなるに従ってその表を時々大きくしていくようなものは、 考慮の対象にはしない。 857 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 01:53:00.58 ID:kjD6KzfX.net] >>837 [補足] 以下、ハッシュの表の様なものが固定サイズであるところの素朴なハッシュの検索 についてだけを考える。 ハッシュの中に入っているデータの個数が N 個の時に、あるキーを持つ データを1個だけ探すのに掛かる平均時間を g(N)とすると、数学的には g(N)=O(N)。 しかし、この g(N) は、g(N) = a N + b と近似した場合の a の値が極端に小さい。 なので、N が小さい時には、O(1)であるかのように振舞う。 そういう意味だ。 これで理解できないなら、数学的想像力や理解力が足りてない。 858 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 02:05:17.38 ID:McsJgKJD.net] RubyガイジとRustガイジの熱いマッチが今始まる 859 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 02:22:55.84 ID:XuzXkdX2.net] >>839 この数学100点マンはRustを叩いてる人で常に生ポインタ派のC/C++史上主義な人 ただしコードを出したことがないのでプログラミング能力がないと推定されている さらにオーダーについても勝手な定義で無茶な主張を繰り返している 860 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 02:24:44.88 ID:McsJgKJD.net] >>840 分かっと 861 名前：るわ 語呂がいいからRustガイジって言っただけ [] [ここ壊れてます] 862 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 02:33:01.01 ID:kjD6KzfX.net] >>840 お前もとことん馬鹿だな。 コード書いても抽象理解が出来ない人には、そのコードの本質は分からんし、 こんなところに書ききれるわけでも無いからかけないだけだ。 なお、抽象 = シンボライズ、シンボリック という意味で、曖昧や玉虫色という意味では無いぞ。 本質的な部分を記号化、定理化、規則化、一般化して理解できるようにしたもの を「抽象化」と言う。 863 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 03:29:12.50 ID:rYDKtnCr.net] linkedlistの計算量を勘違いし 平衡二分木とハッシュセットを混同する 数学100点マンがいると聞いて 864 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 05:30:40.66 ID:lQ57RfmU.net] >>842 >こんなところに書ききれるわけでも無いからかけないだけだ。 スレじゃなくて、IdeoneとかGihubのgistに書いてもらえれば大丈夫ですよ 865 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 05:43:24.70 ID:4SyL85E7.net] >>838 ＞、g(N) = a N + b と近似した場合の a の値が極端に小さい。…�@ なぜですか？ ハッシュテーブルの実装方法から論じてみください もしかして、あなたは�@を数学の公理、みたいに扱っているのですか？そんなことではコンピューターサイエンスは無意味だし面白くないでしょう？ でもC/C++ 至上主義者というのなら、私と気が合いますね 866 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 08:46:35.08 ID:XZMNlO6i.net] >>775 MFC(Win32)に関しては、メッセージキューとイベントは別物だぞ。　イベントは、 イベント処理中でも降って来る。 867 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 10:07:17.08 ID:OAOUQrou.net] なんでハッシュテーブルの話になったのかと思えば>>813にいちゃもん付けたいだけか 868 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 11:16:09.54 ID:O1qGwT+t.net] ベンチマークもなしに実時間の話をされてもなぁ しかも具体的な実装上の問題点の指摘もなく他人のベンチマークは信用できないとか宣われてしまうとこちらとしては会話しても意味がない人なんだと判断せざるを得ないんですよね 869 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 11:52:31.39 ID:q0VGOju1.net] >>845 公理ではなくて、処理時間の平均値を確率論で書いている。 870 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 11:57:28.95 ID:q0VGOju1.net] >>849 [補足] 確率論で証明することが出来るが、とてもめんどくさいので割愛する。 失礼だが、質問者のレベルから推測すると、ちゃんと書いても理解できない。 871 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 12:01:12.30 ID:EOOuRFRK.net] >>845じゃないけど 最悪値が重要な用途もある また、確率はデータの分布が決まってはじめて決まるもの 分布次第ではあなたの想定通りにはならない 872 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 12:06:08.85 ID:q0VGOju1.net] >>851 確率論では、ランダム性を仮定する。 873 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 12:43:27.37 ID:XuzXkdX2.net] >>842 ここはC++ vs Rustスレなのだからコードを出さなければ何も判定できない 机上の空論ばかり書き綴るよりも現実に使われるCPUと向き合わなければならない 例えばRustの標準ライブラリHashMapでも用いているSwiss Tables法ではハッシュ衝突時の別エントリ探索にSIMD命令を用いている CPU命令4つで16エントリ同時に探索候補を判別していきメモリキャシュも活かすようこのためのメタデータを連続領域に配置している 874 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 13:08:20.11 ID:PE/XVSQC.net] >>852 値がガウス分布に従うとかなんらかの仮定をおいていると思うのですがあなたの言うランダム性とはなんですか あらゆる分布を想定しているのですか 875 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 13:21:52.08 ID:iO91q1zt.net] >>831 > O(N)の定義は、Nを無限に大きくしていった時に、 コンピュータサイエンスでアルゴリズムの評価をするときは、Nを無限にするなんて考えません ハッシュアルゴリズムはO(1)でFA 876 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 13:46:42.22 ID:lQ57RfmU.net] >>848 ずっとそんな感じ 計算量ではちゃんとわからない、コストがかかって遅くなる、とか言いつつ、忙しいから実装はできない、お前は馬鹿だから理解できない、みたいなことを数ヶ月に渡って大量に書き込み続けてる 数学でいつも100点取るらしいし、さぞ偉いお方なんでしょうなあ… 877 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 18:09:07.25 ID:cGshi4Y2.net] >>854 いまの場合で言えば、N個のキーに対するハッシュ値が、可能な限り重ならずに 分布すること。 878 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 19:52:13.50 ID:4SyL85E7.net] >>856 リジェクトされたネタだとか… 879 名前：デフォルトの名無しさん mailto:sage [2021/12/06(月) 20:04:46.70 ID:h+yNZQm8.net] >>857 意味不明 880 名前：デフォルトの名無しさん [2021/12/06(月) 21:08:31.14 ID:4qQbBrsy.net] ハッシュが衝突しやすいコリジョンデータを使ったDDos攻撃が出来るのでは？ 881 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 13:11:29.70 ID:jcfwZSTS.net] >>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)である。 882 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 13:27:33.41 ID:pFZAiCY5.net] Wikipediaでも明記されている ・ハッシュテーブルの検索や追加はO(1) ・ハッシュテーブルの拡張もO(1) > ハッシュテーブルはキーをもとに生成されたハッシュ値を添え字とした配列である。 > キーを要約する値であるハッシュ値を添え字として値を管理することで、検索や追加を要素数によらず定数時間O(1)で実現する。 > > 利用率が一定を超えた場合に、より大きいサイズのハッシュテーブルを用意して格納し直す操作が必要となる。これをリハッシュ (rehash) と呼ぶ。 > この操作はすべての要素のハッシュ値を再計算して新たなハッシュテーブルに格納するためO(n)であるが、 > 配列のサイズを指数的に拡張する事で、動的配列の末尾追加操作と同様に償却解析によって計算量をO(1)とみなす事ができる。 883 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 14:35:15.82 ID:iH9Jzajc.net] >>862 例えば、M=128で、128種類のハッシュ値に振り分けられるなっている ハッシュ構造の場合、N=128万にすると、1つのハッシュ値に1万個の (key, value)のペアが対応している。 そして、1個のkeyを検索する時、平均的には、1万個の半分の5000回 くらいkey値の比較を行うと一致するものが見つかる。 なのでこの場合、1個のkeyに対する検索時間は 5000*(keyの比較に要する時間) となる。 Nを128億にすると、 5000万*(keyの比較に要する時間) になる。 884 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 14:52:05.46 ID:iH9Jzajc.net] >>863 誤:128種類のハッシュ値に振り分けられるなっている 正:128種類のハッシュ値に振り分けられるようになっている 誤:5000*(keyの比較に要する時間) 正:5000*(1回のkeyの比較に要する時間)　// ()内は、keyが文字列の場合、1回の文字列比較に掛かる時間。 誤:5000万*(keyの比較に要する時間) 正:5000万*(1回のkeyの比較に要する時間)　// ()内は、keyが文字列の場合、1回の文字列比較に掛かる時間。 >>862 > 利用率が一定を超えた場合に、より大きいサイズのハッシュテーブルを用意して格納し直す操作が必要となる。これをリハッシュ (rehash) と呼ぶ。 >>861 の4行目で、リハッシュは行わないと断った。 はっきり、Mを定数とすると書いている。 885 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 17:09:08.05 ID:Io+x78vq.net] 数学100点マンの机上の空論がさらに輪をかけてるな >>864 > 最大M個の振り分け能力があるハッシュ構造にN個の(key, value)ペアを書き込んでいる場合を考える。 > M=128で、128種類のハッシュ値に振り分けられるようになっている > Nを128億にすると、5000万*(keyの比較に要する時間)になる。 つまり128億個のデータを128個のハッシュ値パターンでハッシュテーブルに格納か 現実の世界ではなく一人だけの特殊な妄想世界で空論 886 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 17:09:50.30 ID:q8J3SSC4.net] worst caseはO(n)って言えば一言で終わる話だった 887 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 18:11:38.99 ID:U30hRDTM.net] 平均もO(n)だろ 888 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 18:19:10.70 ID:j/zIE0U5.net] でそれにC++やRustとどう関係が？ 889 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 18:22:43.53 ID:U30hRDTM.net] さあ 890 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 18:27:32.38 ID:2dc6hCU/.net] とにかく、この >>813 の書き込みはすごい、ってことだ このスレの集大成に近い出来だと思う 891 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 18:35:18.60 ID:U30hRDTM.net] >>623 を無駄に長く書いただけに見える >>624 はスルーで 892 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 18:37:25.57 ID:U30hRDTM.net] 計算可能性 > 計算オーダー > 計算時間 混ぜるな危険 893 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 19:22:19.85 ID:hXWP+cLq.net] >>861 あなたの言うランダム性の定義を伺いたかったのですが 挿入されるkeyはどのような分布に従う仮定なのですか 894 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 19:28:32.42 ID:XGUQnarH.net] 確率論では衝突の発生確率が一様分布と仮定した場合、衝突回数はポアソン分布に従う 895 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 19:37:51.93 ID:smG53G6j.net] 要するに衝突回数は幾何平均(算術平均)とは異なる 896 名前：デフォルトの名無しさん [2021/12/07(火) 19:51:15.50 ID:EZ68mIS/.net] >>873 衝突が起きるとしても、5chのIDが被る程度の稀な確率となる程度のランダム性を想定しています。 897 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 20:13:15.75 ID:hXWP+cLq.net] >>876 分布については特に何も想定してないということですね 898 名前：デフォルトの名無しさん [2021/12/07(火) 20:15:39.60 ID:EZ68mIS/.net] >>877 データに合わせてハッシュアルゴリズムを変更する、アダプティブ・ハッシュ・テクノロジー™をご提案いたします。 899 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 20:16:48.35 ID:EfSST75b.net] 結局のところ衝突回数が算術平均に従う場合はO(n)であるが、この場合確率そのものが極めて小さく分布の期待値が小さいためO(1)に極めて近いとしか評価の仕様がない 900 名前：デフォルトの名無しさん [2021/12/07(火) 20:23:38.39 ID:EZ68mIS/.net] >>813は、言語のバイナリ生成能力を論じるときに計算オーダーは意味がないと言っているのでは？ その理由として、同一の計算オーダーを持つアルゴリズム、あるいは同一のアルゴリズムから、どちらが優れたバイナリを生成できるか論じているので、それはベンチでしか判明しない、と挙げていると思うのです。 901 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 20:33:30.11 ID:U30hRDTM.net] 特定のアルゴリズムを特定の計算オーダーで実装出来ない言語もあるので 全く意味がない事はない 902 名前：デフォルトの名無しさん mailto:sage [2021/12/07(火) 21:45:05.70 ID:Io+x78vq.net] RustとC++は万能

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef