 |
lua-l archive |
|
|
||
|
Am 15.09.2016 um 02:07 schrieb Soni L.:
On 14/09/16 09:02 PM, Miroslav Janíček wrote:On 15 Sep 2016, at 1:08, Soni L. <fakedme@gmail.com> wrote: (…) I consider this function bad, as it relies on #list. This means it's O(log n) + O(n), but it could be changed to O(n) by changing it to: (…)You can ignore the log n part. O(n + log n) ≃ O(n). M.There's a bit of a difference between O(n + log n) and O(n) + O(log n) tho... And I thought the part about cross-impl consistency was more important?
I don't understand where there is an inconsistency across implementations. Surely, if one passes a proper sequence to these functions, one will get the same behavior across implementations. And by noting that #list has undefined behavior if list is not a sequence, I think the documentation indirectly demands the list argument to be a sequence (unless one specifies the i, j parameters of course).
But even though O(n + log n) = O(n) from a complexity point of view, this is still overhead. But IMHO the functions could be implemented the way you suggest even without changing the documentation, since the behavior would only change in the undefined case, as it is now. But if we get back a frontier/border/margin definition for #list, then that isn't the case anymore. I think you raise a good point.
‒ Christian