13 replies to this topic

[flyingfisch]

Ok, let's say I have an array array={1,3,3,6,5}. Now let's say that I want to a new piece of data to the end of the array for every iteration, but I don't need the data from the beginning.

What is the fastest way to do this?

Here are the ideas I have come up with:

array={1,3,3,6,5}

while 1 do
   array[#array+1]=newData
end

The problem with this is that I am creating a table that just keeps getting bigger and bigger, and I really don't need all that memory used up.

My next idea was:

array={1,3,3,6,5}
i=5

while 1 do
   array[i+1]=newData
   array[i-4]=nil
   i=i+1
end

The problem with this is that I have to keep track of where the data is in the table, which is confusing.

So I then came up with this:

array={1,3,3,6,5}

while 1 do
   for i=1,5,1 do
	  array[i]=array[i+1]
   end

   array[5]=newData
end

I think that one's the best, but I was wondering if there was a faster way to do it. Because I think with a lot of data, that for loop could get pretty slow...

If someone could give me some advice I'd appreciate it.

[Casimo]

In c, I would make it like this:

char *save = (char *) malloc(2);
char *temp;
save[0] = 123;
save[1] = 234;
temp = (char *) malloc(3);
memcpy(temp, save, 2);
free(save);
save = temp;

I think that's the fastest way.

Maybe that gives you an idea.

[flyingfisch]

hmm... I don't know C very well.

what does malloc() do?



EDIT:

ah, wait. is memcpy() the key part of that snippet? Is it saving a transposed version of save to temp?

[Casimo]

Ok. I'll explain everything.
malloc(x) fetches x bytes of memory, it returns the pointer to the first byte. You can free the allocated memory with free().
memcpy(x, y, z) copies z bytes from y to z.

So that means:
Get 2 bytes, store 123 and 234 in it.
Now get three bytes. Copy the old array into the new one.
Free the old array.
Set the pointer from the old array to the adress of the new array.
Write something in the 3rd byte of the array.

[flyingfisch]

ah, i understand now, but I don't think lua can do that...

[Casimo]

I also don't think so. That was just food for thought.

[3298]

I would write a ring buffer:

int array[] = { 1, 3, 3, 6, 5 };
unsigned char next_write_pos = 0;
...
array[next_write_pos] = new_data;
next_write_pos = (next_write_pos + 1) % (lengthof array);

Basically it remembers which place in the array shall be overwritten next. This index is incremented with each write operation and if it hits the end, it goes back to 0.

[Casimo]

flyingfisch: Why don't you run a speed test? Stop the time and tell us the result.

[2072]

I ran into a similar issue a while ago: I wanted to have an array to which I would add entries from time to time but I didn't want the array to exceed a certain limit (when the limit was reached it had to overwrite the first entries).
Here is what I did:

do
    local Array = {};
    local LIMIT = 200;
    local CurrentCacheIndex = 1;

    function AddToArray(data)

        Array[CurrentCacheIndex] = data;

        CurrentCacheIndex = (CurrentCacheIndex < LIMIT) and (CurrentCacheIndex + 1) or 1;
    end
end

[flyingfisch]

Ah, that's very clever, I didn't think about short-circuiting...

Thank you for sharing!

[3298]

I ran into a similar issue a while ago: I wanted to have an array to which I would add entries from time to time but I didn't want the array to exceed a certain limit (when the limit was reached it had to overwrite the first entries).
Here is what I did:

do
local Array = {};
local LIMIT = 200;
local CurrentCacheIndex = 1;

function AddToArray(data)

Array[CurrentCacheIndex] = data;

CurrentCacheIndex = (CurrentCacheIndex < LIMIT) and (CurrentCacheIndex + 1) or 1;
end
end

That's the ring buffer I wrote two posts before, translated to Lua. I just don't know Lua, so I wrote it in C.
Does Lua have a modulo operator (remainder from integer division; the % sign is the C one)? If yes, it could be used to update the CurrentCachedIndex (that's the equivalent of my next_write_pos) with a shorter line: My code above for 0-based indices, or this for 1-based indices: CurrentCachedIndex = (CurrentCachedIndex % LIMIT) + 1. I just don't like using comparisons (those "and" and "or" thingies from Lua apparently do comparisons with 0) when there's a solution without conditional stuff, e.g. modulo operations.

[flyingfisch]

Yes, lua does have a modulo operator, its %, just like in C.

[MicroPro]

The ring or circular buffer as 3298 suggested is the best choice. The code in Lua will be something like:

array = {0, 0, 0, 0, 0, ptr=0} -- 5 predefined places plus a helper var
while 1 do
  array[array.ptr] = newData
  array.ptr = (array.ptr + 1) % 5 -- '%5' is the key part
end

You can put ptr outside of the array, I just put it inside so as to "package" it into what it belongs to.

I have almost forgot most of my Lua knowledge; so I'm not sure how to put some numbers already in the array. Maybe you could even tweak the # and table's n member to make it work with easier syntax; i didn't try.

[Casimo]

OFFTOPIC:

Back to c: I discovered realloc(ptr, lenght). It re-allocates the memory of the pointer ptr with the lenght lenght and copies the data.