Finding first unique number.

Introduction

Recently I took a test to find the first unique number in an array.  I did manage to produce the right answer but it was computationally too expensive.  This post is the result of looking into alternatives

Original Solution

var y = numberArray.GroupBy(z => z).Where(z => z.Count() == 1)
                                   .Select(z => z.Key).ToList();
 if (y.Count > 0) actual = y[0];

Alternatives

I asked for help on Stack Overflow as I wanted to see how other devs approached the solution and the following are alternatives where suggested.

1. Change from y.Count to y.Any
2. numberArray.GroupBy(g => g).Where(w => w.Count() == 1).Select(s =>    s.Key).FirstOrDefault();
3. numberArray.ToLookup(x => x).First(x => x.Count() == 1).Key;
4. numberArray.GroupBy(x => x).First(x => x.Count() == 1).Key;

In order to make head or tail of the speed difference I decided to run some tests, the template for each test is.

    var sw = new System.Diagnostics.StopWatch2() { ShowStatsForEachLoop = false };
    int actual = 0;
    //////////////////////////////////////
    sw.Restart();
    sw.Start();
    for (int i = 0; i < Iterations; i++)
    {
       ///
         Find comparison here
       ///
        sw.RestartAndLog();
    }
    sw.Stop();

Test Results

All solutions where run 50 times with an array of 9 numbers the last number being the unique number.
The results below record the average number of CPU ticks for each test.

Ticks
   Min   Max     Avg  Result
    2  14502     584  -3     Original
    2    919      40  -3     if (y.Any()) actual = y[0];
    2   1423      60  -3     a.GroupBy(g => g).Where(w => w.Count() == 1)
                                            .Select(s => s.Key)
                                            .FirstOrDefault();
    2   1553      65  -3     a.ToLookup(i => i).First(i => i.Count() == 1).Key;
    2    317      15  -3     a.GroupBy(i => i).First(i => i.Count() == 1).Key;
    1     4        2  -3     Traditional method.

Conclusion

If using LINQ switching to use .Any() was surprising how big a difference it made.
The other surprise was the difference between .GroupBy() and .ToLookup()

Using a traditional nested-loop produces very much faster results.

actual = -1;
for (int a = 0; a < numberArray.Length; a++) {
    bool unique = true;
    for (int b = 0; b < numberArray.Length; b++) {
        if (a == b)
        continue;
        if (numberArray[a] == numberArray[b]) {
            unique = false;
            break;
        }
    }
    if (unique) {
        actual = numberArray [a];
        break;
    }
}

Source Code

The source code can be found on gitHub @ https://github.com/hungrydev/FirstUniqueNumberExporation

 Acknowledgments

Git hub user Momenso for implementing the traditional method.

Those who responded to my StackOverflow question http://stackoverflow.com/questions/24603994/find-first-unique-number/24629083#24629083

 

 

CodeProject