В настоящее время я делаю тест для среднего случая двоичного поиска. Просто все, что я делаю, это генерирую случайную переменную, а затем ищу эту случайную переменную в массивах разного размера, используя двоичный поиск. Ниже используется мой код:
public static void main(String[] args)
{
//This array keeps track of the times of the linear search
long[] ArrayTimeTaken = new long[18];
//Values of the array lengths that we test for
int[] ArrayAssignValues = new int[18];
ArrayAssignValues[0] = 1000000;
ArrayAssignValues[1] = 10000000;
ArrayAssignValues[2] = 20000000;
ArrayAssignValues[3] = 30000000;
ArrayAssignValues[4] = 40000000;
ArrayAssignValues[5] = 50000000;
ArrayAssignValues[6] = 60000000;
ArrayAssignValues[7] = 70000000;
ArrayAssignValues[8] = 80000000;
ArrayAssignValues[9] = 90000000;
ArrayAssignValues[10] = 100000000;
ArrayAssignValues[11] = 110000000;
ArrayAssignValues[12] = 120000000;
ArrayAssignValues[13] = 130000000;
ArrayAssignValues[14] = 140000000;
ArrayAssignValues[15] = 150000000;
ArrayAssignValues[16] = 160000000;
ArrayAssignValues[17] = 170000000;
//Code that runs the linear search
for (int i = 0; i < ArrayAssignValues.length; i++)
{
float[] arrayExperimentTest = new float[ ArrayAssignValues[i]];
//We fill the array with ascending numbers
for (int j = 0; j < arrayExperimentTest.length; j++)
{
arrayExperimentTest[j] = j;
}
Random Generator = new Random();
int ValuetoSearchfor = (int) Generator.nextInt(ArrayAssignValues[i]);
System.out.println(ValuetoSearchfor);
ValuetoSearchfor = (int) arrayExperimentTest[ValuetoSearchfor];
//Here we perform a the Linear Search
ArrayTimeTaken[i] = BinarySearch(arrayExperimentTest,ValuetoSearchfor);
}
ChartCreate(ArrayTimeTaken);
System.out.println("Done");
}
Вот мой код для бинарного поиска:
static long BinarySearch(float[] ArraySearch,int ValueFind)
{
System.gc();
long startTime = System.nanoTime();
int low = 0;
int high = ArraySearch.length-1;
int mid = Math.round((low+high)/2);
while (ArraySearch[mid] != ValueFind )
{
if (ValueFind <ArraySearch[mid])
{
high = mid-1;
}
else
{
low = mid+1;
}
mid = (low+high)/2;
}
long TimeTaken = System.nanoTime() - startTime;
return TimeTaken;
}
Теперь проблема в том, что результаты не имеют смысла. Ниже приведен график:
Может кто-нибудь объяснить, как 1-й массив занимает так много времени? Я запускал код несколько раз, и в основном каждый раз создавался один и тот же график. Есть ли в Java какие-то результаты кэширования? Может ли кто-нибудь объяснить результат, почему 1-й двоичный поиск занимает так много времени по сравнению с другими, хотя размер массива крошечный по сравнению с остальными?