Array Loops

03-28-2009, 01:48 PM	#1
wraithseeker	Can anyone explain to me what is a O (N) search. I looked at that keyword through dusk knockback system in feedbacks and didn't understand it. How do I prevent it a O (N) search and why is it bad to have a O (N) search. How do I not use a O (N) search and why is does people not like it?

03-28-2009, 02:30 PM

Skater

That O stands for the Big O Notation.
So, lets say you have an unsorted array of n elements and you want to find the first element with the value 5.
You have to loop through the whole array.

JASS:

local integer i=0
loop
exitwhen i>n //n the size of the array
    if array[i]==value then//5 or whatever
        return i
    endif
    set i=i+1
endloop
return -1//not found

So you need max n trys.
If the arrays is sorted for example you just need O(log n). (binary search)
So those O-Notation means how many trys you have to do at least until you find you element.

You can prevent an O(n) search by using for example sorted arrays and bsearch or binary-trees.
Or try a totally different method for you system or whatever.

03-28-2009, 02:39 PM	#3
wraithseeker	I see, thanks + REP

03-28-2009, 07:47 PM	#4
akolyt0r	another great way to prevent O(n) searches in warcraft is e.g Indexing ... For example for units with UnitIndexingUtils or PUI ...and you will have O(1) all the time.

03-28-2009, 09:08 PM	#5
0zyx0	Is there any way to do that with unit type or item type integers? If not, what is best, an O(n) search, or a big if...elseif...-block?

03-29-2009, 12:42 AM	#6
PurplePoot	For an index 'ABCD', you can store it in an array at position ['ABCD'-'A000']. For example, 'A005' is stored at ['A005'-'A000']. 'h003' would be stored at ['h003'-'h000'].

03-29-2009, 01:39 AM

grim001

JASS:

function GetStringIndex takes string s returns integer
    // this function returns the position that wc3 stores a given string at in its string table
    return s
    return 0
endfunction

function SetRawcodeData takes integer rawcode, integer data returns nothing
    set somearray[GetStringIndex(I2S(rawcode))] = data
endfunction

function GetRawcodeData takes integer rawcode, integer data returns nothing
    return somearray[GetStringIndex(I2S(rawcode))]
endfunction

This method works flawlessly online and lets you avoid using GC to attach to rawcodes. It will glitch in single player maps if the user saves and resumes the game at a later time, since the string table will get rebuilt.

03-29-2009, 01:45 AM

PurplePoot

Quote:

Originally Posted by Litany

'h100' - hx000' = 0x10000, too large for a normal array. You'd have to use a sized array or Table, and in the case of Table the subtraction is pointless.

Aye, it assumes you just linearly use indices, but fair enough.

03-29-2009, 06:39 AM	#9
Viikuna-	Stupid pointless post. I read that I2S wrongly.

03-29-2009, 02:22 PM	#10
Anitarf	I'm not a big fan of i2s. Table should work just fine for such a purpose.