Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!weretis.net!feeder1.news.weretis.net!news.albasani.net!.POSTED!not-for-mail From: Jan Burse Newsgroups: comp.lang.java.programmer Subject: Re: setSize ArrayList, when will it come? Date: Thu, 11 Aug 2011 01:47:04 +0200 Organization: albasani.net Lines: 58 Message-ID: References: <9aetckFmvmU1@mid.individual.net> <9aftbqFa9kU1@mid.individual.net> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Trace: news.albasani.net WoD7pIOxf2Mnot6BchbeaAVlMA2WLYx2dkVQI3EdJXuQ1xqwvyf4BTns63X14IkCW0yZK7aWvFsDqZ0SLg73hw== NNTP-Posting-Date: Wed, 10 Aug 2011 23:47:08 +0000 (UTC) Injection-Info: news.albasani.net; logging-data="OwBbqy8CtVBVYI3T61+Z6NzVlrkyBCfvrV4g3R9DtXt1eQiCoc2XgB33o1e4rLFER5fQXrSvbDQXkecIxRwSha6Y158XsUO0D0xw4iuGQkhOkB41eNGdd3bUgVfWn2+O"; mail-complaints-to="abuse@albasani.net" User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:5.0) Gecko/20110706 Firefox/5.0 SeaMonkey/2.2 In-Reply-To: Cancel-Lock: sha1:yOWg1LcfCs1kKxYVvdjkwU4hzyU= Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:6998 Andreas Leitgeb schrieb: > 1.) a good estimate on what size you'll end up using, and > create the ArrayList with that size. Eating up a few > kilobytes (or even up to a megabyte) of nulls too much > is probably still greener than re-allocating the buffer > each time a new largest-so-far index shows up. If the > original estimation turns out to be too small, then grow > it with addAll(...nCopies(...)) - it wouldn't be done > all that often, so the extra effort wouldn't matter. > 2.) if no such limit can be reasonably predicted, then > chances are that a real sparse structure really fits > the bill better. (I didn't quite understand your argument > against using a Map - it didn't make sense to me when you > wrote it) I never placed an argument against map. Where was this? Just assume that the original code had setSize() for whatever reason, and that the redesign of the original code is not at stake. But you are right, a redesign could of course be an option. > The ideal (semi-)sparse structure wouldn't even need a setSize(), > as it would grow the internal buffer as needed to allow .set() to > work with any (non-negative) index, and let .get() just return null > for indices beyond the current end instead of throwing > IndexOutOfBounds-Exceptions. Actually in the current application the Vector/ArrayList need not necessarely be sparse. It could be, but it does not have to be, both scenarios should possible coexist, sparse and non-sparse. The current application has a high frequency of creating for an initially Vector/ArrayList of size 0. Then upon some event (imagine also high frequency) the size might jump to n, and the element at position n-1 is set to non null. And then upon some other event the size might jump to m, and the element at position m-1 is set to non null. But there is no guarantee that n and m are close. Also it can happen that an event j arrives, and the element at position j is set to non null, j being somewhere between 0 and m-1. So that the array might become gradually less sparse. Imagine the above process to last a very short time, until the livecycle of the array ends. Before the livecycle ends, the array might contain up to 100 or more non-null positions. But there is no guarantee that they are close together or not. But when there are 100 entries their indexes might span the range of 1000. But it is very important that the access to the elements is O(1). The sparseness is only mentioned in the oracle bug. But actually I think the sparseness is irrelevant. Just assume you have an existing application with Vector that happily uses setSize(). So what do you do? Bye