[JASS] Asymptotic notation and storage systems

[HINDYhat]

This is for Dr Super Good...

Now, DSG was contradicting me on one aspect of a storage system. He explained to me that his storage system looped through an array of handles to find the handle that you wanted. Now I told him that typecasting + arrays would be a much better idea (considering the amount of iterations), but he kept saying I was wrong.

So he was basically saying that O(n) is faster than O(1).

Can anyone please get on my side and prove to him that O(1) is faster than O(n), because this is getting ridiculously retarded.

 

[Dr Super Good]

Take into account that O(1) only works with handle up to a certain ammount, after that the whole system stops storing or resorts to game cache. Also note that O(1 to n) is also ment to be used for storing values that are not recalled at a rapid rate.

It also proves that it is possiable to attach values to other values without using H2I() at all and is extreemly easy to program as well as it can makes linking objects together extreemly easy.

I do not deny that it is less efficent than hindy's method when comming to hundreds of objects, but for a few it allows extreemly easy MUI in spells and seems to create hardly any lag at all.

 

[HINDYhat]

Take into account that O(1) only works with handle up to a certain ammount

Considering you are storing shit in arrays too, ditto. Stacked arrays are hardly inefficient, anyway.

...is extreemly easy to program...

So is using the GUI, but that doesn't make it better. Besides, what's so hard about calling a function? call SetData(yourHandle, yourAttachment)

I do not deny that it is less efficent than hindy's method when comming to hundreds of objects

It's also less efficient if you have more than 1 object.

 

[Earth-Fury]

Take into account that O(1) only works with handle up to a certain ammount, after that the whole system stops storing or resorts to game cache.

If you're at all capable with the JASS language, the handle count should never reach 8191, let alone 24573. (The only possible scenario I see that happening in is if you leak large numbers of locations, groups, and units, and even then its an insane notion to think that a logical limit on a design pattern is to blame for any issues that arise.)

Also note that O(1 to n) is also ment to be used for storing values that are not recalled at a rapid rate.

Then you advise usage of two separate systems to achieve the same goal, but under different stress levels? And you advocate using the more computationally intensive method anyway?

It also proves that it is possiable to attach values to other values without using H2I() at all and is extreemly easy to program as well as it can makes linking objects together extreemly easy.

Many such methods exist... the reason they aren't used is as they are unfeasibly complex and computationally intensive when compared to the alternates. Hash tables are a prime example. (And who would implement a hash table in JASS anyway? We have gamecache already!... DAMN YOU COHADAR AND YOUR CONTINUED STUPIDITY!)

I do not deny that it is less efficent than hindy's method when comming to hundreds of objects, but for a few it allows extreemly easy MUI in spells and seems to create hardly any lag at all.

Errr, so equivalent ease of use is more important than efficiency... ... Sorry, DSG, but your logic is flawed.

 

[DiscipleOfLife]

Having one array with all handles stored to it and using linear search to find them fails because the n, in the O(n) will be high on average.

However if you can designate a separate space for each spell to store their handles to, it doesn't sound like a bad idea to use linear search to find them, incase each of those spells only have a few handles stored at a time. An O(n) attachment system doesn't need to use H2I() so it most propably is faster than any O(1) handle attachment system using H2I() when n is VERY small.

The thing is that because such a system would only be faster for scripts that only store to a few handles at a time (and thus n being small), it doesn't really matter if the system is fast or not, since it won't be under very much stress unless you use it at crazy intervals.

Also, H2I() is safe, so the only 'pro' you get when not using it is the time you save by not calling it.


@ Earth-Fury & Hashtables
Why not when they are faster than gamecache? You lose some flexibility but gain some speed. That flexibility isn't always needed so why not sacrifice it to shave off some milliseconds?

 

[Dr Super Good]

