I search for solutions in this order: Past Code, Unreal Source, Wiki, BUF, groups.yahoo, google, screaming at monitor. – RegularX
Difference between revisions of "UE3 talk:Insertion Sort Macro"
m (→Possible Optimization: should be correct in most cases, yes) |
(→Possible Optimization) |
||
| Line 4: | Line 4: | ||
Whenever I implement a binary search, I usually just test for two of the three cases, either < and >, leaving == up to the ''else'', or == right at the beginning and only either < or >, handling the other in the ''else''. Only float NaN values might break things as NaN <=> X is always ''false'', even if X also is NaN. —[[User:Wormbo|Wormbo]] 05:47, 17 September 2009 (UTC) | Whenever I implement a binary search, I usually just test for two of the three cases, either < and >, leaving == up to the ''else'', or == right at the beginning and only either < or >, handling the other in the ''else''. Only float NaN values might break things as NaN <=> X is always ''false'', even if X also is NaN. —[[User:Wormbo|Wormbo]] 05:47, 17 September 2009 (UTC) | ||
| + | |||
| + | I've changed the algorithm to not use the equals operator, if !(A > B || B > A) then it doesn't really matter which one comes first, so it shouldn't affect sorting much anyway. Also, the new code makes the operator usage a parameter so you can now easily change the operator used and perform reverse sorting. --[[User:Elmuerte|elmuerte]] 18:42, 17 September 2009 (UTC) | ||
Revision as of 11:42, 17 September 2009
Possible Optimization
Right now within the inner loop it compares the two elements 3 times. A == B, A > B, B > A. But general rules dictate, that if !(A > B), and !(B > A) then it must be A == B, right? (As also explained in the document). So the first compare is actually not needed, thus reducing the requirement for a additional operator to implement for custom types. Is my assumption correct? --elmuerte 19:49, 16 September 2009 (UTC)
Whenever I implement a binary search, I usually just test for two of the three cases, either < and >, leaving == up to the else, or == right at the beginning and only either < or >, handling the other in the else. Only float NaN values might break things as NaN <=> X is always false, even if X also is NaN. —Wormbo 05:47, 17 September 2009 (UTC)
I've changed the algorithm to not use the equals operator, if !(A > B || B > A) then it doesn't really matter which one comes first, so it shouldn't affect sorting much anyway. Also, the new code makes the operator usage a parameter so you can now easily change the operator used and perform reverse sorting. --elmuerte 18:42, 17 September 2009 (UTC)
