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

Groups > comp.lang.java.programmer > #36310 > unrolled thread

Wanted: List of intervals

Back to article view | Back to comp.lang.java.programmer

Contents

  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

Page 2 of 2 — ← Prev page 1 [2]

#36327

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>

[toc] | [prev] | [next] | [standalone]

#36328

On Sat, 18 Feb 2017 08:06:17 +0000, Volker Borchert wrote:

> 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,
>
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.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#36329

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.

-- 

"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>

[toc] | [prev] | [next] | [standalone]

#36330

On Sat, 18 Feb 2017 19:58:59 +0000, 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.
(another 400KB 
Fair comment. T'would still be interesting to see how fast it is though.

This is not on your scale, I know, but the biggest TreeMaps I've used so 
far form the basis of a club duty rostering tool I've written which uses 
TreeMaps to organise its various lists: 
- members keyed by name
- roles to be rostered keyed by rolename
- duties to be filled, keyed by member name and date. 

This season its dealing with just under 100 members and 6700 duties sllit 
over six roles. Its a Swing tool. Running on a relatively slow machine 
(Thinkpad laptop running Fedora 25 on a Core Duo clocked at 1.6 GHz) 
there's a barely perceptible pause when switching between roles, each in 
a separate JFrame, but no noticeable delay while assigning and swapping 
duties within a role. Of course, start up takes 7-8 seconds because its 
reading in 400kB of data while setting up its internal structures and 
loading/saving work in progress (another 400 kB read/written) takes 1-2 
seconds.
 

-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#36342

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.

[toc] | [prev] | [next] | [standalone]

#36343

Eric Sosman <esosman@comcast-dot-net.invalid> wrote:
>      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, ...
>      1) If you are Quite Certain that the intervals are disjoint,

(Any "you"-references furtheron address the OP, not Eric)

Under this disjointness-assumption I'd create a SparseBigBitSet class:

