java - 关于调查 "The Effect of Hardware Variances on the Performance of the Merge Sort Algorithm"的初步研究方法论的评论

标签 java algorithm sorting mergesort methodology

我是一名高中生,正在对“在大型数据集上运行合并排序算法时,CPU、RAM 和存储性能的差异在多大程度上影响合并排序算法的性能进行初步研究?”

方法论

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

这是我要运行的算法:

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

非常感谢!

最佳答案

  • 要对 Java 代码进行基准测试,您应该使用合适的基准测试框架,例如 JMH . JMH 确保预热 JVM 并运行您的代码足够多次以获得一致的结果。没有它,您可能只是在衡量 JVM 启动和编译的性能,而不是排序。这意味着您将测量与您想要测量的完全不同的东西 - 结果将只是噪音,没有信号。

  • 500 个整数是一个低得离谱的数字。如果每个整数的长度为 4 个字节,则只有 2000 个字节的数据。这意味着几件事:

    1. 整个“数据集”将在很短的时间内完成排序 - 我们这里说的是微秒。这将很难准确测量。总的来说,通用操作系统不适合低于 10-20 毫秒的精度,这可能是排序 500 个整数所需时间的 x100 - x1000。因此,您需要对这些数字进行多次排序(比如 1000 次),查看需要多长时间,然后除以 1000 以查看单次运行需要多长时间。这给我们带来了下一个问题:

    2. 整个“数据集”可能会放入一个内存页中。此外,它将完全放入 CPU 缓存中。哎呀,它都可以放入 L1,这是最小(也是最快)的 CPU 缓存。这意味着在排序期间,一切都将在 CPU 内完成,因此没有内存访问,也没有磁盘访问。因此,RAM 的大小和时钟速度只会影响 500 个整数的初始加载,即使这样,影响也可以忽略不计。由于您需要为单个基准测试运行数千次测试,因此您甚至不会在结果中看到任何加载时间,因为对于所有这些运行,数据只会加载一次。

      <

    换句话说,使用 500 英寸,就像通过测量汽车在一米(3.3 英尺,如果您来自大洋彼岸)的距离内的速度来比较不同类型的机油。

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

关于java - 关于调查 "The Effect of Hardware Variances on the Performance of the Merge Sort Algorithm"的初步研究方法论的评论,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58400497/

相关文章:

python - 多维数组快速排序

java - 为什么语句有效但 java、jdbc、oracle 中的准备语句无效?

java - 通过单击 ListViewItem 打开另一个 Activity 并传递文本和图像。

algorithm - 确定等腰三角形的左右边

java - 使用两个列表在每条边上的权重仅为 1 和 2 的图形上的 Prim 算法

python - 实现归并排序算法

delphi - 如何让 TStringList 在 Delphi 中以不同方式排序

java - 使用元素集合时如何在 JPA 中进行批量删除?

java - java中如何动态计算公式?

arrays - 当给定大于 i 的索引的项目数大于 a[i] 时,生成输出数组 A[]