Dismiss Notice
60,000 passwords have been reset on July 8, 2019. If you cannot login, read this.

Big-O question

Discussion in 'Triggers & Scripts' started by Kercyn, Oct 9, 2009.

  1. Kercyn

    Kercyn

    Joined:
    Feb 14, 2009
    Messages:
    850
    Resources:
    0
    Resources:
    0
    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 :thumbs_up:

    And yes, this is my 500th post :grin:
     
  2. Mcasdf

    Mcasdf

    Joined:
    May 13, 2009
    Messages:
    248
    Resources:
    0
    Resources:
    0
    Uhm sorry but what is Big-O?
     
  3. Kercyn

    Kercyn

    Joined:
    Feb 14, 2009
    Messages:
    850
    Resources:
    0
    Resources:
    0
    I was tempted to use LMGTFY, but here it is...
     
  4. aznricepuff

    aznricepuff

    Joined:
    Feb 22, 2006
    Messages:
    749
    Resources:
    4
    Maps:
    2
    Spells:
    1
    Tutorials:
    1
    Resources:
    4
    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.
     
  5. Kercyn

    Kercyn

    Joined:
    Feb 14, 2009
    Messages:
    850
    Resources:
    0
    Resources:
    0
    I was hoping that there would be an easier way :con:

    Thanks anyway :grin:
     
  6. Cokemonkey11

    Cokemonkey11

    Wurst Reviewer

    Joined:
    May 9, 2006
    Messages:
    3,271
    Resources:
    18
    Tools:
    1
    Maps:
    5
    Spells:
    3
    Tutorials:
    2
    JASS:
    7
    Resources:
    18
    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.
     
  7. Shyhalu

    Shyhalu

    Joined:
    Mar 20, 2008
    Messages:
    207
    Resources:
    0
    Resources:
    0
    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.
     
  8. Void

    Void

    Joined:
    Apr 16, 2009
    Messages:
    85
    Resources:
    0
    Resources:
    0
    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)
     
  9. Kercyn

    Kercyn

    Joined:
    Feb 14, 2009
    Messages:
    850
    Resources:
    0
    Resources:
    0
    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.
     
  10. Shyhalu

    Shyhalu

    Joined:
    Mar 20, 2008
    Messages:
    207
    Resources:
    0
    Resources:
    0
    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.



    Code (vJASS):

    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.
     
  11. Kercyn

    Kercyn

    Joined:
    Feb 14, 2009
    Messages:
    850
    Resources:
    0
    Resources:
    0
    Yeah, I know that. Even if it's n3, 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.

    Code (vJASS):

        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