Finding the minimum difference in a list of numbers

I have written following code to find the minimum difference from a list of numbers.

Because I am using a loop once and LINQ again to find the minimum, the algorithm is O(N2).

Can you please tell me if I am using the framework in the most optimal way (speed and memory utilisation) to achieve this task:

using (StreamReader sr = new StreamReader("IN.in"))
using (StreamWriter sw = new StreamWriter("OUT.out"))
{
    int T = int.Parse(sr.ReadLine());
    for (int i = 1; i  intList = sr.ReadLine().Split(' ').Select(e => int.Parse(e)).ToList();
        intList.Sort();

        List diff = new List();
        int leastDiff = int.MaxValue;
        for (int k = 0; k < intList.Count - 1; k++)
        {
            int iDiff = intList[k + 1] - intList[k];
            diff.Add(iDiff);
            leastDiff = Math.Min(leastDiff, iDiff);
        }
        sw.WriteLine(leastDiff);
    }
}

Benchmark

For 3 test case of 5 integers in each list where as for loop implementation takes 55±5 ms. Mr.Mindor LINQ implementation timing varies from 60±50 ms. Memory usage in both implementation is almost 8.3MB

You're worrying about the wrong problems: there isn't a lot more performance to be squeezed out of your code, but you could make substantial improvements to readability.

-
Choose a better file format

Why are you encoding the number of lines to be read into the file itself? That seems like redundant information. Just read all the lines there are and use those. You are also redundantly encoding the number of numbers per line: int N = int.Parse(sr.ReadLine());

You aren't doing anything with the parsed value, which is an indication that it shouldn't be in the file to start with.

-
Make your code reusable

Why not define the algorithm for finding the smallest difference inside an extension method? This allows you to separate the concerns of I/O and your minimum difference finding logic.

public static int SmallestDifference(this IEnumerable source)
{
    var numbers = source as int[] ?? source.ToArray();
    Array.Sort(numbers);
    int difference = int.MaxValue;
    for (int i = 1; i < numbers.Length; i++)
    {
        difference = Math.Min(difference, numbers[i] - numbers[i - 1]);
    }
    return difference;
}

-
Be expressive

Using the deferred execution streaming File.ReadLines method together with an expressive LINQ query, you can write code that reads fluently and makes sense rather than confusing the reader with details:

var minDifferences = from line in File.ReadLines("IN.in")
                     let numbers = from number in line.Split(' ')
                                   select int.Parse(number)
                     select numbers.SmallestDifference().ToString();
File.WriteAllLines("OUT.out", minDifferences);

Now here's a tiny surprise left for the end:


This solution consistently performs at least as well as your original code.

(On average, it's a couple of milliseconds faster per fifty thousand lines, but that's in the realm of microbenchmarking which should be avoided. Just trying to give you a rough idea.)

So stop worrying about performance; strive for clean code instead.

EDIT: I understand that you can't change the format (as per your comment), so I've added the code below to allow you to stick with your current file layout. The modification required is tiny: simply skip the first line, and only look for the smallest difference in lines that have more than one number.

var minDifferences = from line in File.ReadLines("IN.in").Skip(1)
                     let numbers = from number in line.Split(' ')
                                   select int.Parse(number)
                     where numbers.Count() > 1
                     select numbers.SmallestDifference().ToString();
File.WriteAllLines("OUT.out", minDifferences);

StackExchange Code Review Q#15555, answer score: 8