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"))
{
for (int i = 1; i <= T; i++)
{
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];
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

migrated from stackoverflow.comSep 12 '12 at 23:35

This question came from our site for professional and enthusiast programmers.

• O(N2) == O(N) so don't worry. Your main cost here is I/O, not the calculations. – Henk Holterman Sep 11 '12 at 16:26
• Premature optimization is the root of all evil. If you have enough memory (you almost certainly have way more than you need) don't worry about it. If your program isn't taking too long (it almost certainly isn't) then don't worry about it. You should focus on making your code work correctly first, making it easily understandable and readable second (so it can be well maintained) and only look at performance last if your program is unacceptably slow or uses too much memory. – Servy Sep 11 '12 at 16:38
• By O(N2) did you mean "n squared"? Cos that's a bit of an important distinction, and one worth editting your question to clarify. – Rook Sep 11 '12 at 16:40
• @ie. I never had an assignment that encouraged excessive micro-optimization. If that is the case, all the more reason to assert that it's not a good idea because he is being taught bad principles. – Servy Sep 11 '12 at 16:43
• At the risk of sounding like a broken record, wrap your IDisposable types (StreamReader and StreamWriter) in using blocks and get rid of the need to call Close() explicitly. – Jesse C. Slicer Sep 13 '12 at 1:23

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.

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.)

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

• codesparkle, Last two points has been really helpful. But coming to first point unfortunately I can not play with file format and this has been created keeping in mind programmer may read file from C/C++ as well, where specifying, no. of items N, present on a particular line can simplify file i/o for the programmer. – Abhijeet Sep 13 '12 at 17:41
• So deferred execution to read lines using LINQ, will not be make the code cleaner, as again I'll have to write if conditions inside LINQ to skip evaluating SmallestDifference() when reading T or N from file. – Abhijeet Sep 13 '12 at 17:46
• @autrevo I understand your first comment, but I disagree with your second: As you can see, the change only adds a single line. – Adam Sep 13 '12 at 18:11

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)$.

• If you have a lot of numbers per list, it might be worth switching to an O(n) sorting algorithm (e.g., bucket sort). – Brian Sep 11 '12 at 16:29
• @Brian agree! but we have no idea about input data restrictions, TS does not give us them. – ie. Sep 11 '12 at 16:37
• I was suggesting this to the OP as a means of fixing the bottleneck that you point out. – Brian Sep 11 '12 at 16:44
• Finding minimum in the same loop is definitely reasonable step. I wonder, how can we convert this loop to linq, and will there be any performance improvment ? for (int k = 0; k < intList.Count-1; k++) { int iDiff = intList[k + 1] - intList[k]; diff.Add(iDiff); min = Math.Min(min, iDiff); } – Abhijeet Sep 13 '12 at 8:54
• @autrevo you will not get the performance improvement if you use LINQ instead of for-loop. – ie. Sep 14 '12 at 10:08

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.

• I am curious to know the difference between complexity of algorithm, thus advantage of using orderby. Please fill in above O() blank spaces. – Abhijeet Sep 13 '12 at 19:28
• Just to share results, for 3 test case of 5 integers in each list where as for loop implementation takes 55+-5 ms. LINQ implementation timing varies from 60+-50 ms. Memory usage in both implementation is almost 8.3MB – Abhijeet Sep 13 '12 at 19:40
• @autrevo I used OrderBy over an in-place sort in my SmallestDifference method to not alter the original. I did not explicitly copy to an array as codesparkle did for simplicity and readability. What method are you using to get those numbers? And for very small arrays, any overhead in setting up a particular sorting algorithm is going to dominate the time it takes to sort and you are often better off sorting with some naive method. If you truely want to compare you are going to need much larger arrays. – Mr.Mindor Sep 14 '12 at 3:10

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

• The performance difference between using an array and a list is almost nothing. There is very, very little overhead involved in wrapping the array access with the List. Also note that you don't know the number of elements when creating the array, so the array creation will not be any more efficient than using a List. – Servy Sep 11 '12 at 16:35
• "Almost nothing" is still something. Since this question was specifically about performance, I stand by my assertion. Are you suggesting that arrays have no use in the face of Lists? And where do I not know the number of elements? It's calculated at the time of collection creation in each case here. – itsme86 Sep 11 '12 at 16:38
• Why don't you actually measure the difference between the two. My guess is the randomness and noise of the processor will be greater than any performance difference between the two methods. If you want to optimize the code then look for real optimizations at an algorithmic level, rather than micro optimizations at the barely-even-measurable-by-a-computer level. As to knowing the number of elements, ToArray doesn't know how many items are in the IEnumerable it's passed, so it can't allocate an array of the correct size at first; it needs to create several successively larger arrays. – Servy Sep 11 '12 at 16:43
• Well at least you're not trying to defend your original comment. I agree that pre/micro optomizations aren't a great way to spend your effort, but you also shouldn't just willy nilly do things that you know will be less efficient. I also agree that, by far, the single largest bottleneck in this are the I/O operations. However, eliminating the I/O operations, I did benchmark the OP's algorithm vs. mine, and mine was 37% faster over 1000 iterations. Not exactly trivial. – itsme86 Sep 11 '12 at 16:49
• What about my original comment am I not defending? Using a List over an array isn't really "less efficient". From a performance point of view, in this context, they are effectively identical. It's pretty much entirely personal preference. My guess is most of your performance gains came from not performing a second pass over the data, which isn't really a micro-optimization (although probably isn't needed in this context). – Servy Sep 11 '12 at 16:54