Edit Question - KnowledgeHub

Title Body

Reader's Note: this is NOT a duplicate of the similar question Why is processing a sorted array faster than processing an unsorted array? ; the two questions focus on different premises and thus have different explanations. I have a list of 500000 randomly generated Tuple<long,long,string> objects on which I am performing a simple "between" search: var data = new List<Tuple<long,long,string>>(500000); ... var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x); When I generate my random array and run my search for 100 randomly generated values of x , the searches complete in about four seconds. Knowing of the great wonders that sorting does to searching , however, I decided to sort my data - first by Item1 , then by Item2 , and finally by Item3 - before running my 100 searches. I expected the sorted version to perform a little faster because of branch prediction: my thinking has been that once we get to the point where Item1 == x , all further checks of t.Item1 <= x would predict the branch correctly as "no take", speeding up the tail portion of the search. Much to my surprise, the searches took twice as long on a sorted array ! I tried switching around the order in which I ran my experiments, and used different seed for the random number generator, but the effect has been the same: searches in an unsorted array ran nearly twice as fast as the searches in the same array, but sorted! Does anyone have a good explanation

Tags (comma-separated) Cancel