How to sort a Set?
laredotornado
I have a Set of Strings for which I'd like to sort, so that when I
iterate over the set, I'm doing so in sorted order.
Hashtable<String,Hashtable<String,String>> apps = getApps();
java.util.Set<String> allowedApps = apps.keySet();
Iterator<String> i = allowedApps.iterator();
How can I sort the data? Thanks, - Dave
Mark Space
I'd use allowedApps.toArray( String[] ) and then sort the resulting
array. Look at java.util.Arrays.sort().
Roedy Green
<laredo...@zipmail.com> wrote, quoted or indirectly quoted someone
who said :
>How can I sort the data? Thanks, - Dave
hint. A Set as a flavour of Collection. You sort it like any
collection. See http://mindprod.com/jgloss/sort.html
--
Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com
Hendrik Maryns
Hash: SHA1
Mark Space schreef:
Why? What’s wrong with Collections.sort()?
H.
- --
Hendrik Maryns
http://tcl.sfs.uni-tuebingen.de/~hendrik/
==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (GNU/Linux)
Comment: Using GnuPG with SUSE - http://enigmail.mozdev.org
iEYEARECAAYFAkiHYBMACgkQBGFP0CTku6MlwwCgi9OPgyv7S3DB8oiDknH3ZUmE
sgYAn1YTpSHM1dLsIIe3mdoT9IhZL4kn
=9CZl
-----END PGP SIGNATURE-----
Mike Schilling
Youi could use a TreeMap instead of a Hashtable, and the iterator
would return the keys in sorted order automatically.
laredotornado
wrote:
> laredotornadowrote:
Is there a simple way to convert a Hashtable to a TreeMap? The code
that generated the Hashtable is not my own and I'm not free to change
it. - Dave
Lew
wrote:
One should avoid Hashtable unless one, a) needs synchronization and,
b) needs all that extra non-Collections cruft.
The performance characteristics of TreeMap might be suboptimal. If
the need for sorted access is sufficiently rare, or the underlying Map
changes sufficiently infrequently, one could use idioms along the
lines of
SortedMap <String, String> apps = new TreeMap <String, String>
( getApps() );
or
Map <String, String> apps = getApps();
SortedSet <Map.Entry <String, String>> sortedEntries =
new TreeSet <Map.Entry <String, String>> ( apps.entrySet() );
or
Map <String, String> apps = getApps();
SortedSet <String> sortedKeys = new TreeSet <String>
( apps.keySet() );
--
Lew
Mark Space
>
> Why? What’s wrong with Collections.sort()?
It sorts Lists, not Sets.
Roedy Green
<mark...@sbc.global.net> wrote, quoted or indirectly quoted someone
who said :
>>
>> Why? What’s wrong with Collections.sort()?
>
>It sorts Lists, not Sets.
Ouch, yes. Why then is it in Collections?
Roedy Green
<mark...@sbc.global.net> wrote, quoted or indirectly quoted someone
who said :
>It sorts Lists, not Sets.
Collections.sort and Collections.binarySearch should be deprecated and
replaced by Lists.sort and Lists.binarySearch.
Mark Space
> On Wed, 23 Jul 2008 10:59:15 -0700, Mark Space
> <mark...@sbc.global.net> wrote, quoted or indirectly quoted someone
> who said :
>
>>> Why? What’s wrong with Collections.sort()?
>> It sorts Lists, not Sets.
>
> Ouch, yes. Why then is it in Collections?
List is one type of Collection?
I was trying to reply to the OPs issue, which really concerned
Hashtables. That's what he has. There might be some more efficient way
of sorting the keys (?) in a Hashtable, I guess. I just presented what
I thought was the most obvious answer. The OP could nose around the
docs for the objects I mentioned, see if anything looked better, and do
some performance testing.
Or if performance doesn't matter, then just take the first solution that
presents itself. It's really dependent on parameters we don't have at
the moment.
Thomas Kellerer
Roedy Green wrote on 23.07.2008 21:14:
> On Wed, 23 Jul 2008 10:59:15 -0700, Mark Space
> <mark...@sbc.global.net> wrote, quoted or indirectly quoted someone
> who said :
>
>> It sorts Lists, not Sets.
>
> Collections.sort and Collections.binarySearch should be deprecated and
> replaced by Lists.sort and Lists.binarySearch.
There is no class named "Lists" in Java 5 nor Java 6 ...
http://java.sun.com/javase/6/docs/api/allclasses-noframe.html
Christian
> On Wed, 23 Jul 2008 10:59:15 -0700, Mark Space
> <mark...@sbc.global.net> wrote, quoted or indirectly quoted someone
> who said :
>
>> It sorts Lists, not Sets.
>
> Collections.sort and Collections.binarySearch should be deprecated and
> replaced by Lists.sort and Lists.binarySearch.
And List is part of the Collections framework .. as this Collections is
a nice name to contain all static methods for the Collections framework.
I see no need for a deprecation as the naming seems to be intuitive and
practical.
Christian
John W Kennedy
> On Wed, 23 Jul 2008 10:59:15 -0700, Mark Space
> <mark...@sbc.global.net> wrote, quoted or indirectly quoted someone
> who said :
>
>>> Why? What’s wrong with Collections.sort()?
>> It sorts Lists, not Sets.
>
> Ouch, yes. Why then is it in Collections?
On the one hand, Lists are collections. On the other hand, HashSets
cannot be sorted, and TreeSets already are. In order to sort a Set,
therefore, you /must/ create a List (or an Array) and then sort it. It's
not a software restriction; it's a basic logical consequence of what a
Set /is/.
--
John W. Kennedy
"The poor have sometimes objected to being governed badly; the rich
have always objected to being governed at all."
-- G. K. Chesterton. "The Man Who Was Thursday"
Christian
> Roedy Green wrote:
>> On Wed, 23 Jul 2008 10:59:15 -0700, Mark Space
>> <mark...@sbc.global.net> wrote, quoted or indirectly quoted someone
>> who said :
>>
>>>> Why? What’s wrong with Collections.sort()?
>>> It sorts Lists, not Sets.
>>
>> Ouch, yes. Why then is it in Collections?
>
> On the one hand, Lists are collections. On the other hand, HashSets
> cannot be sorted, and TreeSets already are. In order to sort a Set,
> therefore, you /must/ create a List (or an Array) and then sort it. It's
> not a software restriction; it's a basic logical consequence of what a
> Set /is/.
>
>
or implement a set based on ArrayList.. (CopyOnWriteArrayList has
already the addIfAbsent Method implemented which you need)
its a basic logical consequence of what a HashMap is.
If you would want to define also an Order it would be a size overhead ...
as you can't just use your array holding the elements for hashbuckets
that induce some sort of order ... and also a self defined order..
So it is a software restriction.
Lew
> Is there a simple way to convert a Hashtable to a TreeMap?
<http://java.sun.com/javase/6/docs/api/java/util/Map.html#putAll(java.util.Map)>
> The code that generated the Hashtable is not my own
> and I'm not free to change it.
Are there synchronization issues?
Hashtable has been replaced by cleaner alternatives since about 1998.
--
Lew
John W Kennedy
> John W Kennedy schrieb:
>> Roedy Green wrote:
>>> On Wed, 23 Jul 2008 10:59:15 -0700, Mark Space
>>> <mark...@sbc.global.net> wrote, quoted or indirectly quoted someone
>>> who said :
>>>
>>>>> Why? What’s wrong with Collections.sort()?
>>>> It sorts Lists, not Sets.
>>>
>>> Ouch, yes. Why then is it in Collections?
>>
>> On the one hand, Lists are collections. On the other hand, HashSets
>> cannot be sorted, and TreeSets already are. In order to sort a Set,
>> therefore, you /must/ create a List (or an Array) and then sort it.
>> It's not a software restriction; it's a basic logical consequence of
>> what a Set /is/.
>>
>>
> not really .. you coulkd define a Order on a set..
...which TreeSet already is.
> or implement a set based on ArrayList.. (CopyOnWriteArrayList has
> already the addIfAbsent Method implemented which you need)
Have you actually read the documentation for CopyOnWriteArrayList?
Very well. I misspoke. I should have said "it's a basic logical
consequence of what a Set is when implemented by someone sane enough not
to do it in O(n^2)."
--
John W. Kennedy
If Bill Gates believes in "intelligent design", why can't he apply it
to Windows?
Christian
you could for example without to large overhead do a set with a order by
simply holding 2 arrays in the class.. one for the hashbuckets and one
for the order ...
Other way would be to introduce a next pointer in the Entry objects that
points to the next Object in order
there is really no reason what so ever for an ordered set to perform
asymptotically worse then the normal hashset..
Actually Java already has such a Set that does this called LinkedHashSet.
Christian
Roedy Green
<jwk...@attglobal.net> wrote, quoted or indirectly quoted someone who
said :
>On the one hand, Lists are collections. On the other hand, HashSets
>cannot be sorted, and TreeSets already are. In order to sort a Set,
>therefore, you /must/ create a List (or an Array) and then sort it. It's
>not a software restriction; it's a basic logical consequence of what a
>Set /is/.
My complaint is not that you can't order a Collection, but that sort
is part of the Collections class. There should have been a Lists
class created to hold sort and binarySearch.
Roedy Green
<FJIFAL...@spammotel.com> wrote, quoted or indirectly quoted
someone who said :
>> Collections.sort and Collections.binarySearch should be deprecated and
>> replaced by Lists.sort and Lists.binarySearch.
>
>There is no class named "Lists" in Java 5 nor Java 6 ...
Exactly. That was Sun's error that should be corrected.
Lasse Reichstein Nielsen
> you could for example without to large overhead do a set with a order
> by simply holding 2 arrays in the class.. one for the hashbuckets and
> one for the order ...
No, that would require a significant overhead whenever you update
the contents of the set. The order needs updating.
Keeping an ordered array in order during insertion requires linear
time per insert - for inserting in the middle of the array.
> Other way would be to introduce a next pointer in the Entry objects
> that points to the next Object in order
Keeping an ordered linked list in order during insertion requires
linear time per insert - for finding the position to insert at.
> there is really no reason what so ever for an ordered set to perform
> asymptotically worse then the normal hashset..
For insertions, yes there is. If not, you could do sorting in linear
time by inserting the elements into a "ordered hash set", and extracting
them again. That's theoretically impossible, as comparison based sorting
requires at least O(n*log(n)) comparisons.
> Actually Java already has such a Set that does this called LinkedHashSet.
That set retains insertion order, not any logical order.
/L
--
Lasse Reichstein Nielsen
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Christian
> Christian <fake...@xyz.de> writes:
>
>> you could for example without to large overhead do a set with a order
>> by simply holding 2 arrays in the class.. one for the hashbuckets and
>> one for the order ...
>
> No, that would require a significant overhead whenever you update
> the contents of the set. The order needs updating.
>
> Keeping an ordered array in order during insertion requires linear
> time per insert - for inserting in the middle of the array.
>
>> Other way would be to introduce a next pointer in the Entry objects
>> that points to the next Object in order
>
> Keeping an ordered linked list in order during insertion requires
> linear time per insert - for finding the position to insert at.
so we don't do a linked list to connect the elements but rather a
randomised skip list .. so we can get insertion down to log n
>
>> there is really no reason what so ever for an ordered set to perform
>> asymptotically worse then the normal hashset..
>
> For insertions, yes there is. If not, you could do sorting in linear
> time by inserting the elements into a "ordered hash set", and extracting
> them again. That's theoretically impossible, as comparison based sorting
> requires at least O(n*log(n)) comparisons.
ok you have apoint the ordering forces us at least log n for the
insertion .. but not more ..
so ok asymptotically a bit worse. Though not much.
Christian
> On Wed, 23 Jul 2008 21:33:03 +0200, Thomas Kellerer
> <FJIFAL...@spammotel.com> wrote, quoted or indirectly quoted
> someone who said :
>
>>> Collections.sort and Collections.binarySearch should be deprecated and
>>> replaced by Lists.sort and Lists.binarySearch.
>> There is no class named "Lists" in Java 5 nor Java 6 ...
>
> Exactly. That was Sun's error that should be corrected.
>
Why?
imho Collections doesn't stand for operations on the interface Collection
But for operations on the Collections framework. And Lists interface is
part of this.
Lasse Reichstein Nielsen
> so we don't do a linked list to connect the elements but rather a
> randomised skip list .. so we can get insertion down to log n
And then you might as well use a TreeSet to begin with.
The red/black search tree used by TreeSet is typically more efficient
than a skip-list (same complexity, lower constant).
> ok you have apoint the ordering forces us at least log n for the
> insertion .. but not more ..
> so ok asymptotically a bit worse. Though not much.
Indeed. IF you have is a pair of sets, one HashSet, the other an
ordered TreeSet, that contain the same elements, then:
- Any modification must be performed on both. I.e., O(nlog(n))
- Lookups can be performed on the faster one (the HashSet). O(1)
- Iteration would have to be done on the ordered set, but calls to
"remove" would remove from both sets.
All this at the price of extra complexity, and a larger constant
factor. Depending on the size of the set, and the operations performed,
it might be better to just use a TreeSet.
Hendrik Maryns
Hash: SHA1
Lasse Reichstein Nielsen schreef:
| Christian <fake...@xyz.de> writes:
|
|> so we don't do a linked list to connect the elements but rather a
|> randomised skip list .. so we can get insertion down to log n
|
| And then you might as well use a TreeSet to begin with.
|
| The red/black search tree used by TreeSet is typically more efficient
| than a skip-list (same complexity, lower constant).
|
|> ok you have apoint the ordering forces us at least log n for the
|> insertion .. but not more ..
|> so ok asymptotically a bit worse. Though not much.
|
| Indeed. IF you have is a pair of sets, one HashSet, the other an
| ordered TreeSet, that contain the same elements, then:
| - Any modification must be performed on both. I.e., O(nlog(n))
Shouldn’t that be O(log(n) + 1)? Log(n) for the TreeSet, 1 for the
HashSet, no nested looping involved, as far as I can see.
| - Lookups can be performed on the faster one (the HashSet). O(1)
|
| - Iteration would have to be done on the ordered set, but calls to
| "remove" would remove from both sets.
|
| All this at the price of extra complexity, and a larger constant
| factor. Depending on the size of the set, and the operations performed,
| it might be better to just use a TreeSet.
Yes. Only in extreme cases would the difference between O(log(n)) and
O(1) matter.
H.
- --
Hendrik Maryns
http://tcl.sfs.uni-tuebingen.de/~hendrik/
==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (GNU/Linux)
Comment: Using GnuPG with SUSE - http://enigmail.mozdev.org
iEYEARECAAYFAkiIbQUACgkQBGFP0CTku6PADACgrGO7AvNGsNqSW1Fe+CYNoZgu
l7sAn3VkabeLRWOYSYSVnclbdPPHUsB4
=RtZ4
-----END PGP SIGNATURE-----
Patricia Shanahan
...
> Shouldn’t that be O(log(n) + 1)? Log(n) for the TreeSet, 1 for the
> HashSet, no nested looping involved, as far as I can see.
If f(n) is O(log(n)+1) it is also O(log(n)).
Patricia
Patricia Shanahan
> On Wed, 23 Jul 2008 15:47:55 -0400, John W Kennedy
> <jwk...@attglobal.net> wrote, quoted or indirectly quoted someone who
> said :
>
>> On the one hand, Lists are collections. On the other hand, HashSets
>> cannot be sorted, and TreeSets already are. In order to sort a Set,
>> therefore, you /must/ create a List (or an Array) and then sort it. It's
>> not a software restriction; it's a basic logical consequence of what a
>> Set /is/.
>
> My complaint is not that you can't order a Collection, but that sort
> is part of the Collections class. There should have been a Lists
> class created to hold sort and binarySearch.
Do you think Arrays should be split in to ArraysOfObject etc.? There are
methods in Arrays that cannot be applied to every array.
How is that different from having methods in Collections that cannot be
applied to every object whose class in the collection hierarchy?
Patricia
Lasse Reichstein Nielsen
> Shouldn’t that be O(log(n) + 1)? Log(n) for the TreeSet, 1 for the
> HashSet, no nested looping involved, as far as I can see.
Yes, my mistake. O(nlog(n)) is the complexity of adding n elements.
I was probably still thinking about the sorting argument.
Mark Space
>> not really .. you coulkd define a Order on a set..
>
> ...which TreeSet already is.
>
Yup, and the interface for a TreeSet is called a SortedSet, so they are
supported by the API. Just be aware that there is overhead inserting
and searching when using SortedSet (and TreeSet) that Map
implementations like HashMap typically don't incur.
Also, for small sets, EnumSet is efficient and sorted by default, with
little overhead, if you can define the members of the set at compilation.
Roedy Green
wrote, quoted or indirectly quoted someone who said :
>Do you think Arrays should be split in to ArraysOfObject etc.? There are
>methods in Arrays that cannot be applied to every array.
>
>How is that different from having methods in Collections that cannot be
>applied to every object whose class in the collection hierarchy?
the methods in Array are all at least conceptually applicable to
arrays.
The sort and binarySearch methods are not even conceptually applicable
to Collections. I have tripped over that many times. Collections
don't have an order to sort.
Roedy Green
quoted or indirectly quoted someone who said :
>
>Why?
>imho Collections doesn't stand for operations on the interface Collection
>But for operations on the Collections framework. And Lists interface is
> part of this.
I find it confusing having so many List methods dumped into
Collections. If they had been put into their own Lists class, it would
make the code clearer. Have not you been nailed at least more than
once trying to use these methods on a Collection?
binarySearch
checkedList
fill
replaceAll
sort
synchronizedList
unmodifiableList
indexOfSubList
lastIndexOfSubList
reverse
rotate
shuffle
swap
when you make that error, it is a non-trivial problem to fix.
Lew
> I find it confusing having so many List methods dumped into
> Collections. If they had been put into their own Lists class, it would
> make the code clearer. Have not you been nailed at least more than
> once trying to use these methods on a Collection?
>
> binarySearch
> checkedList
> fill
> replaceAll
> sort
> synchronizedList
> unmodifiableList
> indexOfSubList
> lastIndexOfSubList
> reverse
> rotate
> shuffle
> swap
>
> when you make that error, it is a non-trivial problem to fix.
I've used some of these methods and never been tempted to use them on
a type not documented in the Javadocs. The ones with "List" in their
name seem particularly immune to that type of misuse.
I guess I've just been lucky so far.
--
Lew
John W Kennedy
Either a set is ordered or it isn't. If it is ordered, it does not need
to be sorted into its own sequence, and it cannot be sorted into another
sequence. If it is unordered, then to implement it with decent
performance, it must be hashed. If it is hashed, then it cannot be
sorted without destroying the hash. Any which way, you have to make a
copy to sort, and the sane way to make that copy is an Array or ArrayList.
--
John W. Kennedy
"The first effect of not believing in God is to believe in anything...."
-- Emile Cammaerts, "The Laughing Prophet"
John W Kennedy
...especially since the whole collection of collections is riddled with
"not always available" methods, for sensible reasons.
--
John W. Kennedy
"But now is a new thing which is very old--
that the rich make themselves richer and not poorer,
which is the true Gospel, for the poor's sake."
-- Charles Williams. "Judgement at Chelmsford"
Lew
> On Thu, 24 Jul 2008 07:35:08 -0700, Patricia Shanahan <pa...@acm.org>
> wrote, quoted or indirectly quoted someone who said :
>
>> Do you think Arrays should be split in to ArraysOfObject etc.? There are
>> methods in Arrays that cannot be applied to every array.
>>
>> How is that different from having methods in Collections that cannot be
>> applied to every object whose class in the collection hierarchy?
>
> the methods in Array are all at least conceptually applicable to
> arrays.
>
> The sort and binarySearch methods are not even conceptually applicable
> to Collections. I have tripped over that many times. Collections
> don't have an order to sort.
The chances of Java changing to accomodate your particular complaint in this
matter are negligible.
There are often posts of the nature of, "I don't like <some feature of Java>.
It shouldn't be like that!" Clearly the language cannot accomodate every
single such complaint. The triage involved would most likely come down hard
against arbitrary changes to current viable solutions with perfectly workable
semantics. If they were going to do something to "fix" so well-established
and widely-used a class as Collections, they'd be better served fixing the
problems with other classes, say, java.util.Date. Only that ain't gonna
happen either.
Ultimately you're just peeved at the name of the class. If they'd called it
java.util.MiscUtils you'd have no case instead of a flimsy one. I bet they
would have argued against having multiple utility classes for every picayune
distinction - that'd be the source of whining from some other camp.
I guess we just have to abandon the "I wanna Lists class" plaint and
concentrate on suggestions that help us use the language as it actually is, in
reality, usefully today, or change it in important and actually beneficial
ways instead of just petty rearrangements of the deck chairs.
--
Lew
Daniel Pitts
> Hi,
>
> I have a Set of Strings for which I'd like to sort, so that when I
> iterate over the set, I'm doing so in sorted order.
>
> Hashtable<String,Hashtable<String,String>> apps = getApps();
> java.util.Set<String> allowedApps = apps.keySet();
> Iterator<String> i = allowedApps.iterator();
>
> How can I sort the data? Thanks, - Dave
Pedantic: Don't use Hashtable, use HashMap instead
Sets/Maps aren't all orderable. To get a sorted order, you need to
either use a SortedSet/SortedMap (such as TreeSet/TreeMap), or copy the
set into a List, and then sort that list.
--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
Daniel Pitts
> laredotornado wrote:
>> Hi,
>>
>> I have a Set of Strings for which I'd like to sort, so that when I
>> iterate over the set, I'm doing so in sorted order.
>>
>> Hashtable<String,Hashtable<String,String>> apps = getApps();
>> java.util.Set<String> allowedApps = apps.keySet();
>> Iterator<String> i = allowedApps.iterator();
>>
>> How can I sort the data? Thanks, - Dave
>
> array. Look at java.util.Arrays.sort().
>
>
I'd avoid Array, and use
List<String> sortedApps = new ArrayList<String>(allowedApps)
Collections.sort(sortedApps);
*or*
I'd use
SortedSet<String> sortedApps = new TreeSet<String>(allowedApps);
Daniel Pitts
> On Jul 23, 11:05 am, "Mike Schilling" <mscottschill...@hotmail.com>
> wrote:
>> laredotornadowrote:
>>> Hi,
>>> I have a Set of Strings for which I'd like to sort, so that when I
>>> iterate over the set, I'm doing so in sorted order.
>>> Hashtable<String,Hashtable<String,String>> apps = getApps();
>>> java.util.Set<String> allowedApps = apps.keySet();
>>> Iterator<String> i = allowedApps.iterator();
>>> How can I sort the data? Thanks, - Dave
>> would return the keys in sorted order automatically.
>
> Is there a simple way to convert a Hashtable to a TreeMap? The code
> that generated the Hashtable is not my own and I'm not free to change
Yes.
SortedMap<String, Map<String, String>> sorted =
new TreeMap<String, Map<String, String>>(apps);