Re: Speed query

[Ralph Hempel <rhempel@...>]

David Given wrote:

> I want to implement a priority queue. I have two possible strategies
> when inserting an item:
>
> (a) binary chop through the array until I find the place to insert the
> item, then call table.insert to do it.

Depends if the insert is near the beginning of the table. Does this
move all the subsequent elements "up" by one?

> (b) append the item at the end of the array and then use table.qsort to
> sort the entire array.

The table will be in an indeterminate state for a while, if this is
a concern at all. Here, the performance on table.sort() when the table
is already mostly sorted is a concern.

I'm guessing (almost always a bad idea) that both approaches will
move about the same amount of data on average, and that your binary
search code for approach (a) will take longer to write and debug than
the total time you'll spend running approach (b) :-)

Cheers, Ralph