2

Задание звучит следующим образом:

Разработать программу для сравнения эффективности двух алгоритмов сортировки путем их одновременного запуска на случайном массиве из 500 000 целых чисел (случайные числа генерировать в диапазоне от 0 до 1000 000). Для повышения точности сравнения проводить сортировку каждым из алгоритмов не менее 10 раз. Результаты усреднять.

Проблема в том, что программа сортирует массив на первой итерации и дальше опять проходит уже по отсортированному. каким образом мне нужно исправить код, чтобы у меня после каждой итерации отсортированный массив замещался исходным для повторной сортировки? вот код:

class Program
{

    static void Main(string[] args)
    {
        int length = Convert.ToInt32(Console.ReadLine());
        int[] arr = new int[length];
        ArrayRandomizer(arr);
        int[] copyarr = new int[length];
        for (int i = 0; i < arr.Length; i++) {
            copyarr[i] = arr[i];
        }

            Thread t1 = new Thread(new ParameterizedThreadStart(shellSort));
            t1.Start(arr);

            Thread t2 = new Thread(new ParameterizedThreadStart(BubbleSort));
            t2.Start(copyarr);

        Console.Read();

    }
    static int[] ArrayRandomizer(int[] Arr)
    {
        Random rand = new Random();
        for (int i = 0; i < Arr.Length; i++) 
        {
            Arr[i] = rand.Next(0, 1000000);
        }
        return Arr;
    }

    static void shellSort(object ara)
    {
        int[] arr = (int[])ara;

        Stopwatch sw = new Stopwatch();
            sw.Start();
            double[] exectime = new double[10];
            double result=0;
            int index = -1;
            for (int k = 0; k < 10; k++)
            {
                int j;
                int step = arr.Length / 2;
                while (step > 0)
                {
                    for (int i = 0; i < (arr.Length - step); i++)
                    {
                        j = i;
                        while ((j >= 0) && (arr[j] > arr[j + step]))
                        {
                            int tmp = arr[j];
                            arr[j] = arr[j + step];
                            arr[j + step] = tmp;
                            j -= step;
                        }
                    }
                    step = step / 2;
                }

                sw.Stop();
                Console.WriteLine("поток с сортировкой шелла: " + (sw.ElapsedMilliseconds) + " миллисекунд");
                index++;
                exectime[index] = sw.ElapsedMilliseconds;
                sw.Reset();
            }
            for (int n = 0; n < exectime.Length; n++) 
            {
                result += exectime[n];
            }
            Console.WriteLine("Среднее время выполнения шелла: " + result / exectime.Length);

        Thread.Sleep(0);
    }
    static void BubbleSort(object copyara)
   {
            int[] arr = (int[])copyara;
            Stopwatch sw = new Stopwatch();
            sw.Start();
            double[] exectime = new double[10];
            double result = 0;
            int index = -1;
            for (int m = 0; m < 10; m++)
            {


                for (int i = 0; i < arr.Length; i++)
                {
                    for (int j = 0; j < arr.Length - i - 1; j++)
                    {
                    if ((arr[j] > arr[j + 1]))
                        {
                            int temp = arr[j];
                            arr[j] = arr[j + 1];
                            arr[j + 1] = temp;
                        }
                    }
                }

                sw.Stop();
                Console.WriteLine("поток с сортировкой пузырьком: " + (sw.ElapsedMilliseconds) + " миллисекунд");
                index++;
                exectime[index] = sw.ElapsedMilliseconds;
                sw.Reset();
            }
            for (int n = 0; n < exectime.Length; n++)
            {
                result += exectime[n];
            }
            Console.WriteLine("Среднее время выполнения пузырька: " + result / exectime.Length);

            Thread.Sleep(0);
   }
}
2
  • 1
    По-моему, делать тест двух разных алгоритмов одновременно неправильно: массивы по 500000 элементов не влезут в кэш-память процессора, а значит, данные будут подтягиваться из основной памяти в процессе работы. И два одновременно работающих потока будут мешать друг другу. То есть пропускная способность шины памяти может оказаться решающей. Так что тестируйте ваши алгоритмы последовательно. Commented 16 нояб. 2016 в 5:57
  • 1
    Я бы изменил заголовок вопроса на "Сравнение сортировок по времени" или что-то подобное, для соответствия вопросу
    – rdorn
    Commented 16 нояб. 2016 в 6:30

2 ответа 2

2

Чтобы использование массивов вообще не влияло на измерения, то на вход можно передать не один массив, а массив из 10 одинаковых массивов, что впрочем может потребовать лишней памяти.

Соответственно можно копировать массив перед каждым запуском, например Array.Copy() - его же лучше использовать и в начала вместо цикла. Исследование https://stackoverflow.com/questions/5099604/any-faster-way-of-copying-arrays-in-c гласит, то этот метод работает со скоростью копирования памяти. На время копирования массива Stopwatch можно выключать.

2

Как альтернатива предложенному варианту, если вы ограничены по памяти, можно вспомнить, что Random не является настоящим ГСЧ и зависит от начального значения (seed). Если перед генерацией последовательности указать в конструкторе new Random(seed), то последовательность будет генерироваться всегда одинаковая. Это работает медленнее чем копирование, но уменьшает расход памяти до одного массива на все исследуемые методы сортировки.

StopWatch включать строго перед вызовом исследуемого метода и выключать после его завершения.

Про особенности замеров времени почитайте тут, если еще не читали конечно https://ru.stackoverflow.com/a/547742/198316

И забудьте про потоки если нужны нормальные измерения, они только в теории работают параллельно, на практике, они могут и будут мешать друг другу, особенно на долгих операциях с большими данными. Не смотря на количество ядер в современных процессорах, у них как минимум есть общий кэш 3-го уровня, который придется постоянно перечитывать переключаясь между потоками, и нет гарантии, что потоки будут работать на разных ядрах, они вполне могут быть запущены на одном ядре по усмотрению ОС.

1
  • Кстати, хорошая идея с seed. Commented 16 нояб. 2016 в 6:20

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.