2

Всем доброго времени суток, мне нужна ваша помощь, вообщем есть у меня алгоритм сортировки пузырьком, я его реализовал (код приведу ниже) но теперь хочу узнать как написать подсчет времени счета, и время доступа к памяти для чисел 5,100,1000, 10000, 100000 элементов. Поделитесь кодом и своим опытом, заранее большое спасибо.

namespace Bubble_sort
{
    class Program
    {
        static int[] Sort(int[] arr)
        {
            for (int i = 0; i < arr.Length - 1; i++) // O(n2)
            {
                for (int j = 0; j < arr.Length - i - 1; j++) 
                {
                    if (arr[j] > arr[j + 1])
                    {
                        int buf = arr[j]; 

                        arr[j] = arr[j + 1];

                        arr[j + 1] = buf;
                    }
                }
            }
            return arr;
        }

        static void Main(string[] args)

        {
            int x = 1; // O(1)
            int[] array = new int[] { 5, 2, 3, 4, 1 };

            array = Sort(array);

            for (int i = 0; i < array.Length; i++) 
            {
                Console.WriteLine(array[i]);
            }
            Console.ReadKey();
        }
    }
}
1
  • Почему минус ? кто поставил может объяснить ?
    – Ethernets
    23 июл 2016 в 8:38

3 ответа 3

6

Ок. Теперь как измерить время относительно правильно.

1. Проблемы

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

2. Решение в первом приближении

Устраним влияние внешней среды. Полностью конечно, его устранить не выйдет, но уменьшить влияние вполне можно. Для этого вместо одного измерения, делаем N (N>100, подбирается в зависимости от алгоритма). Считаем общее время выполнения и делим на количество итераций - получаем среднее время выполнения, которое сгладит спонтанные всплески активности внешней среды и даст нам более правдоподобную картину.

В простом случае, измеряющий код будет выглядеть так:

var startTime = DateTime.Now;
for(int i = 0; i < N; i++)
{
    //ваш алгоритм здесь
}
var stopTime = DateTime.Now;
var averageTime = new TimeSpan(stopTime.Subtract(startTime).Ticks / N);
Console.WriteLine(averageTime);

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

3. Увеличиваем точность

@3per в своем ответе правильно обратил внимание на на класс Stopwatch. Им и воспользуемся. Модифицируем код выше:

using System.Diagnostics;

var stopwatch = Stopwatch.StartNew();
for(int i = 0; i < N; i++)
{
    //ваш алгоритм здесь
}
stopwatch.Stop();
var averageTime = new TimeSpan(stopwatch.ElapsedTicks / N);
Console.WriteLine(averageTime);

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

4. Предварительная подготовка данных

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

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

Разумеется можно использовать и более изощренные приемы, но в их пользе и эффективности я не уверен.

5. Для маньяков-перфекционистов

Можно еще увеличить точность, выставив максимальный приоритет процессу в котором выполняются измерения, отключить все ненужные фоновые программы, особенно антивирусы, остановить не нужные службы и вообще максимально разгрузить систему сведя список одновременно запущенных программ и служб к абсолютному минимуму. Разумеетcя VisulStudio тоже должна быть выключена и измеряющая программа должна быть запущена без режима отладки с предварительным "прогревом" классов, используемых в измерениях.

"Прогрев" - это предварительное обращение к классу и нужным методам, для того чтобы заранее загрузить сборку в которой расположен нужный класс и скормить нужные классы и методы Jit-компилятору. Это позволит избежать потери времени на эти операции во время измерений и, как следствие, искажения результатов измерений. Самым простым вариантом "прогрева" будет запуск одной итерации измерения без учета результата, а после этого уже запуск основного цикла измерений.

подсчет времени счета, и время доступа к памяти

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

5
  • 1
    Имеет смысл написать вкратце, что такое прогрев и почему он важен. И ещё, у меня код даже в Release-режиме под Visual Studio бежал вдвое (!) медленнее, чем без Visual Studio.
    – VladD
    23 июл 2016 в 14:55
  • Большое спасибо за столь подробный ответ. Все ясно и понятно
    – Ethernets
    23 июл 2016 в 14:58
  • @VladD в ранних версиях студии еще не так заметно, а вот анализатор в VS2015 - это просто жесть. Он еще и памяти сожрать может 2-4 Gb не глядя =(
    – rdorn
    23 июл 2016 в 15:09
  • @VladD к тому же, даже при запуске Release конфигурации, отладчик все равно цепляется к процессу.
    – rdorn
    23 июл 2016 в 15:12
  • Ага, и расход памяти тоже происходит на мгновенно, так что...
    – VladD
    23 июл 2016 в 15:30
6

В существует специальный класс для подсчета времени выполнения - Stopwatch

var stopwatch = Stopwatch.StartNew();
...//ваш код
stopwatch.Stop();
MessageBox.Show(string.Format("{0} миллисекунд затрачено", stopwatch.ElapsedMilliseconds));
1
  • Вам тоже спасибо
    – Ethernets
    23 июл 2016 в 14:58
1

java

Перед началом сортировки пишешь

long before = System.currentTimeMillis();

После сортировки

long after = System.currentTimeMillis();
long time = after-before;

На C#, приблизительно, так же

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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