 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / General / February 2006Avoiding failsafe behaviour of iterators
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 NotDashEscaped: You need GnuPG to verify this message Hi group, I want to iterate over a set, remove the current element, then inside the iteration iterate over the set again, such that I consider all possible pairs with the first element, then remove the second element from the set too if it meets certain constraints. In the end I will end up with an empty set. Of course I am not interested in the deletion process, but I build a new set (equivalence relation) on the way. Now if I understand correctly, the process I describe will cause the first iterator to fail, because it notices elements have been deleted. In my scenario though, this is not a problem; I don?t want to consider pairs in which one of the elements has been deleted. That?s what I deleted them for in the first place. So two questions: - can I get around this failsafe behaviour of java.util.Set? - Does anybody see a better way to implement this? Some code to illustrate the problem (not tested or compiled, still in the process of pseudocoding): (note: no foreach, as I need Iterator.remove) Equivalence<State> equivalence = new Equivalence<State>(allStates); // allStates is the domain of the equivalence for (Iterator<State> inner = allStates.iterator(); inner.hasNext(); ) { State q = inner.next(); Set<State> equivClass = new HashSet<State>(); equivClass.add(q); inner.remove(); for (Iterator<State> outer = allStates.iterator(); outer.hasNext();){ State qPrime = outer.next(); // do a lot of computation to see whether q and q' are equivalent if (equivalent){ equivClass.add(qPrime); outer.remove(); } } equivalence.add(equivClass); } TIA, H.  SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org > - Does anybody see a better way to implement this? If you could explain what it is you are trying to achieve (instead of what you technically want to do), it might be easier to understand the problem and suggest other ways of solving the problem. /tom -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 NotDashEscaped: You need GnuPG to verify this message tom fredriksen schreef: >> - Does anybody see a better way to implement this? > > If you could explain what it is you are trying to achieve (instead of > what you technically want to do), it might be easier to understand the > problem and suggest other ways of solving the problem. Well, I tried, but obviously not hard enough. Well, to be precise, I am trying to implement the minimisation of a tree automaton, as described in TATA, on page 35 of chapter one, which can be found here: http://www.grappa.univ-lille3.fr/tata/; in short: /* I am following the algorithm in TATA, p. 35. * Minimization Algorithm MIN * input: complete and reduced DFTA A = (Q,F,Qf,d) * begin * Set P to {Qf,Q\Qf} // P is the initial equivalence relation * repeat * P' = P * //Refine equivalence P in P' * qP'q' if * qPq' and * forall f in ?Fn forall q1, ..., qi-??1, qi+1, ..., qn in?? Q * d(f(q1,...,qi-1,q,qi+1,...,qn))Pd(f(q1,...,qi-??1,q',qi+1,...,qn)) * until P' = P * Set Qmin to the set of equivalence classes of P * // we denote by [q] the equivalence class of state q w.r.t.P * Set dmin to {(f, [q1], . . . , [qn]) ->?? [f(q1, . . . , qn)]} * Set Qminf to {[q] | q in Qf } * output: DFTA Amin = (Qmin,F,Qminf,dmin) * end */ The crucial part is the computation of the equivalence classes. To do this, I hav a method which more or less does what I wrote in the original mail. So what I have to do inside the loop above is loop over all states in Q, for each state compute its equivalence class, and add that class to the equivalence-under-construction. To compute this equivalence class, I have to loop over all other states, and check whether those two conditions are met (which involves even more looping over all function symbols in the signature of the automaton). The crucial thing to note is that it is useless to compute the equivalence class of a state that already has been found equivalent to a state whose equivalence class I computed in a previous loop, as it will give the same result. So I thought: if I delete a state from the set I still have to consider once I put it in some equivalence class, I avoid doing unnecessary loops. Perhaps a better approach would be to take one arbitrary element, compute its equivalence class, remove this class from the set of states, then repeat until the set is empty. Hm, seems better, I guess I can do it this way. Sometimes it helps to spell out your problems. Still open for other suggestions. Thanks for taking the time, H. SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org > The crucial thing to note is that it is useless to compute the > equivalence class of a state that already has been found equivalent to a > state whose equivalence class I computed in a previous loop, as it will > give the same result. So I thought: if I delete a state from the set I > still have to consider once I put it in some equivalence class, I avoid > doing unnecessary loops. Forget the silly mathematic set notation and think like a software engineer or computer scientist. To find oens you already have what data structure would you need? I would have some type of map which allows me to avoids multiple passes over the data. Right off without spending time to study the problem I'm not sure of the key to my suggested map (equivalenceclass and state?), but your sentences above seem to be nearly talking about looking something up. The map can link back to the "natural" representation of the set, be it array or other data structure. -Paul -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 NotDashEscaped: You need GnuPG to verify this message P.Hill schreef: >> The crucial thing to note is that it is useless to compute the >> equivalence class of a state that already has been found equivalent to a [quoted text clipped - 5 lines] > Forget the silly mathematic set notation and think like a software > engineer or computer scientist. Unfortunately, I am a mathematician with minor cs education, working as a programmer. > To find oens ? ones? > you already have what > data structure would you need? I would have some type of map which [quoted text clipped - 4 lines] > The map can link back to the "natural" representation of the set, > be it array or other data structure. Not entirely clear to me, but seems to make sense. In fact, you want to compute all equivalence classes at the same time, having a map mapping a state to its class. Seems possible, some brainstorming: - pick one state, make its class (i.e. new HashSet<State>()) add state1->class1 to map add state1 to list of visited states - pick next state, check whether it is equivalent to the first, yes -> add to class no -> make new class add state2->class2 to map add state2 to list of states ... - pick next state, for all previous states: check whether it is equivalent, yes-> add to class no to all-> make new class add staten->classn to map add staten to list of states Here the list of states represents the equivalence classes by one element of it. I don?t even need a new list there, but can iterate over the KeySet of the map. This needs only one loop over all states, plus an inner loop of maximal length the number of equivalence classes. Thus it is an O(nm) algorithm. Not bad, probably best possible. Waaw, your post seemed cryptic at first, but many thanks! H. SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org Hendrik Maryns sez: ... > Not entirely clear to me, but seems to make sense. In fact, you want to > compute all equivalence classes at the same time, having a map mapping a [quoted text clipped - 26 lines] > length the number of equivalence classes. Thus it is an O(nm) > algorithm. Not bad, probably best possible. Not sure I understand what you're trying to do, but it looks like if you use state as map key you should get O(n) performance: override equals() for the state, hashmap.get( state ) should give you O(1), if your "state class" is one object, .put( state, class ) is O(1) as well. So you only have to iterate over all states. SignatureAll whitespace is equivalent except in certain situations -- ANSI C standard committee On Wed, 15 Feb 2006 19:24:07 -0800, "P.Hill" <goodhillREMOVE@xmissionREMOVE.com> wrote, quoted or indirectly quoted someone who said : >Forget the silly mathematic set notation and think like a software >engineer or computer scientist. To find oens you already have what [quoted text clipped - 4 lines] >seem to be nearly talking about looking something up. >The map can link back to the "natura Is there any way to compute a sort of equivalence class hashcode to help you find the collisions rapidly? You just keep attempting to add new equivalence classes and have a HashMap refuse to add them if it has them already. You'd think HashSet would be a useful tool for arranging unique Objects. However, it is useless for that purpose because it will only tell you if an equivalent Object is already in the HashSet. It won't divulge a reference to the canonical Object itself. To arrange uniqueness, you need a HashMap with key and value referencing the same canonical unique Object. see http://mindprod.com/jgloss/hashset.html SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 NotDashEscaped: You need GnuPG to verify this message Roedy Green schreef: > On Wed, 15 Feb 2006 19:24:07 -0800, "P.Hill" > <goodhillREMOVE@xmissionREMOVE.com> wrote, quoted or indirectly quoted [quoted text clipped - 13 lines] > new equivalence classes and have a HashMap refuse to add them if it > has them already. Equivalence classes are just Sets of states. But they all have to be disjoint. Indeed I wrote a wrapper class Equivalence<E>, which has add(Set<E>), and tests for disjointness to all previously entered classes. The problem is, that I am building up those classes in the process: I make an empty set, add the element, then go on finding equivalent elements, and add those, then when I am sure there are no more (i.e. after I have compared the first with all others), add the class to the equivalence. > You'd think HashSet would be a useful tool for arranging unique > Objects. However, it is useless for that purpose because it will only > tell you if an equivalent Object is already in the HashSet. It won't > divulge a reference to the canonical Object itself. To arrange > uniqueness, you need a HashMap with key and value referencing the same > canonical unique Object. Yes, but I plan on making the classes first and then adding them, once they are complete. Maybe I should rethink my strategy. And thanks for the pointers to EnumSet (not usable, there are way too much States to use the State Pattern, and they are created dynamically), and BitSet. I think I will revert to the latter in a later stage of implementation, for now, I?m happy if it works, be it less efficiently. H. SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 [quoted text clipped - 39 lines] > equivalence.add(equivClass); > } As you know, the second Iterator will cause the first to fail. Is it possible to use a second Set that is identical in content to the first? Is it possible to avoid Iterator.remove()? (As I understand your requirement, it is to build up a result; you shouldn't have to modify the input sets to do that.) -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 NotDashEscaped: You need GnuPG to verify this message Adam Maass schreef: >> Equivalence<State> equivalence = new Equivalence<State>(allStates); >> // allStates is the domain of the equivalence [quoted text clipped - 15 lines] > > As you know, the second Iterator will cause the first to fail. Indeed. > Is it possible to use a second Set that is identical in content to the > first? No, as the point of removing the states is to avoid iterating over them. > Is it possible to avoid Iterator.remove()? (As I understand your > requirement, it is to build up a result; you shouldn't have to modify the > input sets to do that.) Yes. See my other post for a first idea of a solution. Thanks, H. SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org > Is it possible to use a second Set that is identical in content to the > first? Or just copy the data into a List. Use indexes/ListIterator on the copy. Tom Hawtin SignatureUnemployed English Java programmer http://jroller.com/page/tackline/ > I want to iterate over a set, remove the current element, then inside > the iteration iterate over the set again, such that I consider all > possible pairs with the first element, then remove the second element > from the set too if it meets certain constraints. Can't you just do (pseudo-code): while (set isn't empty) { elem1 = remove arbitrary element from set; for (elem2 in set) // uses iterator { if ( blahBlahBlah(elem1, elem2) ) remove elem2; // via iterator } } You only use one iterator at a time. The key as that the implementation of "remove arbitrary element" can be done with a temporary iterator which you discard as soon as it has removed the first element. -- chris -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 NotDashEscaped: You need GnuPG to verify this message Chris Uppal schreef: >> I want to iterate over a set, remove the current element, then inside >> the iteration iterate over the set again, such that I consider all [quoted text clipped - 12 lines] > } > } Indeed, this is a nice approach, I thought about it later, too. > You only use one iterator at a time. The key as that the implementation of > "remove arbitrary element" can be done with a temporary iterator which you > discard as soon as it has removed the first element. Hm, seems pity to me to have to create an iterator just to get one element, but the interface of Set does not allow to get an arbitrary element, so I guess that is the only way... Thanks, H. SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org Hendrik Maryns sez: ... > Hm, seems pity to me to have to create an iterator just to get one > element, but the interface of Set does not allow to get an arbitrary > element, so I guess that is the only way... Last I looked concurrent modification exception (or whatever it's called) was thrown only if the number of elements has changed. If your set allows null elements, you could try setting deleted ones to null instead of actually deleting them. (But check the implementation in src.zip first.) Dima SignatureThe most horrifying thing about Unix is that, no matter how many times you hit yourself over the head with it, you never quite manage to lose consciousness. It just goes on and on. -- Patrick Sobalvarro Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2008 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.