Finding the minimum difference in a list of numbers

Question

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(N²).

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 <= T; i++)
    {
        int N = int.Parse(sr.ReadLine());
        List<int> intList = sr.ReadLine().Split(' ').Select(e => int.Parse(e)).ToList();
        intList.Sort();

        List<int> diff = new List<int>();
        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

Answer 1

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

Answer 2

First of all using LINQ method Min is not making this algorithm \$O(n^2)\$. If you want to avoid this call, you can calculate min "in-place":

//...

var min = int.MaxValue;

for (int k = 0; k < intList.Count-1; k++)
{
    min = Math.Min(min, intList[k + 1] - intList[k]);
}

sw.WriteLine(min); 

//...

Anyway, the most heavy operation here is Sort. It makes this algorithm \$O(n*log n)\$.

Answer 3

As for using Linq, what you are looking for is a pairwise version of the Aggregate Extension method, which is not built in, but is not incredibly difficult to implement.

As your question is about finding the minimum difference from a list of numbers, I'm not going to touch on the source of the list.

I'm going to agree with codesparkle that you want reusability and readability.

For the extension method:

public static class Extensions
{
    public static TAccumulator PairwiseAggregate<TAccumulator,TSource>(this IEnumerable<TSource> source, TAccumulator seed, Func<TAccumulator, TSource, TSource, TAccumulator> aggregator ) 
    {
        IEnumerator<TSource> e = source.GetEnumerator();
        e.MoveNext();
        TSource current = e.Current;
        while(e.MoveNext())
        {
            TSource next = e.Current;
            seed = aggregator(seed, current, next);
            current = next;
        }
        return seed;
    } 
}

Then the smallestDifference method:

    public static int SmallestDifference(this IEnumerable<int> source)
    {
        return source.OrderBy(i => i).PairwiseAggregate(int.MaxValue, (seed, first, second) => Math.Min(seed, second-first));

    }

PairwiseAggregate is \$O(n)\$.

The \$O(n log n)\$ of SmallestDifference is ruled by the O(n log n) of the OrderBy (quick sort).

If you don't want to use the default Sorting Algorithm, then an extension can be written for that as well.

Answer 4

For one thing, arrays are more efficient than Lists. If you know how big the collection is going to be you should opt for an array instead. This is the case for your diff collection.

However, you can skip having a diff collection altogether and just keep track of the smallest diff so far:

int smallestDiff = int.MaxValue;
for(int k = 0;k < intList.Count - 1; k++)
    smallestDiff = Math.Min(smallestDiff, intList[k + 1] - intList[k]);

You're also needlessly using a List for your intList collection:

int[] intList = sr.ReadLine().Split(new char[] { ' ' }, SplitOptions.None).Select(e => int.Parse(e)).ToArray();
Array.Sort(intList);