Talk:Dutch national flag problem: Difference between revisions
Content added Content deleted
| Line 22: | Line 22: | ||
:::: 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 by an arbitrary gc implementation.) 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) |
:::: 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 by an arbitrary gc implementation.) 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) |
||
::::: Cache miss is irrelevant because it's not worse in the O(n) method than in whatever other method you can think of. It's funny how cache suddenly becomes an issue now, but not when you were using a generic sort routine, hmm? In any event, let it be known that ''I'' wasn't the one who dragged cache into this discussion, someone else did. --[[User:Ledrug|Ledrug]] 17:01, 2 July 2012 (UTC) |
::::: Cache miss is irrelevant because it's not worse in the O(n) method than in whatever other method you can think of. It's funny how cache suddenly becomes an issue now, but not when you were using a generic sort routine, hmm? In any event, let it be known that ''I'' wasn't the one who dragged cache into this discussion, someone else did. --[[User:Ledrug|Ledrug]] 17:01, 2 July 2012 (UTC) |
||
:::::: Correct, I raised that issue. I raised it because I tried to devise a test that would let me compare the efficiency of the builtin with the efficiency of an O(n) userspace sort. That said, I failed to point out that cache miss is a measurable issue even for in-place modify: data which is smaller than a cache element will have one timing and data which is larger than a cache element will have a different timing, even for in-place modify. Anyways, when builtin sort is faster than userspace sort, and efficiency is the grounds for using userspace sort instead of builtin sort, what does that mean for this task? --[[User:Rdm|Rdm]] 17:08, 2 July 2012 (UTC) |
|||
:::::Ignoring those sort of technical details (because they're not important to this task)...it seems that the original intent of the problem is to find a way to do it that in fact ''does'' minimize comparisons and reads on the data. O(n) would do that. O(n log(n)) would not do that. It seems like a big requirement of the original problem. If that isn't going to be part of the task here, then it might not be very valuable. --[[User:Mwn3d|Mwn3d]] 16:14, 2 July 2012 (UTC) |
:::::Ignoring those sort of technical details (because they're not important to this task)...it seems that the original intent of the problem is to find a way to do it that in fact ''does'' minimize comparisons and reads on the data. O(n) would do that. O(n log(n)) would not do that. It seems like a big requirement of the original problem. If that isn't going to be part of the task here, then it might not be very valuable. --[[User:Mwn3d|Mwn3d]] 16:14, 2 July 2012 (UTC) |
||
:::::: Actually, O(n log(n)) would do that for the original data if it's being applied to an extracted result rather than the original data. --[[User:Rdm|Rdm]] 16:21, 2 July 2012 (UTC) |
:::::: Actually, O(n log(n)) would do that for the original data if it's being applied to an extracted result rather than the original data. --[[User:Rdm|Rdm]] 16:21, 2 July 2012 (UTC) |
||