Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #36325
| From | Eric Sosman <esosman@comcast-dot-net.invalid> |
|---|---|
| Newsgroups | comp.lang.java.programmer |
| Subject | Re: Wanted: List of intervals |
| Date | 2017-02-17 08:20 -0500 |
| Organization | A noiseless patient Spider |
| Message-ID | <o86t7j$s4l$1@dont-email.me> (permalink) |
| References | <o854lm$f4d$1@Gaia.teknon.de> |
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.
Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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