I have a String[] with values like so:
public static final String[] VALUES = new String[] {"AB","BC","CD","AE"};
Given String s, is there a good way of testing whether VALUES contains s?
views:
13619answers:
7+1 Beat me to it!
Cuga
2009-07-15 00:05:15
I am somewhat curious as to the performance of this versus the searching functions in the Arrays class versus iterating over an array and using an equals() function or == for primitives.
Thomas Owens
2009-07-15 00:06:07
Thanks! Very quick on the draw!
Mike Sickler
2009-07-15 00:06:55
They would both be a linear search.
Steve Kuo
2009-07-15 00:07:56
@Thomas: I think that asList() might actually allocate a new object that delegates to the existing array, so you are paying the allocation cost. The list is backed by the array so the elements themselves shoudln't be reallocated.
Uri
2009-07-15 00:09:05
You don't lose much, as asList() returns an ArrayList which has an array at its heart. The constructor will just change a reference so that's not much work to be done there. And contains()/indexOf() will iterate and use equals(). For primitives you should be better off coding it yourself, though. For Strings or other classes, the difference will not be noticeable.
Joey
2009-07-15 00:09:07
The `Array.asList` method is very fast for arrays of primitives. ;)
Tom Hawtin - tackline
2009-07-15 01:05:34
+5
A:
You can use the Arrays class to perform a binary search for the value. If your array is not sorted, you will have to use the sort functions in the same class to sort the array, then search through it.
Thomas Owens
2009-07-15 00:05:00
You can use the sort functions in the same class to accomplish that...I should add that to my answer.
Thomas Owens
2009-07-15 00:06:44
Will probably cost more than the asList().contains() approach, then, I think. Unless you need to do that check very often (but if it's just a static list of values that can be sorted to begin with, to be fair).
Joey
2009-07-15 00:10:56
True. There are a lot of variables as to which would be the most effective. It's good to have options though.
Thomas Owens
2009-07-15 00:13:48
+8
A:
If the array is not sorted, you will have to iterate over everything and make a call to equals on each.
If the array is sorted, you can do a binary search, there's one in the Arrays class.
Generally speaking, if you are going to do a lot of membership checks, you may want to store everything in a Set, not in an array.
Uri
2009-07-15 00:05:48
Also, like I said in my answer, if you use the Arrays class, you can sort the array then perform the binary search on the newly sorted array.
Thomas Owens
2009-07-15 00:10:39
@Thomas: I agree. Or you can just add everything into a TreeSet; same complexity. I would use the Arrays if it doesn't change (maybe save a little bit of memory locality since the references are located contiguously though the strings aren't). I would use the set if this would change over time.
Uri
2009-07-15 00:14:59
+8
A:
Just to clear the code up to start with. We have (corrected):
public static final String[] VALUES = new String[] {"AB","BC","CD","AE"};
This is a mutable static which FidnBugs will tell you is very naughty. It should be private:
private static final String[] VALUES = new String[] {"AB","BC","CD","AE"};
(Note, you can actually drop the new String[]; bit.)
So, reference arrays are bad, and in particular here we want a set:
private static final Set<String> VALUES = new HashSet<String>(Arrays.asList(
new String[] {"AB","BC","CD","AE"}
));
(Paranoid people, such as myself, may feel more at ease if this was wrapped in Collections.unmodifiableSet - it could even be made public.)
"Given String s, is there a good way of testing whether VALUES contains s?"
VALUES.contains(s)
O(1).
Tom Hawtin - tackline
2009-07-15 01:13:02
A:
ObStupidAnswer (but I think there's a lesson in here somewhere):
enum Values {
AB, BC, CD, AE
}
try {
Values.valueOf(s);
return true;
} catch (IllegalArgumentException exc) {
return false;
}
Tom Hawtin - tackline
2009-07-15 01:18:26
A:
Actually , if you use HashSet as Tom Hawtin proposed you don`t need to worry about sorting and your speed is the same as with Binary Search on a presorted array, probably even faster.
It all depends on how your code is set up, obviously, but from where I stand, the order would be:
On a UNsorted array
HasSet
asList
sort & Binary
On a sorted array
HasSet
Binary
asList
So either way, HasSet ftw
not
2010-06-11 02:37:56