C++ vs Rust
レス数が950を超えています。1000を超えると書き込みができなくなります。
>>845じゃないけど
最悪値が重要な用途もある
また、確率はデータの分布が決まってはじめて決まるもの
分布次第ではあなたの想定通りにはならない >>842
ここはC++ vs Rustスレなのだからコードを出さなければ何も判定できない
机上の空論ばかり書き綴るよりも現実に使われるCPUと向き合わなければならない
例えばRustの標準ライブラリHashMapでも用いているSwiss Tables法ではハッシュ衝突時の別エントリ探索にSIMD命令を用いている
CPU命令4つで16エントリ同時に探索候補を判別していきメモリキャシュも活かすようこのためのメタデータを連続領域に配置している >>852
値がガウス分布に従うとかなんらかの仮定をおいていると思うのですがあなたの言うランダム性とはなんですか
あらゆる分布を想定しているのですか >>831
> O(N)の定義は、Nを無限に大きくしていった時に、
コンピュータサイエンスでアルゴリズムの評価をするときは、Nを無限にするなんて考えません
ハッシュアルゴリズムはO(1)でFA >>848
ずっとそんな感じ
計算量ではちゃんとわからない、コストがかかって遅くなる、とか言いつつ、忙しいから実装はできない、お前は馬鹿だから理解できない、みたいなことを数ヶ月に渡って大量に書き込み続けてる
数学でいつも100点取るらしいし、さぞ偉いお方なんでしょうなあ… >>854
いまの場合で言えば、N個のキーに対するハッシュ値が、可能な限り重ならずに
分布すること。 ハッシュが衝突しやすいコリジョンデータを使ったDDos攻撃が出来るのでは? >>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)である。 Wikipediaでも明記されている
・ハッシュテーブルの検索や追加はO(1)
・ハッシュテーブルの拡張もO(1)
> ハッシュテーブルはキーをもとに生成されたハッシュ値を添え字とした配列である。
> キーを要約する値であるハッシュ値を添え字として値を管理することで、検索や追加を要素数によらず定数時間O(1)で実現する。
>
> 利用率が一定を超えた場合に、より大きいサイズのハッシュテーブルを用意して格納し直す操作が必要となる。これをリハッシュ (rehash) と呼ぶ。
> この操作はすべての要素のハッシュ値を再計算して新たなハッシュテーブルに格納するためO(n)であるが、
> 配列のサイズを指数的に拡張する事で、動的配列の末尾追加操作と同様に償却解析によって計算量をO(1)とみなす事ができる。 >>862
例えば、M=128で、128種類のハッシュ値に振り分けられるなっている
ハッシュ構造の場合、N=128万にすると、1つのハッシュ値に1万個の
(key, value)のペアが対応している。
そして、1個のkeyを検索する時、平均的には、1万個の半分の5000回
くらいkey値の比較を行うと一致するものが見つかる。
なのでこの場合、1個のkeyに対する検索時間は
5000*(keyの比較に要する時間)
となる。
Nを128億にすると、
5000万*(keyの比較に要する時間)
になる。 >>863
誤:128種類のハッシュ値に振り分けられるなっている
正:128種類のハッシュ値に振り分けられるようになっている
誤:5000*(keyの比較に要する時間)
正:5000*(1回のkeyの比較に要する時間) // ()内は、keyが文字列の場合、1回の文字列比較に掛かる時間。
誤:5000万*(keyの比較に要する時間)
正:5000万*(1回のkeyの比較に要する時間) // ()内は、keyが文字列の場合、1回の文字列比較に掛かる時間。
>>862
> 利用率が一定を超えた場合に、より大きいサイズのハッシュテーブルを用意して格納し直す操作が必要となる。これをリハッシュ (rehash) と呼ぶ。
>>861 の4行目で、リハッシュは行わないと断った。
はっきり、Mを定数とすると書いている。 数学100点マンの机上の空論がさらに輪をかけてるな
>>864
> 最大M個の振り分け能力があるハッシュ構造にN個の(key, value)ペアを書き込んでいる場合を考える。
> M=128で、128種類のハッシュ値に振り分けられるようになっている
> Nを128億にすると、5000万*(keyの比較に要する時間)になる。
つまり128億個のデータを128個のハッシュ値パターンでハッシュテーブルに格納か
現実の世界ではなく一人だけの特殊な妄想世界で空論 worst caseはO(n)って言えば一言で終わる話だった とにかく、この >>813 の書き込みはすごい、ってことだ
このスレの集大成に近い出来だと思う >>623 を無駄に長く書いただけに見える
>>624 はスルーで 計算可能性 > 計算オーダー > 計算時間
混ぜるな危険 >>861
あなたの言うランダム性の定義を伺いたかったのですが
挿入されるkeyはどのような分布に従う仮定なのですか 確率論では衝突の発生確率が一様分布と仮定した場合、衝突回数はポアソン分布に従う >>873
衝突が起きるとしても、5chのIDが被る程度の稀な確率となる程度のランダム性を想定しています。 >>876
分布については特に何も想定してないということですね >>877
データに合わせてハッシュアルゴリズムを変更する、アダプティブ・ハッシュ・テクノロジー™をご提案いたします。 結局のところ衝突回数が算術平均に従う場合はO(n)であるが、この場合確率そのものが極めて小さく分布の期待値が小さいためO(1)に極めて近いとしか評価の仕様がない >>813は、言語のバイナリ生成能力を論じるときに計算オーダーは意味がないと言っているのでは?
その理由として、同一の計算オーダーを持つアルゴリズム、あるいは同一のアルゴリズムから、どちらが優れたバイナリを生成できるか論じているので、それはベンチでしか判明しない、と挙げていると思うのです。 特定のアルゴリズムを特定の計算オーダーで実装出来ない言語もあるので
全く意味がない事はない リンクリストの話は?リンクリスト、皆のアドバイスを受け入れて辞め、ハッシュテーブルに絞ることにしたんですか… >>873
異なるキーに対するハッシュ値が、可能な限り異なるランダム性。 >>866
処理時間を g(N)とすると、worst case ではなく、平均が、g(N) = O(N)。
O(N)という記号を使わずに、詳細に書くと、
g(N) = a * N + b
だが、利用されるハッシュ値の振り分け数が M 個の場合、
a = b / M
程度となり、M = 1024 の場合、a は、0.001 * b 程度の小さな値になる。
横軸を N、縦軸を g(N) とするグラフを書くと、一次関数となり、y 切片が b、
傾きが 0.001 * b 程度となり、ほぼ水平であるが、僅かに右肩上がりとなる。
もしこれが完全に水平なら O(1)。
今回の場合、非常に水平に近いが確実に単調増加であるので、O(1)のように
見えるが本当は O(N)。 >>886
O(1)とO(N)の間にはO(logN)やO(√N)など無数にある >>887
もちろん、それは当然。
それは全く否定していない。 >>888
[補足]
「グラフが水平なら O(1)」とは書いたが、「O(1)ならグラフが水平」とは
書いてない。
つまり、グラフが水平である事はO(1)であることの十分条件であるが、
必要条件ではない。
「グラフが水平 ⇒ O(1)」とは述べているが、その逆の
「O(1) ⇒ グラフが水平」とは述べて無いことに注意。 >>886
それがworst caseの話なんだってw
amortized average caseがO(1)とみなせる前提をガン無視して
「ほらO(n)だろ」とか言ってても誰も相手にしてくれない >>890
いや、違う。
平均は、
g(N) = b * (N/M + 1)
程度。
worst は、
g(N) = b * N
どちらも O(N)ではあるが。 >>891
なお、数学の秀才なら気付くと思うが、この平均の式は、本当は正しくない。
ただし、大体は合ってる。 >>892
[補足]
何が正しくないかというと、本当は、ある箇所を2 で割る必要があるから。
例えば次のように :
g(N) = b * (N/(2M) + 1)
しかし、これでも、まだ少し正しくない。 数学100点君は数学用語の定義を誤解釈しまくって理解してしまっている感じ
説明の内容からしても多分中高生か啓蒙書を読みかじったおじさんなんだろ なんでここは、数学が理解できない人ばっかりなんだ。
だから、プログラマが馬鹿にされる。 C++ vs Rust を語る前に、せめて、数学的に明らかに正しいことを理解できるから
でないとどうにもならん。
それ以前の問題。 それと、科学者にとって最も大事なことは、頭の良さでも知識でもなく、
正直さだ。
自説を主張するために正しい主張を否定してはいけない。 「ランダムアクセス」って任意の要素にアクセスすることを指すんだけど、乱択的に与えられた要素にアクセスすることをそう呼ぶんだと思い込んでる奴が複数いてクソワロ >>894
結果は一時式でも、それを求めるには確率論以前に、イマジネーションが必要。
どこかに書いてある知識の組み合わせでは導出できない。
確率論は、自分の想像力が重要に成るので、計算力だけでは無理な分野。
書いてある定理を組合すだけでも導けない。
数学は、基礎の部分はイマジネーションで作られているから、頭の良い
人以外には作れない。
いくら勉強しても無駄。 ハッシュに格納するまでの過程は確率論でも格納された後はただのリニア検索だけの話にすり替わってないか? >>900
誰でも後から客観的に検証できる性質が数学含む科学の特徴ですよ
イマジネーションって言い換えればあなたの妄想ってことですよね データ追加の話をするのであれば、どのようなアルゴリズムでも無限個数を追加するなら無限時間かかるわw chaining使ってる場合でスロット数(M)が固定値かつ要素数(N)に対して小さければO(n)になるのは当然だよね
それで100点君は何を主張したいんだっけ? これか >>813
>また、N個のデータを持っているハッシュ構造は、1回の検索は、数学的に厳密にはO(N)
>だが、実験的(実際的)にはO(1)のように振舞うと言われており、厳密に扱うには、
>オーダーの記号だけでは表現しきれない。
「1回の検索は、数学的に厳密にはO(N)」になるのは
一般的なハッシュテーブルの実装とは関係ない架空の条件下の話だね
つかBig O記法が何の目的で使われるのか把握してなかったのか・・・
長々とお疲れさんでした 何の目的で使われるの?せっかくだから聞いておきたい なにを言いたいのかさっぱりわからないんだが、さかのぼって読んでみると
>>861
> 最大M個の振り分け能力があるハッシュ構造にN個の(key, value)ペアを
> 書き込んでいる場合を考える。
> ただし、Mは 定数とし、N が大きくなっても拡張していかないものとする。
> このとき、一回の検索に掛かる平均時間をg(N,M)とすると、
> ほぼ、
> g(N,M)=b・(ceil(N/(2M))
いや、全然違うし
一体何をあらわしてる式なんだ? c++: cほど性能はいらないけど、コーティングでcより楽したい
Rust: c++くらいの性能はほしいけど、間抜けがメモリリークをエンバグするのを防ぎたい
Rustの狙いはc++&コーティング規約&lintでけっこうカバーできるけど、Rustは言語仕様としてコーダー全員に規約遵守を強制しているのが強み。
Rustが本当に普及してきたら、Rust対抗としてC++と連携できるSmartC++が出てくるんじゃないのかね。 >>908
>Rust: c++くらいの性能はほしいけど、間抜けがメモリリークをエンバグするのを防ぎたい
これが重要だな。 間抜けがミスをするというと十分に訓練を受けたパログラマーならミスをしないと読めるが
実際にはコードベースが大きくなると間抜けなミスをする確率が高まるので
自分はミスをしないと思い込むのではなくミスした場合も検出できるようにすべき
静的解析やrustの真価はそういうところにあると思う >>911
そのためのコーディング規約&lintだろ。
極端な話、Rustみたいに
基本unique_ptrにして共有する部分だけshared_ptrを使用&生ポインタ禁止、
3rdパーティライブラリはunsafeなラッパークラスで閉じ込めた使用のみ可、
といったコーディング規約にして設計すりゃポカミスぐらいは防げる。 >>913
何もrustに限った話ではないというのはその通りで
静的解析やrustと書いたのはそういう規約やlintで補うことも可能という意図
ただrustのshared mutabilityを原則禁じるルールなど、lintで同等のチェックするのは難しい気がする >>913
その規約を遵守させる工数がバカにならないんだよなぁ
人数が増えるとさらに倍になるし ポカミスってのは規約守り忘れとかも含むんだよな
lintやコンパイラみたいな機械的なチェック以外は基本信用できない コンパイラに強制させたいのならnext c++待ちかね。
Rustの問題点が顕在化してきたくらいのタイミングで、RustアンチテーゼとしてSmartC++とか出てくるんじゃない?
c++のバットノウハウを禁止できればRust使う必要性はずいぶん薄れるな。
「SmartC++のスコープ内では生ポインタ変数禁止」「nullのスマートポインタの生成禁止」くらいでも十分な気がしてきた。 Lifetime ProfilerでRustのborrow checkerに近いものを実装しようとしてるけど
機能的にも未熟だし標準的に使われるレベルになるかどうかも現段階では怪しい
そんな夢見てるくらいならRust使ったほうが堅いし現実的 >>918
Rustの問題点てなんですか?
揶揄してるわけじゃなくてまだ入門の勉強中なのでいろいろ興味あります >>920
よく言われるのが学習コストの高さ。
c++もいいかげん複雑すぎる言語と言われているけど、Rustはそれに輪をかけて難しい。
特に他の言語を勉強した初級・中級者は変数の挙動から何から違う(&他の言語のようにやるときのためのガイドラインも無い)ので地獄を見るかと。 >>921
そんなことはないと思う
Rustはわかりやすかったぜ
しかも他より書きやすく便利になった さすがのとほほさんも、Rust入門は書けてもC++入門は言語使用がでかすぎて書けなかった模様w
https://www.tohoho-web.com/www.htm >>923
ちょっとは「何がわかりやすかったか」ぐらいは書こうぜ。 素直に公式のチュートリアルを流す分にはそんなに詰まるところはないと思うけどな
変に他言語の流儀を持ち込もうとするとハマりやすいというのはありそう
あといきなりWebアプリ作りたいとか思うとasyncで死ぬってのは多分ある >>29
https://lkml.org/lkml/2021/12/6/461
ついに正式に第二言語としてとりこまれましたとさ
完璧にお前の負けやな
いいか?自分の間違えを完璧に認めて
土下座するんだぞ?
写真上げろよガイジ Mac Objective-C
Windows C++
Linux Rust >>925
structとenumだけでナンでもできてわかりやすかったです
クラスや継承ピラミッドがないのも嬉しかったです
あと&selfやらderefやらその他のimpl&のおかげらしくポインタか否かを気にせず使えるのも便利ですね >>927
ArmとGoogleとMicrosoftとRed Hatの後押しのおかげで
RustがLinuxの第二言語の地位を確立したのね auto derefが害になるRc::cloneしか思いつかなかった
他にどういう問題があるの? >>931
少し前進したな。このまま着実に進めて行って欲しい。 個人開発の範囲内だとC++では困るかつRustなら上手くやれるっていうことがないから勉強する意欲があまりなかったんだが、ここまで来ると覚えとかなきゃ損なのかもな 損かどうかはともかく一度触ってみるのはいいんじゃないかな
C++書いてる時点でライフタイム周りは分かってるわけだし、結構複雑な言語機能もバリバリ使いこなせるタイプなんだからRustが合う可能性は比較的高いと思う >>934
derefじゃ循環参照作れないと思うが 記述量がどうしても Rust は多いイメージなんだよなあ C++のテンプレートメタプログラミングよりも
高い効率と抽象性をRustでも実現できるの?
だったらRust使うが >>941
一般的に洗脳されていると難しいけれど色んなレベルでの意識改革ができると今後に役立つよ
例えばC++自体の限界のためにテンプレートメタプログラミングでやらざるを得なかったケースがRustでは使わずに出来てしまうケースもあるし
C++ではこうやるべきだと思えていたお決まりの手法が発想を転換するとRustでは別の手法によりもっと自然に出来てしまうケースもある
一方で失敗する人たちはそういった意識改革が出来ずにC++では当たり前に思えていた方法でそのまま突き進もうとしてしまい本来は簡単に出来ることを複雑にしてしまう
もちろん能力がある人たちならばこの意識改革が出来るため必要に応じて発想の転換など臨機応変に対応することが出来ますから大丈夫 >>942
> 例えばC++自体の限界のためにテンプレートメタプログラミングでやらざるを得なかったケースがRustでは使わずに出来てしまうケースもある
> C++ではこうやるべきだと思えていたお決まりの手法が発想を転換するとRustでは別の手法によりもっと自然に出来てしまうケースもある
ふむふむ。例えばどういう具体例がありますか? そういう気付きや意識改革を自分で出来ない人たちはもっと基本的なところからスタートすると良いかな
例えばRustにはclassすらないしtry/catch/throwすらない
C++の視点から見るとそんなのでまともなプログラミングできるの??となる
しかし現実にRustではそれらがなくとも普通に問題なく便利にプログラミングが出来ている
そして発想の転換が出来るようになるとclassやtry/catch/throwはプログラミングする上で必須なものではなかったんだなと真の理解が進む
まずはこういう基礎的なところからスタートするのがよいでしょう type traitに関してはまんまtraitで置き換えてコンパイル時に判定できる
type traitベースでenable_ifするのはtrait boundで
テンプレートメタプロそこまで詰めてやったことないから逆にRustでできなさそうなの挙げて欲しいかも
それか両方詳しいひとカモン >>943
典型的なのはSFINAEを駆使してた部分がtraitで解決できるとかかな
まぁconceptと同じようなもんだけど、conceptは正直まだ発展途上だと思う C++はSFINAEがあるから部分的に型エラーになっても大丈夫だけど
Rustのジェネリクスはそういうのは許容しないからちょっと表現範囲は狭いね
ジェネリクスの範囲外は手続きマクロでカバーする感じ
こっちは任意のコード生成だから、テンプレートより遥かに自由度が高い(が、当然乱用するとやばい) >>944
こういうの見るとどんどんRustが嫌いになっていく… >>948
Rustコミュニティーは若いからな。
説明ノウハウ無い&自浄作用無いので、アホがクズみたいなレスでマウント取ろうとするのは仕方ないよ。 >>942
テンプレート機能はC++の一部だしテンプレートメタプログラミングはその機能を使ったプログラミングに過ぎない
言語自体の限界とはまったく関係ないしやらざるを得ないという表現はなにを指しているのかわからない
>>944
そんなことを言ったらRustにもプログラミング上必須でない機能が無数にあるだろう
言語間に差があることは前提で言語ごとに設計の仕方が異なるからRustの話を聞いただけだ そういう何も分かってない系は放置してくれると助かります…… レス数が950を超えています。1000を超えると書き込みができなくなります。