On 08/21/2012 10:04 PM, Jan Provazník wrote:
On 08/17/2012 11:45 AM, Imre Farkas wrote:
On 08/15/2012 05:24 PM, Jozef Zigmund wrote:
On Thu, 2012-08-02 at 14:24 +0200, ifarkas@redhat.com wrote:
This revision includes:
- a new page where user can enable/disable strategies
- fixes to address Jan's and Jozef's findings during their review
ACK, you can pushed the patchset.
As we discussed it's needed to fix ASAP instance variables in patchset according "Coding Guidelines" part Instance Variables. [1]
Question at the end: Other story is discussion about probability distribution and throwing out the matches of selected provider accounts. As we weren't able to say exactly if it's ok or not, we'd like to ask community(the best some person who has good knowledge from this field) :)
What's happened? We are using random match in two places when we are trying to run deployment. One of that match is thrown out because the calculated match is changed by new one in the final launch. The questions is if we are breaking probability distribution of the provider account's selection ?
I don't think so. If it was true, it would mean that the pseudo random generator distributes random numbers in some regular periodic cycle. It would be very weak pseudo random generator ;).
You can check that this is not happening with simple test (same principle as Imre's script):
- generate however-big-you-want array of rand(100) numbers
- pick every 3rd (or other) item and add them to array
- group numbers in this array by their first number -> you get 10
groups, counts of random numbers in each group is balanced
But Jozef mentioned that this selection algorithm is called 3 times when launching a deployment - twice in pre-launch phase when checking if a match exists. For these checks it's not necessary to pick one match from possible matches - in these pre-launch validations all you need to know is if any match exists.
So it would be best to split find_match_with_common_account method into 2 methods: first which returns all possible matches (this would be used both in pre-launch validations and launch itself) and second method which picks one match from all possibilities.
Yeah, perfectly makes sense! Thanks for getting into the discussion on the probability distributions! :-)
Imre
[1] - https://www.aeolusproject.org/redmine/projects/aeolus/wiki/Coding_Guidelines
-- Jozef
I created a simple script which you can run on current master branch. It runs a number of experiments in 2 ways:
- 1st: it is using all the number from the random generator
- 2nd: it randomly throws out some outputs of the random generator
Then it displays how many times each match have been picked. If you run the experiment you can see there's no significant difference whether we are throwing away some numbers of the random generator, or not.
Here's the source: https://gist.github.com/3377279
Why is that? I don't exactly know the mathematical proof for this, so maybe I am wrong here, but intuitively you can consider the following: Each pick has the same probability distribution: x% to be picked as A, y% to be picked as B. No matter which subset do you examine, it is true for the whole subset that x% of the subset will be picked as A, and y% will be picked as B, because each and every item in the subset belong to the same probability distribution.
Any issue regarding the test, or comment/critique are more than welcomed!
Imre
Jan