The fact also remains that it is undoughtly flexable. Noobs can use the system in their map and it will not fail to opperate after a while if their map leaks a ton which I can garuntee that they mostly will. Thus it gives extreem portability as any map can use it and it will always function, even if all handle values are used up and WC3 crashes it will function untill the end). Thus my logic is not flawed. Also the system was designed to not loop through many objects at all, for example a 4 part spell that has few instances at once.

Other useful advantages are the ease of data management, for example you could instantly destroy all instances of a spell via 1 loop with a very sane number of times it loops (as apposed to having to make eithor a special array to store all instances in a simlar order or loop through the max size of the array which is a hell of a lot slower). Also you can preform searches easily for any object that is attached.

Basically, I used it purly in my spell pack to experiment and so that I can assure people that my spells will never fail, no matter how badly made their map is (will leak to a degree if units are removed but no one sane does that). For my own map I most certainly would use a direct system as then I know exactly how many handles are made and I know that no handles are leaked.

On average for what I use the system for with the exception of my damage shield system, its probably a hell of a lot better than game cache which is what I wanted.

 

[Earth-Fury]

If all you really care about is ensuring your released systems will work 100% of the time, then whats wrong with gamecache backup in a system that is faster in any case where the map maker doesn't completely fail at life?

You want to use a method which is less optimal in 99% of cases, simply because it works semi-optimally for people who obviously will never have anything work with any kind of optimal speed? It would take 1 handle leak a second for 40 minutes to reach a handle count of 24573. That is a LOT of leaks, which will cause non-optimal performance of ANYTHING. Your logic IS flawed.

 

[HINDYhat]

Your logic is flawed because retards don't even use Jass storage systems anyway.

 

[Earth-Fury]

Your logic is flawed because retards don't even use Jass storage systems anyway.

now your logic is flawed, as retards do use released spells and systems which can be cut and pasted in to their maps

 

[HINDYhat]

They do, but they don't develop the spells themselves, therefore they have no reason to fuck up the system.

 

[Drone]

Huh...

Am I reading this correctly?

O(n) Finding a handle by looping through an (extended) array compared to O(1) where you retrieve a handle in an (extended) array by using it's unique instance handle id.....

Isn't is obvious that looping through an array is inefficient, or am I just missing something .....

 

[HINDYhat]

That's what I said...

 

[Troll-Brain]

i'm not a programmer but i care about performance issues so tell me which is the fastest solution :

use this : http://wc3campaigns.net/pastebint.php?t=93235&code=29e26baa170b05af2d3ffd04408ae7e1
I know call a function is "slow" but imagine i avoid the calls of Set and Get with a textmacro.
Or use a struct and use the cache to link the index of the struct and the handle ?

 

[GhostWolf]

i'm not a programmer but i care about performance issues so tell me which is the fastest solution :

use this : http://wc3campaigns.net/pastebint.php?t=93235&code=29e26baa170b05af2d3ffd04408ae7e1
I know call a function is "slow" but imagine i avoid the calls of Set and Get with a textmacro.
Or use a struct and use the cache to link the index of the struct and the handle ?

I'm not a human but I care about idiot issues so tell me which is the best solution:

use this : http://www.hiveworkshop.com/forums/newthread.php?do=newthread&f=271
Or use my mind and think where to post my stuff ?

 

[Troll-Brain]

I'm not a human but I care about idiot issues so tell me which is the best solution:

use this : http://www.hiveworkshop.com/forums/newthread.php?do=newthread&f=271
Or use my mind and think where to post my stuff ?

i just don't want to create an other thread because it's quite the same subject, don't cry

 

[Earth-Fury]

i'm not a programmer but i care about performance issues so tell me which is the fastest solution :

use this : http://wc3campaigns.net/pastebint.php?t=93235&code=29e26baa170b05af2d3ffd04408ae7e1
I know call a function is "slow" but imagine i avoid the calls of Set and Get with a textmacro.
Or use a struct and use the cache to link the index of the struct and the handle ?

