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


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 4 of 4

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

  1. #1
    Join Date
    Jun 2004
    Posts
    29

    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 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

  2. #2
    Join Date
    Sep 2004
    Posts
    223
    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

  3. #3
    Join Date
    Sep 2004
    Posts
    150
    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.

  4. #4
    Join Date
    Feb 2004
    Posts
    808

    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 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:
    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 "+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
    The 6th edict:
    "A thing of reference thing can hold either a null thing or a thing to any thing whose thing is assignment compatible with the thing of the thing" - ArchAngel, www.dictionary.com et al.
    JAR tutorial GridBag tutorial Inherited Shapes Inheritance? String.split(); FTP?

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

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