Do Vectors search and remove in log(n) time?

[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 divide-and-conquer 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

[Kram]

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

[Philwx]

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.

[cjard]

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 divide-and-conquer 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 1-1000000

over X million iterations, times the lookups of a random number from the range

here, i'll have a pop:

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 "+edTime-stTime+" 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