Advertisement

Author Topic: Correct way to PUT something in an Array ?  (Read 1754 times)

0 Members and 1 Guest are viewing this topic.

Offline laggy

  • Members
  • *
  • "Behold a pale horse"
Correct way to PUT something in an Array ?
« on: 22 Mar 2009, 10:10:41 »
guys is an array created through BLUFOR present trigger and onAct: guys = thislist
he is a single unit.

Then I have:

guys = guys + [he]

Is this the best way (or even correct) to put something in an array ?

Laggy
And I looked and beheld a pale horse and his name that sat on him was Death and Hell followed with him.

Offline Worldeater

  • Former Staff
  • ****
  • Suum cuique
Re: Correct way to PUT something in an Array ?
« Reply #1 on: 22 Mar 2009, 10:26:41 »
yes
try { return true; } finally { return false; }

Offline laggy

  • Members
  • *
  • "Behold a pale horse"
Re: Correct way to PUT something in an Array ?
« Reply #2 on: 22 Mar 2009, 10:30:44 »
Thanks Worldeater  :D
And I looked and beheld a pale horse and his name that sat on him was Death and Hell followed with him.

Offline Spooner

  • Members
  • *
  • Mostly useless
    • Community Base Addons
Re: Correct way to PUT something in an Array ?
« Reply #3 on: 22 Mar 2009, 14:18:45 »
That way is perfectly correct, but the best way is:
Code: [Select]
guys set [count guys, he];
You see, if you use the standard way of putting the new element into an array and adding together two arrays, the system needs to create an entirely new array and copy all the values from the original two arrays into it. If there are only 3 items in the array, then yes, there really isn't much difference, so just use the one that makes it clearer for you. However, if you have 3000 elements in the array, you can see that the cost would be great!

In case it isn't obvious, setting an element one past the last element in the array (the current last element is numbered ((count guys) - 1)) will extend the existing array and place the new element in the new "space".

Advanced
Using this method of pushing on a new element also keeps all references to the original array correct. Probably not an issue for most people just creating a "throw-away" array though. Anyway, I use a macro for this to make it more clear what I am doing, as well as saving me typing 'guys' twice:
Code: (push macro) [Select]
#define PUSH(ARRAY,ELEMENT) (ARRAY) set [count (ARRAY), (ELEMENT)];

PUSH(guys,he)
« Last Edit: 22 Mar 2009, 14:21:09 by Spooner »
[Arma 2] CBA: Community Base Addons
[Arma 1] SPON Core (including links to my other scripts)

Offline Deadfast

  • Members
  • *
Re: Correct way to PUT something in an Array ?
« Reply #4 on: 22 Mar 2009, 14:24:25 »
Now that's some handy info you got there Spooner ;)

Offline Worldeater

  • Former Staff
  • ****
  • Suum cuique
Re: Correct way to PUT something in an Array ?
« Reply #5 on: 22 Mar 2009, 15:54:29 »
That way is perfectly correct, but the best way is:
Code: [Select]
guys set [count guys, he];

Hmmm, did you measure? A small test indicates there's no speed increase at all (filled arrays with numbers from 0..25k100k three times using both methods).
« Last Edit: 22 Mar 2009, 16:03:27 by Worldeater »
try { return true; } finally { return false; }

Offline Spooner

  • Members
  • *
  • Mostly useless
    • Community Base Addons
Re: Correct way to PUT something in an Array ?
« Reply #6 on: 22 Mar 2009, 17:58:19 »
Oh, I'm very surprised by that. Maybe resize entirely copies the entire array anyway... Nevertheless, if both are equivalent then the push solution should be used, since it allows BIS to "correct" their implementation in the future. Well, I say should, but I expect that very few scripters actually use arrays big enough to make a difference in any case! Not to mention the fact that there is nothing wrong with good practice (push/pop rather than copying methods) in SQF just because that good practice is only relevant in every other computer language made :whistle:

OK, how about memory wastage? The join solution should leave a horde of unreferenced strings lying on the heap waiting for the garbage-collector...
[Arma 2] CBA: Community Base Addons
[Arma 1] SPON Core (including links to my other scripts)

Offline Worldeater

  • Former Staff
  • ****
  • Suum cuique
Re: Correct way to PUT something in an Array ?
« Reply #7 on: 22 Mar 2009, 22:15:21 »
Well, that's a bit too much speculation for my taste. After all the engine is a black box and we don't know for sure what's really going on under the hood. Only because it looks like it is copying the array does not mean it actually does!

Keep in mind that the guys who implemented ArmA script are coding for a living and probably know a thing or two about it.
try { return true; } finally { return false; }

Offline Trexian

  • Members
  • *
Re: Correct way to PUT something in an Array ?
« Reply #8 on: 24 Mar 2009, 21:14:07 »
At the risk of going too far off topic, is there a best practice for removing an element/value from an array?  I understand 2 basic ways of doing this.

1) BigHonkingArray = BigHonkingArray - [_x] or [_otherArray select _element] or [value]

or

2) A conditional loop that checks each element against what you want to remove, and basically creates a new array with the values you want.

I always generally use the former.  The latter, I think, is useful if you need to loop a specific number of times (like (count BigHonkingArray) -1) and can't mess with the size of BigHonkingArray.