using DataSystem and / or timed event to link the index of a struct to a handle. A call to H2I and a few simplistic boolean comparisons will beat the speed of the gamecache.

 

[Troll-Brain]

using DataSystem and / or timed event to link the index of a struct to a handle. A call to H2I and a few simplistic boolean comparisons will beat the speed of the gamecache.

and i doesn't matter if an array is quite full or quite empty ?
the time to read/write an array variable don't change ?

 

[Earth-Fury]

and i doesn't matter if an array is quite full or quite empty ?
the time to read/write an array variable don't change ?

There would be some initial allocation time, as arrays are supposedly allocated in chunks up to 8191 indexes. However, once an array is initialized, the read / write times should be constant, no matter which index you access.

 

[Troll-Brain]

There would be some initial allocation time, as arrays are supposedly allocated in chunks up to 8191 indexes. However, once an array is initialized, the read / write times should be constant, no matter which index you access.

thx + rep

15 characters limitation is so boring

 

[Earth-Fury]

thx + rep

15 characters limitation is so boring

The reason that limit is there is to prevent posts such as that one. The reason you can leave a comment in reputation is to give a space to make such comments.

 

[Troll-Brain]

The reason that limit is there is to prevent posts such as that one. The reason you can leave a comment in reputation is to give a space to make such comments.

but sometimes the answer should be like that :
No.

But well it doesn't really matter, we are not in a perfect world

 

[Dr Super Good]

Hindy noted it incorrectly, it actually was O(1 to n) as it sometimes does not have to loop at all and for optimization sake, it only loops as much as it has to. However I can not deny that if arrays were much bigger that hindys method would be unbeatable, sadly they are not.

And like I said, it works best in some situations thus my logic is not flawed since obviously you would not use that method for a physics system but it works amply fast for 1-2 simple spells.

Fact still remains that it is probably faster than game cache when it comes to small numbers of objects being stored which is ample for most simple spells. Also it depends highly on what you are doing, since the loop could be incorperated into part of the spell itself (preforming a spell effect) which then would make it better suited than other methods.

 

[Earth-Fury]

Hindy noted it incorrectly, it actually was O(1 to n) as it sometimes does not have to loop at all and for optimization sake, it only loops as much as it has to. However I can not deny that if arrays were much bigger that hindys method would be unbeatable, sadly they are not.

... you can use multiple arrays with a lightning quick conditional. You could potentially use 50 arrays together to form a single "mega array" with more index space than you can imagine, sacrificing quite a bit of time to looking up the correct array at that scale, of course. But at a lower scale, with 3 or so arrays, you loose almost no time to array lookup.

Also, "O(1 to n)" isn't proper big O notation, DSG... O(n) is. I suggest you read http://en.wikipedia.org/wiki/Big_O_notation

And like I said, it works best in some situations thus my logic is not flawed since obviously you would not use that method for a physics system.

It doesn't work better barring a 0.1% of cases where n is close to 1, and even there no one has compared iteration to the speed of an H2I call. Your logic is flawed.

Fact still remains that it is probably faster than game cache when it comes to small numbers of objects being stored which is ample for most simple spells.

Yes, and cutting a single finger off when preparing dinner is better than cutting your whole hand off. It doesn't mean you're smart for cutting only your finger off.

 

[Dr Super Good]

Who the hell cares if hindy shoots his mouth off with all crazy formula that half the people have not heard of, the fact still remains that 90% of the time when used it will only have to loop a few times (1-2) which makes your logic flawed as it is amply fast for most simple spell systems.

You also are avoiding the benifits completly, and I am sure there is a spell where such a system is the most efficent way to make it (if it was made).

However this has given me an idea, for larger number of objects a combination of the 2 ideas could be used. Basically the idea is that it stores the items in an approximate address of where the handle would be but each slot is worth 5-6 handles. If the slot is used it moves onto the next slot and stores it. This idea would be an improvement for speed when it comes to many objects as it will have a reduced search size to preform. However such a system would purly be for show and would be slower for less objects but still it is the sort of thing done just for the sake of it.

