Brought to you by EarthWeb
ITKnowledge Logo Login Graphic Click Here!
Click Here!
ITKnowledge
Find:
 
EXPERT SEARCH ----- nav

EarthWeb Direct

EarthWeb sites: other sites

Previous Table of Contents Next


When should you use a Vector?

Vectors are one of the most useful container classes in the java.util package. However, they’re not right for everything. In particular, Vectors are slower than raw arrays; they can’t handle primitive data types, and they can be quite slow when inserting or removing objects from any place except the end of the Vector.

If you can use a fixed array instead of a Vector, you should. As a rough rule of thumb, any operation that uses a Vector is about three times slower than the same operation performed with a plain array. That’s primarily a result of the extra method calls needed to perform basic insertions, deletions, and accesses. It’s always better to do it directly if you can.

The most common reason to use a Vector is that you don’t know how many objects you’ll need to deal with at compile time, only at runtime. However, if the Vector is going to be filled only once and then not modified, you’re better off using a real array.

For example, one place common place vectors are used unnecessarily is in processing <PARAM> tags passed to an applet. It’s quite common to pass an undetermined number of parameters to an applet like this:

     <PARAM NAME="String1" VALUE="Kalel">
     <PARAM NAME="String2" VALUE="Kara">
     <PARAM NAME="String3" VALUE="Jorel">
     <PARAM NAME="String4" VALUE="Lara">
     <PARAM NAME="String5" VALUE="Lois">

You may not know when you compile an applet how many of these parameters there will be. At first glance this appears to be a perfect place for a Vector. You can read these parameters into the Vector in your applet’s init() method like this:

     Vector v = new Vector();
     String name = null;
     int i = 0;
     while ((name = getParameter("String" + ++i)) != null) {
      v.addElement(name);
     }

However, this is overkill. You do not need the full power of a Vector just to collect an undetermined number of quantities. There are several alternative solutions to this problem that don’t involve the overhead of a Vector. For example, you could create the Vector as above, then copy it into an array with an Enumeration, like this:

     String[] names = v.size();
     Enumeration e = names.elements();
     int i = 0;
     while (e.hasMoreElements()) {
      names[i++]  =(String)  e.nextElement();
     }

Alternatively, you could just use the first loop to determine how many PARAM tags you have to deal with, then use a second loop to read them, like this:

     String name = null;
     int i = 0;
     while ((name = getParameter("String" + ++i)) != null) {
     }
     String[] names = new String[i];
     for (int j = 0; j <= i; j++) {
      names[j] = getParameter("String" + (j+1));
     }

There are some other more complicated solutions, such as implementing your own growable array, but the bottom line is that you shouldn’t use a Vector as merely an array whose size will be determined at runtime. You should use a Vector only when the array is going to be constantly changing size and having elements removed and deleted. If you’re only calling addElement() and never insertElementAt(), contains(), removeElement(), or the other such methods of the Vector class, then using a Vector instead of a plain array will make your program slower than it needs to be.

Bitsets

The Bitset class is an indexed list of bits. Each component of a Bitset has a boolean value: true or false. A one or set bit is considered to be true and a zero or unset bit is considered to be false. The primary purpose of a Bitset is to provide an extremely space-efficient means of storing many binary values. Bitsets are not necessarily very fast, but they should be very small.

Java implements Bitsets as arrays of longs. The first 64 bits — that is, bits 0 through 63 — are stored in the zeroth component of the array. The second 64 bits — that is, bits 64 through 127 — are stored in the first component of the array, and so on.

Extensive manipulation of these longs with the bit-level operators discussed in Chapter 2 is used to extract and set the values of individual bits. For example, consider the process of extracting the value of bit 97 from the Bitset bs. At the high level, all you need to do is this:

     boolean b = bs.get(97);

Now consider what you have to do to get the value of the 97th bit from an array of longs called la:

     boolean b;
     long L = la[1];  // the 97th bit is in the first component
     L = L & 0x00008000; // mask off the 97th bit
     if (L == 0) b = false; // bit 97 wasn't set
     else b = true; // bit 97 was set

That’s a lot more complex, which is why this is hidden inside a class in the first place. Of course you want a general method for finding an arbitrary bit. That takes even more effort, such as this:

     long[] la;

     public boolean get(int i) {

      int index = i / 64; // find the right component of the array
      long bit = 1L << (i % 64); // find the right bit
      long result = la[index] & bit; // mask off the desired bit
      if (result == 0) return false; bit wasn't set
      else return true;

     }

Sun’s actual code is a little faster than this, but a little harder to understand.

Some operations are easier. For example, the logical operations and, or, not, and xor simply require performing the equivalent bitwise operations between each corresponding component of the arrays forming the two Bitsets. The only catch is that you may need to expand one array if it’s smaller than the other is.


Previous Table of Contents Next
HomeAbout UsSearchSubscribeAdvertising InfoContact UsFAQs
Use of this site is subject to certain Terms & Conditions.
Copyright (c) 1996-1999 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.