Big-O question

[Kercyn]

Is there any way to find the Big-O of a GUI trigger or a JASS script? Yes, there is, but how? I'm not really familiar with Big-Os, that's why I ask. The last thing I need is smart-ass remarks, so either be constructive or don't post at all. Thank you

And yes, this is my 500th post

 

[Mcasdf]

Uhm sorry but what is Big-O?

 

[Kercyn]

I was tempted to use LMGTFY, but here it is...

 

[aznricepuff]

Unless the author of the script specifically tells you, you would have to read through the code and do the calculations yourself. Or you can get stopwatch and run benchmarks yourself (though depending on the script it may be hard to set up). This way is not very accurate, but you'll at least be able to tell the difference between sublinear, linear, and greater than linear run times.

 

[Kercyn]

I was hoping that there would be an easier way

Thanks anyway

 

[Cokemonkey11]

if there's a loop looking through an entire array, it's O(n). Otherwise it's O(1).

Technically that's not true, but it should suffice for what you're looking for.

 

[Shyhalu]

Post the trigger in question

Otherwise use the general rule

loop is Order 1 through n, or O(n)
This includes unit groups and player groups
This also includes arrays, but n is defined, so its always 1 to arraysize

non looped is 1, or O(1)


n^2 is a inner loop, or loop inside loop

IE:
loop
exit condition
some actions
loop2
exitcondition2
someactions 2
endloop

So, lets say you picked every unit within a preset region, thats O(n)
Now if for every unit picked, you made a certain or random amount of spell effects, thats O(n) too

That would be N^2, because for every N units you are doing N actions

N^3 would be for every spell effect you made, you made a certain amount of items.

N+N would be one loop right after another
N^2+N is one loop with an inner loop, after that entire thing is finished you perform another loop.

 

[Void]

most of the time this information doesn't help you very much at least for jass scripts because you generally work with very small sample sizes (like 10 simultaneous instances of a spell) so it happens quite often that O(ln(n)) is slower then O(n) for all reasonable cases (most of the time you can say O(1) is good and every thing else is slower how much slower do a benchmark)
(if you got a lot of data (like >100 integers and you want to sort them) O-notation can help you o/c but for every thing else use benchmarks)

 

[Kercyn]

The trigger in question has a loop inside a loop inside a loop, that's why I asked. But, as you said, work in JASS is done in very small scripts, so it would be OK.

 

[Shyhalu]

The trigger in question has a loop inside a loop inside a loop, that's why I asked. But, as you said, work in JASS is done in very small scripts, so it would be OK.

Thats O(N^3)

Depending on its actual content it could be more. But its probably something you should avoid running constantly or alongside other scripts.

Small scripts pile up, and just because they are small does not mean they are efficient. That is fairly dependant on the amount of function calls.
This would be much less efficient than incrementing x inside the actual loop and similiar things would add onto the big O of the trigger.

function incrementx takes nothing returns nothing
      udg_x = udg_x+1
endfunction

loop
     exitwhen udg_x == 0

      call incrementx()
      //some code here
endloop

Just because its in JASS does not mean its lagless, its just faster than GUI because it avoids wrapper functions and junctions. But that doesn't mean poorly coded or inefficient things get a free pass from lag.

 

[Kercyn]

Yeah, I know that. Even if it's n³, it shouldn't take that long, because for small values of n there's not much difference. Anyway, here's the actual script so that you can see for yourself.

    loop
        exitwhen ct > 10000
        loop
            exitwhen eligible = true
            loop
                exitwhen DistanceBetweenPoints(temploc1,temploc2) > 200
                set temploc1 = GetRandomPointInDisk(GetLocationX(castloc), GetLocationY(castloc), 0, 400)
                set temploc2 = GetRandomPointInDisk(GetLocationX(castloc), GetLocationY(castloc), 0, 400)
            endloop
            call ForGroupBJ(GetUnitsInRangeOfLocMatching(450, castloc, Condition(TentPickGroup)), function TentGroupPopulation)      
            if tentgroup == null then
                set eligible = true
            endif
        endloop
    //Some other imba stuff here, ct gets increased by 500 each time it loops.
    endloop