0

Let be the following binary search function:

public static bool BinarySearching(int[] array, int searchValue)
{
    Array.Sort(array);
    double p = 0;
    double q = 0;
    int r = array.Length - 1;

    while (p <= r)
    {
        q = Math.Floor((p + r) / 2);

        if (array[(int)q] == searchValue)
        {
            return true;
        }

        else if (array[(int)q] != searchValue && array[(int)q] > searchValue)
        {
            r = (int)(q - 1);
        }

        else if (array[(int)q] != searchValue && array[(int)q] < searchValue)
        {
            p = (int)(q + 1);
        }
    }

    return false;
}

}

If we want to measure its execution time, we would do something like 

var watch = System.Diagnostics.Stopwatch.StartNew();
BinarySearching(int[] array, int searchValue);
watch.Stop();
var elapsedMs = watch.ElapsedMilliseconds;

But is it any more bautiful way to measure like through the separate function, such that varaible is calculated function itself? For example, in pseudocode it is 

public static string ComplexityCounter(bool algorithm(int[] array, int searchValue))
{
    var watch = System.Diagnostics.Stopwatch.StartNew();
    algorithm(int[] array, int searchValue);
    watch.Stop();
    var elapsedMs = watch.ElapsedMilliseconds;
    string result = elapsedMs.ToString();
    return result;
}

And, sure it doesn't work in terms of C#, can you help me to revise it or to propose your own try ? The most interesting is to find such structure for all algorithms regardless of the type of variable it produces.

Rand Random
  • 7,300
  • 10
  • 40
  • 88
Petro Kolosov
  • 169
  • 9
  • 1
    Unrelated to your question, but what is the point in making p and q `double` and then doing all the `int` casting bonanza throughout your code? Why not making these two variables of type `int`? –  Mar 12 '19 at 15:08
  • i did double, bacuse otherwise it goes warning from `Math.Floor()` , its generic variable type is double – Petro Kolosov Mar 12 '19 at 15:13
  • Well, why would you need to use Math.Floor? There is no necessity to use this method, no? –  Mar 12 '19 at 15:16
  • How is it not necessary to use Math.Floor if floor function is in Binary Search algorithm by definition ? – Petro Kolosov Mar 12 '19 at 15:22
  • The answer is: simple integer division. This is how it is not neccessary to use Math.Floor here. Integer division per definition is rounding towards zero. Now, since in your algorithm here `p+r` will not become negative (correct me if i am wrong), the division `(p+r)/2` is a division with a non-negative result. For non-negative results, rounding towards zero is equivalent to floor rounding. (Even if there were the possibility of `p+r` becoming negative, there are other ways to deal with such a scenario that don't require double/int ping-pong... –  Mar 12 '19 at 15:26
  • I will study on it after – Petro Kolosov Mar 12 '19 at 15:49

3 Answers3

0

You can pass an Func<bool> as an argument like so:

public static TimeSpan Measure(Func<int[], int, bool> method, int[] arg1, int arg2)
{
    var stopwatch = new Stopwatch();
    stopwatch.Start();
    var result = method.Invoke(arg1, arg2);
    stopwatch.Stop();
    return stopwatch.Elapsed;
}

and then you can invoke it like so:

var timeTaken = Measure(MethodToMeasure, new [] {1, 2, 3}, 1);
Kieran Devlin
  • 1,373
  • 1
  • 12
  • 28
  • It works noramally and gives proper result in terms of microseconds, altrough it still looks complicated and requires fixes to be used on different type of functions – Petro Kolosov Mar 12 '19 at 16:25
  • but combining your answer with answer of @Malior gives desireable result, I'd give you up vote if i cound have at least 15 rep :) – Petro Kolosov Mar 12 '19 at 16:29
0

I suggest you to accept an Action, thats more generic and you can use it for much more functions. You can then call it using a lamda expression. Example:

    private static long MeasureDuration(Action algorithm)
    {
        var watch = System.Diagnostics.Stopwatch.StartNew();

        algorithm.Invoke();

        watch.Stop();

        return watch.ElapsedMilliseconds;
    }

I linke using .Invoke(), it's making it easier to understand that this is an action that been called.

and call it like this:

  bool found;
  var result = MeasureDuration(() => found = BinarySearching(myArray, mySearchValue));
Malior
  • 1,221
  • 8
  • 16
  • your solution is enough good, but when I apply it in my code i get time spent = 0 – Petro Kolosov Mar 12 '19 at 15:28
  • you mean the result variable is 0 at the end? That's qite strange. One mine it works. But I added a thread sleep. How long is your array.. Maybe it's just to quick to measure in milli seconds. Add some System.Threading.Thread.Sleep(500) to check, if it's because of this. – Malior Mar 12 '19 at 15:38
  • I prefer this to be as answer and this is exactly that i meant, but it doesn't work for boolean – Petro Kolosov Mar 12 '19 at 15:40
  • Yes, the method is too quick and it works now with System.Threading.Thread.Sleep(500), but still, how to change the milli seconds to micro seconds ? – Petro Kolosov Mar 12 '19 at 15:43
  • What do you mean with "does not work for bool" ? About micro seconds, this is another topic. I recommend this question https://stackoverflow.com/questions/1206367/c-sharp-time-in-microseconds. Instead of using stopwatch, just make DateTime.Now before and after, and subtrack both from each other. you get a TimeSpan. – Malior Mar 12 '19 at 15:50
  • It always gives elapsed time = 0, even i look through array of 10^5 dimmension, so i think its still doesn't work – Petro Kolosov Mar 12 '19 at 16:17
  • Solved as follows: `public static TimeSpan Measure(Action method) { var stopwatch = new Stopwatch(); stopwatch.Start(); method.Invoke(); stopwatch.Stop(); return stopwatch.Elapsed; }` – Petro Kolosov Mar 12 '19 at 16:32
0

Assuming you don't want to discard the result of the algorithm as in the Action based answer, the most generic way to implement it is probably to make the method generic in the return type, and bind the input parameters of the algorithm inside the lambda expression, which thus has type Func<T>. I'm assuming you can use the new C# 7 tuple syntax

private static (T, long) GetResultAndDuration<T>(Func<T> algorithm)
{
   var watch = System.Diagnostics.Stopwatch.StartNew();

   T result = algorithm();

   watch.Stop();

   return (result, watch.ElapsedMilliseconds);
}

And you can call it as follows:

(var result, var duration) = GetResultAndDuration(() => MyCoolAlgorithm(42, "some param"));
Jonas Høgh
  • 10,358
  • 1
  • 26
  • 46