11
Processing a sorted array is faster than an unsorted one? · Kaushik Gopal's Site
source link: https://jkl.gg/b/processing-sorted-array-is-faster-than-processing-unsorted-array/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Processing a sorted array is faster than an unsorted one? »
Kaushik Gopal
This super intesting stack overflow answer explains why -in programming- if you have a sorted array, somehow magically it can seem like it’s easier to process each element vs processing the same array if it were unsorted.
tl;dr - branch prediction
With a sorted array, the condition data[c] >= 128 is first false for a streak of values, then becomes true for all later values. That’s easy to predict. With an unsorted array, you pay for the branching cost.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK