Neil Forrest

Greenhorn

Posts: 13

posted 12 years ago

Hi,

Can anyone spot the logic bug in my code? It's a binary search program. I'm timing the search times for different inputs. It works up until the input is n=10^6 on the command line. Then it just keeps running. The longest I've let it go is over 12 hours. What I don't get is that for lesser n values, it's really fast. Memory is not the problem...

public class Binary{

//** declarations of variables

int[] list,list_search;

int size,count;

long time1;

long time2;

//** constructor

public Binary(int n, int k){

size=n;

count=k;

int i;

list=new int[size];

list_search=new int[count];

time1 = 0;

time2 = 0;

//** generate the list of elements

for(i=0;i<size;i++){

list[i]=1+(int)(n*Math.random());

}

for(i=0;i<count;i++)

list_search[i]=1+(int)(n*Math.random());

//sort the list

sort();

//search the element

startsearch();

}

//** sort the list before binary search... done in ascending order

public void sort(){

int i,j,temp;

for(i=0;i<size;i++){

for(j=i;j<size;j++){

if(list[i]>list[j]){

temp=list[i];

list[i]=list[j];

list[j]=temp;

}

}

}

}

//** method for binary search

public void binary(int key){

int low=0;

int high=size-1;

int middle;

while(low<high){

middle=(low+high)/2;

if(key==list[middle])

break;

else if(key<list[middle])

high=middle-1;

else if(key>list[middle])

low=middle+1;

}

}

public void startsearch(){

int i;

time1 = System.currentTimeMillis();

for(i=0;i<count;i++){

binary(list_search[i]);

time2 = System.currentTimeMillis();

}

System.out.println("Search Time: "+ (time2 - time1) +" ms");

}

//** main function

public static void main(String args[]){

int n,k;

if(args.length!=2){

System.out.println("Required number of arguments are not provided");

}

else{

n=Integer.parseInt(args[0]);//parsing the size for number of elements in the list

k=Integer.parseInt(args[1]);// parsing the size of number of elements to be searched

Binary ss =new Binary(n,k);//object created to compare the two search

}

}

}

Can anyone spot the logic bug in my code? It's a binary search program. I'm timing the search times for different inputs. It works up until the input is n=10^6 on the command line. Then it just keeps running. The longest I've let it go is over 12 hours. What I don't get is that for lesser n values, it's really fast. Memory is not the problem...

public class Binary{

//** declarations of variables

int[] list,list_search;

int size,count;

long time1;

long time2;

//** constructor

public Binary(int n, int k){

size=n;

count=k;

int i;

list=new int[size];

list_search=new int[count];

time1 = 0;

time2 = 0;

//** generate the list of elements

for(i=0;i<size;i++){

list[i]=1+(int)(n*Math.random());

}

for(i=0;i<count;i++)

list_search[i]=1+(int)(n*Math.random());

//sort the list

sort();

//search the element

startsearch();

}

//** sort the list before binary search... done in ascending order

public void sort(){

int i,j,temp;

for(i=0;i<size;i++){

for(j=i;j<size;j++){

if(list[i]>list[j]){

temp=list[i];

list[i]=list[j];

list[j]=temp;

}

}

}

}

//** method for binary search

public void binary(int key){

int low=0;

int high=size-1;

int middle;

while(low<high){

middle=(low+high)/2;

if(key==list[middle])

break;

else if(key<list[middle])

high=middle-1;

else if(key>list[middle])

low=middle+1;

}

}

public void startsearch(){

int i;

time1 = System.currentTimeMillis();

for(i=0;i<count;i++){

binary(list_search[i]);

time2 = System.currentTimeMillis();

}

System.out.println("Search Time: "+ (time2 - time1) +" ms");

}

//** main function

public static void main(String args[]){

int n,k;

if(args.length!=2){

System.out.println("Required number of arguments are not provided");

}

else{

n=Integer.parseInt(args[0]);//parsing the size for number of elements in the list

k=Integer.parseInt(args[1]);// parsing the size of number of elements to be searched

Binary ss =new Binary(n,k);//object created to compare the two search

}

}

}

posted 12 years ago

Well, without even looking at the search routine, I can point out that the sort routine's performance will be proportional to n^2. If it takes 1 millisecond to sort 100 items, it will take over 250 hours (!) to sort 1 million items!

You could replace your custom sort routine with a call to one of the sort() functions in the java.util.Arrays() class -- they perform a n ln n -- which is going to make an

You could replace your custom sort routine with a call to one of the sort() functions in the java.util.Arrays() class -- they perform a n ln n -- which is going to make an

*enormous*difference!
Layne Lund

Ranch Hand

Posts: 3061

posted 12 years ago

The Java API also contains a binarySearch() method. Of course, if this is a class assignment, there may be some restrictions on what methods you can use from the API. Still, I thought I'd mention it in case you are allowed to use it.

Layne

Layne

posted 12 years ago

you have discovered one of the classic issues with this kind of sort. It works fantastic for small sets, but just grinds (almost) to a halt as the input set gets bigger.

As you progress in your studies, you will learn some other sorting methods that will speed things up... most of the time. You can find entire books on nothing but searching and sorting (which are closely related). What makes coding fun and interesting is that you can have two completly different sort algorithms. Depending on the input data (and how clever your sorts are), in one case, one sort will be blindingly fast and the other unbearably slow. The other case will cause the exact opposite. result.

What I don't get is that for lesser n values, it's really fast.

you have discovered one of the classic issues with this kind of sort. It works fantastic for small sets, but just grinds (almost) to a halt as the input set gets bigger.

As you progress in your studies, you will learn some other sorting methods that will speed things up... most of the time. You can find entire books on nothing but searching and sorting (which are closely related). What makes coding fun and interesting is that you can have two completly different sort algorithms. Depending on the input data (and how clever your sorts are), in one case, one sort will be blindingly fast and the other unbearably slow. The other case will cause the exact opposite. result.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Consider Paul's rocket mass heater. |