Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #36315
| From | Martin Gregorie <martin@address-in-sig.invalid> |
|---|---|
| Newsgroups | comp.lang.java.programmer |
| Subject | Re: Wanted: List of intervals |
| Date | 2017-02-16 23:58 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <o85eag$uqr$1@dont-email.me> (permalink) |
| References | <o854lm$f4d$1@Gaia.teknon.de> |
On Thu, 16 Feb 2017 21:13:26 +0000, Volker Borchert wrote:
> 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).
>
Good KISS approach.
I wonder about a couple of things you may be able to find out before
going much further.
- how do you know that ArrayList.sort is O(log^2 n) when the method
description doesn't say what algorithm is used?
I've worked through the various sort algorithms in "Software Tools
in Pascal"(implemented in PL/9 and timed running on a 2MHz
6809 box some time ago). The in-memory sorts ranged from Bubble Sort
(n^2) to Quicksort (nlog n). However, I noticed during my tests that
quicksort has an unspoken assumption that comparison is cheaper than
exchanging misordered elements. As a result its blindingly fast if the
key is an int but exchanges involve copying the elements. However, if
comparisons are slow, e.g. lexigraphic comparison of multiple keys and
misordered element exchanges are fast , e.g. swapping pointers to
static elements, then the humble shell sort is quicker.
In Java I'd hope that a decent compiler would swap references to
misordered elements within the ArrayList to static elements in heap
storage, so a comparison of ArrayList.sort() vs a quicksort algorithm
could go either way.
- Just for giggles, have you tried replacing the ArrayList with a
self-ordering structure such as a TreeMap?
I know you thought about using a TtreeMap, but have you tried using
one and timing it? Don't forget that large red/black trees are quite
efficient at searching for a key because the search path is only
sqrt(n) deep, so just 23 comparisons are needed to find a key in a
tree containing 8 million items. 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.
The sources I'd use to find sort algorithms with example implementations
and performance analyses are "Algorithms" (Sedgewick), the aforementioned
"Software Tools in Pascal" and "Algorithms + Data Structures =
Programs" (Wirth) - all present their example implementations in Pascal,
but that is easy to transcribe directly into Java.
Sedgewick's Algorithms is an excellent book that belongs in any serious
programmer's library.
--
martin@ | Martin Gregorie
gregorie. | Essex, UK
org |
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