lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]



On Oct 2, 2013, at 1:51 AM, liam mail <liam.list@googlemail.com> wrote:


On 2 October 2013 09:27, Tim Hill <drtimhill@gmail.com> wrote:
Scenario: I'm writing a 3rd party API that expects a sequence as an argument. For example:

sum = addSeq(t)
The addSeq() function adds all the values in the sequence in the table t, returning the total.
>>It's EXPENSIVE to check that a table is a sequence and therefore EXPENSIVE to create a robust API in this case.


Just pointing out that your scenario is flawed. You are going to iterate over the array entries to find the resulting sum.

--Liam


No, I'm going to have to check it's an array first, and then iterate it. The array iteration is of course O(n), and I'm unaware of any way to validate that a table is an array in less than O(n), so the API performance is half what it could be if I could use some kind of table.issequence() check.

Worse, any Lua code that checks for a sequence inevitably has to iterate the entire set of table keys, which means all the array entries and all the non-array entries. So it's worse than O(2n).

--Tim