Develop a Java program to compare the performance of data retrieval for the foll
ID: 675417 • Letter: D
Question
Develop a Java program to compare the performance of data retrieval for the following search methods:
Sequential Search
Binary search of a sorted array
Hashed search
Find prime
I have all of the other classes and methods, as well as a random list of data to search. I just need the code required to implement each of these searches:
public void BinarySearch()
{
}
public void HashedSearch()
{
}
public int FindPrime()
{
}
Must use these steps:
Sequential Search
Read the data file into an array
Apply search
Collect stats
Save stats in arrays
Go to step 1
Binary Search
Read the data file into an array
Copy to an array of exact size
Sort the array (Use Java sort)
Apply search
Collect stats
Save stats in arrays
Go to step 1
Hashed Search
Read the data file into an array
Create an array of size N (largest prime number <twice the size of data (use hashing function address = data %N)
Apply search
Collect stats
Save stats in arrays
Go to step 1
Sequential Search
Read the data file into an array
Apply search
Collect stats
Save stats in arrays
Go to step 1
Binary Search
Read the data file into an array
Copy to an array of exact size
Sort the array (Use Java sort)
Apply search
Collect stats
Save stats in arrays
Go to step 1
Hashed Search
Read the data file into an array
Create an array of size N (largest prime number <twice the size of data (use hashing function address = data %N)
Apply search
Collect stats
Save stats in arrays
Go to step 1
Explanation / Answer
Caution: Function to read data from a file into an array should be defined outside the mentioned functions.
Assumption: We assume the data is of type integer.
//function to read data from a file into an array
public int[] readData(String filename, int len) throws IOException
{
//len is the length of data in file 'filename'
//Create file handler
File file=new File(filename);
int count=0; //count no. of lines read
//Create an array of length len
int array[];
array=new int[len];
//Read data from file
try {
BufferedReader reader=new BufferedReader(new FileReader(file));
String data="";
while((data=reader.readLine())!= null)
{
array[count]=Integer.parseInt(data);
}
reader.close();
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
return array;
}
BinarySearch() function:
public void BinarySearch(int[] array, int key)
{
//flag to indicate search is successful or unsuccessful
boolean flag=false;
//sort the array
Arrays.sort(array);
//start time for search
long startTime=System.currentTimeMillis();
//search the key
int start = 0;
int end = array.length - 1;
while (start <= end)
{
int mid = (start + end) / 2;
if (key == array[mid]) {
flag=true;
}
if (key < array[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
long endTime=System.currentTimeMillis();
if(flag)
System.out.println("Key found");
else
System.out.println("Key not found");
System.out.println("Time elapsed in search(ms):"+(endTime-startTime));
}
FindPrime() function:
//return largest prime < 2*N
public int FindPrime(int N)
{
int array[];
array=new int[2*N]; //array to hold prime numbers
int j=0; //counter for array
//loop to generate prime numbers
for(int i=0;i<2*N;i++)
{
if(isPrime(i))
{
array[j]=i;
j++;
}
}
//sorts the array of prime numbers
Arrays.sort(array);
//return largest prime number < 2*N
return array[array.length-1];
}
//utility function to check whether a number is prime
private boolean isPrime(int a)
{
for(int k=2;k<a;k++)
{
if(a%k==0)
{
return false;
}
}
return true;
}
HashedSearch() function:
For HashedSearch(), instructions are ambiguous. Need to be clarified. After that, it can be implemented. It is not specified whether HashTable needs to be implemented afresh or Java HashMap can be used.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.