Jump to content



Photo

Question About Optimization


  • Please log in to reply
13 replies to this topic

#1 flyingfisch

flyingfisch

    Casio Maniac

  • Deputy
  • PipPipPipPipPipPipPipPip
  • 1891 posts
  • Gender:Male
  • Location:OH,USA
  • Interests:Aviation, Skiing, Programming, Mountain Biking.

  • Calculators:
    fx-9860GII
    fx-CG10 PRIZM

Posted 25 February 2013 - 04:03 AM

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. :)

#2 Casimo

Casimo

    Casio Overlord

  • Members
  • PipPipPipPipPipPipPip
  • 641 posts
  • Gender:Not Telling

Posted 25 February 2013 - 02:46 PM

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.

#3 flyingfisch

flyingfisch

    Casio Maniac

  • Deputy
  • PipPipPipPipPipPipPipPip
  • 1891 posts
  • Gender:Male
  • Location:OH,USA
  • Interests:Aviation, Skiing, Programming, Mountain Biking.

  • Calculators:
    fx-9860GII
    fx-CG10 PRIZM

Posted 25 February 2013 - 02:54 PM

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?


#4 Casimo

Casimo

    Casio Overlord

  • Members
  • PipPipPipPipPipPipPip
  • 641 posts
  • Gender:Not Telling

Posted 25 February 2013 - 03:17 PM

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.

#5 flyingfisch

flyingfisch

    Casio Maniac

  • Deputy
  • PipPipPipPipPipPipPipPip
  • 1891 posts
  • Gender:Male
  • Location:OH,USA
  • Interests:Aviation, Skiing, Programming, Mountain Biking.

  • Calculators:
    fx-9860GII
    fx-CG10 PRIZM

Posted 25 February 2013 - 03:23 PM

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

#6 Casimo

Casimo

    Casio Overlord

  • Members
  • PipPipPipPipPipPipPip
  • 641 posts
  • Gender:Not Telling

Posted 25 February 2013 - 03:27 PM

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

#7 3298

3298

    Casio Addict

  • Members
  • PipPipPip
  • 79 posts
  • Gender:Male
  • Location:Germany

  • Calculators:
    fx-9750G Plus
    Algebra FX 2.0 (ROM 1.03,broken)
    HP 50G

Posted 25 February 2013 - 07:37 PM

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.
  • MicroPro likes this

#8 Casimo

Casimo

    Casio Overlord

  • Members
  • PipPipPipPipPipPipPip
  • 641 posts
  • Gender:Not Telling

Posted 26 February 2013 - 06:02 AM

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

#9 2072

2072

    Casio over god

  • Admin
  • PipPipPipPipPipPipPipPip
  • 1565 posts
  • Gender:Male
  • Location:Somewherebourg
  • Interests:Alternative states of consciousness, programming, making things work the best they possibly can.

  • Calculators:
    AFX2 ROM 1.02, CFX-9940GT+, FX-180P-Plus

Posted 02 March 2013 - 10:07 PM

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


#10 flyingfisch

flyingfisch

    Casio Maniac

  • Deputy
  • PipPipPipPipPipPipPipPip
  • 1891 posts
  • Gender:Male
  • Location:OH,USA
  • Interests:Aviation, Skiing, Programming, Mountain Biking.

  • Calculators:
    fx-9860GII
    fx-CG10 PRIZM

Posted 05 March 2013 - 11:14 PM

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

Thank you for sharing!

#11 3298

3298

    Casio Addict

  • Members
  • PipPipPip
  • 79 posts
  • Gender:Male
  • Location:Germany

  • Calculators:
    fx-9750G Plus
    Algebra FX 2.0 (ROM 1.03,broken)
    HP 50G

Posted 06 March 2013 - 09:01 AM

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. :P
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. :greengrin:

#12 flyingfisch

flyingfisch

    Casio Maniac

  • Deputy
  • PipPipPipPipPipPipPipPip
  • 1891 posts
  • Gender:Male
  • Location:OH,USA
  • Interests:Aviation, Skiing, Programming, Mountain Biking.

  • Calculators:
    fx-9860GII
    fx-CG10 PRIZM

Posted 06 March 2013 - 02:23 PM

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

#13 MicroPro

MicroPro

    Casio Overlord

  • Deputy
  • PipPipPipPipPipPipPip
  • 640 posts
  • Gender:Male
  • Location:Iran

  • Calculators:
    Casio ClassPad 300

Posted 10 March 2013 - 07:41 PM

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.

#14 Casimo

Casimo

    Casio Overlord

  • Members
  • PipPipPipPipPipPipPip
  • 641 posts
  • Gender:Not Telling

Posted 04 April 2013 - 03:47 PM


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.



0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users