Using binarysearch instead of for loop doesnt work

Using binarysearch instead of for loop doesnt work - Printable Version

+- SA-MP Forums Archive (https://sampforum.blast.hk)
+-- Forum: SA-MP Scripting and Plugins (https://sampforum.blast.hk/forumdisplay.php?fid=8)
+--- Forum: Scripting Help (https://sampforum.blast.hk/forumdisplay.php?fid=12)
+--- Thread: Using binarysearch instead of for loop doesnt work (/showthread.php?tid=630596)

Using binarysearch instead of for loop doesnt work - faxxe - 16.03.2017

Ahoy friends.

For my pickup system im using 2 for loops to check arrays if they contain the pickupid of the pickup, the player picked up.

Код:

public OnPlayerPickUpPickup(playerid, pickupid)
{
	new index;
	switch(GetPickupType(pickupid,index))
	{
		case INVALID_PICKUP_TYPE:
			{
			}
		case MONEY_TYPE:
			{
				maxmoney -= 1;
				GivePlayerMoney(playerid, 1000);
				printf("ID picked up: %d",maxmoney);
				MoneyPickups[index]=-1;
				HeapSort(MoneyPickups);
				DestroyPickup(pickupid);
			}
		case ACTOR_TYPE:
			{
				ShowMenuForPlayer(shopmenu,playerid);
				TogglePlayerControllable(playerid,false);
			}
	}
	return 1;
}



stock GetPickupType(pickupid, &index)
{
    for(new i; i<sizeof(MoneyPickups); i++)
    {
        if(MoneyPickups[i] == pickupid) return index=i,MONEY_TYPE;
    }
    for(new i; i<sizeof(ActorPickups); i++)
    {
        if(ActorPickups[i] == pickupid) return index=i,ACTOR_TYPE;
    }
    return INVALID_PICKUP_TYPE;
}

Due to efficiency reasons i want to use binary search instead because the array is sorted, so its the most efficient way.

But unfortutanetly my code doesnt work.

Код:

stock GetPickupType(pickupid, &index)
{
	new mres = binarysearch(MoneyPickups,pickupid,0,sizeof(MoneyPickups)-1);
        if(mres > -1 && MoneyPickups[mres] == pickupid) return index=mres,MONEY_TYPE;
	new ares = binarysearch(ActorPickups,pickupid,0,sizeof(ActorPickups)-1);
	if(ares > -1 && MoneyPickups[ares] == pickupid) return index=ares,ACTOR_TYPE;
	
	
	
	return INVALID_PICKUP_TYPE;
}

If i try it this way, only this part seems to be executed:

Код:

	new mres = binarysearch(MoneyPickups,pickupid,0,sizeof(MoneyPickups)-1);
        if(mres > -1 && MoneyPickups[mres] == pickupid) return index=mres,MONEY_TYPE;

So the MoneyPickups work, but the ActorPickups doesnt.

If i change the order and do it this way

Код:

stock GetPickupType(pickupid, &index)
{
	
	new ares = binarysearch(ActorPickups,pickupid,0,sizeof(ActorPickups)-1);
	if(ares > -1 && MoneyPickups[ares] == pickupid) return index=ares,ACTOR_TYPE;
	new mres = binarysearch(MoneyPickups,pickupid,0,sizeof(MoneyPickups)-1);
	if(mres > -1 && MoneyPickups[mres] == pickupid) return index=mres,MONEY_TYPE;
	
	
	return INVALID_PICKUP_TYPE;
}

If i do it this way, the ActorPickups part is being executed, and they work well but MoneyPickups doesnt work anymore
It seems like the the second part is always being skipped for some reason, how can i fix this problem?

The for loop code works fine but i dont know why it doesnt work with binary search.
My binsearch function works fine and the return value should be the index of the found element inside of the array.

Код:

stock binarysearch(a[],key,l,r)
{
	new k;
	while(r >=l)
	{
		k = (l+r)/2;
		if(key == a[k])
		{
			return k;
		}
		if(key < a[k]) 
		{
			r = k-1;
		}
		else 
		{    
			l= k+1;
		}        
	}    
	return -1;
}

Re: Using binarysearch instead of for loop doesnt work - NaS - 16.03.2017

Shouldn't this

Код:

if(ares > -1 && MoneyPickups[ares] == pickupid) return index=ares,ACTOR_TYPE;

checking ActorPickups[ares] == pickupid instead of MoneyPickups?

Re: Using binarysearch instead of for loop doesnt work - faxxe - 16.03.2017

Quote:

Originally Posted by NaS

Shouldn't this

Код:

if(ares > -1 && MoneyPickups[ares] == pickupid) return index=ares,ACTOR_TYPE;

checking ActorPickups[ares] == pickupid instead of MoneyPickups?

Wut

You are right, i will try

Re: Using binarysearch instead of for loop doesnt work - faxxe - 16.03.2017

Damn, dude thats it

Its working now! Dont know why i didnt find this! +rep

Re: Using binarysearch instead of for loop doesnt work - Nero_3D - 16.03.2017

Already saw your last topic but I am still wondering why do you do it in this roundabout way instead of indexing the array with the pickupid
The only advantage I see is that the access to all ActorPickups and MoneyPickups is faster but I think this is rarely needed / or not needed at all in my opinion

Re: Using binarysearch instead of for loop doesnt work - faxxe - 16.03.2017

Quote:

Originally Posted by Nero_3D

Already saw your last topic but I am still wondering why do you do it in this roundabout way instead of indexing the array with the pickupid
The only advantage I see is that the access to all ActorPickups and MoneyPickups is faster but I think this is rarely needed / or not needed at all in my opinion

Yep its really fast! Just O(log n) execution time, so in my array with size of MAX_PICKUPS - sizeof(ActorPickups), around 4000 elemts O(log n) would be 3,64.
The way by using a for loop is O(n) so 4000, so its almost 1000 times faster!

I want to add other pickup types and a pickup streamer so i guess it could be useful in the feature.

Re: Using binarysearch instead of for loop doesnt work - Nero_3D - 16.03.2017

Quote:

Originally Posted by faxxe

I want to add other pickup types and a pickup streamer so i guess it could be useful in the feature.

Ah okay, I thought everyone who exceed the sa-mp limit uses the streamer plugin nowadays

Because otherwise if you stay under the limit you simply could have done

PHP код:



new gPickupType[MAX_PICKUPS];

// GenerateRandomPickup

pickupid = CreatePickup(modelid,type,rx1,ry2,rz3,virtualworld);

// some security checks to check that pickupid is valid

gPickupType[pickupid] = MONEY_TYPE;

// OnPlayerPickUpPickup

switch(gPickupType[pickupid])