Hi!
I would like to write a conflict resolution strategy that orders (all) activations into a completely random order. I've written a simple class implementing the Strategy interface, looks like this: public final class RandomActivation implements Strategy, Serializable { private static final long serialVersionUID = 1L; private static final String mName = "RandomActivation"; private final Random mGenerator; public RandomActivation() { mGenerator = new Random(); } public final int compare( final Activation pAct1, final Activation pAct2 ) { int result; final double r1 = mGenerator.nextDouble(); final double r2 = mGenerator.nextDouble(); if ( r1 < r2 ) { result = 1; } else if ( r1 > r2 ) { result = -1; } else { result = 0; } return result; } public final String getName() { return mName; } } (I don't know whether the random numbers are really necessary, as I've read in a former message that returning 0 would result an indeterministic order of the activations, anyway my problem has nothing to do with this.) I've noticed that this strategy doesn't behave as I have expected. I watched how many times the compare method was invoked after a new activation was placed to the agenda, and I don't understand why there are such activations that aren't compared to every other activations. Isn't this the way the conflict resolution should work? Compare every activations to every others? For example there was such activation that was compared to only one other activation... Why is that? Or am I misunderstanding something? Please explain me how and how many times the compare method should be invoked, and how can I reach a complete random reordering of the agenda. Thanks. -------------------------------------------------------------------- To unsubscribe, send the words 'unsubscribe jess-users [hidden email]' in the BODY of a message to [hidden email], NOT to the list (use your own address!) List problems? Notify [hidden email]. -------------------------------------------------------------------- |
Lots of questions here, some explicit, some implicit. First I'll
answer the one about why you saw an activation compared to only one other. Imagine you have a sorted partial deck of cards -- say you have a 5, 8, 10, Queen and King, in that order, top to bottom. The cards have the important property that they can be sorted into a definite order, and that order is stable. No matter how many times you check, the 8 will always belong after the 5. Furthermore, it's a transitive relationship: if the 10 comes after the 8, and the 8 comes after the 5, then the 10 comes after the 5. Remember that -- we'll come back to it later. Now imagine you're picking up cards one at a time and inserting them into the correct place in the deck. If you pick up a 4, what would you do? You'd see the 5 on top, realize that it's larger than the 4, and lay the 4 on top. You've only compared the 4 to one other card. If you picked up a Jack, however, you might cut the deck in half and compare the card with the middle cards, searching around a little bit until you found the right spot. The important point is that no matter what, the number of necessary comparisons is always vastly less than the number of cards. Jess doesn't actually use a fully-sorted array for the agenda. It uses a "priority queue" (which you can Google to learn more about). A priority queue is a very clever data structure which (1) always knows which item is "first", (2) lets you insert new items quickly, and (3) lets you remove items quickly. So Jess always knows which activation is next to fire, but it doesn't need to have all the other ones sorted completely into firing order; they're only partially ordered. This keeps the number of comparisons to a minimum. Now, to return to the point about the stable, transitive ordering: your compare() function doesn't behave that way, and that's bad because Jess assumes that it does. If we call that function with the same arguments again and again, we'll get different answers. That means it doesn't provide a random ordering, but rather *no* ordering. What you want is a function whose result for any two activations is unpredictable but stable and transitive. You could achieve this by creating a map of activation/Integer pairs. The first time compare() sees a given activation as an argument, it could generate a random number and store it in that map. Then the comparisons would just be comparing those random numbers from the map. By keeping the random numbers and reusing them for all comparisons, you'd achieve both necessary properties. On Jun 5, 2011, at 7:03 AM, Rajcsányi Vilmos wrote: > Hi! > > I would like to write a conflict resolution strategy that orders > (all) activations into a completely random order. > I've written a simple class implementing the Strategy interface, > looks like this: > > public final class RandomActivation implements Strategy, Serializable > { > private static final long serialVersionUID = 1L; > private static final String mName = "RandomActivation"; > private final Random mGenerator; > > public RandomActivation() > { > mGenerator = new Random(); > } > > public final int compare( final Activation pAct1, final > Activation pAct2 ) > { > int result; > > final double r1 = mGenerator.nextDouble(); > final double r2 = mGenerator.nextDouble(); > > if ( r1 < r2 ) > { > result = 1; > } > else if ( r1 > r2 ) > { > result = -1; > } > else > { > result = 0; > } > return result; > } > > public final String getName() > { > return mName; > } > } > > (I don't know whether the random numbers are really necessary, as > I've read in a former message that returning 0 would > result an indeterministic order of the activations, anyway my > problem has nothing to do with this.) > I've noticed that this strategy doesn't behave as I have expected. > I watched how many times the compare method was invoked after a new > activation was placed to the agenda, > and I don't understand why there are such activations > that aren't compared to every other activations. Isn't this the way > the conflict resolution should work? > Compare every activations to every others? > For example there was such activation that was compared to only one > other activation... Why is that? > Or am I misunderstanding something? Please explain me how and how > many times > the compare method should be invoked, and how can I reach a complete > random reordering of the agenda. > Thanks. > > > -------------------------------------------------------------------- > To unsubscribe, send the words 'unsubscribe jess-users > [hidden email]' > in the BODY of a message to [hidden email], NOT to the list > (use your own address!) List problems? Notify [hidden email] > . > -------------------------------------------------------------------- --------------------------------------------------------- Ernest Friedman-Hill Informatics & Decision Sciences, Sandia National Laboratories PO Box 969, MS 9012, Livermore, CA 94550 http://www.jessrules.com -------------------------------------------------------------------- To unsubscribe, send the words 'unsubscribe jess-users [hidden email]' in the BODY of a message to [hidden email], NOT to the list (use your own address!) List problems? Notify [hidden email]. -------------------------------------------------------------------- |
Thank you for the detailed answer! All clear now...
2011.06.05. 18:33 keltezÃ©ssel, Ernest Friedman-Hill Ãrta: > Lots of questions here, some explicit, some implicit. First I'll > answer the one about why you saw an activation compared to only one > other. > > Imagine you have a sorted partial deck of cards -- say you have a 5, > 8, 10, Queen and King, in that order, top to bottom. The cards have > the important property that they can be sorted into a definite order, > and that order is stable. No matter how many times you check, the 8 > will always belong after the 5. Furthermore, it's a transitive > relationship: if the 10 comes after the 8, and the 8 comes after the > 5, then the 10 comes after the 5. Remember that -- we'll come back to > it later. > > Now imagine you're picking up cards one at a time and inserting them > into the correct place in the deck. If you pick up a 4, what would you > do? You'd see the 5 on top, realize that it's larger than the 4, and > lay the 4 on top. You've only compared the 4 to one other card. > > If you picked up a Jack, however, you might cut the deck in half and > compare the card with the middle cards, searching around a little bit > until you found the right spot. The important point is that no matter > what, the number of necessary comparisons is always vastly less than > the number of cards. > > Jess doesn't actually use a fully-sorted array for the agenda. It uses > a "priority queue" (which you can Google to learn more about). A > priority queue is a very clever data structure which (1) always knows > which item is "first", (2) lets you insert new items quickly, and (3) > lets you remove items quickly. So Jess always knows which activation > is next to fire, but it doesn't need to have all the other ones sorted > completely into firing order; they're only partially ordered. This > keeps the number of comparisons to a minimum. > > Now, to return to the point about the stable, transitive ordering: > your compare() function doesn't behave that way, and that's bad > because Jess assumes that it does. If we call that function with the > same arguments again and again, we'll get different answers. That > means it doesn't provide a random ordering, but rather *no* ordering. > What you want is a function whose result for any two activations is > unpredictable but stable and transitive. You could achieve this by > creating a map of activation/Integer pairs. The first time compare() > sees a given activation as an argument, it could generate a random > number and store it in that map. Then the comparisons would just be > comparing those random numbers from the map. By keeping the random > numbers and reusing them for all comparisons, you'd achieve both > necessary properties. > > On Jun 5, 2011, at 7:03 AM, RajcsÃ¡nyi Vilmos wrote: > >> Hi! >> >> I would like to write a conflict resolution strategy that orders >> (all) activations into a completely random order. >> I've written a simple class implementing the Strategy interface, >> looks like this: >> >> public final class RandomActivation implements Strategy, Serializable >> { >> private static final long serialVersionUID = 1L; >> private static final String mName = "RandomActivation"; >> private final Random mGenerator; >> >> public RandomActivation() >> { >> mGenerator = new Random(); >> } >> >> public final int compare( final Activation pAct1, final Activation >> pAct2 ) >> { >> int result; >> >> final double r1 = mGenerator.nextDouble(); >> final double r2 = mGenerator.nextDouble(); >> >> if ( r1 < r2 ) >> { >> result = 1; >> } >> else if ( r1 > r2 ) >> { >> result = -1; >> } >> else >> { >> result = 0; >> } >> return result; >> } >> >> public final String getName() >> { >> return mName; >> } >> } >> >> (I don't know whether the random numbers are really necessary, as >> I've read in a former message that returning 0 would >> result an indeterministic order of the activations, anyway my problem >> has nothing to do with this.) >> I've noticed that this strategy doesn't behave as I have expected. >> I watched how many times the compare method was invoked after a new >> activation was placed to the agenda, >> and I don't understand why there are such activations >> that aren't compared to every other activations. Isn't this the way >> the conflict resolution should work? >> Compare every activations to every others? >> For example there was such activation that was compared to only one >> other activation... Why is that? >> Or am I misunderstanding something? Please explain me how and how >> many times >> the compare method should be invoked, and how can I reach a complete >> random reordering of the agenda. >> Thanks. >> >> >> -------------------------------------------------------------------- >> To unsubscribe, send the words 'unsubscribe jess-users [hidden email]' >> in the BODY of a message to [hidden email], NOT to the list >> (use your own address!) List problems? Notify >> [hidden email]. >> -------------------------------------------------------------------- > > --------------------------------------------------------- > Ernest Friedman-Hill > Informatics & Decision Sciences, Sandia National Laboratories > PO Box 969, MS 9012, Livermore, CA 94550 > http://www.jessrules.com > > > > > > > > > -------------------------------------------------------------------- > To unsubscribe, send the words 'unsubscribe jess-users [hidden email]' > in the BODY of a message to [hidden email], NOT to the list > (use your own address!) List problems? Notify > [hidden email]. > -------------------------------------------------------------------- > -------------------------------------------------------------------- To unsubscribe, send the words 'unsubscribe jess-users [hidden email]' in the BODY of a message to [hidden email], NOT to the list (use your own address!) List problems? Notify [hidden email]. -------------------------------------------------------------------- |
Free forum by Nabble | Edit this page |