 |
lua-l archive |
|
|
||
|
On 15/09/16 01:38 PM, Christian N. wrote:
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.
It can't, because then table.concat(t, 1, #t) and table.concat(t) would behave differently. Defining it in terms of #list is bad.
Either way, table.concat doesn't accept `nil`, so it already does nil checks. This change would make table.concat slightly faster, as well as cache and memory friendly (swap memory, compressed memory, etc all run better on linear access, so #list followed by iteration might be many times slower than just iteration).
‒ Christian
-- Disclaimer: these emails may be made public at any given time, with or without reason. If you don't agree with this, DO NOT REPLY.