Why java.util.Arrays uses Two Sorting Algorithms

March 30th, 2013

java.util.Arrays uses quicksort (actually dual pivot quicksort in the most recent version) for primitive types such as int and mergesort for objects that implement Comparable or use a Comparator. Why the difference? Why not pick one and use it for all cases? Robert Sedgewick suggests that “the designer’s assessment of the idea that if a programmer’s using objects maybe space is not a critically important consideration and so the extra space used by mergesort maybe’s not a problem and if the programmer’s using primitive types maybe performance is the most important thing so we use the quicksort”, but I think there’s a much more obvious reason.
Read the rest of this entry »

Why Functional Programming in Java is Dangerous

January 20th, 2013

In my day job I work with a lot of very smart developers who graduated from top university CS programs such as MIT, CMU, and Chicago. They cut their teeth on languages like Haskell, Scheme, and Lisp. They find functional programming to be a natural, intuitive, beautiful, and efficient style of programming. They’re only wrong about one of those.
Read the rest of this entry »

XOR Defines an Abelian Group

November 26th, 2012

Something I realized in the middle of an introductory course on cryptography when the instructor said the word “commutative” for the first time: N-bit strings with the operation XOR are an abelian group.
Read the rest of this entry »

Counterexamples and Proofs

August 11th, 2012

Memo to self: when attempting to prove a theorem, and it just doesn’t seem to be working; don’t forget to search for counterexamples. The theorem may not actually be true.
Read the rest of this entry »

1% Problems

July 22nd, 2012

I hate 1% problems. No this isn’t an OWS slogan. I’m thinking of those code issues that really aren’t a problem 99% of the time, but when they bite, they’re really hard to debug and they cause real pain. Several common cases in Java:

  1. Using java.util.Date or java.util.Calendar instead of JodaTime.
  2. Not specifying a Locale when doing language sensitive operations such as toLowerCase() and toUpperCase().
  3. Not escaping strings passed to SQL, XML, HTML or other external formats.

What I hate most is that it’s really, really hard to convince other developers that these are problems they should take seriously. Read the rest of this entry »