Path: csiph.com!usenet.pasdenom.info!gegeweb.org!de-l.enfer-du-nord.net!feeder2.enfer-du-nord.net!feeds.phibee-telecom.net!usenet.ukfsn.org!not-for-mail
From: Martin Gregorie <martin@address-in-sig.invalid>
Newsgroups: comp.lang.java.programmer
Subject: Re: Inserting In a List
Date: Thu, 4 Apr 2013 00:42:43 +0000 (UTC)
Organization: UK Free Software Network
Lines: 76
Message-ID: <kjiia3$9nj$5@localhost.localdomain>
References: <d4ecae37-89d4-4747-a8ae-aea86fbbecf2@googlegroups.com> <myList-20130402133907@ram.dialup.fu-berlin.de> <ZKz6t.393788$kp4.308027@newsfe09.iad> <kjfh97$i51$3@localhost.localdomain> <kjfljm$fej$1@dont-email.me> <kjfnf3$k7l$1@localhost.localdomain> <1vzadyb0cgq7k.rsclf5bucb9k$.dlg@40tude.net> <kjibb7$9nj$3@localhost.localdomain> <qn8nxbe8ddqw.as3lqwtl6ezx$.dlg@40tude.net>
NNTP-Posting-Host: 84.45.235.129
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
X-Trace: localhost.localdomain 1365036163 9971 84.45.235.129 (4 Apr 2013 00:42:43 GMT)
X-Complaints-To: usenet@localhost.localdomain
NNTP-Posting-Date: Thu, 4 Apr 2013 00:42:43 +0000 (UTC)
User-Agent: Pan/0.139 (Sexual Chocolate; GIT bf56508 git://git.gnome.org/pan2)
Xref: csiph.com comp.lang.java.programmer:23260

On Thu, 04 Apr 2013 01:08:15 +0200, Joerg Meier wrote:

> On Wed, 3 Apr 2013 22:43:51 +0000 (UTC), Martin Gregorie wrote:
> 
>> On Wed, 03 Apr 2013 02:04:19 +0200, Joerg Meier wrote:
>>> On Tue, 2 Apr 2013 22:52:20 +0000 (UTC), Martin Gregorie wrote:
>>>> On Tue, 02 Apr 2013 18:22:55 -0400, Eric Sosman wrote:
>>>>> On 4/2/2013 5:06 PM, Martin Gregorie wrote:
>>>>>>[...]
>>>>>> Its also not clear to me whether the OP is expecting some form of
>>>>>> sorted list of filenames. If he is expecting that, it would be best
>>>>>> to use a TreeMap<String> rather than an ArrayList<String> to store
>>>>>> the filenames.
>>>>>      Is there a reason to prefer TreeMap (or other SortedMap) over
>>>>> accumulate-disordered-and-sort-afterward?
>>>> I think so, yes, because none of File's list() and listFiles()
>>>> methods guarantee the order of the returned files. By using TreeMap
>>>> or equivalent the OP gets the sort for free, should it be required.
>>> For free ?
>> I meant in terms of coding effort.
> 
> In terms of coding effort, it's one single line.
>
Fair enough - unless, of course a new coder tries to sort the ArrayList 
rather than using one of the standard SortedMaps. I note that there are 
only two and that, while ConcurrentSkipListMap is obviously faster than 
TreeMap for insert/amend/delete operations it would seem to be much 
slower at producing ordered lists.

> A TreeMap has a higher access cost than an ArrayList. It's O(log(n)) for
> both get and put, whereas ArrayList's is O(1).
>
For individual items that's true, but if the list is being updated, even 
at a low rate, then ordered access will need to at least check for out of 
order data before anything gets retrieved. Thats an overhead that any 
structure that preserves order through updates doesn't have.

> Not really. Since you want access by key, it makes no sense to use an
> ArrayList at all.
>
Which is where I came in: the OP had said that he wanted to get a String 
containing a list of filenames that he represented as 

"filename1,filename2,filename3,...." 

which at least suggests that the filenames should be ordered. 

That is why I suggested that if that's what he wanted he should be using 
a TreeMap rather than an ArrayList.

 > a TreeMap would indeed be superiour to storing logical map data in an
> ArrayList - I'm not even sure how you would fit both key and value into
> an ArrayList. Was your alternative to using a Map to make a patchwork
> Entry class to put keys and values in, and then make an ArrayList of
> those ?
> 
I didn't suggest any alternative and never intended to, but you can see 
somebody throwing the list of filenames into an ArrayList and then 
running a bubble sort against the array. Ugly, I know, and bubble sorts 
are horridly inefficient, but there's very little code in one. More to 
the point, this would be a very natural approach for anybody coming from 
a high level language background, e.g. Python, Perl, C, BASIC, PL/1, 
COBOL,... doing exactly this.
 
> Because if it was, I can think of plenty more scenarios that would be
> worse than storing things in a TreeMap. Storing them in a String, for
> example. But just because Strings suck to store map data in doesn't mean
> everyone who wants to store map data should therefore use a TreeMap.
> 
Indeed.


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