2

I'm using the Random class in my struct's CompareTo() to pick, with equal probability, one of the structs when both have the same field values. The Random class is instantiated with a fixed seed to get a reproducible sequence of pseudo-random values, to ensure that my program would give the same exact comparison results no matter how many times I run it with the same input.

I'm thinking of replacing the random numbers with a memory reference or GetHashCode() instead. Will doing so guarantee that:

(1) the selection is made with equal probability, and

(2) that I would end up with the same results if I run the program again ?

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;
        }
}

Thanks !

1

6 Answers 6

16

I'm using the Random class in my struct's CompareTo() to pick, with equal probability, one of the structs when both have the same field values.

First off, that's a completely bizarre thing to do. That's like saying "When I'm asked to sort a bunch of numbers, and two of them are both 12, I pick one of the 12's at random to be smaller". That doesn't make a lick of sense. Those two twelves are identical. You don't have a way to tell one twelve from another!

Why are you doing this strange thing? If the two values are identical then say they are identical.

Upon reading your code more carefully, I see that you're persisting the random number into the state of the structure. If you want to do this strange thing, that's the right way to go about it.

I originally thought that you were randomizing the comparison operator itself. That is an extremely dangerous thing to do. Sorting algorithms are allowed to take strong dependencies on the sort being a total order sort. A comparison is required to find a total ordering that is self consistent. You must absolutely never say that the first item is bigger than the second, the second is bigger than the third, and the third is bigger than the first. That violates the required transitivity of the comparison, and a sort algorithm is permitted to go into an infinite loop or do any other odd behaviour when given a comparison operation that is ill-behaved.

I'm thinking of replacing the random numbers with a memory reference or GetHashCode() instead.

That is an even worse idea. GetHashCode is useful for one thing and one thing only: balancing a hash table. If you're not balancing a hash table and you call GetHashCode you are doing something wrong.

Moreover, think it through. The situation you're in is that two structs otherwise compare as equal. GetHashCode is contractually required to return the same result for any two structs that compare as equal. GetHashCode is explicitly not a source of disambiguation between two identical things! It is in fact the opposite of that.

Will this guarantee that the selection is made with equal probability?

Nope. GetHashCode is not a source of randomness and no guarantees whatsoever are made about the distribution of hash codes.

Will this guarantee that I would end up with the same results if I run the program again ?

Absolutely not.

3
  • 2
    It's not dangerous, because the random number is assigned on creation and is there-after an immutable part of the struture's state. It therefore doesn't violate the transitivity of the relative orderings. I still can't for the life of me figure out why they'd want to do this.
    – Jon Hanna
    Dec 14, 2011 at 17:01
  • @JonHanna: Ah, I see; I did not read the code carefully enough. Since the random value is persisted, that is safe, yes. Weird, but safe. Dec 14, 2011 at 17:05
  • Premature pessimisation is the root of much weirdness. I do see now that they aren't locking on calls to Random.Next() which isn't thread-safe, so if there's more than one thread involved it's dangerous in that way.
    – Jon Hanna
    Dec 14, 2011 at 17:18
4

Your code isn't dangerous as some suspect, because you are consistent in the use of the numbers (they're random only on object creation).

What I can't see though, is why on earth this could give any benefit.

Consider the case without _randValue. Say you've one struct (we'll call it x) where _param1 equals 2.0 and _param2 equals .12, and another struct (we'll call it y) where _param1 equals 2.0 and _param2 equals .12.

Well, the only way that makes anything different between x and y is that you've added a _randValue to them.

Because they're structs, they don't even have a persistent identity between assignments and boxings. If we do MyStruct z = x we don't have another pointer to x we have a brand new MyStruct.

And even besides that, it makes no difference.

The sole effect of your changes are:

  1. You've added extra memory usage to all cases of the structure.
  2. You've made sorting more expensive.
  3. You've made construction more expensive.
  4. You've made construction a multi-threading bottleneck, because you have to lock on Random.Next().

None of these are likely to be particularly significant, but premature pessimisation is the root much weirdness.

2

By "Memory Reference" do you mean the address of the struct? If you want predictability then you can't use memory addresses.

What are you proposing to hash? If you hash properties of the struct that are equal the hash codes will be equal as well.

I guess I'm confused by 1) why Random is not working for you and 2) why you don't just call two structs with equal values "equal"?

1

Since the Random class is doing what you want, and you're able to seed it to ensure that you get the same values every time, why do you want to change it?

I'm not entirely sure what you plan to do using a memory reference, but even if you could point at the same address and see the same data every time you run the code, you couldn't guarantee a fair distribution of values in memory unless you've filled it with with a random function anyway.

A hashing function should return a fair spread of values, but it's not really the tool for the job — if you want a random number, user a random number generator!

1

I'd personally prefer just a pure random number, but to answer your points:

  1. Yes, it's a hash algorithm, just like md5 or sha (although this algorithm was not specifically created for the purposes you describe)
  2. Yes, the value will be sustained between program launches (@henk-holterman is correct but the value is not guaranteed to stay the same only for strings)
  3. GetHashCode will be way faster
5
  • Wouldn't the hash codes of the 2 structs be the same in this case ?
    – alhazen
    Dec 13, 2011 at 22:40
  • @alhazen: Yes, since the structs are equal they will have the same hash code. The crazy idea here is that, say, if the hash code is odd then the left equal struct is "smaller" than the right one. This is a recipe for disaster, since that is by definition an intransitive comparison. Dec 13, 2011 at 23:46
  • 1. It's a hash algorithm, at that point the similarity with MD5 or the SHA family ends. 2. There's no promise here, and less so between frameworks. 3. How?
    – Jon Hanna
    Dec 14, 2011 at 17:48
  • 1. What else do you expect from similarity bw GetHashCode and MD5 or SHA - they all different in implementation and similar in purpose - create a footprint of the object. 2. Saying this is the same as saying MD5 or SHA do not guarantee to provide identical output for different versions of the algorithms or the length of the output. So disagree here as well. 3. Call it a hunch, but implementation of GetHashCode for String looks way more simple than MD5, plus recommendations for GetHashCode ask developers to keep performane high. Don't see a point in proving this by benchmark.
    – Arthur P
    Dec 14, 2011 at 19:48
  • 1. They've completely different purposes and use-cases. 2. No it's not, it's part of the purpose of MD5 that it provide the same output. Other times it can be part of the purpose that a hash doesn't (e.g. the hash internal to System.Xml.NameTable changes what it will hash a string to each time to twart some DoS attacks). 3. Well yes it's faster than MD5, but not to what was in the question.
    – Jon Hanna
    Dec 14, 2011 at 21:28
0

My reading of your code says that you are using rand has a tie-breaker. I can't see why you would want identical objects differentiated, or even care as to the order of identical objects.

e.g. in this list-

 A
 B
 B
 C

why would you care or want to know which instance of B is first?

I would suggest the better solution would be to add fine grained field that makes sense to the user, say a date created or modified timestamp. You would then have a meaningful tie-breaker, though ties could still occur, I just don't think they would be a problem.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.