Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #36324
| From | Martin Gregorie <martin@address-in-sig.invalid> |
|---|---|
| Newsgroups | comp.lang.java.programmer |
| Subject | Re: Wanted: List of intervals |
| Date | 2017-02-17 12:10 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <o86p7j$5ea$1@dont-email.me> (permalink) |
| References | <o854lm$f4d$1@Gaia.teknon.de> <o85eag$uqr$1@dont-email.me> <o85qo5$kpr$1@Gaia.teknon.de> |
On Fri, 17 Feb 2017 03:30:13 +0000, Volker Borchert wrote: > Shouldn't that be log(n)? sqrt(8000000) is about 2800... > Yes. Its been a while (1999): I translated the red-black tree code in Sedgewick's "Algorithms" into C and implemented it initially on an Alphaserver. It ran successfully pretty much straight away. There were about 100 million items in the tree. Keys were numeric strings averaging 10 chars long and we were managing 25,000 - 30,000 lookups/sec. Misses were added to the tree as they ocurred. This used my own code due to features of DEC Unix, which had a Mach-based micro-kernel. The library red-black tree code ran like a dog with a wooden leg, never exceeding around 1200 lookups/sec because it held the tree structure pointers, user data and key separately, so it needed 3 mallocs for each node stored. The Mach kernel serialised user process memory management because there was only a single copy of the memory management code. So, I implemented my own memory management (grabbed a 1MB chunk. Subsequent requests doubled in size until the chunks hit 16MB), which gave us the speedup we needed by minimising memory management calls by a very large factor: evidently the default heap extension size was relatively small for this strategy to work as well as it did. >> 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. -- 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