Good day to all, I need your help, in general I have a bubble sorting algorithm, I implemented it (I will give the code below) but now I want to know how to write the counting of the counting time, and the memory access time for numbers 5,100,1000, 10000, 100000 items. Share the code and your experience, thanks in advance.

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(); } } }
  • Why minus? Who set can explain? - Ethernets

3 answers 3

OK. Now how to measure time relatively correctly.

1. Problems

  • real time of the algorithm can be measured in microseconds and less.
  • the operation of other programs and services running on the computer at the same time may affect the algorithm’s work time, while we are working in a multitasking environment.

2. Decision in the first approximation

Eliminate the influence of the external environment. Completely of course, it will not be eliminated, but it is quite possible to reduce the influence. To do this, instead of a single measurement, we make N (N> 100, it is selected depending on the algorithm). We consider the total execution time and divide by the number of iterations - we get the average execution time, which will smooth out spontaneous bursts of environmental activity and give us a more plausible picture.

In the simple case, the measuring code will look like this:

 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);

There is one such solution, but a huge disadvantage; the result will represent the “average hospital temperature,” even with a large number of measurements. This is due to the fact that the system clock has an accuracy of the order of one millisecond, and this is enough only for a very rough estimate of very slow algorithms.

3. Increase accuracy

@ 3per in his response correctly drew attention to the class Stopwatch . We will use it. Modify the code above:

 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);

This option will show the average, but still closest to reality, the execution time of your algorithm. A further increase in accuracy is possible by increasing the number of measurements. This approach will allow you to quite accurately compare the time of work of different algorithms or one algorithm on different data sets, but the absolute accuracy will not still not be too high.

4. Preliminary data preparation

For algorithms like sorting, you need to take care of the preliminary preparation of data for measurements. This is primarily needed in order to ensure equal conditions at each iteration of the measurements and minimize the impact of the time of obtaining a new data set. If we, for example, want to estimate the sorting time by simple inserts, then it has the best and the worst set of input data. This should be taken into account when measuring and, in general, a random data set may not be the best choice. In addition, it should be noted that filling the sorted array with new data also takes time.

There are two options for solving the problem: prepare in advance a set of data arrays for sorting equal to the number of iterations, or measure in advance the average time of filling or copying an array and subtract it from the average measured time.

Of course, you can use more sophisticated techniques, but I'm not sure about their usefulness and effectiveness.

5. For perfectionist maniacs

You can even increase the accuracy by setting the maximum priority to the process in which measurements are performed, disable all unnecessary background programs, especially antiviruses, stop unnecessary services and generally unload the system, reducing the list of simultaneously running programs and services to an absolute minimum. Of course, VisulStudio should also be turned off and the measuring program should be started without debug mode with a preliminary warm-up of the classes used in the measurements.

"Warming up" is a preliminary reference to the class and the necessary methods in order to preload the assembly in which the desired class is located and feed the required classes and methods to the Jit compiler. This will avoid loss of time for these operations during measurements and, as a result, distortion of measurement results. The simplest version of the “warm-up” will be to start one iteration of the measurement without considering the result, and after that start the main measurement cycle.

counting counting time, and memory access time

The time of access to memory is an integral part of the time of the algorithm, and has a very insignificant independent value, because is determined mainly by the hardware parameters of the system. Two criteria are used to evaluate the algorithms: the running time of the algorithm and the amount of additional memory required, but not the time to access it. In other details, the evaluation of the algorithms deserves a separate question, and it seems that the answer to it is already given here.

  • one
    It makes sense to write briefly what warming is and why it is important. And yet, my code even in the Release-mode under Visual Studio ran twice (!) More slowly than without Visual Studio. - VladD 2:55 pm
  • Many thanks for such a detailed answer. Everything is clear and understandable - Ethernets
  • @VladD in early versions of the studio is not so noticeable, but the analyzer in VS2015 is just hard. He is also able to gobble up memory 2-4 Gb without looking = ( - rdorn
  • @VladD besides, even when running the Release configuration, the debugger still clings to the process. - rdorn 3:12 pm
  • Yeah, and the memory consumption also happens instantly, so ... - VladD

In there is a special class for calculating runtime - Stopwatch

 var stopwatch = Stopwatch.StartNew(); ...//ваш код stopwatch.Stop(); MessageBox.Show(string.Format("{0} миллисекунд затрачено", stopwatch.ElapsedMilliseconds));
  • Thank you too - Ethernets

java

Before you start sorting write

 long before = System.currentTimeMillis();

After sorting

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

On C #, approximately,