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

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

Re: Wanted: List of intervals

Show all headers | View raw

On 2/18/2017 2:58 PM, Volker Borchert wrote:
> Martin Gregorie wrote:
>> On Sat, 18 Feb 2017 08:06:17 +0000, Volker Borchert wrote:
>>
>>> Martin Gregorie wrote:
>>>> 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,
>>>
>> There's no reason why the key Long has to be separate: you can define
>> your own class to hold the long and a boolean and use the long's getter
>> method as the key reference.
>
> It'll still be an object separate from the TreeSet/TreeMap $Entry
> and have its own two word header and the reference from the $Entry.

     Although at first I thought you were more concerned with speed
than with size, it now appears memory consumption is important to
you also.  If that's the case, you might consider using long[] arrays
instead of Lists and Maps and Sets and so on.  Some possibilities:

     1) If you are Quite Certain that the intervals are disjoint, you
could simply stash the endpoints in a single long[], then sort them
with Arrays.sort(long[],int,int), and make a final pass to combine
adjacent intervals.

     2) If you don't need the entire range of `long' but have at least
one bit to spare, you can make (1) more robust by tagging each endpoint
with its position: `(lower << 1) | 0' and `(upper << 1) | 1'.  Sort as
in (1), but now the final pass can detect overlaps.

     3) Maintain two arrays `long[] lower' and `long[] upper', and stash
one end of each interval in each.  Sort both, then the final pass scans
over both arrays in lock-step.  If `lower[i] < upper[i-1]' an overlap
has been detected.

     All three approaches perform more sorting than would be necessary
with a List<Interval>: For N intervals, (1) and (2) must sort arrays
of 2N items, while (3) sorts two N-item arrays.  This might not be so
bad, though, because sorting primitives may well be faster than sorting
Intervals -- fewer polymorphic calls to compare() or compareTo(), better
locality, that sort of thing.  Also, it's easy to parallelize the two
sorts in (3) by running one of them in a background Thread.  You'd need
to measure (of course), but it's not a foregone conclusion that the time
penalty would be excessive.  Meanwhile, using about 16N bytes instead of
about 36N (for ArrayList<Interval>, depends on JVM, YMMV) might be a
worthwhile gain.

-- 
esosman@comcast-dot-net.invalid
Fourteen hundred thirty-one days to go.

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