TIA.
Sic semper tyrannosauro.

Offline Spooner

  • Members
  • *
  • Mostly useless
    • Community Base Addons
Re: Correct way to PUT something in an Array ?
« Reply #9 on: 24 Mar 2009, 23:05:33 »
The former won't work if there is a possibility that there could be repeated values in the array, since subtracting an array removes all elements from that array, but otherwise, it is the best way:
Code: [Select]
[1, 2, 2, 3] - [2] // => [1, 3] rather than [1, 2, 3]
This may be what you want to happen, of course (remember too, that this creates a new array with the altered values in it, rather than affecting the original array!) :whistle:

If you need to pop off the last element, then use:
Code: [Select]
_poppedElement = _array select ((count _array) - 1); // Might not always need to preserve this value.
_array resize ((count _array) - 1); // Shrink the array by one.
If you need to remove just one element at an arbitrary position (rather than all values of a certain element):
Code: (removeElement.sqf) [Select]
private ["_array", "_index", "_size"];
_array = _this select 0;
_index = _this select 1;

// Move all elements after _index down one.
_size = count _array;
for "_i" from _index to (_size - 2) do
{
    _array set [_i, _array select (_i + 1)];
};
_array resize (_size - 1);
Code: [Select]
removeElement = compile preprocessFileLineNumbers "removeElement.sqf";

_array = [1, 2, 2, 2, 3, 3, 4];
[_array, _array find 3] call removeElement; // Remove a 3.
// _array => [1, 2, 2, 2, 3, 4];

[_array, 3] call removeElement; // Remove 4th element
// _array => [1, 2, 2, 3, 4];
Remember that push/pop (and this implementation of remove I have given) affect the original array and thus are different to implementations that construct another array with the change in it. Changing the original array is always more efficient and affects all existing references to it, but if you want to preserve the original array, then you want to use a method that doesn't affect the original array.

* stacks (for info on push/pop/shift/unshift and why stacks are more efficient than static arrays; in ArmA we can use an array as a stack, since there isn't a separate data type).

Remember that efficiency is almost totally irrelevant unless you are running a large number of operations on large arrays. Don't expect a noticeable difference if you aren't really pushing the limits (and the vast majority of scripts don't do that!). However, the original question was what was the best way, not what involves least typing.

I thought it might be worth discussing benchmarking as a separate topic. I found push to run several orders of magnitude faster than concatenate, but WorldEater found them to run exactly the same time...
« Last Edit: 24 Mar 2009, 23:10:12 by Spooner »
[Arma 2] CBA: Community Base Addons
[Arma 1] SPON Core (including links to my other scripts)

Offline Worldeater

  • Former Staff
  • ****
  • Suum cuique
Re: Correct way to PUT something in an Array ?
« Reply #10 on: 27 Mar 2009, 09:06:57 »
Yeah... thanks to my crappy testing.

Using proper testing the method suggested by you is indeed faster (which amazes me somewhat since they know they are dealing with arrays because of the squared brackets).
try { return true; } finally { return false; }

Offline Spooner

  • Members
  • *
  • Mostly useless
    • Community Base Addons
Re: Correct way to PUT something in an Array ?
« Reply #11 on: 27 Mar 2009, 17:01:36 »
Don't worry, I spent a long time trying to make a decent benchmark myself. time definitely doesn't work in the way you'd expect it to.

The interpreter is totally aware that it are working with arrays and is, in fact, using the most optimised implementation for what you ask it to do (computers are very literal, as you know):
Code: [Select]
_array = _array + [_element];
Is asking "Please create a new array by concatenating _array and [_element], then assign that new array to _array". The interpreter doesn't look at the whole line when parsing,

Think of it differently:
Code: [Select]
_newArray = _array + [_element];
which obviously can't be optimised to a push, since the interpreter cannot alter _array, or
Code: [Select]
_referenceToArray = _array;
// Later...
_array = _referenceToArray + [_element];
Which could potentially become a push, but it is that much harder for the parser to catch (well, the parser can't catch that one, so you'd need to perform optimisation passes over the generated parse-tree, something that would take longer to do in an interpreter than time it would save; in a compiler, the time spent matters a lot less).

For interest, the parser would break down:
Code: [Select]
_array = _array + [_element];
into (well, simplified, but)
1. Create a new array (call it _tmp1).
2. Put _element into _tmp1.
3. Create a new array (call it _tmp2) and copy all values of _array and _tmp1 into it.
4. Set _array to reference _tmp2
5. The original _array and _tmp1 are no longer referenced, so can be cleaned up by the garbage collector.

I am explaining this in detail since some people might be interested in how interpreters work. You absolutely don't need to understand all this as a normal user of SQF ;)

I'll repeat again, that push is only optimised over concatenate for large arrays (and probably only when pushing a single element). Still, push should never be slower than concatenate, and is often faster, so using push universally makes sense.
[Arma 2] CBA: Community Base Addons
[Arma 1] SPON Core (including links to my other scripts)

Offline Trexian

  • Members
  • *
Re: Correct way to PUT something in an Array ?
« Reply #12 on: 27 Mar 2009, 17:07:12 »
Hey Spooner -

Is that push part of your core?   :good:
Sic semper tyrannosauro.