Класс секундомера .NET ведет себя странно

Итак, у меня есть все алгоритмы поиска, и я отправляю 20000 случайных чисел каждому алгоритму, пытаясь выяснить, сколько времени займет каждый из них.

        public void functionsForSorts(int[] array)
    {
        Stopwatch sw = new Stopwatch();
        long elapsedTime = sw.ElapsedTicks;

        if (array.Length == 20000) 
        {
            sw.Start();
            BubbleSort.Bubble(array);
            sw.Stop();
            elapsedTime = sw.ElapsedMilliseconds;
            label1.Text += "\t" + elapsedTime.ToString() + " miliseconds ";
            Application.DoEvents();

            sw.Restart();
            SelectionSort.Selection(array);
            sw.Stop();
            elapsedTime = sw.ElapsedMilliseconds;
            label2.Text += "\t" + elapsedTime.ToString() + " miliseconds ";
            Application.DoEvents();

            sw.Restart();
            InsertionSort.Insertion(array);
            sw.Stop();
            elapsedTime = sw.ElapsedMilliseconds;
            label3.Text += "\t" + elapsedTime.ToString() + " miliseconds ";
            Application.DoEvents();

            sw.Restart();
            MergeSort.mergeSort(array, 0, array.Length - 1);
            sw.Stop();
            elapsedTime = sw.ElapsedMilliseconds;
            label4.Text += "\t" + elapsedTime.ToString() + " miliseconds ";
            Application.DoEvents();

            sw.Restart();
            ShellSort.Shell(array);
            sw.Stop();
            elapsedTime = sw.ElapsedMilliseconds;
            label5.Text += "\t" + elapsedTime.ToString() + " miliseconds ";
            Application.DoEvents();

            sw.Restart();
            QuickSort.Quicksort(array, 0, array.Length - 1);
            sw.Stop();
            elapsedTime = sw.ElapsedMilliseconds;
            label6.Text += "\t" + elapsedTime.ToString() + " miliseconds ";
            Application.DoEvents();
        }

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

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


person imdrunkisuppose    schedule 04.03.2013    source источник
comment
Можете ли вы показать нам весь код?   -  person Dave Bish    schedule 04.03.2013
comment
Можете ли вы попробовать провести тест с какой-нибудь другой случайной операцией, такой как label1.Tag = sw.ElapsedMillilseconds.ToString() вместо i5k.Insertion(array), просто чтобы посмотреть, имеет ли какое-либо отношение к ней операция сортировки — чтобы посмотреть, получите ли вы 0 в любой операции, выполненной в этом позиция?   -  person BlueMonkMN    schedule 04.03.2013
comment
На самом деле, если вы смотрите только на миллисекунды вместо тактов, вам придется использовать более длинную операцию, например System.Threading.Thread.sleep(1000).   -  person BlueMonkMN    schedule 04.03.2013
comment
К вашему сведению, Stopwatch является частью .NET, а не частью C#.   -  person John Saunders    schedule 04.03.2013


Ответы (4)


Если массив уже отсортирован, возможно, ваша сортировка вставками не выполнялась и завершилась менее чем за 1 миллисекунду. Это может быть возможно, если ваша предыдущая сортировка оставила массив отсортированным.

(Редактировать - мне, видимо, очень трудно набирать слово "возможно" вместо "возможно"... исправлено.)

person BlueMonkMN    schedule 04.03.2013
comment
Хороший улов; для меня сортировка 40k int занимает 3 мс из зашифрованных данных, но из этого отсортированного состояния: 0 мс время вложения - person Marc Gravell; 04.03.2013
comment
@MarcGravell Вы копируете код сортировки вставками из случайных онлайн-ресурсов, или он у вас уже есть, или вы используете встроенную быструю сортировку .NET (которая на самом деле работает медленнее для отсортированных данных, поэтому я в этом сомневаюсь), или вы просто уже вручную реализовать свою собственную сортировку вставками? - person BlueMonkMN; 04.03.2013
comment
в целях быстрого теста я просто использую Array.Sort - не то же самое, но только после теоретических ограничений здесь - person Marc Gravell; 04.03.2013
comment
@MarcGravell О, я думаю, Array.Sort действительно работает быстрее на уже отсортированных данных. Я думал, что это быстрая сортировка, и эта быстрая сортировка не работает быстрее на уже отсортированных данных, и мой тест подтвердил это. Но потом я понял, что каждый раз перетасовывал свои данные в своем цикле, и когда я перестал это делать, мое время сократилось до 0 миллисекунд на уже отсортированных данных, как и у вас. Моя память о поведении быстрой сортировки для уже отсортированных данных должна быть ошибочной, потому что MSDN действительно говорит, что Array.Sort является быстрой сортировкой. - person BlueMonkMN; 04.03.2013
comment
Хм. Быстрая сортировка предположительно имеет наихудший случай для уже отсортированных данных, но платформа .NET должна использовать некоторые приемы, описанные в stackoverflow.com/questions/2415193/, чтобы избежать легко раскрываемых наихудших сценариев. - person BlueMonkMN; 04.03.2013
comment
Ты гений, я не знаю, почему это не привлекло мое внимание раньше, я пытался отсортировать уже отсортированный список... - person imdrunkisuppose; 05.03.2013

что невозможно

с чего ты взял, что это невозможно? имейте в виду, что даже Stopwatch имеет ограниченную точность. 0 не означает, что "это не заняло времени"; это может означать «недостаточно времени для регистрации с доступной точностью». Чтобы получить разумное время для чего-то быстрого, вам часто нужно выполнить его несколько раз (то есть: тысячи или даже миллионы раз) в цикле внутри временной области. Не видя, что делает Insertion, насколько мы знаем, это нормально.

Лично я бы использовал:

sw = Stopwatch.StartNew();
// probably loop here!!
i5k.Insertion(array);
sw.Stop();
person Marc Gravell    schedule 04.03.2013
comment
читайте внимательно, это дает правильный результат, когда я запускаю только код сортировки вставки, он портится, когда я запускаю весь код, я не просто отправляю 5000 номеров, я также отправляю 10000, 20000 и 40000, возможна ли вставка sort, чтобы отсортировать все эти числа за 0 миллисекунд? - person imdrunkisuppose; 04.03.2013
comment
@imdrunkisuppose, как я могу ответить на этот вопрос, не видя вашего кода вставки? Но да: компьютеры быстрые. Действительно быстро. - person Marc Gravell; 04.03.2013
comment
@imdrunkisuppose моя локальная машина может сортировать массив из 40 тыс. целых чисел за 3 мс. Если у вас мощная коробка, 0 мс не является необоснованным. - person Marc Gravell; 04.03.2013
comment
хорошо, так как основная логика поиска со вставками такая же, и это не так быстро, кстати, мои случайные числа могут быть в 4 раза больше, чем длина массивов, и поскольку я сказал, что код дает правильный результат, когда я просто комментирую другие функции и просто отправьте этот, он показывает правильный результат, даже за 5к. - person imdrunkisuppose; 04.03.2013
comment
Вы сбрасываете массив между каждым запуском, согласно ответу BlueMonkMN? - person jszigeti; 04.03.2013

 elapsedTime = sw.ElapsedMilliseconds;

Миллисекунда — это очень долго, современный процессор может выполнять миллионы инструкций за мс. Достаточно, чтобы выполнить сортировку вставками менее чем за одну миллисекунду, поэтому ElapsedMilliseconds возвращает 0. Не отказывайтесь от разрешения, которое вы получаете из секундомера, вместо этого используйте его свойство Elapsed.

person Hans Passant    schedule 04.03.2013

Не используйте Stopwatch.ElapsedMilliseconds, который вернет 0, если операция заняла менее 1 миллисекунды.

Вместо этого используйте Stopwatch.ElapsedTicks. А также сделайте то, что Марк сказал выше.

person Matthew Watson    schedule 04.03.2013