Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #36322
| From | v_borchert@despammed.com (Volker Borchert) |
|---|---|
| Newsgroups | comp.lang.java.programmer |
| Subject | Re: Wanted: List of intervals |
| Date | 2017-02-17 03:30 +0000 |
| Organization | Private site at Eddersheim, Germany |
| Message-ID | <o85qo5$kpr$1@Gaia.teknon.de> (permalink) |
| References | <o854lm$f4d$1@Gaia.teknon.de> <o85eag$uqr$1@dont-email.me> |
Martin Gregorie wrote: > - how do you know that ArrayList.sort is O(log^2 n) It's O(n log n), not O(log^2 n). > when the method > description doesn't say what algorithm is used? It's either mergesort or TimSort which should be better on arrays containing "runs" of elements in either ascending or descending order. Anyway, asymptotic worst case can't be much better. > The in-memory sorts ranged from Bubble Sort > (n^2) to Quicksort (nlog n). Quicksort is O(n log n) only on average, worst case is O(n^2) e.g. for input data that is sorted the wrong way. And it is not stable, but that is not a problem in my case. On the other hand, it does not need extra memory. So I might even consider it. > I know you thought about using a TreeMap, 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. Shouldn't that be log(n)? sqrt(8000000) is about 2800... > 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. -- "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
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