为什么 C# 中的冒泡排序对我来说比 JavaScript 慢？

Question

我是 C# 的新手，一直在玩弄它。我在 C# 中实现了冒泡排序，希望它比 JavaScript 更快，因为它是一种编译语言，但我的速度要慢得多。

我正在对 100,000 个数字进行排序。

在 C# 中，我得到的速度大约为：1 分 30 秒

C#代码：

using System.Diagnostics;

public class Program {

    public static void Main(string[] args) {

        List<int> randoms = generateRandoms(0, 1000000, 100000);
        Console.WriteLine(randoms.Count);

        Stopwatch stopWatch = new Stopwatch();
        
        stopWatch.Start();
        bubbleSort(randoms);
        stopWatch.Stop();
        TimeSpan timeSpan = stopWatch.Elapsed;
        Console.WriteLine("Total processing time... {0:00}:{1:00}:{2:00}.{3:000}", timeSpan.Hours, timeSpan.Minutes, timeSpan.Seconds, timeSpan.Milliseconds);
        Console.Read();
    }

    static List<int> generateRandoms(int min, int max, int amount) {

        Random rnd = new Random();
        List<int> randoms = new List<int>();

        for (int i = 0; i < amount; i++) {
            int r = rnd.Next(min, max+1);
            randoms.Add(r);
        }

        return randoms;
    }


    static List<int> bubbleSort(List<int> list) {
        //Bubble sort
        for (int i = 0; i < list.Count; i++) {
            for (int j = 0; j < list.Count - i - 1; j++) {
                if (list[j] > list[j+1]) {
                    int temp = list[j];
                    list[j] = list[j+1];
                    list[j+1] = temp;
                }
            }
        }

        return list;
    }


    static void print(List<int> list) {
        for (int i = 0; i < list.Count; i++) {
            Console.WriteLine(list[i]);
        }
    }
}

在 JavaScript 我得到大约：30 秒

JavaScript代码：

function bubbleSort(array) {

    for (let i = 0; i < array.length; i++) {
        for (let j = 0; j < array.length-i-1; j++) {

            if (array[j] > array[j+1]) {
                [array[j], array[j+1]] = [array[j+1], array[j]];
            }
        }
    }
}

function generateRandoms(min, max, n) {
    const arr = [];
    for (let i = 0; i < n; i++) {
        arr.push(Math.floor(Math.random() * (max-min+1) + min));
    }

    return arr;
}

const array = generateRandoms(0, 1000000, 100000);
console.log(array.length);

const start = new Date();
bubbleSort(array);
const end = new Date();

console.log(`Performance: ${end - start}ms`);

我认为它与 C# 中的“列表”数据结构有关，但在查看文档后，我在 bubbleSort 函数中使用的所有操作似乎都是 O(1)

有谁知道为什么 C# 的速度对我来说差得多？我正在使用 .Net v6.0.201。我也在为这两个程序使用 VSCode。

Answer 1

I figured it had to do with the "List" data structure in C#, but after looking into the documentation, it appears all operations I am using in the bubbleSort function are O(1)

O(1) 不一定快，它只是常数。将 C# 代码更改为使用数组可使其速度大致翻倍。不确定为什么会这样（List 在底层使用数组）但 IIRC 数组有时能够省略边界检查。

此外，您的 C# 交换比 JS 交换做的工作多一点；你可以替换这个：

int temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;

有了这个：

(list[j], list[j+1]) = (list[j+1], list[j]);

经过这些改变，两种语言更加接近，但 JS 仍然胜出；我不确定为什么。

更新：如果我记得在 Release 模式下编译，C# 对我来说会更快。

Answer 2

在 release 模式下构建时，C# 与 JS 一样快，甚至快一点。至少在我的电脑上。

Total processing time... 00:01:00.611 : 调试 bin

Total processing time... 00:00:19.586 : 释放 bin

为什么 C# 中的冒泡排序对我来说比 JavaScript 慢？

Why is Bubble Sort in C# slower than JavaScript for me?

javascript

c#

sorting

bubble-sort