On Wed, 22 Feb 2012 18:51:27 -0600, Jonathan M Davis <[email protected]>
wrote:
On Thursday, February 23, 2012 01:38:05 Juan Manuel Cabo wrote:
(And not talking about some cheesy insertion sort!!)
If you build an array once and for all, and all you want
is to do binary search on it later, it doesn't make sense to
allocate that big contiguous .data. I'd rather leave it
as an appender.
--jm
On Wednesday, 22 February 2012 at 23:22:35 UTC, Juan Manuel Cabo
wrote:
>> No, because the array doesn't actually exist until appender
>> makes copy.
>
> Will one be able to use the sort!()() algorithm directly on
> your appender,
> that is, without accessing/creating the underlying array?
If appender ends up with multiple arrays in it, then random access is no
longer O(1) and is therefore unacceptable. As such, most sort algorithms
wouldn't work with it.
Also, your bit about using appender to pass an array around wouldn't work
either, because it wouldn't simply be wrapper around an array anymore.
- Jonathan M Davis
P.S. Please don't top post. Replies should go _after_ the preceding message.
Well, a VList (which is a list of arrays) is has O(1) amortized indexing.
Actual performance of my implementation would be O(N / (4080/T.sizeof)), which
isn't so bad. And anything under a page of ram would be O(1).
