I am reading this question on stack overflow and it was irritating for me that the most people say: reversing a linked list is possible only in O(n). Okay, this is true for a single linked lists, but not for double linked lists like I will show you with my quick and dirty CarouselList:

The key point is the incrementer/decrementer:

static class Incrementer<T> {

 Node<T> getNext(Node<T> node) {
   return node.next;
 }

 Node<T> getStart(Node<T> head) {
   return head;
 }
}

static class Decrementer<T> extends Incrementer<T> {

 @Override
 Node<T> getNext(Node<T> node) {
   return node.previous;
 }

 @Override
 Node<T> getStart(Node<T> head) {
   return head.next;
 }
}

This way the ‘iteration order’ can be easily switched in O(1). Of course this comes to the cost of a bit more expensive iteration but this is another issue …

If the implementation could use an ArrayList (not a linked list) it would be more simple: return different iterators based on a ‘reverse’ attribute. Then either return an iterator with counter++ or return one with counter– if reverse == true

Update: This post was reposted @ dzone with lots of upvotes – Thanks!

Yesterday I learned that there is an O(n) integer sort algorithm (I should have read this before in a basic algorithm book :-/).

Now I wondered: is this necessary in real applications? E.g. somewhere in Java? Today I have taken the counting sort and I can argue: yes, you should use integer sort especially for large arrays!

And when in detail should you apply the fast integer sort? Apply it if

• you have positive integer values to sort. The requirement ‘positive’ and ‘integer’ is necessary for the listed O(n) algorithm, but not if you implement your own possible better solution.
• you have a limited interval for the integer values (preferable min and max=M should be known before you sort)
  E.g. if you know the maximum integer number in your array will be M=10^7 then you should use the integer sort if the array length n is roughly greater than M/2500 = 40000. This linear equation should hold true (for some values ;-)), because quick sort is nearly independent of M and the time-offset for integer sort increases nearly linear with M as you can see in the graph

Now take a look at the graph where y=time in seconds for 10 runs and x=array length:

Conclusion

I would apply this sorting algorithm only for n>10^7 where the difference between quicksort and integer sort could lay in the range of seconds. The memory consumption was not measured but should be ~twice times higher for the fast integer sort.

Java Sourcecode

//class LinearSort
public static void main(String[] args) {

 // init jvm
 new LinearSort().start(1000, 10000, 10000);
 new LinearSort().start(1000, 10000, 10000);

 // run performance comparison
 for (int maxInteger = 1000; maxInteger < 100000000; maxInteger *= 3) {
  for (int arrLength = 1000; arrLength < 100000000; arrLength *= 3) {
   System.gc();
   new LinearSort().start(arrLength, maxInteger, 10);
  }
 }
}

 private Random rand = new Random();

 // stop watch for integer sort with *unknown* range. marked as Lin in the plot
 private SimpleTimer linearStopWatch = new SimpleTimer();</pre>

 // stop watch for integer sort with known range. marked as Lin' in the plot
 private SimpleTimer linearKnownStopWatch = new SimpleTimer();

 private SimpleTimer qSortStopWatch = new SimpleTimer();

 private void start(int arrLength, int maxInteger, int times) {
 for (int count = 0; count < times; count++) {
   int[] list1 = new int[arrLength];
   for (int i = 0; i < arrLength; i++) {
     // do only allow positive integers until the specified 'max'-value
     list1[i] = Math.abs(rand.nextInt(maxInteger));
   }
   linearStopWatch.start();
   LinearSort.sort(list1);
   linearStopWatch.pause();

   int[] list2 = Arrays.copyOf(list1, arrLength);
   qSortStopWatch.start();
   Arrays.sort(list2);
   qSortStopWatch.pause();

   list2 = Arrays.copyOf(list1, arrLength);
   linearKnownStopWatch.start();
   LinearSort.sort(list2, 0, maxInteger);
   linearKnownStopWatch.pause();
 }

 System.out.println(maxInteger + ";" + arrLength + ";" + linearStopWatch
 + ";" + linearKnownStopWatch
 + ";" + qSortStopWatch); // + ";" + qSortListStopWatch);
}

 static int[] sort(int[] array, int min, int max) {
   //the range is useful to minmize the memory usage
   //countIntegers holds the number of each integer
   int[] countIntegers = new int[max - min + 1];

   for (int i = 0; i < array.length; i++) {
     countIntegers[array[i] - min]++;
   }

   int insertPosition = 0;
   //fill array in sorted order
   for (int i = min; i <= max; i++) {
     for (int j = 0; j < countIntegers[i - min]; j++) {
       array[insertPosition++] = i;
     }
   }
   return array;
 }

 static int[] sort(int[] array) {
   int min, max = min = array[0];
   //determine the max and min in the array
   for (int i = 1; i < array.length; i++) {
     if (array[i] < min)
       min = array[i];

     if (array[i] > max)
       max = array[i];
   }
   return sort(array, min, max);
 }

 //class SimpleTimer

 private long lastStart = -1;
 private long time;

 public void start() {
   if (lastStart != -1)
     throw new IllegalStateException("Call stop before!");

   lastStart = System.currentTimeMillis();
 }

 public void pause() {
   if (lastStart < 0)
     throw new IllegalStateException("Call start before!");

   time = time + (System.currentTimeMillis() - lastStart);
   lastStart = -1;
 }

 public String toString() {
   return time / 1000f + "";
 }

A small group on twitter started a funny (or stupid?) mem #internetmusiker (which is internet-musician in English). The initial idea came from FR31H31T. The task was to slightly change a name of a musician, band or song and get a phrase which sounds like an internet- or computer-technical phrase. The results were sometimes very funny and my favourite examples are:

Nine inch Mails, Modem Talking, Deftunes, Wii valdi oder iValdi and Sudo Lindenberg

Look here for the full list!

Now I wanted to know which phrases were the most retweeted once and I wrote a small Java application which uses the twitter4j API to do this task.

Twitter twitter = new Twitter(login, pw);
for (int page = 1; page < 1500; page++) {
 Query query = new Query("internetmusiker");
 query.setPage(page);
 query.setRpp(50);

 try {
   QueryResult res = twitter.search(query);
   if (res.getTweets().size() == 0) {
     log("No more tweets found");
     break;
   }
   log("page:" + page + " found " + res.getTweets().size() + " tweets");
   for (Tweet twe : res.getTweets()) {
      allTweets.add(twe);
   }
 } catch (TwitterException ex) {
   log("End of search reached", ex);
   break;
 }
}

To avoid a full search for the next time I saved the results via my small helper object StoreableTweet to a text file and used ‘query.setSinceId(maxId);’ while querying.

To calculate the retweets there is no API provided (or am I wrong?) so I needed to parse for a ‘RT @name text’ and look up the text within all the tweets. For that I created a hash map with the text content as keys.

 Map<String, StorableTweet> mappedTweets = new HashMap();

 for (StorableTweet stw : allTweets) {
   String key = stw.getTextToRetweet();
   if (mappedTweets.containsKey(key))
     log("Mapped tweets collection already contains tweet:"
         + stw.toPersistentString());

   mappedTweets.put(key, stw);
 }

 for (StorableTweet stw : allTweets) {
   if (stw.getOrigRetweetedText().length() > 0) {
     StorableTweet retweet = mappedTweets.get(
       stw.getOrigRetweetedText());
     if (retweet == null)
       log("Skip retweet: cannot find retweet "
          + stw.toPersistentString());
     else
       retweet.addRetweet(stw);
   }
 }

Again you can look here for the resulting html file. So start your own with #internetmusiker oder even #internetmusician?