I have 2 vectors containing String objects
I need to determine whether each String present in the first Vector is present in the 2nd Vector or not
Is there anyways to to this such that its complexity is less than O(n^2) i.e Order(n square)
The result obtained should be fast as this is algorithm is to be used in a real-time user application
Plz help
java.util.Vector#contains(Collection) appears to be O(n^2). Running this with 2 Vectors containing strings "0","1",..."9999" takes 1.344 s on my computer. Converting the other Vector to a sorted array and using binary search takes 0.015 s...
import java.util.*;
class Test {
static Vector createTestVector(int n) {
Vector res = new Vector();
for(int i=0; i<n; i++) res.add(i+"");
return res;
}
static boolean containsAll(Vector a, Vector b) {
String[] x = new String[b.size()];
x = (String[])b.toArray(x);
Arrays.sort(x);
for(int i=0; i<a.size(); i++) if(search(x,(String)a.get(i))<0) return false;
return true;
}
private static int search(String[] array, String item) {
int start = 0, end = array.length, mid;
while(start<end) {
mid = (start + end)/2;
int test = array[mid].compareTo(item);
if(test==0) return mid;
if(test<0) start = mid + 1;
else end = mid;
}
return -1;
}
public static void main(String[] args) {
Vector a = createTestVector(10000), b = a;
boolean same = false;
long now = System.currentTimeMillis();
//same = a.containsAll(b);
same = containsAll(a,b);
now = System.currentTimeMillis() - now;
System.out.println(same + " " + (now/1000.0));
}
}
Message was edited by:
perkele
All all elements from the 2nd vector into a trie.
Then for each element in the 1st vector check to see if the trie contains it.
http://www.graphbuilder.com/trie/
This approach should be O(n + m) where n is the number of the characters in the first vector and m is the number f the characters in the second vector.