This is the mail archive of the systemtap@sourceware.org mailing list for the systemtap project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: array sorting checked in


On Sat, 2005-09-24 at 08:29 -0400, Frank Ch. Eigler wrote:

> > yet you want to allow sorrting an array of unknown size using bubble
> > sort? that can be as bad as O(n log n)
> 
> Actually, a bubble sort is even worse at O(n**2).  The main sort
> function is described as a "merge sort", but I can't quite recognize
> it as such in the code.  

That's probably because it is taught as a recursive algorithm, but in
the real world it is always (in my experience) implemented iteratively.

> I assume all this was chosen for ease of
> prototyping rather than longevity.

I wrote it in a hurry, but sorting isn't rocket science. Assuming we
leave sorting in as a feature, what would you like changed?

> > if you want to maintain stability and accuracy, you either have to
> > limit the size of the array and quite possibilty store it in order,
> > which is O(1) operation for each addition.  [...]
> 
> That is incorrect.  If you think about it, you'll see that maintaining
> a sorted array (i.e., at each insert/delete operation) is just about
> as costly as sorting it once at the end.  

No, it would normally be much, much more costly, even ignoring
scalability problems. Imagine an array updated 100,000 times that
contains only 32 elements. Inserting the elements requires a mimimum of
100,000 comparisions. Sorting it at the end requires a worst case of 100
comparisions.

Even if each element is inserted only once and never updated, you
basically have an insertion sort which is O(n**2), unlike merge sort
which is O(n log n).

I don't imagine _stp_map_sort() being used except at probe exit. If you
are still worried about performance, I tried sorting maps containing
200,000 strings. It took about 0.3 seconds.

Martin




Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]