Я учусь в старшей школе и провожу первичное исследование на тему «В какой степени различия в производительности ЦП, ОЗУ и хранилища влияют на производительность алгоритма сортировки слиянием, когда он запускается на больших наборах данных?»
Методология
Исследовательский вопрос будет исследован путем запуска алгоритма сортировки слиянием на различных аппаратных компонентах (ЦП, ОЗУ и основной диск) и оценки того, какой аппаратный компонент является наиболееэффективен при повышении эффективности алгоритма. Производительность аппаратных компонентов будет изменяться путем разгона и разгона ЦП и ОЗУ, при этом программа будет сохранять программу, работающую на SSD и HDD, и записывать время, необходимое алгоритму для сортировки 500 случайно сгенерированных целых чисел в массиве. Небольшой набор данных использовался по сравнению с большими данными, используемыми крупными компаниями, чтобы избежать налогообложения ограниченных доступных ресурсов путем постоянного достижения пределов оборудования из-за узких мест или из-за выгорания. Чтобы по-настоящему понять эффективность сортировки слиянием algorthim для большого набора данных, размер набора данных в идеале должен составлять около миллиарда элементов данных, но для этого потребуется превосходное решение ЦП, ОЗУ, хранилища и охлаждения для защиты оборудования и сохранения. с обработкой больших объемов данных. Повторим, что алгоритм сортировки слиянием очень популярен в крупных корпорациях, чтобы легко находить элементы в больших списках, и, таким образом, вполне вероятно, что в действительности алгоритм сортировки слиянием был изменен, чтобы быть более эффективным и лучше обрабатывать миллиарды элементов данных. Перед проведением этого эксперимента важно контролировать различные посторонние переменные, которые могут исказить точность результатов, представленных в этом эссе. Во-первых, важно, чтобы операционная система, в которой выполняется алгоритм, была одинаковой во всех испытаниях, чтобы способ, которым ОС выделяла и расставляла приоритеты памяти, был одинаковым во всех тестах. Кроме того, все аппаратные компоненты, такие как ЦП, ОЗУ, графика, материнская плата и решение для охлаждения, должны быть одинаковыми для всех тестов, чтобы избежать любых производственных различий в протоколах или спецификациях, таких как доступный кэш, задержка, количество ядер илимногопоточность. Все эти различия могут напрямую улучшить или ухудшить производительность алгоритма сортировки слиянием и, таким образом, привести к искажению результатов. Наконец, никакие другие программы не должны быть открыты во время процесса тестирования, чтобы другие программы не использовали память или вычислительные мощности, предназначенные для сортировки.
Вот алгоритм, который я собираюсь запустить:
import java.util.Random;
public class Merge_Sort {
private int[] arr;
public void main() {
double startTime = System.nanoTime();
createArray();
mergeSort(0, arr.length - 1);
double endTime = System.nanoTime();
double totalTime = endTime - startTime;
System.out.println("Total Time to run the algo: " +
totalTime / 1000000000);
}
public void createArray() {
arr = new int[500];
for (int i = 0; i < arr.length; i++) {
arr[i] = randomFill();
}
}
public int randomFill() {
Random rand = new Random();
int randomNum = rand.nextInt();
return randomNum;
}
public void merge(int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int[] L = new int[n1];
int[] R = new int[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++) {
L[i] = arr[l + i];
}
for (j = 0; j < n2; j++) {
R[j] = arr[m + 1 + j];
}
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
public void mergeSort(int l, int r) {
if (l < r) {
// large l and h
int m = (l + r) / 2;
// Sort first and second halves
mergeSort(l, m);
mergeSort(m + 1, r);
merge(l, m, r);
}
}
public void printArray(int A[]) {
int i;
for (i = 0; i < A.length; i++) {
System.out.println(A[i]);
}
System.out.println("\n");
}
}
Будем весьма благодарны за любые комментарии по методологии, в частности, верно ли мое обоснование использования небольшого набора данных (500).
Большое спасибо!