Re: ADT.Heap performance poorer than just sorting and slicing

On Wed, Feb 24, 2016 at 10:48 PM, Arne Goedeke <[email protected]> wrote:
> On 02/22/16 20:33, Chris Angelico wrote:
>
>> Is there a better way to use a heap? Or should I simply accept that
>> the highly optimized sort() function is generally going to be better
>> for anything less than billions of rows?
>
> Well, theoretically the sorting solution should become slower
> at some point. Your heap has constant size, so the insert/pop is
> constant time. On the other hand, in pike most 'special' data structures
> have a relatively high extra cost. This is because operations on arrays
> (and mappings for that matter) usually use special opcodes and do not
> need to make (pike) function calls. This is true for both data
> structures implemented in C modules and all the more for those written
> in pike.
> For instance, in case of the bloom filters I wrote some time ago, the
> overhead for doing the function calls for lookups or inserts is about
> 30% of the overall runtime.

Fair enough. The largest plausible dictionary I have handy is still
less than a million words, and sort-and-slice is still dramatically
faster than the other options. Here's timings:

Enter a word: helo
[0] 13.732 (null)
[1] 14.075 hello helos helot ohelo helo
[2] 27.382 hello helos helot ohelo helo
[3] 25.602 hello helos helot ohelo helo
[4] 22.044 hello helio helco helos helo
[5] 20.526 hello helio helco helos helo

The first time is simply this:

String.fuzzymatch(words[*], checkme);

As in, it does the fuzzy matching, collects them in an array, and does
nothing else. Maybe a C-implemented heap would be quicker... but a C
implementation of fuzzymatch would make more difference, given that
the sorting and slicing (visible in figure [1]) is only 2.5% slower.
So it's the overhead of a Pike-implemented data structure over the
C-implemented array sort that's killing this.

I'll stick with sort-and-slice!

ChrisA