Talk:Dutch national flag problem: Difference between revisions
→Algorithms
Line 19:
::: With three colors, the sorting can be done in-place, so cache miss is not relevant--the O(n) method requires absolutely minimal swaps, so if the entire array can't fit into cache, there isn't anything better you can do anyway. Plus, the same cache issue is in your default sort routine, too. But what's really wrong with initial Python and J examples is that they completely disregarded the essential constraint the problem posed, and provided something uninstructive. In a sense, they are more like counter-examples than examples: what ''not'' to do to solve the original problem. --[[User:Ledrug|Ledrug]] 15:36, 2 July 2012 (UTC)
:::: When you say "cache miss is not relevant" you are making assumptions about the language implementation, about the OS, and about the hardware. (You have assumed, for example, that intermediate results will not have to be garbage collected.) Note also that in a typical machine architecture you have fixed costs associated with the hardware -- if you do not use those resources you're wasting them. --[[User:Rdm|Rdm]] 15:59, 2 July 2012 (UTC)
== "ensuring that they are not in the order of the Dutch national flag" ==
| |||