It holds an array of BitSet of some (fine-tuneable) size BLOCK each.
The SparseBigBitSet will implement something like Set<Long> interface,
(except maybe for primitive long, rather than Long) and for each
offset l, l will be split into l/BLOCK and l%BLOCK, where l/BLOCK
will determine which BitSet to pick from main array (and on demand 
create it), while l%BLOCK will address the bit within the BitSet.
Due to signedness of int used within each BitSet and on the array,
you might only get close to virtual 2^62 bits of the total long range.
If that's a problem, split up the array into a cascade of arrays.
(the more levels of arrays you stack, the better will the "sparse-
feature" work.)

This will provide you with a giant virtual bitset, whose total
consumed heap-size will only roughly grow with actual 1-bits
saved in it.

For convenience, the SparseBigBitSet class should offer a 
toggle(long l) method, because that will be the most common
operation used on it.

When you read in the data from file, you toggle each offset in the
bit set.  Any offset that shows up twice (and thus disappears) was
a join-point of two adjacent intervals.

For reading out, BitSet has a method for finding next 1-bits, and
between the BitSets you can skip all null-entries in your array.
Iterating the 1-bits, then you get alternating interval starts 
and interval ends, already sorted!

[toc] | [prev] | [next] | [standalone]

#36323

On Thursday, 16 February 2017 22:02:57 UTC, Volker Borchert  wrote:

[...]
> If I can't find anything, I'll probably write a special mergesort

In that case, look at the Fork/Join framework. It can be really performing for parallel tasks. 

[toc] | [prev] | [next] | [standalone]

#36325

On 2/16/2017 4:13 PM, Volker Borchert wrote:
> Given:  a file containing an unordered list of disjoint but possibly
>         adjacent [long lower, long upper) intervals.
> Wanted: a list of such intervals, sorted by lower, with adjacent input
>         intervals concatenated
>
> The worst case input list size n is (current knowledge) a million.
>
> Currently, I just read them into an ArrayList, sort() it and finally
> concatenate. ("Make it work _first_ before you make it work _fast_.")
> Asymptotic time is dominated by sorting's O(n log n).

     You mention "a file" and "read," which suggests there's actual
I/O taking place.  If that's so, I suspect the running time will be
dominated by the input (16 MB if binary, ?? MB plus conversion time
if text), and that improving the post-input processing time will
have little effect on the overall situation.  The CPU can do a lot
of work in the time required for just one disk seek.

> Does anyone know of a suitable (i.e., asymptotic time O(n log n)
> or better, but less than 2n references) data structure that merges
> during insertion? Apache commons-collections TreeList is unordered
> thus requires binary search at O(log^2 n) for insert, and standard
> TreeSet seems to be expensive when looking for previous and next.

     If it turns out that the sort-and-combine phase does in fact take
an objectionable amount of time, you might try to overlap it with the
I/O: Even if the CPU consumption rises, the ability to consume it in
parallel with the I/O instead of after the I/O may be worth while.
Two plausible approaches occur to me:

     - Use a SortedMap<LowerBound,UpperBound>, adding and merging as
intervals arrive from the input.  You mention the CPU expense, but if
the CPU would otherwise simply be waiting for I/O, well, ...

     - Use a SortedSet<Interval>, just stuffing them in the way you now
do with ArrayList<Interval>, and make a combining pass afterward.  The
advantage is that the sorting overlaps the I/O, even though it's likely
more CPU-costly.

-- 
esosman@comcast-dot-net.invalid
One thousand four hundred thirty-three days to go.

[toc] | [prev] | [next] | [standalone]

#36390

On 16 Feb 2017 21:13:26 GMT, v_borchert@despammed.com (Volker
Borchert) wrote:

>
>Given:  a file containing an unordered list of disjoint but possibly
>        adjacent [long lower, long upper) intervals.
>Wanted: a list of such intervals, sorted by lower, with adjacent input
>        intervals concatenated

I would put them into an ArrayList and sort them. Oracle's sort is
impressively fast.

Now allocate a second arraylist the same size.

Copy the elements over one by one  If the ranges overlap, fix up the
last elt copied.

In my own language I could have a list of intervals in a switch. It
would be nice for Java.

[toc] | [prev] | [next] | [standalone]

#36393

Roedy Green wrote:
> On 16 Feb 2017 21:13:26 GMT, v_borchert@despammed.com (Volker Borchert) wrote:
> 
> >Given:  a file containing an unordered list of disjoint but possibly
> >        adjacent [long lower, long upper) intervals.
> >Wanted: a list of such intervals, sorted by lower, with adjacent input
> >        intervals concatenated
> 
> I would put them into an ArrayList and sort them. Oracle's sort is
> impressively fast.
> 
> Now allocate a second arraylist the same size.
> 
> Copy the elements over one by one  If the ranges overlap, fix up the
> last elt copied.

Was doing that, am doing that - replacing rather than fixing up
to have truly immutable value objects.

Was hoping to find a solution to avoid creating possibly large
numbers of adjacent intervals without slowing down. Lesson learnt.

OTOH. As somebody pointed out, file input will probably dominate.
Unless of course if from SSD or OS buffer cache.

Will be back if/when it bites me in the field.

> In my own language I could have a list of intervals in a switch. It
> would be nice for Java.

Imagine a world without thought experiments.

-- 

"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>

[toc] | [prev] | [next] | [standalone]

#36394

Volker Borchert <v_borchert@despammed.com> wrote:
> Was hoping to find a solution to avoid creating possibly large
> numbers of adjacent intervals without slowing down. Lesson learnt.

Just wondering if you actually noticed the suggestions about
large sparse Bitsets.

PS: No, they wouldn't require a final loop over all possible
   numbers - that's where the "sparse" kicks in.

[toc] | [prev] | [next] | [standalone]

#36400

Andreas Leitgeb wrote:
> Volker Borchert <v_borchert@despammed.com> wrote:
> > Was hoping to find a solution to avoid creating possibly large
> > numbers of adjacent intervals without slowing down. Lesson learnt.
> 
> Just wondering if you actually noticed the suggestions about
> large sparse Bitsets.

Yes. If I understood it correctly, it's somewhat similar to a "trie"?
Might consider it if current solution falls over. But then I'd start
with decoupling file I/O from data structure updates (lock-free single
linked queue or something like that) to make the former go as smoothly
as possible, following another upthread hint.

-- 

"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>

[toc] | [prev] | [next] | [standalone]

#36401

Volker Borchert <v_borchert@despammed.com> wrote:
> Andreas Leitgeb wrote:
>> Volker Borchert <v_borchert@despammed.com> wrote:
>> > Was hoping to find a solution to avoid creating possibly large
>> > numbers of adjacent intervals without slowing down. Lesson learnt.
>> Just wondering if you actually noticed the suggestions about
>> large sparse Bitsets.
> Yes. If I understood it correctly, it's somewhat similar to a "trie"?

In a way, yes.

The other nice aspect is, that by toggling duplicate entries, you get
merged intervals on insertion without extra effort.

[toc] | [prev] | [next] | [standalone]

#36402

Andreas Leitgeb wrote:
> Volker Borchert <v_borchert@despammed.com> wrote:
> > Andreas Leitgeb wrote:
> >> Volker Borchert <v_borchert@despammed.com> wrote:
> >> > Was hoping to find a solution to avoid creating possibly large
> >> > numbers of adjacent intervals without slowing down. Lesson learnt.
> >> Just wondering if you actually noticed the suggestions about
> >> large sparse Bitsets.
> > Yes. If I understood it correctly, it's somewhat similar to a "trie"?
> 
> In a way, yes.
> 
> The other nice aspect is, that by toggling duplicate entries, you get
> merged intervals on insertion without extra effort.

As I had noticed upthread:

>>> 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.

With your set, toggle() would do the "if (!remove()) add()"
efficiently.

-- 

"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>

[toc] | [prev] | [next] | [standalone]

#36403

Volker Borchert <v_borchert@despammed.com> wrote:
> Andreas Leitgeb wrote:
>> Volker Borchert <v_borchert@despammed.com> wrote:
>> > Yes. If I understood it correctly, it's somewhat similar to a "trie"?
>> In a way, yes.
>> The other nice aspect is, that by toggling duplicate entries, you get
>> merged intervals on insertion without extra effort.
> With your set, toggle() would do the "if (!remove()) add()"
> efficiently.

Yes, by not having to navigate the structure twice, each time...

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.java.programmer

csiph-web