Neither Set nor List specify any speed or complexity guarantees for any
operation. It will depend on the actual implementation you use.
ArrayList and HashSet? Or LinkedList and TreeSet? Or something else?
Set and List are interfaces, not implementations. So "yes and no". It's due
to how the objects you're using are implemented, not how Set and List are
implemented in general.
I do know that Set and List are interface that collectively fall under
Collection. I meant to question that, in general any Set
implementation like HashSet or a TreeSet (I have used HashSet) would
be faster than List like ArrayList or LinkedList or Vector(I used
ArrayList)
They're different things. It's a general rule to use the correct container
for your needs. Sets are for use where you want to have no repeats and no
indexed access (i.e. "4th element"). Lists are for when you care about index
or order, or want repeats.
For that matter for a small collection(where elements are less than 0)
ArrayList (sorted) seems to be faster with or without repeated values.
Where as its inverse for a bigger Collection.
Each of them has a number of different implementations to pick from depending
on your exact needs. TreeSet, for instance, can be iterated based on a sort
order, where HashSet has no order at all. ArrayList has fast lookup by
position but can be expensive to add elements if it's not sized properly.
LinkedList has slow lookup by position.
Would it be wise to consider a collection on basis of its size?
@ Eric
Insufficient information, and an unwarranted presumption.
The benchmarking for following code on windows xp AMD 64 1.8 GHz 1 GB
RAM.
Applications running - Firefox, Eclipse, Command prompt instance.
Background services like Etrust Antivirus, Network services etc..
--------- code ------------
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
public class Prime {
// TreeSet implementation
private static Set calculatePrime1(int number){
Set<Integer> listA = null;
Set<Integer> finalList = null;
int count =0;
listA=new TreeSet<Integer>();
finalList= new TreeSet<Integer>();
for(int i=2;i<number;i+=2)
listA.add(i);
while (count<number){
Iterator<Integer> it = listA.iterator();
count=it.next();
finalList.add(count);
listA.remove(count);
int internalCount=count;
while(internalCount<number){
internalCount += count;
listA.remove(internalCount);
}
if(listA.isEmpty())
break;
}
return finalList;
}
// ArrayList implementation algorithm same as Treeset
private static List calculatePrime2(int count){
List<Integer> list = new ArrayList<Integer>(count);
List<Integer> primeFound = new ArrayList<Integer>();
list.add((Integer)2);
for (Integer i = 3; i <= count; i+=2) {
list.add(i);
}
int divisor=3;
while (divisor<count/2) {
primeFound.add(list.get(0));
divisor=list.get(0);
for (int i = divisor; i<=count; i+=divisor) {
list.remove((Object)i);
}
}
primeFound.addAll(list);
return (List<Integer>)primeFound;
}
// ArrayList with slight difference from previous approach
private static List calculatePrime3(int count){
List<Integer> list = new ArrayList<Integer>(count);
List<Integer> primeFound = new ArrayList<Integer>();
for (Integer i = 3; i <= count; i+=2) {
list.add(i);
}
int divisor=3;
while (divisor<count) {
Iterator<Integer> it = list.iterator();
divisor=it.next();
primeFound.add(divisor);
int internalCount=divisor;
list.remove(0);
while(internalCount<count) {
internalCount = internalCount+ divisor;
list.remove((Integer)internalCount);
}
if (list.isEmpty())
break;
}
primeFound.addAll(list);
return (List<Integer>)primeFound;
}
public static void main(String [] args){
BenchMark b = new BenchMark();
int count=100;
calculatePrime1(count);
System.out.println(b.finish());
b = new BenchMark();
calculatePrime2(count);
System.out.println(b.finish());
b= new BenchMark();
calculatePrime3(count);
System.out.println(b.finish());
}
}
--------- Benchmark code -----------
public class BenchMark {
private long start;
public BenchMark() {
start = System.nanoTime();
}
public long finish(){
return System.nanoTime()-start;
}
}
--------- Code ends ------------
Bench mark output in eclipse
first run -->
1917283
2136026
331327
second run -->
1920076
2136584
331607
third run -->
1909740
2231848
330488
Benchmark output in Command prompt
first run -->
2121220
1596851
338032
second run -->
2189943
1593778
336076
third run -->
2107251
1597968
339150
is there some more information that would be helpful?