Werner LEMBERG <[email protected]> writes: >> It would appear that the main application is the removal of >> duplicates, with the idiom >> >> sort >> uniq >> >> in some form or other. This can be replaced by >> >> make map/hash of pointers >> iterate through list >> if pointer in hash, delete list element, else put pointer in hash >> >> in order to a "stable" O(n lg n) uniq for which the structure of the >> final list does not depend on the memory order of the original >> elements. > > This certainly sounds like a better solution.
However, rethinking this, it seems like a "solution" for not seeing the symptoms of a problem: we stabilize results artificially. Mike saw significant fluctuations of his results here depending on the memory position of data, presumably because of a wrong order of operations in the followup. The "better solution" I propose above will lead to the identical wrong order of operations from run to run. Now the best that might have happened is that the memory address merely served as a tie-breaker for two equally good solutions. In that case, it may make sense to apply a tie-breaker that is less arbitrary. "It was first in the list before we started", however, is a hardly less arbitrary tie-breaker. It is merely deterministic, but in no other respect natural. So I'd prefer if we kept the more efficient variant. It turns out that weeding out duplicates _and_ post-sorting according to some arbitrary criterion can be done in a single pass if you use the memory address comparison as a tie-breaker for the post-sorting (assuming that the post-sorting will always think x == x). However, comparing memory addresses is cheap, and the post-sorting may have a more expensive sorting criterion, so weeding out duplicates separately (via the memory address thingy) before starting with more expensive sorting criteria still makes good sense, as then the expensive sorting criterion is needed less often. -- David Kastrup _______________________________________________ bug-lilypond mailing list [email protected] https://lists.gnu.org/mailman/listinfo/bug-lilypond
