Retrieving an array index?

[THobson]

I agree - keep the banana

[MachoMan]

I made a better one  ;D

In a worst case scenario it is 2x as fast as GB's

Code: [Select]

/*       MachoMan's
          Inspired
             by
             GB
         ==========
    Superior Index Finder
      Works 2x as Fast!! ;)
         ==========

  call: [item, array] call index
  Returns an index of the item.
  if not in Array return -1.
*/

private ["_array","_item","_index1","_index2","_found1","_found2"];

_item = _this select 0;
_array = _this select 1;
_found1 = FALSE;
_found2 = FALSE;
_index1 = 0;
_index2 = count _array -1;

while { !(_found1 OR _found2) AND (_index1 <= _index2) } do
{
   if (_item1 == (_array select _index1) AND (_found1 = FALSE)) then {_found1 = TRUE} else {_index1 = _index1 + 1};
   if (_item2 == (_array select _index2) AND (_found2 = FALSE)) then {_found2 = TRUE} else {_index2 = _index2 - 1};
};

if (found2) then {_index1 = _index2);
if (!(_found1 OR _found2)) then {_index1 = -1};

_index1

Most Computer Science ppl will know this algorithm

(Syntax may contain minor errors)

[Mr.Peanut]

Is the above algorithm faster for all sizes of arrays? Please tell the name of the  search algorithm your code is based upon e.g. binary?

Never mind. I see now that it simply searches the array from both ends.

[MachoMan]

Lol implementing binary search in ofp would be simple insane, perhaps I should try try it ;D

But binary search unfortunately only works on sorted lists of integers (numbers).

So yes it simply searches the array both ways, because loops are inherently slow.

[CrashDome]

Instead of returning a -1 after checking array, you can check the array via the 'in' command before your search. This would eliminate the searching if it isn't in the array.

i.e. stuff your search into a  

if (_item in _array) then
{
  ; all your stuff
}
else
{_index1 = -1;};

_index1

[MachoMan]

True, but I think in will go through the entire array from the beginning to the end. So this will take longer, because we have to go through it anyway. If we use in we will loop the array 2x.

[CrashDome]

*doh!*

[Unnamed]

I work on the assumption that any internal OFP script command will work faster than it's scripted equivelant. So the in command should be quicker at checking an array. But as your also going to be searching the array you may as well do them all in one script.

Unless your going to search through hundreds of array elements, a basic forEach loop should be quick enough:

Code: [Select]

_Found=False
_Index=0
{If !(_Found) Then {If (_x==_ThingToFind) Then {_Found=True} Else {_Index=_Index+1}}} ForEach _Array

BTW If you want to find an object in an array of hundreds\thousands, you can avoid searching loops altogether.

What is it exactly, your going to be searching for?

[MachoMan]

Noname, your script is cool, but it uses one flawed assumption:
There is no guaranty that foreach will start at element zero.

Perhaps it does, but we can never know it for sure, can we? The comref doesn't say it, so BIS doesn't guaranty it. (Not that it does guaranty the functioning of any other command. ;D )

[Komuna]

Actually, MachoMan, it does.

Check v.1073/1.074 - the new scripting structure is basically made of arrays, and you may notice one or two scripts using this method to either search for values or call commands through a certain order.

[Unnamed]

Perhaps it does, but we can never know it for sure, can we?

I must admit, it would not suprise me But I use it quite alot for small arrays and Ive had no problems yet. At a push just change it to:

Code: [Select]

{If !(_Found) Then {If ((_Array Select _Index)==_ThingToFind) Then {_Found=True} Else {_Index=_Index+1}}} ForEach _Array
It is just a basic search, the script you posted should return 90% of results quicker, I use the same method  to range in Mortars.

But thats essentialy what the find command will do, although I rekon you would have to be searching a pretty big array to notice the speed difference between VBS's find command and any of these scripts.

[LCD]

some1 found me a job :wow: now give me lawyers office thatll gimme work

LCD OUT