<< Back to previous view

[TGEN-1] generators/shuffle violates contract of Comparable Created: 13/Oct/12  Updated: 14/Oct/12  Resolved: 14/Oct/12

Status: Resolved
Project: test.generative
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Ben Smith-Mannschott Assignee: Ben Smith-Mannschott
Resolution: Completed Votes: 0
Labels: None
Environment:

Mac OS X 10.8.2
java version "1.7.0_06"
Java(TM) SE Runtime Environment (build 1.7.0_06-b24)
Java HotSpot(TM) 64-Bit Server VM (build 23.2-b09, mixed mode)


Attachments: File fisher-yates-shuffle.diff    
Patch: Code
Approval: Accepted

 Description   

JDK 7's sort function is stricter about verifying that implementations of the comparison function actually obey their contract. It will even helpfully throw an exception when this is not the case:

java.lang.IllegalArgumentException: Comparison method violates its general contract!

The root cause is this gem:

generators.clj
(defn shuffle
      "Shuffle coll"
      [coll]
      (sort-by (fn [_] (long)) coll))

Which does not work on JDK7 since TimSort is clever enough to detect that the ordering function is behaving inconsistently, resulting in the previously mentioned exception.

Also, this is just a bad idea:

A variant of the above method that has seen some use in languages that support sorting with user-specified comparison functions is to shuffle a list by sorting it with a comparison function that returns random values. However, this is an extremely bad method: it is very likely to produce highly non-uniform distributions, which in addition depends heavily on the sorting algorithm used.

(wikipedia)



 Comments   
Comment by Ben Smith-Mannschott [ 14/Oct/12 11:13 AM ]

Fixed by 5a59bf0f on test.generative.

Generated at Tue Sep 02 07:08:15 CDT 2014 using JIRA 4.4#649-r158309.