CODEWITHSUNDEEP
c#listforeach
runfastman
runfastman

Reputation: 947

Sort List or foreach which would be faster

I have a dictionary of items with the ID as a key. Those items also have a timespan value. One function needs to do something with the items where timespan > searchTime.

Would sorting the list fist be faster or would the sorting take as long as the foreach function. I wish there was a sorted dictionary that allowed you to sort on a different key.

Which would be faster?

List<StatePath> timeSorted = new List<StatePath>();
timeSorted = itemDict.ToList();
timeSorted.Sort((ts1, ts2) => TimeSpan.Compare(ts1.time, ts2.time));
int i = timeSorted.Count -1;
while((i > 0) && timeSorted[i].time >= searchTime)
{
  //do something
}

or 

foreach(var curItem in itemDict.Values)
{
  if(curItem.time >= searchTime)
  {
    //do something
  }
}

Upvotes: 0

Views: 212

Answers (2)

Joel Coehoorn
Joel Coehoorn

Reputation: 416049

When comparing two options, there's almost always context that can change the outcome. If you're not measuring both, you should be. And this presumes it even matters; odds are, the difference here is not driving the performance for you app.

That said, I'd probably do it like this:

foreach(var curItem in itemDict.Values.Where(i => i.time >= searchTime))
{
    //do something
}

Specifically, I wonder what you think happens when you call timeSorted.Sort(). This method clearly must run it's own foreach loop or similar in order to complete the operation.

Upvotes: 1

Dave
Dave

Reputation: 4412

In theory, the foreach loop should be faster. The best possible speed for sort is O(n log n), while your for loop is O(n).

In practice, of course, you should test and see which one is faster.

Upvotes: 0

Related Questions