Re: Constant time insertion into a sorted list?

On Jul 18, 9:55 am, jaycx2.3.calrob...@xxxxxxxxxxxxxxxxxxxxxx (Robert
Maas, http://tinyurl.com/uh3t) wrote:

From: Alex Fraser <m...@xxxxxxxxxxx>
I tried a straight-forward priority queue implemented with an array.

As soon as you allocate an array, the maximum number of entries is
fixed by the size of the array, hence regardless of what algorithm
you use, the time is bounded by the time it takes to process the
entire array. Therefore constat time is trivial: Take however long
it takes to find the item you want, then insert idle cycles to
finish the maximum possible time, so it *always* takes the maximum
possible time, which is a *constant*.

Funny how if the original request is taken literally, you want the
time to be constant, you don't care if that constant is a half
hour, it's trivial to satisfy your request in a way you really
don't want!

So from a practical point of view, with fixed-allocation of array,
use any log(NumberActiveEntries) algorithm, and if you *really*
want *constant* time then pad with idle cycles to fill out the rest
of the log(ArraySize) time. Or to make your algorithm easier,
*always* have the array 100% full, by putting dummy entries as filler
for any unused cells in the array, so that the basic log(N) algorithm
will in fact always consume exactly log(ArraySize) time.
Thus the algorithm for enquing a new entry is:
  Dequeue a dummy, then enqueue the new entry.
and the algorithm for dequeuing the most urgent entry is:
  Dequeue the most urgent entry and set it aside, enqueue a dummy, return saved value.

This may be easier said than done, since there really is no simple
exactly log(N) algorithm in the first place. All algorithms are
bounded by log(N) but sometimes run shorter. Can anybody think
of an algrithm that always achieves exactly log(N) time?
Self-balancing binary tree doesn't work because the number of
pivots needed to rebalance varies from call to call.
I don't think heap achieves exactly fixed log(N) time either.

I think you're going to have to be practical and settle for bounded
time rather than absolutely fixed time:
  ActualTime <= log(NumberOfActiveEntries) <= log(SizeOfArray)
Let some *other* process kill time with idle cycles to fill up the
unused time, OK? Or run the whole process at interrupt level, with
the main program doing some background task such as factoring one
of the RSA challeges or processing radiotelescope data to search
for signals from outer space etc.

The purpose behind finding a constant time algorithm to perform this
task is so that the time it takes to perform an insertion incurs a
predictable and small search overhead when the number of items in the
list is unbounded. To make insertion constant with the method you
describe, then the number of entries in the list cannot grow beyond a
predefined size, so that you know how long to spin idly to make
insertion time "constant."

I understand your point, but it's unrelated to what I'm trying to
accomplish. log n in the worst case is already rather trivial through
a variety of methods, but it always has the property of necessarily
taking longer to find the insertion point, the more entries are in the
list. This is what I want to avoid if it's even possible. I'm not
looking for a generalized solution to real-time number sorting, since
there are certain potentially exploitable properties of the numbers
that will be inserted into this list (numbers representing timers,
that will always be increasing, but at different rates).
.

Relevant Pages

  • Re: An algorithm questions
    ... Mathieu Dutour -- Doubly linked list in two arrays + a array ... Richard Harter -- The devil's list algorithm ... The storage costs are: ... dependent; I prefer to use unsigned char arrays for that reason; YMMV. ...
    (comp.lang.c)
  • Re: regex question - trying to find ".mp3" in a SELECT box
    ... But `Array' is a Function object reference. ... Establish a new execution context using F's FormalParameterList, ... Since is not a primitive value, the exception should be thrown. ... | 5.2 Algorithm Conventions ...
    (comp.lang.javascript)
  • Re: Mergesort Vs Quicksort
    ... I might not have correctly remembered my algorithm of months ago ... for sorting records in an array using one auxilary of the ... on how things turn out from lower levels of recursion, ... whether the number of records in the array segment to be sorted is ...
    (comp.programming)
  • Re: Reference to derived type element by index?
    ... as a set of distinctively-named scalars. ... In another scope, the same common block ... would be a single array. ... algorithm and a specific application of the algorithm, ...
    (comp.lang.fortran)
  • [SUMMARY] Maximum Sub-Array (#131)
    ... # sum the integer values of array contents ... algorithm, ... all possible lengths, to check each subarray. ... $ time ruby -r max_sub_array ...
    (comp.lang.ruby)