LeetCode's C# timing for this problem isn't useful?


  • 0
    I

    After experimenting a bit, I found that my C# solutions for hamming distance had unexpected timings. They seemed much too close to each other and somewhat random. I'm guessing there is some other cost in the test harness itself which is overwhelming the actual algorithm costs?

    As an example, here is some code you can paste into LinqPad (in C# Program mode) which on each run generates two random ints and runs each of the three functions 5mil times to get the avg cost in nanoseconds.

    With compiler optimizations on (click the /o+ in the bottom right corner of LinqPad), on my machine it has the method using Linq at around 500ns, the one using shift and & 1 is around 16ns and the one with & one less is around 9ns. I know my test harness isn't perfect but that kind of spread is what I'd expect judging from discussions of the different algorithms online.

    Using LeetCode, I submitted each algorithm three times. The first algorithm was 49/53/55ms, the second 46/48/52ms and the last was 43/45/46ms. While the average is trending toward being in the right order, I'm pretty sure it shouldn't be possible for the second algorithm to take longer than the first.

    Any thoughts? This was my first time using Leetcode, so I don't know if this happens a lot?

    void Main()
    {
    	var times = 5000000;
    	var rand = new Random();
    
    	var x = rand.Next();
    	var y = rand.Next();
    //	var x = B("010");
    //	var y = B("100");
    
    	DumpBin(x);
    	DumpBin(y);
    	
    	LinqWay(x, y).Dump();
    	ShiftWhile(x, y).Dump();
    	ShiftMinus(x, y).Dump();
    	
    	Profile(times, x, y, LinqWay);
    	Profile(times, x, y, ShiftWhile);
    	Profile(times, x, y, ShiftMinus);
    }
    
    int LinqWay(int x, int y) {
    	return Convert.ToString(x ^ y, 2).Count(n => n == '1');
    }
    
    int ShiftWhile(int x, int y) {
    	var diff = x ^ y;
    	var result = 0;
    	while (diff > 0) {
    		result += diff & 1;
    		diff >>= 1;
    	}
    	return result;
    }
    
    int ShiftMinus(int x, int y) {
    	var diff = x ^ y;
    	var result = 0;
    	while (diff > 0) {
    		diff &= (diff - 1);
    		result++;
    	}
    	return result;
    }
    
    void DumpBin(int num) {
    	PrintBin(num).Dump();
    }
    
    int B(string bin) {
    	return Convert.ToInt32(bin, 2);
    }
    
    string PrintBin(int num) {
    	return Convert.ToString(num, 2).PadLeft(32, '0');
    }
    
    void Profile(int times, int x, int y, Func<int, int, int> func) {
    	var rand = new Random();
    	var before = Util.ElapsedTime;
    	for (var i = 0; i < times; i++) {
    		func(x, y);
    	}
    	var elapsed = Util.ElapsedTime - before;
    	var avgNano = (elapsed.TotalSeconds * 1000000000) / times;
    	Math.Round(avgNano).ToString().PadLeft(5, '0').Dump();
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.