Journal Articles

CVu Journal Vol 28, #1 - March 2016
Browse in : All > Journals > CVu > 281 (11)

Note: when you create a new publication type, the articles module will automatically use the templates user-display-[publicationtype].xt and user-summary-[publicationtype].xt. If those templates do not exist when you try to preview or display a new article, you'll get this warning :-) Please place your own templates in themes/yourtheme/modules/articles . The templates will get the extension .xt there.

Title: ACCU London: Dietmar Khül

Author: Martin Moene

Date: 01 March 2016 20:40:23 +00:00 or Tue, 01 March 2016 20:40:23 +00:00

Summary: A (clueless) review of the Jan 16th ACCU London Meeting.

Body: 

Dear NHS Direct,

I recently attended ACCU London’s talk about ‘Quicker Sorting’ by Dietmar Kühl, hoping to get my plumbing sorted or pick up some DIY tips. The evening started with a huge pile of burritos, which I was not expecting, though they were most welcome. The 30 or more of us then sat in the room and Dietmar proceeded to tell us how he had tried to beat std::sort starting with the undergraduate computer science exercise of writing quick sort. Having never been a computer science undergraduate, I was unclear how this exercise could possibly be good for anyone. I do prefer gardening, though my knees sometimes give me trouble.

Quick sort takes a pivot point, which is handy since I have recently had a pivot gate installed. I digress. Back to the plumbing. It then puts the smaller numbers on one side and the larger numbers on the other. And does the same for each side. This is apparently brilliant provided the numbers weren’t already in order. I must wonder why you’d want to sort numbers that were already sorted, but people make all kinds of strange requests. Dietmar reassured us that it can sort all kinds of things whether they are numbers or not, and whether they are already sorted or not. I wonder if it can sort NaNs? I presume you could add a pre-condition check to see if the inputs were already sorted in order to avoid slowing things down by re-sorting them. But checking the precondition that might slow things down further.

So, quick sort isn’t always that quick. Dietmar then showed how just comparing three or fewer items using ifs and elses rather than recursing further speeds things up. He went on to show further refinements many of which got a few extra speedups, initially catching up with a standard implementation, and then beating it slightly.

The take home message was that std::sort is not a single algorithm and what they tell you in a computer science undergraduate degree might not be the whole story. He then took us to a German bar round the corner and we had a long discussion about climbing roses. Well I did, but I may have joined the wrong group in the pub.

Yours sincerely,

Mrs Trellis.

North Wales.

Notes: 

More fields may be available via dynamicdata ..