To think this whole argument started over a respawn system where hindy was confusing this one guy on chat so I listed many ways he could make one. Then Hindy suddenly took a dislike to it and started to think that I some how said it was better than his way when I only said it has some advantages (of which speed was not one of them).

 

[Drone]

@Dr Super Good

Do you have a link to the system you're talking about?

So basically you are saying to divide storage space into handle clusters?
How can this ever be slower for less objects but not for many objects?
I mean you know in what slot a handle is stored. I assume you're indexing them inside the clusters. It means that you do an extra operation where it's not needed and if you need the approximate address of where the handle would be, then you'd have to resort to H2I as well.
So basically you're back where you started. Speed is not improved, since you know where a handle approximately is, no matter how many objects.
This will never be faster or more efficient than a single handle id reference lookup.

 

[Earth-Fury]

Who the hell cares if hindy shoots his mouth off with all crazy formula that half the people have not heard of,

Errrr... Most people who do a lot of programming become familiar with Big O Notation on at least some level...

the fact still remains that 90% of the time when used it will only have to loop a few times (1-2) which makes your logic flawed as it is amply fast for most simple spell systems.

1. Provide benchmarks that are not impirical or based on FPS. Theres a microtime function in JAPI's default package, if i recall correctly.
2. Your logic is now again flawed in the concept that dual implementations to reach any kind of optimal efficiency in the event n is large would be required.

You also are avoiding the benifits completly, and I am sure there is a spell where such a system is the most efficent way to make it (if it was made).

again, that would be something like 0.1% of cases at best, and even then the performance differential would be so low that it wouldn't really matter.

However this has given me an idea, for larger number of objects a combination of the 2 ideas could be used. Basically the idea is that it stores the items in an approximate address of where the handle would be but each slot is worth 5-6 handles. If the slot is used it moves onto the next slot and stores it. This idea would be an improvement for speed when it comes to many objects as it will have a reduced search size to preform. However such a system would purly be for show and would be slower for less objects but still it is the sort of thing done just for the sake of it.

.. A hash table would be a better solution, if I understand what you're saying well enough. And even there, a single H2I call would likely dwarf the speed of a hash table in most circumstances.

To think this whole argument started over a respawn system where hindy was confusing this one guy on chat so I listed many ways he could make one. Then Hindy suddenly took a dislike to it and started to think that I some how said it was better than his way when I only said it has some advantages (of which speed was not one of them).

No comment.

 

[Dr Super Good]

Earth-Fury, your logic is flawed and thats that. (Im fed up with this).

The main reason he even made this topic was to annoy me which he does as a hobby.

The only reason I even tryed such a system is called "experimenting" which is something most programmers do at some stage.

 

[Drone]

Earth-Fury, your logic is flawed and thats that. (Im fed up with this).

The main reason he even made this topic was to annoy me which he does as a hobby.

The only reason I even tryed such a system is called "experimenting" which is something most programmers do at some stage.

The fact that you're ignoring my post completely says enough. Not that I'm bothered with that. I was merely interested in why you were so determined. Curious as to how your system functions considering the things you said about it.

Something else that programmers do is develop a system, test it compared to other systems and then make claims they can back up with something presentable. You on the other hand seem to start the other way around, considering you haven't defended your claims with anything solid.

No offense Dr. Super Good, but that's not the thing most programmers do at some stage.

 

[Dr Super Good]

You can see the system in action in my spell pack available in the spell section (the damage shield system and other spells use it).
I am aware that it is slower and thus a comparision is hardly needed. I however will one day like to compare it with game cache to see where the cutoff point is as that is about the only other logical test next to a leak test.

The only other advantage is like I said, as the data is close together it is easy to preform an entire opperation on which could be useful for some spell ideas.

 

