breinify / brein-time-utilities Goto Github PK

Hello, is the interval tree thread safe? It doesn't seem so but then what is the purpose of the atomic boolean being used in remove?

Hello,
I am interested in making the interval tree thread-safe and wanted to get your feedback on the various approaches, feasibility, etc. For my case I will have many more readers than writers and writes will be infrequent compared to reads.

1. Seems like a ReadWriteLock might suffice here. Simply wrapping the modifying methods with a write lock and a read lock for the read methods. May lower throughput quite a bit depending upon thread contention.
2. Potentially a lock-free version could be achieved if you can find a serialization point/node in the tree under which the modification would take place and then separately rebuild that subtree and then use a CAS operation to update that node in the original tree. I'm not quite sure how the self-balancing aspect of the tree might affect this.

Are there any other ideas that might work? Have you had a need for thread safety in your own use?

Thanks again!

Hello,
Have you done any benchmarking on the tree? I am not quite sure what performance to expect, so let me describe my use case.
I have a map, mapping keys to interval trees. In the worst case there are about 35 keys in the map and in turn I query 35 interval trees. Each tree has ~1000 items in it. The overlap query is not cutting the tree down by much (by design), so I am fetching close to all items from each tree. Doing this sequentially and then combining all tree overlap streams into a single list is taking ~40-50ms, which seems a bit high.
psuedo code:
map.entrySet().stream().map(e -> e.value().overlaps(query)).flatMap(identity()).map(id -> getObject(id)).collect(toList());
getObject() is just a lookup in another map to get the object from the id in the tree.
Simply changing this to a parallelStream() improved the performance by ~4x.
Do you have any pointers or guidance on improving the performance of the tree? Or Is this even the right approach? It is still a bit baffling to me why the sequential performance is not as high as I would imagine.
Thanks!

Hi,
In com.brein.time.timeintervals.intervals.IdInterval.compareId(IdInterval), the method is using compareTo() to compare the ids. Should this be equals() instead? Thanks!

Hi Phillipp,
Is there no way to traverse the tree in sorted order of the intervals? It doesn't seem like there is with an augmented interval tree but wanted to check with you. Thanks

Hi, I'm trying to use the library for a custom type. So, I've implemented IInterval interface.
Since, it IInterval extends Comparable, I thought, the tree uses IInterval's compareTo() method for comparison.

But, it seems the tree uses valueComparator from IntervalValueComparator to compare nodes.

So, my question is, is compareTo() in IInterval being used, somewhere?

Hi,

The following code output OVERLAPS instead of the expected AFTER. What am I doing wrong?

        LongInterval i1 = new LongInterval(1L, 5L);
        LongInterval i2 = new LongInterval(8L, 10L);
        System.out.println(i1.ir(i2));

I'm using version 1.6.2.

Thanks,
Carlos

Could you please augment the interval tree to include the operations of deletions of intervals? Including the possibility to efficiently remove several nodes in the tree given an interval?

Hello,
Does the iterator return entries according to the comparator, e.g. in ascending order of the intervals?

Thanks
Evan

It would be nice to implement some other operations on intervals like union, disjoints, etc..

Merging (union) can be similar to following one:
https://gist.github.com/zac-xin/4349436