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=size1;
int middle;
while(low<high){
middle=(low+high)/2;
if(key==list[middle])
break;
else if(key<list[middle])
high=middle1;
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=size1;
int middle;
while(low<high){
middle=(low+high)/2;
if(key==list[middle])
break;
else if(key<list[middle])
high=middle1;
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 enormous difference!
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!
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 offbyone errors
Anderson gave himself the promotion. So I gave myself this tiny ad:
The WEB SERVICES and JAXRS Course
https://coderanch.com/t/690789/WEBSERVICESJAXRS
