Path: csiph.com!news.swapon.de!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Martin Gregorie <martin@address-in-sig.invalid>
Newsgroups: comp.lang.java.programmer
Subject: Re: A third easy performance optimisation needed
Date: Thu, 13 Jul 2017 11:27:09 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 30
Message-ID: <ok7led$ngc$1@dont-email.me>
References: <87d1946ab3.fsf@munus.decebal.nl>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 13 Jul 2017 11:27:09 -0000 (UTC)
Injection-Info: mx02.eternal-september.org; posting-host="a030be9b927e55fdbc797641d56ce0cb"; logging-data="24076"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+CTWmQW9hWQJ5ro6YboZXDhtXXX2wxfa8="
User-Agent: Pan/0.141 (Tarzan's Death; 168b179 git.gnome.org/pan2)
Cancel-Lock: sha1:LgqVkIeNtxtNOjOkNZ3hF961dTU=
Xref: csiph.com comp.lang.java.programmer:36880

On Thu, 13 Jul 2017 09:54:56 +0200, Cecil Westerhof wrote:

> I am going to give a presentation about how to easily improve the
> performance of your Java programs. Two subjects I already have are using
> final and being careful with autoboxing. I would like a third one.
> Anyone a good suggestion?

If you need both keyed random access and sequential access to a medium to 
large collection of objects, use a TreeMap rather than loading the data 
into flat structure (ArrayList) and sorting it because:

- a TreeMap efficiently inserts objects in key sequence

- walking a TreeMap is quite an efficient way of visiting objects 
  in key sequence

- keyed retrieval becomes progressively more efficient as the collection
  size grows. If the collection contains 2^n items, you only need n key
  comparisons to find a given key, so 4 comparisons if the tree holds 16
  items but only 23 comparisons if it holds 8 million items.
    
This is because TreeMap is implemented as a red-black binary tree. This 
is a self-balancing tree structure. See Sedgewick: "Algorithms" for a 
discussion of how it works.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |