Whats gonna be count faster?

The place to post your WML questions and answers.

Moderator: Forum Moderators

Forum rules
  • Please use [code] BBCode tags in your posts for embedding WML snippets.
  • To keep your code readable so that others can easily help you, make sure to indent it following our conventions.
Post Reply
User avatar
ChaosRider
Posts: 846
Joined: April 15th, 2012, 1:15 pm

Whats gonna be count faster?

Post by ChaosRider »

I have interesting question, whats gonna be count faster? Its about creating switch which works on some random variable, when they are low then we dont care much because its allways fast done, but what when they are huge? Like a 10^5? Is it better to make it in one rand:

Option A
Spoiler:
or maybe its better to split it for many lower random values like this one below:

Option B
Spoiler:
Creator of WOTG (+2880 units), MWC (+615 units), SurvivorsArea, RandomColosseum, RC WOTG, RC MWC, ColosseumRandomClonesBattle, BetweenDarknessAndLight, StealingWeapons, MoreUnitsForms, MoreDamageTypes, CanBeOnlyOne, ColosseumOneWinner, BonusSpam, CriticalStrike - available at 1.12 Wesnoth server.
User avatar
Dugi
Posts: 4961
Joined: July 22nd, 2010, 10:29 am
Location: Carpathian Mountains
Contact:

Re: Whats gonna be count faster?

Post by Dugi »

Please ignore this, I haven't read the code properly. The other guys are right.

I wish I could delete posts also after that somebody posted later.
Last edited by Dugi on March 30th, 2014, 10:09 pm, edited 2 times in total.
User avatar
Alarantalara
Art Contributor
Posts: 786
Joined: April 23rd, 2010, 8:17 pm
Location: Canada

Re: Whats gonna be count faster?

Post by Alarantalara »

I have no idea, you could always time it and see. Lua can grab the current time if you're curious.

However, at that size, I would be very tempted to try some other approach entirely if only to avoid going insane with the amount of writing involved. Also, I would suspect that at that size, you'd end up cutting and pasting a lot and most of the results wouldn't be entirely unique, which should be possible to write once and provide parameters to change the behaviour instead.
User avatar
iceiceice
Posts: 1056
Joined: August 23rd, 2013, 2:10 am

Re: Whats gonna be count faster?

Post by iceiceice »

ChaosRider:

From source inspection, there is no way that (1) would be slower.

https://github.com/wesnoth/wesnoth/blob ... .cpp#L1984

I assume that you would think that it might be slower because it would cause wesnoth to list all numbers from 1 - 10,000, but that isn't how it is implemented. The method of (2) would probably only be necessary if you wanted probabilities like 10^{-200}, and then it would be because you can't store integers with such precision.
User avatar
Alarantalara
Art Contributor
Posts: 786
Joined: April 23rd, 2010, 8:17 pm
Location: Canada

Re: Whats gonna be count faster?

Post by Alarantalara »

iceiceice wrote:ChaosRider:

From source inspection, there is no way that (1) would be slower.

https://github.com/wesnoth/wesnoth/blob ... .cpp#L1984

I assume that you would think that it might be slower because it would cause wesnoth to list all numbers from 1 - 10,000, but that isn't how it is implemented. The method of (2) would probably only be necessary if you wanted probabilities like 10^{-200}, and then it would be because you can't store integers with such precision.
Following the source above, (2) is required if you want more than 1 073 741 823 possibilities.

I had to guess, I'd be in favour of option (2) being faster at some point. The Lua code https://github.com/wesnoth/wesnoth/blob ... l-tags.lua evaluates every switch statement just in case more than one passes. By breaking it into pieces, you could reduce the number of cases evaluated by orders of magnitude at this scale. Dugi does have a point about the extra calls into the Lua engine, but that should only push the crossover out farther. Still 10^5 isn't that huge, so I still have no idea.
User avatar
iceiceice
Posts: 1056
Joined: August 23rd, 2013, 2:10 am

Re: Whats gonna be count faster?

Post by iceiceice »

Alarantalara: How could (2) possibly be faster than (1)? The source block I referenced will run the same speed for any range of the form "x..y" of long ints. At least, I don't see how the "crossover point" could be different from the "(1) stops working" point.

Edit: And just so that the argument is not totally pointless... from looking at it a second time I have spotted either a bug / some undocumented behavior. I think that if you call,

Code: Select all

      [set_variable]
         name=random_value
         rand=1..3,1..2,1
      [/set_variable]
then you will get 1 with chance 3/6, 2 with chance 2/6, 3 with chance 1/6?

Should confirm and document on wiki perhaps.
User avatar
Alarantalara
Art Contributor
Posts: 786
Joined: April 23rd, 2010, 8:17 pm
Location: Canada

Re: Whats gonna be count faster?

Post by Alarantalara »

The problem isn't generating random numbers, the problem is in the switch statement. If the switch statement actually has 10^5 different case values, then the Lua code that takes that quickly generated variable will still evaluate every last one of the cases to see if they match. So it takes O(1) to generate the value but O(n) to do the switch (where n is the number of cases in the switch. In option 2, there are now log(max value) random numbers generated, but you now evaluate O(log N) case statements (where the base of the log is the number of cases at each level).

Edit:
The behaviour described in your edit is exactly correct. I believe the case where they're written out =1,1,1,2,2,3 is used in UtBS to select unit types with varying probability, except it's a list of unit types, not numbers, of course.
User avatar
ChaosRider
Posts: 846
Joined: April 15th, 2012, 1:15 pm

Re: Whats gonna be count faster?

Post by ChaosRider »

I just asked such a question cause i have one event many times started (why i will tell it later). Its for dialogues between units (i have diffrent sentences for players units and diffrent for ai sides). Its started in: recall, recruit, advance, side turn. Right now i have 50 sentences for players and 50 for ai units (if unit is allowed to talks then later its picked randomly one of 50 this sentences). In this event i store all units (first i thought to store only from side which is turn now, but this could looks worse, thx other way units from many sides can talks in same turn), so to dont slow much players game i was curious about this. Is it better to split it for more than one switch or not, but i see it could be usefull only with values which aint used to describe anything in normal human life :P.

Btw about dialogues (i think this should be in some other topic but well), you could use this simple idea in main wesnoth (make it more advance, depence each dialogue of adjected enemies/teammates or maybe other things (depence of unit race/ hp which have right now)). Game could be more realistic, and as i know no body thought about it earlier :P.

Below is my code for this event:
Spoiler:
Creator of WOTG (+2880 units), MWC (+615 units), SurvivorsArea, RandomColosseum, RC WOTG, RC MWC, ColosseumRandomClonesBattle, BetweenDarknessAndLight, StealingWeapons, MoreUnitsForms, MoreDamageTypes, CanBeOnlyOne, ColosseumOneWinner, BonusSpam, CriticalStrike - available at 1.12 Wesnoth server.
User avatar
Alarantalara
Art Contributor
Posts: 786
Joined: April 23rd, 2010, 8:17 pm
Location: Canada

Re: Whats gonna be count faster?

Post by Alarantalara »

That's about what I expected when you asked the question.

Conveniently, I did exactly what you want in a currently unreleased campaign. You want something like this:

Code: Select all

[event]
        name=prestart

        [set_variables]
            name=alarmed_peasant_messages
            [value]
                message= _ "Help!"
            [/value]
            [value]
                message= _ "Invaders!"
            [/value]
            [value]
                message= _ "My home is in ruins!"
            [/value]
            [value]
                message= _ "Undead!"
            [/value]
            [value]
                message= _ "Save me!"
            [/value]
            [value]
                message= _ "We’re under attack!"
            [/value]
            [value]
                message= _ "Run for your lives!"
            [/value]
            [value]
                message= _ "Where are the militia?"
            [/value]
            [value]
                message= _ "Foul monster!"
            [/value]
            [value]
                message= _ "Stop eating my chickens!"
            [/value]
            [value]
                message= _ "Stay away from my children!"
            [/value]
            [value]
                message= _ "I should have locked the doors!"
            [/value]
            [value]
                message= _ "Aah! They’re coming in the window!"
            [/value]
            [value]
                message= _ "What’s that foul smell?"
            [/value]
        [/set_variables]
[/event]

[other_event]
	[set_variable]
		name=i
		rand=0..$($alarmed_peasant_messages.length|-1)
	[/set_variable]
	[message]
		speaker="peasant_$x1|_$y1|"
		message=$alarmed_peasant_messages[$i].message
	[/message]
	{CLEAR_VARIABLE alarmed_peasant_messages[$i],i}
[/other_event]
I also clear alarmed_peasant_messages[$i] in the method to ensure that no message is used more than once. You can leave that part out if you want.

Edit: This is just a copy/paste from what I had written, thus the very different speaker definition, but I'm sure you can see how to adapt it to your messages.
User avatar
ChaosRider
Posts: 846
Joined: April 15th, 2012, 1:15 pm

Re: Whats gonna be count faster?

Post by ChaosRider »

I would add also option to recreate this whole variable when all values are used and this variable is empty.

About this using once each option i had near to this problem in my add-on Colosseum Random, when i wanted to do each land be created once, i did there loop which is picking from 6 options some land type only if other variable which describe this land (is it was already used or not) have some value equal for it, if its avaible then i increase other variable by 1 (of which depence loop), whats funny is when 5 options are picked loop is doing all the time until it wont take the last one option :D...


If you got some funny rpg sentences which arent in this posted by me event feel free to post it here or in private message, but i would suggest to dont send one or two sentences, but atleast 10 or more :D... (for players & for ais). How it works you can check by playing Modified World Conquest or Modified World Conquest 2 (this second is easier :P)
Creator of WOTG (+2880 units), MWC (+615 units), SurvivorsArea, RandomColosseum, RC WOTG, RC MWC, ColosseumRandomClonesBattle, BetweenDarknessAndLight, StealingWeapons, MoreUnitsForms, MoreDamageTypes, CanBeOnlyOne, ColosseumOneWinner, BonusSpam, CriticalStrike - available at 1.12 Wesnoth server.
User avatar
Alarantalara
Art Contributor
Posts: 786
Joined: April 23rd, 2010, 8:17 pm
Location: Canada

Re: Whats gonna be count faster?

Post by Alarantalara »

I have no need to restock the message list in what I'm writing since trigger happens fewer times than I have messages. The reason I mention leaving the clear out is that once you have enough messages, it's less important that there be no repeats and the clear operation is almost as slow as the switch is since it has to update all the elements that come after the removed one.

Incidentally, there is an even better way to create the variable array, but I'll leave you to figure it out. I have changed my own code to use it now. Serves me right for cloning something else from that same campaign instead of looking at how best to write it.
Post Reply