This is the mail archive of the
systemtap@sourceware.org
mailing list for the systemtap project.
Re: array sorting checked in
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