Spot the defect: Bad comparisons, part one

Spot the defect: Bad comparisons, part one

Rate This
  • Comments 15

The mutable List<T> class provides an in-place sort method which can take a comparison delegate. It's quite handy to be able to sort a list into order by being able to compare any two elements, but you have to make sure you get it right.

First off, what are the requirements of the comparison delegate? They are clearly documented: the comparison takes two elements and returns a 32 bit signed integer. If the first element is greater than the second then the integer is greater than zero. If the first element is less than the second then the integer is less than zero. If the first element is equal to the second then the integer is zero.

See if you can figure out why each of these comparisons can give bad results.

Comparison #1: Putting on my top hat:

enum Clothes
{
  Hat,
  Tie,
  Socks,
  Pocketwatch,
  Vest,
  Shirt,
  Shoes,
  Cufflinks,
  Gloves,
  Tailcoat,
  Underpants,
  Trousers
}

static int Compare(Clothes x, Clothes y)
{
  const int xGreater = 1;
  const int yGreater = -1;

  // If x has to go on after y then x is the greater
  // If y has to go on after x then y is the greater
  // Otherwise, they are equal

  switch (x)
  {
  case Clothes.Tie:
    if (y == Clothes.Shirt) return xGreater;
    break;
  case Clothes.Socks:
    if (y == Clothes.Shoes) return yGreater;
    break;
  case Clothes.Pocketwatch:
    if (y == Clothes.Shirt || y == Clothes.Vest) return xGreater;
    break;
  case Clothes.Vest:
    if (y == Clothes.Shirt) return xGreater;
    if (y == Clothes.Tailcoat || y == Clothes.Pocketwatch) return yGreater;
    break;
  case Clothes.Shirt:
    if (y == Clothes.Tie || y == Clothes.Pocketwatch ||
      y == Clothes.Vest || y == Clothes.Cufflinks || y == Clothes.Tailcoat)
      return yGreater;
    break;
  case Clothes.Shoes:
    if (y == Clothes.Trousers || y == Clothes.Socks || y == Clothes.Underpants)
      return xGreater;
  break;
  case Clothes.Cufflinks:
    if (y == Clothes.Shirt) return xGreater;
    break;
  case Clothes.Tailcoat:
    if (y == Clothes.Vest || y == Clothes.Shirt) return xGreater;
    break;
  case Clothes.Underpants:
    if (y == Clothes.Trousers || y == Clothes.Shoes) return yGreater;
    break;
  case Clothes.Trousers:
    if (y == Clothes.Underpants) return xGreater;
    if (y == Clothes.Shoes) return yGreater;
      break;
  }
  return 0;
}

OK, before you read on, can you figure out what the defect here is? It seems perfectly straightforward: if two things have to be ordered then they are ordered, and if not, then we say we don't care by setting them equal.

Does that work?

.

.

.

.

.

.

.

If you actually try it out on a real list of randomly ordered clothes, you'll find that much of the time this sorts the list into a senseless order, not into an order that preserves nice properties like shoes going on after trousers. Why?

An undocumented but extremely important assumption of the sorting algorithm is that the comparison function provides a consistent, total order. Part of providing a total order means that the comparison must preserve the invariant that things equal to the same are equal to each other. This idea that if you don't care about the order of two things then you can call them equal is simply false. In our example Tie is equal to Hat and Hat is equal to Shirt, and therefore the sort algorithm is justified in believing that Tie should be equal to Shirt, but it isn't.

Suppose, for example, the first element is "Hat". A sort algorithm is perfectly justified in scanning the entire list, determining that everything is equal to the first element, and concluding that therefore it must already be sorted. Clearly a list where every element is equal to the first element is sorted! The actual implementation of QuickSort in the BCL is quite complex and has several clever tricks in it that help optimize the algorithm for common cases, such as subsets of the list already being in sorted order. If the comparison is not consistent then it is easy to fool those heuristics into doing the wrong thing. And in fact, some sort algorithms will go into infinite loops or crash horribly if you give them an incomplete comparison function.

The right algorithm for sorting a set with a partial order is topological sort; use the right tool for the job.

