Sorting with Augmentation

Menu

Diary
OldIRC
URLs
misc
techie
writing

More content will be added to fill this space at some point in the future.

home :: techie :: blog :: programming :: AugmentAndSort.txt

Sorting with Augmentation

When sorting a list of objects, objects will tend to be compared more than once each. With a CPU intensive compare operation this can be inefficient. It tends to be better to produce a new list of simple keys by which the objects canbe sorted and a link to the object, which can then be resolved over the sort. This means that the complex operation is only don O(n) times, rather than O(n log n). And a more simple thing happens O(n log n) times.

This can also be used to great effect with the command line "sort" utility. Say you have a set of log lines, starting with dates of the form DD-MM-YYYY. This is not easy to sort. However, we can augment each line with the date of the form YYYYMMDD which can then be compared either numerically or lexographically to sort the dates. After sorting, the augmentation can be removed.

 $ cat .... | perl -pe 's/(([0-9]{2})-([0-9]{2})-([0-9]{4}))/\4\3\2|\1/' |
              sort  | cut -d \| -f 2

Last updated: 09:41, 24 Jul 2003 [ /techie/blog/programming ] Link..