4 ms·
The Dwarfs and The Fast Marking Algorithm
- tptacek 16y agoShort summary: instead of relying on initialization to a known value, ignore the initial values of the array and rely instead on a consistency constraint (data may be random, but won't be random and satisfy the constraint) that you can set and check. A neat trick you can probably use in other places as well.
- shasta 16y agoAnyone know the name of this algorithm? There is a similarly solved classic problem in complexity theory: Given an O(m) list of O(n)-bounded integers, determine if there are duplicates in O(m) time and O(n) space.
- ori_b 16y agoI don't know if it has a name (it seems to simply be referred to as "an efficient sparse set representation"), but I think I initially remember seeing it introduced in "Compilers: Principles, Techniques, and Tools" in an exercise at some point in the past. A good description of it is here: http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html http://research.swtch.com/2008/03/using-uninitialized-memory...
- duskwuff 16y agoThis seems trivially incorrect. If both arrays are randomized at the outset, there is nothing to prevent them from containing valid data indicating a state having objects marked. In fact, if you free one set of arrays used by this structure and immediately allocate another, there's a good chance that your "random" initial state will, in fact, be the exact one you just freed.
- jaspervdj 16y agoThe trick is in the counter variable. Read the update section, and the source code (it's not much, really).
- sesqu 16y agoRight, you neglected to mention the use for the counter in your prose.
- RiderOfGiraffes 16y agoI'm often left confused by people who downvote me without leaving a correction or counter-argument, so I guess I ought to explain why I've downvoted you here. Who is the "you" in your sentence? The author of the comment to which you reply? They never mention the counter. The author of the original article? You're not replying to them. And the counter isn't mentioned in the original prose, but it's clearly mentioned in the description of the algorithm. Surely that's reasonable. It's a single variable, hence constant to allocate in both space and time. So your comment seems to make an unreasonable criticism that doesn't add value, and that's why I've downvoted it.
- sesqu 16y agoI was referring to jaspervdj, who is both the author of the comment to which I reply and the author of the original article (well, I presume). The article states: "an element in array can, by chance, point to an element in marks, but this won’t matter since the element in marks won’t point back, and so we can determine it’s fake." This sentence is missing the part where the counter is made use of, and as such is erroneous. The mentioned element can point back, and its index must be compared with the counter to ascertain whether it is valid. Although that is a small omission, it is in no way trivial, and probably the source of all the confused comments the posting received.
- RiderOfGiraffes 16y ago
- abhat 16y agoWont it have issues with concurrency, Since you have multiple dwarves constantly updating the list, you must ensure that only one dwarf is updating the list at a time. Otherwise there can be errors if two dwarfs try to add rooms at a same time!