On Mon, Jul 8, 2019 at 10:09 PM Pavel Stehule <pavel.stehule@gmail.com> wrote:
> po 8. 7. 2019 v 18:47 odesílatel Paul A Jungwirth <pj@illuminatedcomputing.com> napsal:
> I am not against a multirange type, but I miss a explanation why you introduce new kind of types and don't use just
arrayof ranges.
Hi Pavel, I'm sorry, and thanks for your feedback! I had a response to
your earlier email but it was stuck in my Drafts folder.
I do think a multirange would have enough new functionality to be
worth doing. I was pretty reluctant to take it on at first but the
idea is growing on me, and it does seem to offer a more sensible
interface. A lot of the value would come from range and multirange
operators, which we can't do with just arrays (I think). Having a
range get merged correctly when you add it would be very helpful. Also
it would be nice to have a data type that enforces a valid structure,
since not all range arrays are valid multiranges. My reply yesterday
to Jeff expands on this with all the functions/operators/etc we could
offer.
Your other email also asked:
> I don't think - working with large arrays is slow, due often cache miss.
>I understand so it depends on data, but in this area, I can imagine significant memory reduction based on running
processing.
>
> array builder doesn't respect work_men, and I think so any different way is safer.
I'm still thinking about this one. I tried to work out how I'd
implement a tree-based sorted list of ranges so that I can quickly
insert/remove ranges. It is very complicated, and I started to feel
like I was just re-implementing GiST but in memory. I did find the
interval_set class from Boost's boost_icl library which could offer
some guidance. But for now I want to press forward with a
sort-then-iterate implementation and consider a different
implementation later. If you have any guidance I would appreciate it!
I especially want something that is O(n log n) to insert n ranges.
Other suggestions here are very welcome! :-)
Regards,
Paul
