
Do Vectors search and remove in log(n) time?
Hi,
I'm working on an application using a Vector to store a sorted list of numbers. Since it's sorted, it would be advantageous to use a log(n) algorithm for searching and removing items. So I'm wondering if the Vector.contains(Object) and Vector.remove(Object) methods know to search for items in a divideandconquer manner when it's sorted. I'd use these methods if this is so. Otherwise, I'm wondering if it would make my program run faster if I were to create my own contains(Object) and remove(Object) methods for searching and removing. Does anyone know what kind of algorithms the Vector class uses for these tasks?
Gib

im not sure, but i doubt that the methods that sun use would be considered to be slow, they would have thought about it quite well, so i would imagine that if you were to code your own methods, they maybe better and they may not.
But if your vector searching is fitted to your situation specifically, then maybe you should overwrite the methods, maybe it will be better (in your situation only)
hope i clear enough
A kram a day keeps the doctor......guessing

Well, the fact that your list is sorted helps you greatly. Doing a binary search gives O(Log(n)) and requires a sorted list.
Here is an easy to follow article on it.
http://www.tbray.org/ongoing/When/20...3/03/22/Binary
Binary search is very easy to code on your own if Sun doesn't have it already.

Re: Do Vectors search and remove in log(n) time?
Originally posted by gibby
Hi,
I'm working on an application using a Vector to store a sorted list of numbers. Since it's sorted, it would be advantageous to use a log(n) algorithm for searching and removing items. So I'm wondering if the Vector.contains(Object) and Vector.remove(Object) methods know to search for items in a divideandconquer manner when it's sorted. I'd use these methods if this is so. Otherwise, I'm wondering if it would make my program run faster if I were to create my own contains(Object) and remove(Object) methods for searching and removing. Does anyone know what kind of algorithms the Vector class uses for these tasks?
Gib
you can work it out.. it would be a trivial matter to write a class that:
preallocates a 10, hundred, thousand, ten k, 100 k, million sized vector
populates it with 11000000
over X million iterations, times the lookups of a random number from the range
here, i'll have a pop:
Code:
for(int i=1;i<7;i++){
int range = Math.pow(10, i);
Vector v = new Vector(range);
//populate
for(int j=0;j<range;j++){
v.add(j);
}
System.out.println("doing 1 million lookups in a " + range + "sized vector");
long stTime = System.currentTimeMillis();
for(int k = 0; k<1000000; k++){
v.contains( (int)(Math.random()*range) );
}
long edTime = System.currentTimeMillis();
System.out.println("took "+edTimestTime+" millis");
}
tidy that and run it.. maybe have to tune my choice of x = 1 million
if the time increased log(n) then search is log n
oh, and Vector preserves insertion order so removal is o(n) where n is the number of items that need shunting to insert or delete..
additionally, vector is synchronized, which makes it much slower than an ArrayList. if you arent needing synchronization, use an arraylist
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Development Centers
 Android Development Center
 Cloud Development Project Center
 HTML5 Development Center
 Windows Mobile Development Center