Next time: we do the same thing, backwards

  • The $64K question here is why was this perfectly reasonable assumption not documented in the first place? I imagine many people might find words like "transitive" and "consistent total order" scary, but still.

  • Problem with the initial specification in comments:

     // If x has to go on after y then x is the greater

     // If y has to go on before x then y is the greater

    They should both be "before" or "after", yes?

  • @Anton.

    Sorting is Hard, let's go shopping.

    /barbie

    The docs call out that it uses QuickSort.

    wikipedia ( en.wikipedia.org/.../Quicksort ) helpfully identifies it as a comparison sort ( en.wikipedia.org/.../Comparison_sort )

    "A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator obey two of the properties of a total order:

      1. if a ≤ b and b ≤ c then a ≤ c (transitivity)

      2. for all a and b, either a ≤ b or b ≤ a (totalness or trichotomy).

    "

    If someone can't be bothered to understand even the most basics aspects of an algorithm before they use it I'm not overly forgiving.

  • Eric,

     Your point brings tough memories... I used stl sort algorithms I forgot for which version to sort doubles.

     And some of the doubles where NaNs, default < was used for comparison and sure enough under some arrangement of doubles I would get sporadic data and sometimes access violation (lucky case)

  • In addition to the valid point that it should be safe to assume people using features like Sort() are in fact familiar with such a basic concept, there's also the fact that the comparison function above is just plain crazy even if it did happen to produce a valid order. It's a maintenance nightmare. Either the enum itself should be ordered according to what someone considers the correct sort order or (if the sort order is independent of the enum data structure) some mapping from enum to an ordered list should be declared. Either way, the comparison function should just be a simple comparison of two values, not this insane switch statement.

    Sheesh. The scary thing is that if Eric is posting the code here, there's a pretty good chance something similar to this actually showed up "in the wild". Yikes!

  • Are there bonus points for guessing what's going to be wrong with the code in the next post before it's been posted, based on "Next time: we do the same thing, backwards"? Psychic deblogging?

  • So are we going to get to see your JS toposort ported to C#?

  • Gabe: replace "var" with "int", "for" with "foreach" and you are almost done with porting :)

  • This type of comparison function can also end up with stuff like a<b, b<c, and a=c.  So a comes before b, b comes before c, but a and c are equal, so b comes before a.

  • ... resulting in an infinite loop while the sort function tries to get a before b and b before a at the same time... fun fun fun.

  • "In our example Tie is equal to Hat and Hat is equal to Shirt, and therefore the sort algorithm is justified in believing that Tie should be equal to Shirt, but it isn't."

    I love this analogy - the one tweak I would make is to use Trousers and Underpants as the two things that get mixed up, just because I like the idea of a guy getting into that position while already wearing a top hat.

  • I just wrote the following pex test for fun:

           [PexMethod]

           public static void Transitive(ClothSort.Clothes x, ClothSort.Clothes y, ClothSort.Clothes z)

           {

               PexAssume.IsTrue(ClothSort.Compare(x, y) <= 0);

               PexAssume.IsTrue(ClothSort.Compare(y, z) <= 0);

               PexAssert.IsTrue(ClothSort.Compare(x, z) <= 0);

           }

    It found 9 unique inputs which violate the transitivity law. example (tie, hat, shirt) are not transitive under equality. The other properties however hold:

           [PexMethod]

           public static void Reflexive(ClothSort.Clothes x)

           {

               Assert.IsTrue(ClothSort.Compare(x, x) == 0);

           }

           [PexMethod]

           public static void Symmetric(ClothSort.Clothes x, ClothSort.Clothes y)

           {

               var cmp1 = ClothSort.Compare(x, y);

               var cmp2 = ClothSort.Compare(y, x);

               Assert.IsTrue(cmp1 == 0 && cmp2 == 0 || cmp1 < 0 && cmp2 > 0 || cmp1 > 0 && cmp2 < 0);

           }

    I love pex. It was so easy to test this comparison function. research.microsoft.com/.../downloads.aspx

  • @tobi

    Hi was curios about pex and how it works and for my surprise you can try it online, so I just copied pasted the code to the web but it find only one exception, did I do something wrong?

    (I hope this permanent link works)

    www.pexforfun.com/default.aspx

  • I find it peculiar that you have declared constants xGreater and yGreater. Using 1 and -1 would be better as it would be clearer what value you are returning.

  • One trap with such comparisons is that the comparison operators on floating-point types don't provide a total ordering. In particular NaN isn't equal to itself, and isn't either larger or smaller than any number.

    And when abusing Sort as shuffle you need to make sure you generate the random number only once, and not on each comparison. The browser choice screen fell for this one.

Page 1 of 1 (15 items)