Lowest Index of Array

[Caleb_P]

Is there a (fast) way to find the lowest index of an array? For example…

[lua]

local myTable={

  true,

  true,

  true,

  true

}

– Now myTable has indexes from 1-4

myTable[1]=nil

– Now myTable has indexes from 2-4

print(detectLowestIndex(myTable)) – 2

---

---

local myTable={}

for i=200, 300 do

  myTable[i]=true

end

print(detectLowestIndex(myTable)) – 200

[/lua]

Of course the easiest way would be to iterate through from 1 until you find an entry, but is there any faster way? Would also be nice to find the highest index.

• C

[StarCrunch]

function FindLowestAndHighest (myTable) local lowest, highest for k in pairs(myTable) do if type(k) == "number" and k % 1 == 0 and k \> 0 then -- Assuming mixed (possibly non-integer) keys if lowest then lowest = math.min(lowest, k) highest = math.max(highest, k) else lowest, highest = k, k end end end return lowest or 0, highest or 0 -- "or 0" in case there were no indices end

Untested, but something like the above would be needed in the most generic case. pairs() isn’t particularly fast, and in the absence of any context you’ll have to iterate the entire table anyhow, since there’s no guaranteed order in how the keys are distributed.

table.maxn() gives you the highest index, but any speed gain comes from the compiler, not because it somehow got around those algorithmic constraints. (http://www.lua.org/source/5.1/ltablib.c.html#maxn, basically the same code minus the integer check)

If you know your maximum upper bound and it’s fairly low, then a straight-up iteration is probably fine. There’s going to be some crossing-over point versus pairs() for a truly sparse table, which can be found by experiment.

Another option might be to fill “empty” elements with false or some dummy “nil” table you can compare against and ignore. Then you can at least search reliably in [1, #myTable], and Lua will maintain the (faster) integer hash structure internally. Your users (and in your own case, your serialization library) may need to be aware of this, obviously.

If you need something more heavy-duty, it’s on to the world of data structures. :) (Probably something like an “ordered map”.)

[bryan.m.mitchell]

You could keep track of the lowest index.  Instead of directly assigning nil as the value in the table, you could create a function called removeObjectAtIndex(index), make the value nil and return the lowest index to be stored for later access.  If the object you are removing is the current lowest known index, then you just return the next available index (by iterating up through the indexes to find the next lowest).  If it’s NOT currently the lowest index, you just return the current lowest index so that information is not changed.  With this approach you would only have to iterate through when removing objects, and only when you’re removing the lowest indexed object in the table. 

If, however, you just use table.insert and table.remove, I believe it will shift the indexes for you, so your lowest index will aways be 1.

[Caleb_P]

Thanks for the help, both of ye.

@StarCrunch: Any links you happen to have lying around to explain “ordered maps”…?

@bryan.m.mitchell: Interesting. Could also do the same for high - I believe I’ll try that out.

• C

[StarCrunch]

Hi.

A quick search turns up this, which might look a little weird in the code department (Scheme, although an influence on Lua, is pretty alien-looking  ), but mentions a few of the possible trees you might build on top of (AVL trees, as in his example; red-black; treaps).

This may have helpful links, not sure. (Also, in the C++ STL, the std::map is apparently ordered, but honestly you’d probably have an easier time reading Scheme than STL code  :o ). Another interesting data structure is the skip list.

Probably not what you’re doing, but if you start with a fully populated area, want to delete a few elements, then pull them off in order, there are priority queues. Here’s one in Lua: skew heap

Anyhow, like I said it depends on context and what you want others to (be able to) see. If hiding matters, you could supplement Bryan’s suggestion, say, by keeping the data in a separate table and then associating the two via a weak table (key = original table, value = indices table, or just the low or high index). I believe this was how the Lua standard library implemented the “n” field for tables back in… 5.0? (That way, only tables that wanted that feature paid the cost.)

Also, all of these fall into the idea of amortization, which basically means “spreading the work around” (and figuring out which operation will have to soak up the cost).

[Caleb_P]

Thanks! Will look into these articles.

• C

[Mirada_Connect]

Unless there is a specific reason for wanting to leave part of the array empty, you would be able to avoid the problem entirely by using table:remove and table:insert, since they can move information in a table up and down to avoid nils.

I realise that isn’t exactly what your asking for, but it might help someone who sees this avoid needing to do this in the future.

[StarCrunch]

function FindLowestAndHighest (myTable) local lowest, highest for k in pairs(myTable) do if type(k) == "number" and k % 1 == 0 and k \> 0 then -- Assuming mixed (possibly non-integer) keys if lowest then lowest = math.min(lowest, k) highest = math.max(highest, k) else lowest, highest = k, k end end end return lowest or 0, highest or 0 -- "or 0" in case there were no indices end

Untested, but something like the above would be needed in the most generic case. pairs() isn’t particularly fast, and in the absence of any context you’ll have to iterate the entire table anyhow, since there’s no guaranteed order in how the keys are distributed.

table.maxn() gives you the highest index, but any speed gain comes from the compiler, not because it somehow got around those algorithmic constraints. (http://www.lua.org/source/5.1/ltablib.c.html#maxn, basically the same code minus the integer check)

If you know your maximum upper bound and it’s fairly low, then a straight-up iteration is probably fine. There’s going to be some crossing-over point versus pairs() for a truly sparse table, which can be found by experiment.

Another option might be to fill “empty” elements with false or some dummy “nil” table you can compare against and ignore. Then you can at least search reliably in [1, #myTable], and Lua will maintain the (faster) integer hash structure internally. Your users (and in your own case, your serialization library) may need to be aware of this, obviously.

If you need something more heavy-duty, it’s on to the world of data structures. :) (Probably something like an “ordered map”.)

[bryan.m.mitchell]

You could keep track of the lowest index.  Instead of directly assigning nil as the value in the table, you could create a function called removeObjectAtIndex(index), make the value nil and return the lowest index to be stored for later access.  If the object you are removing is the current lowest known index, then you just return the next available index (by iterating up through the indexes to find the next lowest).  If it’s NOT currently the lowest index, you just return the current lowest index so that information is not changed.  With this approach you would only have to iterate through when removing objects, and only when you’re removing the lowest indexed object in the table. 

If, however, you just use table.insert and table.remove, I believe it will shift the indexes for you, so your lowest index will aways be 1.

[Caleb_P]

Thanks for the help, both of ye.

@StarCrunch: Any links you happen to have lying around to explain “ordered maps”…?

@bryan.m.mitchell: Interesting. Could also do the same for high - I believe I’ll try that out.

• C

[StarCrunch]

Hi.

A quick search turns up this, which might look a little weird in the code department (Scheme, although an influence on Lua, is pretty alien-looking  ), but mentions a few of the possible trees you might build on top of (AVL trees, as in his example; red-black; treaps).

This may have helpful links, not sure. (Also, in the C++ STL, the std::map is apparently ordered, but honestly you’d probably have an easier time reading Scheme than STL code  :o ). Another interesting data structure is the skip list.

Probably not what you’re doing, but if you start with a fully populated area, want to delete a few elements, then pull them off in order, there are priority queues. Here’s one in Lua: skew heap

Anyhow, like I said it depends on context and what you want others to (be able to) see. If hiding matters, you could supplement Bryan’s suggestion, say, by keeping the data in a separate table and then associating the two via a weak table (key = original table, value = indices table, or just the low or high index). I believe this was how the Lua standard library implemented the “n” field for tables back in… 5.0? (That way, only tables that wanted that feature paid the cost.)

Also, all of these fall into the idea of amortization, which basically means “spreading the work around” (and figuring out which operation will have to soak up the cost).

[Caleb_P]

Thanks! Will look into these articles.

• C

[Mirada_Connect]

Unless there is a specific reason for wanting to leave part of the array empty, you would be able to avoid the problem entirely by using table:remove and table:insert, since they can move information in a table up and down to avoid nils.

I realise that isn’t exactly what your asking for, but it might help someone who sees this avoid needing to do this in the future.