Я пытаюсь проверить разницу в производительности моих методов быстрой сортировки и сортировки слиянием, но по какой-то причине первый цикл цикла всегда показывает ровно 0,003 миллисекунды, а остальные 0 миллисекунд.
public static void RunDiagnostics(int[] rangeOfLengthsToTest, int numOfTestsPerLength)
{
Stopwatch stopwatch = new Stopwatch();
int[] array;
double totalQuicksortTime, totalMergesortTime;
for (int i = rangeOfLengthsToTest[0]; i <= rangeOfLengthsToTest[1]; i++)
{
totalQuicksortTime = 0;
totalMergesortTime = 0;
for (int k = 0; k < numOfTestsPerLength; k++)
{
array = GetArray(i, new int[] { -9999, 9999 });
stopwatch.Start();
QuickSort((int[])array.Clone());
stopwatch.Stop();
totalQuicksortTime += stopwatch.ElapsedMilliseconds;
stopwatch.Restart();
MergeSort((int[])array.Clone());
stopwatch.Stop();
totalMergesortTime += stopwatch.ElapsedMilliseconds;
}
Console.WriteLine($"Quicksort took an average of {totalQuicksortTime / numOfTestsPerLength} milliseconds to sort arrays with a length of {i}.");
Console.WriteLine($"Mergesort took an average of {totalMergesortTime / numOfTestsPerLength} milliseconds to sort arrays with a length of {i}.");
Console.WriteLine();
}
}
Даже когда я печатаю прошедшие миллисекунды каждого запуска вместо их усреднения, они все равно умножают только на нули.
изменить: Вот мои методы (извините, если они немного бесполезны):
static void Main(string[] args)
{
RunDiagnostics(new int[] { 3, 12 }, 1000);
}
public static int[] GetArray(int length, int[] RangeOfNumbers)
{
Random rng = new Random();
int[] arr = new int[length];
for (int i = 0; i < arr.Length; i++)
arr[i] = rng.Next(RangeOfNumbers[0], RangeOfNumbers[1]);
return arr;
}
public static void QuickSort(int[] array)
{
QuickSort(0, array.Length - 1);
void QuickSort(int left, int right)
{
if (right > left)
{
if (right - left == 1)
{
if (array[left] > array[right])
Swap(left, right);
}
else
{
Swap(GetStartingPivotIndex(), right);
int pivot = Partition(left, right - 1);
QuickSort(left, pivot - 1);
QuickSort(pivot + 1, right);
}
}
int GetStartingPivotIndex()
{
if (array[left] > array[right])
{
if (array[left + (right - left) / 2] > array[right])
return right;
else
return left + (right - left) / 2;
}
else
{
if (array[left + (right - left) / 2] > array[left])
return left;
else
return left + (right - left) / 2;
}
}
int Partition(int low, int high)
{
while (low != high)
{
if (array[low] < array[right])
low++;
else if (array[high] > array[right])
high--;
else
Swap(low, high);
}
Swap(low, right);
return low;
}
void Swap(int index1, int Index2)
{
int temp = array[index1];
array[index1] = array[Index2];
array[Index2] = temp;
}
}
}
public static void MergeSort(int[] array)
{
MergeSort(array);
int[] MergeSort(int[] array)
{
int[] array1 = array.Take(array.Length / 2).ToArray();
int[] array2 = array.Skip(array.Length / 2).ToArray();
if (array1.Length > 1)
MergeSort(array1);
if (array2.Length > 1)
MergeSort(array2);
int c1 = 0;
int c2 = 0;
bool flag1 = false;
bool flag2 = false;
for (int i = 0; i < array.Length; i++)
{
if (flag1 && !flag2)
{
array[i] = array2[c2];
if (c2 == array2.Length - 1)
flag2 = true;
else c2++;
}
else if (flag2 && !flag1)
{
array[i] = array1[c1];
if (c1 == array1.Length - 1)
flag1 = true;
else c1++;
}
else if (!flag1 && !flag2)
{
if (array1[c1] < array2[c2])
{
array[i] = array1[c1];
if (c1 == array1.Length - 1)
flag1 = true;
else c1++;
}
else
{
array[i] = array2[c2];
if (c2 == array2.Length - 1)
flag2 = true;
else c2++;
}
}
}
return array;
}
}
Помимо того, что сказал @Austin, если вы хотите правильно измерить производительность, подумайте о том, чтобы попробовать BenchmarkDotNet
@Austin Остин Я добавил свои методы (извините, если это беспорядок. Все еще новичок в этом деле).
Если
rangeOfLengthsToTestсодержит только два значения, почему бы просто не взять дваint? Кроме того, если секундомер работал, вы включаете времяarray.Clone()и приведение результата кint[]для обоих видов. Конечно, они могут быть одинаковыми для обоих видов, но они могут отличаться. Я предлагаю убрать его и дважды позвонить поGetArray. Я бы также просто использовал метод из одной из криптобиблиотек, чтобы получить массив случайных чисел.stopwatch.ElapsedMillisecondsвозвращает целочисленное значение и возвращает ноль, если истекшее время меньше одной миллисекунды. Попробуйте вместо этого использоватьstopwatch.Elapsed.TotalMilliseconds, который представляет собой значение с плавающей запятой и обеспечивает точность менее миллисекунды.@HereticMonkey: Даже если бы они стоили одинаково, разница в % между обоими методами сортировки тогда фальсифицируется, поэтому я бы никогда не стал измерять несвязанные вещи, если это возможно.
@Austin также добавил main. В нем действительно нет ничего интересного.
@JosephDaSilva Это было так. Спасибо.
Не помещайте ответы в вопрос. Просто опубликуйте свой собственный в соответствующем поле.
Не пишите свой собственный код для измерения производительности. Скорее всего, вы ошибетесь. BenchmarkDotNet специально предназначен для тестирования производительности и помогает вам правильно протестировать его, чтобы вы могли быть уверены в результате.
@mason В основном это должно было быть просто простым способом понять различия, но когда я увидел, что это не работает, я хотел понять, почему.
@LarsTech должен ли я по-прежнему оставлять реализацию своих методов в ответе, даже если они не связаны с проблемой? Похоже, это не будет полезно для тех, у кого такая же проблема в будущем...