Gần đây tôi đã triển khai thuật toán QuickSort trong C#. Sắp xếp trên một mảng nguyên có chứa hàng triệu mục, hiệu suất của mã này xấp xỉ 10% phía sau việc triển khai .NET.Chi phí của các phương thức nội tuyến trong C#
private static void QS(int[] arr, int left, int right)
{
if (left >= right) return;
var pIndex = Partition(arr, left, right);
QS(arr, left, pIndex);
QS(arr, pIndex + 1, right);
}
Trên một mảng gồm 5 triệu mục, mã này chậm hơn khoảng 60ms so với .NET.
Sau đó, tôi đã tạo phương thức khác có phương pháp Partition() được gạch chân thành QS() (loại bỏ lệnh gọi phương thức và câu lệnh return). Tuy nhiên điều này dẫn đến sự sụt giảm về hiệu suất xuống khoảng 250ms chậm hơn phương pháp sắp xếp của .NET.
Tại sao điều này lại xảy ra?
Chỉnh sửa: Đây là mã theo phương pháp Partition(). Trong phiên bản nội tuyến của QS(), toàn bộ nội dung của phương pháp này ngoại trừ câu lệnh return thay thế dòng var pIndex = Partition(arr, left, right);.
private static int Partition(int[] arr, int left, int right)
{
int pivot = arr[left];
int leftPoint = left - 1;
int pIndex = right + 1;
int temp = 0;
while (true)
{
do { pIndex--; } while (arr[pIndex] > pivot);
do { leftPoint++; } while (arr[leftPoint] < pivot);
if (leftPoint < pIndex)
{
temp = arr[leftPoint];
arr[leftPoint] = arr[pIndex];
arr[pIndex] = temp;
}
else { break; }
}
return pIndex;
}
Chỉnh sửa # 2: Trong trường hợp có ai quan tâm trong việc biên soạn, đây là đoạn code mà gọi là thuật toán:
Sửa # 3: mã kiểm tra mới từ gợi ý Haymo của.
private static void Main(string[] args)
{
const int globalRuns = 10;
const int localRuns = 1000;
var source = Enumerable.Range(1, 200000).OrderBy(n => Guid.NewGuid()).ToArray();
var a = new int[source.Length];
int start, end, total;
for (int z = 0; z < globalRuns; z++)
{
Console.WriteLine("Run #{0}", z+1);
total = 0;
for (int i = 0; i < localRuns; i++)
{
Array.Copy(source, a, source.Length);
start = Environment.TickCount;
Array.Sort(a);
end = Environment.TickCount;
total += end - start;
}
Console.WriteLine("{0}\t\tTtl: {1}ms\tAvg: {2}ms", ".NET", total, total/localRuns);
total = 0;
for (int i = 0; i < localRuns; i++)
{
Array.Copy(source, a, source.Length);
start = Environment.TickCount;
Quicksort.SortInline(a);
end = Environment.TickCount;
total += end - start;
}
Console.WriteLine("{0}\t\tTtl: {1}ms\tAvg: {2}ms", "Inlined", total, total/localRuns);
total = 0;
for (int i = 0; i < localRuns; i++)
{
Array.Copy(source, a, source.Length);
start = Environment.TickCount;
Quicksort.SortNonInline(a);
end = Environment.TickCount;
total += end - start;
}
Console.WriteLine("{0}\tTtl: {1}ms\tAvg: {2}ms\n", "Not inlined", total, total/localRuns);
}
}
Bạn có thể cung cấp ví dụ tương thích không? – CodesInChaos
Bạn có thể đăng toàn bộ mã bạn sử dụng, bao gồm mã bạn sử dụng để đo thời gian không? – svick
Trình tối ưu hóa chỉ trong thời gian đã có các phương thức nội tuyến. Nó có thể đưa ra quyết định tốt hơn bạn, nó thực sự biết mã máy trông như thế nào và có thể đánh giá liệu nội tuyến có thực sự là một tối ưu hóa hay chỉ dẫn đến mã bloat. Một tối ưu hóa thực sự là làm cho mã thông minh hơn. Tối ưu hóa QS là tài liệu tốt, chỉ cần nhìn vào bài viết Wikipedia cho người mới bắt đầu. –