lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


You could even store the tree nodes in an array rather than an explicit pointer based tree, for cache benefits. Insertion or removal could get expensive if the nodes are pretty heavy, especially with cascading rebalancing fix ups. But if iterating over the structure was the main concern, it might be a very good solution.

On Jun 6, 2015 7:48 PM, "Tim Hill" <drtimhill@gmail.com> wrote:

On Jun 6, 2015, at 3:03 PM, Andrew Starks <andrew.starks@trms.com> wrote:

Yes, I was guessing it was something like that.

Yes. Time series data, for me. That's why I'm mostly interested in integers (samples/scale). I also imagine that floats would make it more difficult to implement and therefore not worth it.

But generally, if all integers were stored in order, then some nice things become possible / necessary.
Things like: "nexti", "firsti", "lasti", and some way to get the index at or lower than some specified value.

I use a single sequence and a table with the index / time value at [1] and the vale at [2]. So every key value is indirected once, simply because I need them to be in order.  I use a simple binary search function, given a desired time value, returns: index (of sequence), value, next_value. I use insert/remove to keep everything together. I couldn't see a way to implement something faster in C.

-Andrew

In C you would use something like a red-black tree, which would give you insert/delete and the ability to iterate over the list in order (regardless of holes).

—Tim