Случайные числа против GetHashCode () в CompreTo ()?

Question

Я использую класс Random в своей структуре CompareTo(), чтобы с равной вероятностью выбрать одну из структур, когда оба имеют одинаковые значения поля.Класс 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;
        }
}

Спасибо!

Answer 1

Я использую класс Random в своей структуре CompareTo (), чтобы с одинаковой вероятностью выбрать одну из структур, когда оба имеют одинаковые значения поля.

Во-первых, это совершенно странная вещь. Это все равно, что сказать: «Когда меня просят отсортировать группу чисел, и двум из них по 12, я выбираю одну из 12 наугад, чтобы она была меньше». Это не имеет смысла. Эти два двенадцати идентичны . У тебя нет способа отличить двенадцать от другого!

Почему ты делаешь эту странную вещь? Если эти два значения идентичны, то говорят, что они идентичны.

После более внимательного прочтения вашего кода я вижу, что вы сохраняете случайное число в состоянии структуры. Если вы хотите сделать эту странную вещь, это правильный путь.

Первоначально я думал, что вы рандомизировали сам оператор сравнения . Это чрезвычайно опасная вещь . Алгоритмы сортировки могут иметь сильные зависимости от сортировки по полному порядку. Для сравнения требуется , чтобы найти общий порядок, который является самосогласованным . Вы никогда не должны говорить, что первый элемент больше второго, второй больше третьего, а третий больше первого. Это нарушает требуемую транзитивность сравнения, и алгоритму сортировки разрешается входить в бесконечный цикл или выполнять любое другое странное поведение, если ему дается операция сравнения, которая ведет себя плохо.

Я подумываю заменить случайные числа ссылкой на память или GetHashCode ().

Это еще хуже идея. GetHashCode полезен только для одной цели: балансировки хеш-таблицы. Если вы не балансируете хеш-таблицу и вызываете GetHashCode , вы делаете что-то не так .

Более того, продумайте это до конца. Ситуация, в которой вы находитесь, состоит в том, что две структуры в противном случае сравниваются как равные. По контракту GetHashCode должен возвращать одинаковый результат для любых двух структур, которые сравниваются как равные . GetHashCode явно не является источником неоднозначности между двумя одинаковыми вещами! Это на самом деле противоположность этому.

Будет ли это гарантировать, что выбор сделан с равной вероятностью?

Неа. GetHashCode не является источником случайности и не дает никаких гарантий относительно распределения хеш-кодов.

Будет ли это гарантией того, что я получу те же результаты, если снова запустите программу?

Абсолютно нет.

Answer 2

Ваш код не опасен, как некоторые подозревают, потому что вы последовательны в использовании чисел (они случайны только при создании объекта).

Хотя я не могу понять, почемуна земле это может принести какую-либо пользу.

Рассмотрим случай без _randValue.Допустим, у вас есть одна структура (мы назовем ее x), где _param1 равно 2,0, а _param2 равна 0,12, и другая структура (назовем ее y), где _param1 равно 2,0 и_param2 равно .12.

Ну, единственный способ отличить что-либо между x и y - это добавить к ним _randValue.

Поскольку они являются структурами, у них даже нет постоянной идентичности между назначениями и боксами.Если мы делаем MyStruct z = x, у нас нет другого указателя на x, у нас есть совершенно новый MyStruct.

И даже помимо этого, это не имеет значения.

Подошваэффект ваших изменений:

1. Вы добавили дополнительное использование памяти для всех случаев структуры.
2. Вы сделали сортировку более дорогой.
3. ВыВы сделали конструкцию более дорогой.
4. Вы сделали конструкцию узким местом с многопоточностью, поскольку вам необходимо зафиксировать Random.Next().

Вероятно, ни один из них не будетОсобенно значимо, но преждевременная пессимизация является корнем многих странностей.

Answer 3

Под ссылкой на память вы подразумеваете адрес структуры? Если вам нужна предсказуемость, вы не можете использовать адреса памяти.

Что вы предлагаете хешировать? Если вы хешируете свойства структуры, которые равны, хеш-коды также будут равны.

Полагаю, меня смущает 1) почему Random не работает для вас и 2) почему вы просто не называете две структуры с одинаковыми значениями равными?

Answer 4

Я бы лично предпочел просто случайное число, но чтобы ответить на ваши вопросы:

1. Да, это алгоритм хеширования, такой же, как md5 или sha (хотя этот алгоритм не был специально создан для целей, которые вы описываете)
2. Да , значение будет поддерживаться между запусками программы (@ henk-holterman является правильным, но значение не гарантируется, что оно останется прежним только для строк )
3. GetHashCode будет намного быстрее

Answer 5

Поскольку класс Random делает то, что вы хотите, и вы можете заполнить его, чтобы каждый раз получать одни и те же значения, почему вы хотите его изменить?

Я не совсем уверен, что вы планируете делать, используя ссылку на память, но даже если бы вы могли указывать на один и тот же адрес и видеть одни и те же данные каждый раз, когда запускаете код, вы не можете гарантировать справедливое распределение значения в памяти, если вы все равно не заполнили их случайной функцией.

Функция хеширования должна возвращать значительный разброс значений, но на самом деле это не инструмент для работы - если вам нужно случайное число, используйте генератор случайных чисел!

Answer 6

Мое чтение вашего кода говорит о том, что вы используете rand с тай-брейком.Я не понимаю, почему вы хотели бы, чтобы идентичные объекты дифференцировались, или даже заботитесь о порядке идентичных объектов.

например, в этом списке -

 A
 B
 B
 C

почему вы заботитесь или хотитечтобы узнать, какой экземпляр B является первым?

Я бы предложил, что лучшим решением было бы добавить мелкозернистое поле, которое имеет смысл для пользователя, скажем, дату создания или измененную временную метку.Тогда у вас будет значимый нарушитель связей, хотя связи все еще могут возникать, я просто не думаю, что они будут проблемой.