Talk:Sort disjoint sublist: Difference between revisions
Content added Content deleted
(Tough to call!) |
(→Indices as collection: new section) |
||
| Line 5: | Line 5: | ||
:: I expect that swapping through a level of indirection to be less efficient than extracting the values, sorting them, then putting them back, for typical machine architectures and random sorts. --[[User:Rdm|Rdm]] 12:58, 14 February 2011 (UTC) |
:: I expect that swapping through a level of indirection to be less efficient than extracting the values, sorting them, then putting them back, for typical machine architectures and random sorts. --[[User:Rdm|Rdm]] 12:58, 14 February 2011 (UTC) |
||
::: I wouldn't want to call that either way; depends on too many factors (notably whether cache limits are observed). Only way to know is to measure in a realistic setting. –[[User:Dkf|Donal Fellows]] 16:42, 14 February 2011 (UTC) |
::: I wouldn't want to call that either way; depends on too many factors (notably whether cache limits are observed). Only way to know is to measure in a realistic setting. –[[User:Dkf|Donal Fellows]] 16:42, 14 February 2011 (UTC) |
||
== Indices as collection == |
|||
I see that many languages take the indices as a general collection (or array) instead of specifically as a set. If they're doing that, should they also be enforcing uniqueness of the indices before progressing with the rest of the sort? (To be exact, failing to do this gives wrong answers…) –[[User:Dkf|Donal Fellows]] 16:45, 14 February 2011 (UTC) |
|||
Revision as of 16:45, 14 February 2011
Adapted from a question/answer here. Note that the solution for languages with pointers might be different than the Python as you may be able to adapt a sort routine to sort via an extra level of indirection. --Paddy3118 06:34, 12 February 2011 (UTC)
- ... Which has just been done by the Go example. Sweet! --Paddy3118 06:02, 14 February 2011 (UTC)
- I expect that swapping through a level of indirection to be less efficient than extracting the values, sorting them, then putting them back, for typical machine architectures and random sorts. --Rdm 12:58, 14 February 2011 (UTC)
- I wouldn't want to call that either way; depends on too many factors (notably whether cache limits are observed). Only way to know is to measure in a realistic setting. –Donal Fellows 16:42, 14 February 2011 (UTC)
- I expect that swapping through a level of indirection to be less efficient than extracting the values, sorting them, then putting them back, for typical machine architectures and random sorts. --Rdm 12:58, 14 February 2011 (UTC)
Indices as collection
I see that many languages take the indices as a general collection (or array) instead of specifically as a set. If they're doing that, should they also be enforcing uniqueness of the indices before progressing with the rest of the sort? (To be exact, failing to do this gives wrong answers…) –Donal Fellows 16:45, 14 February 2011 (UTC)