Timeline for Why is processing a sorted array faster than processing an unsorted array?
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 21, 2022 at 10:32 | comment | added | Peter Cordes | Binary search for the cut-point is unnecessary, just start summing from the end you want to keep, stopping when you get to a value you don't want. (Unless HW prefetching works much worse when looping downwards instead of upwards). Of course, actually taking time to sort is not a useful part of an algorithm that starts with unsorted data. A histogram might be, if you want to answer multiple queries for different cut-points, other than 128, from the same data. (Since the small value-range means there are many duplicates in this smallish array.) | |
| S May 11, 2019 at 11:31 | history | suggested | Konard | CC BY-SA 4.0 |
Added link to wikipedia
|
| May 11, 2019 at 11:02 | review | Suggested edits | |||
| S May 11, 2019 at 11:31 | |||||
| Jan 29, 2016 at 1:24 | history | wiki removed | Shog9 | ||
| Jan 28, 2016 at 20:56 | history | made wiki | Post Made Community Wiki by George Stocker | ||
| Apr 22, 2015 at 21:07 | history | edited | user1196549 | CC BY-SA 3.0 |
added 1 character in body
|
| Feb 20, 2014 at 9:40 | history | edited | user1196549 | CC BY-SA 3.0 |
added 14 characters in body
|
| Dec 20, 2013 at 23:05 | history | edited | Lance Roberts | CC BY-SA 3.0 |
deleted 1 characters in body
|
| Jul 24, 2013 at 20:37 | comment | added | user1196549 | @DeadMG: this is indeed not the standard dichotomic search for a given key, but a search for the partitioning index; it requires a single compare per iteration. But don't rely on this code, I have not checked it. If you are interested in a guaranteed correct implementation, let me know. | |
| Jul 24, 2013 at 16:31 | comment | added | sehe |
sum= 3137536 - clever. That's kinda obviously not the point of the question. The question is clearly about explaining surprising performance characteristics. I'm inclined to say that the addition of doing std::partition instead of std::sort is valuable. Though the actual question extends to more than just the synthetic benchmark given.
|
|
| Jul 24, 2013 at 8:18 | history | edited | user1196549 | CC BY-SA 3.0 |
added 206 characters in body
|
| Jul 24, 2013 at 8:06 | history | edited | user1196549 | CC BY-SA 3.0 |
added 198 characters in body
|
| Jul 24, 2013 at 7:57 | history | answered | user1196549 | CC BY-SA 3.0 |