Re: array sorting checked in

[fche@redhat.com (Frank Ch. Eigler)]

jamesd.wi wrote:

> [...]
> am I missing something?

Yes.

> 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.  I assume all this was chosen for ease of
prototyping rather than longevity.

> [...] The programmer can't know in advance the size of the array, if
> he knew that information he wouldn't be running systemtap.

Array sizes are limited - by design we perform no dynamic memory
allocation during a systemtap session run.  If those limits are
exceeded, the user will be told and will be able to retry with a
larger limits.

Regardless, even if the array size is limited, it can still be large
enough that sorting would be a problem.

> 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.  I have no idea what you mean
by "accuracy" being a factor either way.


- FChE