Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Martin Gregorie Newsgroups: comp.lang.java.programmer Subject: Re: Wanted: List of intervals Date: Fri, 17 Feb 2017 12:10:27 -0000 (UTC) Organization: A noiseless patient Spider Lines: 40 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Injection-Date: Fri, 17 Feb 2017 12:10:27 -0000 (UTC) Injection-Info: mx02.eternal-september.org; posting-host="17406cb177b6f21e4110ccaccd13568c"; logging-data="5578"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+TRWRyEdhAi1hLPRZvTVa1lxVW8sZ3jQU=" User-Agent: Pan/0.141 (Tarzan's Death; 168b179 git.gnome.org/pan2) Cancel-Lock: sha1:uLvsmGHdm1bFbZDHFw/weHcKttA= Xref: csiph.com comp.lang.java.programmer:36324 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 |