2

構造体で Random クラスを使用して、CompareTo()両方のフィールド値が同じ場合、構造体の 1 つを同じ確率で選択しています。Random クラスは、固定シードを使用してインスタンス化され、疑似乱数の再現可能なシーケンスを取得します。これにより、同じ入力で何度実行してもプログラムがまったく同じ比較結果を返すようになります。

代わりに、乱数をメモリ参照または GetHashCode() に置き換えることを考えています。そうすることで、次のことが保証されます。

(1) 選択は等しい確率で行われ、

(2) プログラムを再度実行すると、同じ結果になるということですか?

struct MyStruct : IComparable<MyStruct>
{
        private readonly float _param1;
        private readonly float _param2;
        private readonly int _randValue;

        public MyStruct(float param1, float param2)
        {
                _param1 = param1;
                _param2 = param2;
                _randValue = _random.Next();
        }

        public int CompareTo(MyStruct other)
        {
            if (_param1 < other._param1)
            {
                return -1;
            }
            else if (_param1 > other._param1)
            {
                return 1;
            }
            else if (_param2 > other._param2)
            {
                return -1;
            }
            else if (_param2 < other._param2)
            {
                return 1;
            }
            // If both params are equal, then select one of the structs with
            // equal probability
            else if (_randValue < other._randValue)
            {
                return -1;
            }
            else if (_randValue > other._randValue)
            {
                return 1;
            }

            return 0;
        }
}

ありがとう ！

4

6 に答える 6

16

構造体の CompareTo() で Random クラスを使用して、同じ確率で構造体の 1 つを選択しています (両方のフィールド値が同じ場合)。

まず、それはまったく奇妙なことです。それは、「たくさんの数字をソートするように求められ、そのうちの 2 つが両方とも 12 である場合、12 のうちの 1 つを無作為に選んで小さくする」と言っているようなものです。それは意味がありません。それらの 2 つの 12 は同一です。12 と 12 を区別する方法はありません。

なんでこんな変なことするの？2 つの値が同一である場合、それらは同一であると言います。

コードを注意深く読むと、乱数を構造体の状態に保持していることがわかります。この奇妙なことをしたい場合は、それが正しい方法です。

私はもともと、比較演算子自体をランダム化していると思っていました。 それは非常に危険なことです。並べ替えアルゴリズムは、並べ替えが全順序並べ替えであることに強く依存することが許可されています。自己矛盾のない完全な順序付けを見つけるには、比較が必要です。最初の項目が 2 番目の項目よりも大きい、2 番目の項目が 3 番目の項目よりも大きい、3 番目の項目が 1 番目の項目よりも大きい、などとは決して言ってはなりません。これは必要な比較の推移性に違反しており、並べ替えアルゴリズムは、動作の悪い比較操作が与えられたときに、無限ループに陥ったり、その他の奇妙な動作を行ったりすることが許可されています。

代わりに、乱数をメモリ参照または GetHashCode() に置き換えることを考えています。

それはさらに悪い考えです。GetHashCode が役立つのは、ハッシュ テーブルのバランスを取ることだけです。ハッシュ テーブルのバランスをとっていないのに GetHashCode を呼び出すと、何か問題があります。

さらに、よく考えてください。あなたがいる状況は、そうでなければ2つの構造体が等しいと比較されるということです。GetHashCode は、 equal として比較される任意の 2 つの構造体に対して同じ結果を返すことが契約上必要です。GetHashCode は、2 つの同一のものの間のあいまいさを明確にするソースではありません! それは実際にはその反対です。

これにより、選択が等しい確率で行われることが保証されますか?

いいえ。GetHashCode はランダム性のソースではなく、ハッシュ コードの配布については一切保証されません。

これにより、プログラムを再度実行しても同じ結果になることが保証されますか?

絶対違う。

于 2011-12-13T23:45:12.847 に答える
4

数字の使用には一貫性があるため、コードは危険ではありません（オブジェクトの作成時にのみランダムになります）。

しかし、私には見えないのは、これが地球上で何らかの利益をもたらす可能性がある理由です。

なしの場合を考えてみましょう_randValue。2.0に等しく.12に等しい1つの構造体（これを呼びますx）と、 _param12.0に_param2等しく.12に等しい別の構造体（これを呼びますy）がある_param1とします_param2。

さて、との間で何かを変える唯一の方法は、それらにを追加したことです。xy_randValue

それらは構造体であるため、割り当てとボクシングの間に永続的なアイデンティティさえありません。もしそうなら、私たちは真新しいものを持っているというMyStruct z = x別のポインタを持っていません。xMyStruct

そしてそれ以外に、それは何の違いもありません。

変更による唯一の影響は次のとおりです。

  1. 構造のすべてのケースに余分なメモリ使用量を追加しました。
  2. 並べ替えがより高価になりました。
  3. あなたは建設をより高価にしました。
  4. をロックする必要があるため、構築をマルチスレッドのボトルネックにしましたRandom.Next()。

これらのどれも特に重要である可能性は低いですが、時期尚早の悲観化は根本的な多くの奇妙さです。

于 2011-12-14T17:14:58.123 に答える
2

「メモリ参照」とは、構造体のアドレスを意味しますか? 予測可能性が必要な場合は、メモリ アドレスを使用できません。

何をハッシュすることを提案していますか? 等しい構造体のプロパティをハッシュすると、ハッシュ コードも等しくなります。

私は混乱していると思います。

于 2011-12-13T22:27:56.703 に答える
1

Randomクラスは必要な処理を実行しており、毎回同じ値を取得できるようにシードすることができるので、なぜそれを変更したいのですか？

メモリ参照を使用して何を計画しているのか完全にはわかりませんが、コードを実行するたびに同じアドレスをポイントして同じデータを表示できたとしても、メモリ内の値の公平な分散を保証することはできません。とにかくランダム関数でそれを埋めていない限り。

ハッシュ関数は値の公平な広がりを返すはずですが、それは実際には仕事のためのツールではありません—乱数が必要な場合は、乱数ジェネレーターを使用してください！

于 2011-12-13T22:25:51.387 に答える
1

私は個人的に純粋な乱数を好みますが、あなたのポイントに答えるには:

  1. はい、これは md5 や sha のようなハッシュ アルゴリズムです (ただし、このアルゴリズムは、説明した目的のために特別に作成されたものではありません)。
  2. はい、値はプログラムの起動間で維持されます (@henk-holterman は正しいですが、文字列に対してのみ値が同じままであるとは限りません)
  3. GetHashCode はより高速になります
于 2011-12-13T22:35:59.320 に答える
0

あなたのコードを読んだところ、使用しrandているタイブレーカーがあることがわかりました。同一のオブジェクトを区別したり、同一のオブジェクトの順序を気にしたりする理由がわかりません。

たとえば、このリストでは-

 A
 B
 B
 C

Bのどのインスタンスが最初であるかを気にしたり、知りたいと思うのはなぜですか?

より良い解決策は、作成日または変更されたタイムスタンプなど、ユーザーにとって意味のあるきめ細かいフィールドを追加することです。その後、意味のあるタイブレーカーが得られますが、引き分けが発生する可能性はありますが、問題になるとは思いません.

于 2013-02-19T01:43:49.270 に答える