评论初级研究调查的方法 "The Effect of Hardware Variances on the Performance of the Merge Sort Algorithm"

Question

我是一名高中生，正在对 "To what extent do variances in the performance of CPU, RAM, and storage affect the performance of the merge sort algorithm when it is run on large data sets?"

进行初步研究

方法论

研究问题将通过运行在各种硬件组件（CPU、RAM 和主驱动器）上使用合并排序算法并评估哪个硬件组件最有效地增加算法的效率。硬件组件的性能将通过对 CPU 和 RAM 进行降频和超频来改变，同时将程序运行ning 算法存储在 SSD 与 HDD 上，并记录算法运行所需的时间对数组中的 500 个随机生成的整数进行排序。与大公司使用的大数据相比，使用了一个小数据集，以避免因瓶颈不断达到硬件极限或导致倦怠而对有限的可用资源造成负担。要真正了解合并排序算法对大数据集的功效，数据集的大小理想情况下应为十亿左右的数据元素，但这需要卓越的 CPU、RAM、存储和冷却解决方案来保护硬件并跟上处理大量数据的步伐。重申一下，合并排序算法在大型公司中非常流行，可以轻松定位大型列表中的项目，因此实际上合并排序算法可能已被修改为更高效并更好地处理数十亿个数据元素。在进行这个实验之前，重要的是要控制各种可能影响本文结果准确性的无关变量。首先，重要的是算法运行所在的操作系统在所有试验中都是相同的，这样 OS 分配内存和确定内存优先级的方式在所有测试中都是相同的。此外，所有硬件组件（例如 CPU、RAM、显卡、主板和冷却解决方案）对于所有测试都必须相同，以避免在协议或规范（例如可用缓存、延迟、数量）方面出现任何制造差异核心数，或多线程性能。所有这些差异都可以直接提高或降低归并排序算法的性能，从而导致结果失真。最后，在测试过程中不得打开其他程序，以避免其他程序使用用于排序目的的内存或处理能力。

这是我要使用的算法运行ning:

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) 的推理是否准确，我们将不胜感激。

非常感谢！

Answer 1

要对 Java 代码进行基准测试，您应该使用适当的基准测试框架，例如 JMH。 JMH 确保预热 JVM 并运行您的代码足够多次以获得一致的结果。没有它，您可能只是在衡量 JVM 启动和编译的性能，而不是排序。这意味着您将测量与您想要测量的完全不同的东西 - 结果将只是噪音，没有信号。
500 个整数是一个低得离谱的数字。如果每个整数的长度为 4 个字节，则只有 2000 个字节的数据。这意味着一些事情：
1. 整个 "dataset" 将在很短的时间内完成排序 - 我们这里说的是微秒。这将很难准确测量。总的来说，通用操作系统不适合低于 10-20 毫秒的精度，这可能是排序 500 个整数所需时间的 x100 - x1000。因此，您需要对这些数字进行多次排序（比如 1000 次），看看这需要多长时间，然后除以 1000，看看单个运行需要多长时间。这就引出了下一个问题：
2. 整个 "dataset" 可能适合一个内存页。此外，它将完全放入 CPU 缓存中。哎呀，它都可以放入 CPU 缓存中最小（也是最快）的 L1。这意味着在排序期间，所有内容都将在 CPU 内完成，因此没有内存访问，也没有磁盘访问。因此，RAM 的大小和时钟速度只会影响 500 个整数的初始加载，即使这样，影响也可以忽略不计。由于您需要运行对单个基准测试进行数千次测试，因此您甚至不会在结果中看到任何加载时间，因为所有这些 [=41= 的数据只会加载一次]s.
换句话说，使用 500 英寸，就像通过测量汽车在一米（3.3 英尺，如果您来自大洋彼岸）的距离内的速度来比较不同类型的机油。

要获得任何有意义的结果，您需要大大增加要排序的数据量，当然还要使用 JMH。我还会使用不同的数据大小并加入一些额外的排序算法来进行比较。展示输入的大小和不同的硬件选择如何影响结果会很有趣。

评论初级研究调查的方法 "The Effect of Hardware Variances on the Performance of the Merge Sort Algorithm"

Comment on the Methodology of Primary Research investigating "The Effect of Hardware Variances on the Performance of the Merge Sort Algorithm"

java

sorting

algorithm

mergesort

methodology