Re: Inserting In a List
On 4/2/2013 9:26 PM, Arne Vajh?j wrote:
On 4/2/2013 9:03 PM, Eric Sosman wrote:
On 4/2/2013 8:20 PM, Arne Vajh?j wrote:
On 4/2/2013 8:04 PM, 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 ? The cost is just distributed amongst the insert calls,
and is
likely considerably higher than with an unsorted list that has a single
sort call once it is filled.
It is not that obvious to me that:
n O(1) + 1 O(nlogn) is that much faster than n log(n)
By design, O() obscures all the coefficients. If you were
to say that n*log(n) and 9999999999999999999999999999*n*log(n)
are both O(n*log(n)) you would be right -- but if you were to
claim the former was not "that much faster" than the latter you
would be wrong by a factor of 9999999999999999999999999999.
Yes.
But given same big-O I would expect some solid reasons for a
big difference in coefficients before I assume a big difference
in performance.
... and that's the gist of my question: It seems to me likely
that the actual time to sort an ArrayList of large-ish N size will
be less than the time to build a TreeMap (BTW, Martin probably
meant TreeSet) of the same N items. Argument: The TreeSet expends
effort in keeping itself always sorted all the time, while the
ArrayList has the freedom to be disordered up until the end, and
then to impose an ordering just once. The ArrayList is asked to
present one sorted version of N items, while the TreeSet must
offer sorted versions of 1,2,3,...,N items. If the intermediate
orderings are not required, I don't see much reason to compute them.
I can follow you so far that TreeSort is likely a bit slower
than the ArrayList sort.
But I can not see any reason to expect a big difference.
It is fundamentally the same divide and conquer principle
applied.
The original assertion is "it would be *best* [emphasis mine]
to use a TreeMap<String> [sic] rather than an ArrayList<String>".
I'm not claiming that the difference is "big," nor even that the
difference is "important" -- for reasonably-sized directories, at
any rate. What I'm questioning is "best."
Also, I dispute "fundamentally the same." There is, I think,
a "fundamental" difference between a scheme that makes a sorted
traversal possible once at the end of things and a scheme that
promises such a traversal at every single intermediate stage.
The latter, it seems to me, necessarily does more work because it
adheres to a guarantee at points 1,2,...,N instead of at N only.
--
Eric Sosman
esosman@comcast-dot-net.invalid