Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #36327

Re: Wanted: List of intervals

Show all headers | View raw

Martin Gregorie wrote:
> On Fri, 17 Feb 2017 03:30:13 +0000, Volker Borchert wrote:
> 
> >>   You'd probably beat even that by walking the tree with two pointers
> >>   and doing the concatenation as you read the data out of it. Its quite
> >>   possible that this may be the fastest solution for a large data set.
> > 
> > Yes. This is one possible solution I've been thinking of. And since I'm
> > probably not the first one with this sort of problem, I hoped someone
> > else has published an implementation. A red/black tree is too easy to
> > get wrong for me being keen on doing it myself.
> >
> No need of that: the TreeMap class is based on a red-black tree.

At least I'd have to subclass it to reasonably implement the
look-at-neighbors-during-addition and to avoid the additional
object overhead for either the $Entry (if using TreeSet<Range>)
or two Long (if using TreeMap<Long,Long>). And even then, the
$Entry will still have three references and one boolean extra.
Given that insertion is O(log n) with nontrivial constants,
I'd gain little if any in time and pay extra in space compared
to my ugly-but-working ArrayList-sort-concatenate solution
which costs two refs extra - one in the ArrayList and one in
the temporary array during mergesort.

After some thinking and explaining the problem to my horse
while warming up, I came up with a neat trick based on the
precondition that the ranges do never overlap: it is sufficient
to keep a single SortedSet<long>, do
	void add(long lower, long upper) {
	  if (lower < upper) {
	    if (!set.remove(lower))
	      set.add(lower);
	    if (!set.remove(upper))
	      set.add(upper);
	    assert (set.size() & 1) == 0;
	  }
	}
then iteration over set will return lower and upper bounds
alternatingly.

I then took looks at Guava, Apache commons collections, Apache
commons primitives (which is marked "dormant"), Colt, pcj, but
they only have hash sets. The only SortedSet<long> I could find
was from fastutil, but at first sight it uses an AVL tree which
is an improved red-black tree and will probably have even more
memory overhead.

I then thought further, of using a linear probing HashSet<long>,
compacting its underlying long[] when done, and sorting that.
This would be reasonably conservative with memory and should
save some time because the sort(long[]) should be a little
faster than sort(Range[]) by a primitive field, and because it
would not be O(n log n) but O(n' log n') with n' < n.

But I think the possible savings do not justify being so clever
so soon. Therefore, unless I can find a SortedSet with really
little memory overhead, or the sort() proves to be a problem
in the field, I'll probably keep my quick-and-dirty solution.

Lesson learnt: There Is No Free Lunch.

-- 

"I'm a doctor, not a mechanic." Dr Leonard McCoy <mccoy@ncc1701.starfleet.fed>
"I'm a mechanic, not a doctor." Volker Borchert  <v_borchert@despammed.com>

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-16 21:13 +0000
  Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-16 17:11 -0500
    Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-17 02:49 +0000
      Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-16 22:32 -0500
        Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-18 07:28 +0000
        Re: Wanted: List of intervals Robert Klemme <shortcutter@googlemail.com> - 2017-02-19 20:02 +0100
          Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-19 17:13 -0500
            Re: Wanted: List of intervals Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-02-19 17:18 -0500
              Re: Wanted: List of intervals Robert Klemme <shortcutter@googlemail.com> - 2017-02-19 23:31 +0100
                Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-19 23:00 -0500
                Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-19 23:09 -0500
              Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-19 22:52 -0500
                Re: Wanted: List of intervals Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-02-20 07:47 -0500
                Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-02-20 13:30 +0000
                Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-20 08:51 -0500
  Re: Wanted: List of intervals Robert Klemme <shortcutter@googlemail.com> - 2017-02-16 23:18 +0100
    Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-17 02:54 +0000
  Re: Wanted: List of intervals Martin Gregorie <martin@address-in-sig.invalid> - 2017-02-16 23:58 +0000
    Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-17 03:30 +0000
      Re: Wanted: List of intervals Martin Gregorie <martin@address-in-sig.invalid> - 2017-02-17 12:10 +0000
        Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-18 08:06 +0000
          Re: Wanted: List of intervals Martin Gregorie <martin@address-in-sig.invalid> - 2017-02-18 13:18 +0000
            Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-18 19:58 +0000
              Re: Wanted: List of intervals Martin Gregorie <martin@address-in-sig.invalid> - 2017-02-18 20:45 +0000
              Re: Wanted: List of intervals Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-02-19 10:57 -0500
                Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-02-19 17:36 +0000
  Re: Wanted: List of intervals a.laforgia@gmail.com - 2017-02-17 03:13 -0800
  Re: Wanted: List of intervals Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-02-17 08:20 -0500
  Re: Wanted: List of intervals Roedy Green <inquiry@mindprod.com> - 2017-03-08 01:30 -0800
    Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-03-09 19:32 +0000
      Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-03-09 23:05 +0000
        Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-03-11 01:40 +0000
          Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-03-11 12:39 +0000
            Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-03-11 18:15 +0000
              Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-03-11 21:47 +0000

csiph-web