Sequential Search Performance

[Neil Forrest]

Hi,
Hope you can help...my program below compiles but it's not performing as I'd like. The idea is that once the two arguments are entered on the command line: array size(n) where the max size is 10^6 and number of searches(k);the program generates a random search value. What should happen is that based on the two arguments, the search value is either found or not and the search time is captured in ms. First off I'm not sure how to incorporate the random value component into the code, and second, no matter what I input as arguments, I get a search time of 0ms.

Any hints?

Thanks,
Neil

//SequentialSearch.java

import java.io.*;
import javax.swing.*;


public class SequentialSearch
{
private long time1; // start time
private long time2; // end time

public SequentialSearch()
{
time1 = 0;
time2 = 0;
}

public int sequentialSearch(int[] list, int k)
{
boolean found = false;
int i, searches = 0;
time1 = System.currentTimeMillis(); // set start time

// search list
for(i = 0; i < list.length; i++)
{
searches++;
if( k == list[i]) // if true, key is found
{
found = true;
break;
}
}

time2 = System.currentTimeMillis(); // set end time

if ( found == true )
{
System.out.println("Search Value: " + k +
"\nValue Found: Yes" +
"\nSearch Comparisons: " + searches +
"\nList Size: " + list.length +
"\nSearch Time: " + (time2-time1));
}
else
System.out.println("Search Value: " + k +
"\nValue Found: No" +
"\nSearch Comparisons: " + searches +
"\nList Size: " + list.length +
"\nSearch Time: " + (time2-time1));
return 0;
}

public static void main (String[] args) throws IllegalArgumentException
{

SequentialSearch s = new SequentialSearch(); // create reference to SequentialSearch class
Assert.notFalse(args.length == 2, "Usage: SequentialSearch <size> <searches>");
int n = Integer.parseInt(args[0]); // number of array elements
int k = Integer.parseInt(args [1]); // search target key
int [] list = new int[n]; // create list array of n size

System.out.println("Argument 1 = " + args[0] + "\nArgument 2 = " + args[1] + "\n\n");

for(int i = 0; i < list.length; i++)
list[i] = i + 1;

s.sequentialSearch(list, k); // invoke search method
}

}

[Layne Lund]

Check out Math.random() or the Random class for generating random numbers. I'll have to take a closer look at your code to answer your other questions, but I wanted to give you this suggestion for now so you can start trying to figure it out.

Layne

[Layne Lund]

I don't see anything obviously wrong with your code. I assume that the System.out.println() in main() shows the values for n and k that you expect, right? Have you tried testing it with the largest values possible? I would guess that with very small values of n and k, the amount of time is so miniscule that it is impossible to measure. You should use the largest allowed values to see if that makes a difference in the amount of time used.

With that said, I have a few cdomments about your code. First it would be a lot easier for us to read if you use the UBB CODE tags. These will perserve your formatting and indentation. Second, there doesn't seem to be any reason to declare time1 and time2 as private class variables. Since they are not used in any other methods you can declare them as local variables in the sequentialSearch() method. Third, why do you have two counters (search and i)? Both of them will have the exact same value when the for loop finishes, so I don't see a reason to have both.

These are all probably rather trivial and not much to worry about. However, I believe that you should start learning good habits now so that you don't have to break them later. The main thing I'm trying to point out here is that, ideally, you should have a reason for every line of code you type.

I'm sorry that I can't be of any more help than this.

Keep Coding!

Layne

[David Harkness]

Originally posted by Neil Forrest:
two arguments are entered on the command line: ... and number of searches(k);the program generates a random search value.

That's not what the program does. The second argument (k) is used as the value to find; it's not randomly generated.

As to the time being short, what values of n have you used? For small values (less than 1000000) on modern hardware I wouldn't be surprised if the granularity of the timing in JDK pre 1.5 shows it to take 0 ms. You'll notice that pre 1.5 (or is it 1.4?) the smallest differences in System.currentTimeMillis() are 15 and 16 milliseconds, otherwise it's zero.

You're iterating an array and doing an int increment and comparison for each iteration. This takes very little time.

[Layne Lund]

Originally posted by David Harkness:
That's not what the program does. The second argument (k) is used as the value to find; it's not randomly generated.

As to the time being short, what values of n have you used? For small values (less than 1000000) on modern hardware I wouldn't be surprised if the granularity of the timing in JDK pre 1.5 shows it to take 0 ms. You'll notice that pre 1.5 (or is it 1.4?) the smallest differences in System.currentTimeMillis() are 15 and 16 milliseconds, otherwise it's zero.

You're iterating an array and doing an int increment and comparison for each iteration. This takes very little time.

Isn't the granularity dependant on the underlying hardware as well as the JDK?

Layne

[David Harkness]

Originally posted by Layne Lund:
Isn't the granularity dependant on the underlying hardware as well as the JDK?

I would think so, yes. But running the same code on the same hardware and OS yielded different granularity when I upgraded from 1.3 to 1.4, and I've seen the 15/16 ms granularity since Java's beginning on different hardware.