[HINDYhat]

Who the hell cares if hindy shoots his mouth off with all crazy formula that half the people have not heard of, the fact still remains that 90% of the time when used it will only have to loop a few times (1-2) which makes your logic flawed as it is amply fast for most simple spell systems.

Considering this was suggested for a unit revive system, it could also be A LOT more than 1-2 iterations. Besides, asymptotical notation is essential to coding efficient algorithms and systems, and isn't as unknown as you'd expect.

Also, O(n) includes the possibility that n could also be a constant below the total amount of objects. There are tons of 'big O'-type functions, such as o, which is just like O except the amount of operations excludes the nth operation, I believe. There is also Θ (which I believe includes n and all constants above n) and ω, which includes all constants above n without the nth operation... Not sure anyway, don't kill me if I got this wrong.

 

[Captain Griffen]

    integer array BIG[40955]

Problem solved. Slightly off O(1) due to the split meaning it is faster at the lower levels, but that's a good thing. As fast as using normal arrays at the lower levels, and faster if you leak handle indexes because it doesn't go over to game cache.

 

[DiscipleOfLife]

    integer array BIG[40955]

Problem solved. Slightly off O(1) due to the split meaning it is faster at the lower levels, but that's a good thing. As fast as using normal arrays at the lower levels, and faster if you leak handle indexes because it doesn't go over to game cache.

BIG[H2I(h)-0x100000] is just a simpler version of HSAS, CSData and all the other data systems, but not faster, atleast not in practice (when you don't leak an insane amount of handles). I guess it's better because you only have to have H2I written somewhere in your map instead of an attachment system, but what I'm trying to say here is that this solves nothing that hasn't been solved before.

"As fast as using normal arrays at the lower levels" is just not true. Normal arrays are nearly 3 times faster when storing at the lowest level. Propably because of the function call that comes with big arrays:

BIG after JassHelper

globals
integer array s__BIG
integer array s__2BIG
integer array s__3BIG
integer array s__4BIG
integer array s__5BIG
integer array s__6BIG
endglobals

function sg__BIG_get takes integer i returns integer
    if(i<8191) then
        return s__BIG[i]
    elseif(i<16382) then
        return s__2BIG[i-8191]
    elseif(i<32764) then
        if(i<24573) then
            return s__3BIG[i-16382]
        else
            return s__4BIG[i-24573]
        endif
    else
        if(i<40955) then
            return s__5BIG[i-32764]
        else
            return s__6BIG[i-40955]
        endif
    endif
endfunction

function sg__BIG_set takes integer i,integer v returns nothing
    if(i<8191) then
        set s__BIG[i]=v
    elseif(i<16382) then
        set s__2BIG[i-8191]=v
    elseif(i<32764) then
        if(i<24573) then
            set s__3BIG[i-16382]=v
        else
            set s__4BIG[i-24573]=v
        endif
    else
        if(i<40955) then
            set s__5BIG[i-32764]=v
        else
            set s__6BIG[i-40955]=v
        endif
    endif
endfunction

[EDIT]I mean ~3 times faster when H2I()-0x100000 isn't included, i.e. getset small[0] versus getset BIG[0]. I now realize you propably were taking the H2I()-0x100000 in consideration in which case the difference wouldn't be as significant.[ENDOFEDIT]


I made a little benchmark with Bob666's benchmarker:

    local integer d = 1
    loop
        exitwhen Stack[d] == t
        set d = d + 1
    endloop

vs

local integer d = BIG[H2I(t)-0x100000]

When the timer t was stored in Stack[1], linear search was 17% faster, and when it was stored in Stack[2] the contestants tied. I did only 1 short test per scenario so these aren't too exact numbers, but this still goes to show that using linear search is a viable option in some cases.

 

[HINDYhat]

Thank you for doing a benchmark.

Great DSG, so your method is faster when ONE object is stored in index 1. AWESOME.