Re: [Pharo-users] Is there a way to stop arrays sorting automatically?
Henry said
It's not broken, but certainly deserves a comment as to why it operates inline; In the general case, one should not use/care about any given permutation outside the block. Allocating n! instances of an n-sized array by default, is a bad tradeoff considering performance degradation for uses where n >> 3. In the first case, a user can add a simple #copy, while in the second case, a user would probably want/have to reimplement the method entirely. <<< Thanks, that makes perfect sense. I will have a go at adding a suitable comment. Cheers Andy
I would check this in Pharo, but have so far failed to get it running under Ubuntu 17.10. Squeak _is_ running there, sort of, and the definition of #permutationsDo: in Interval is this code: permutationsDo: aBlock "Repeatly value aBlock with a single copy of the receiver. Reorder the copy so that aBlock is presented all (self size factorial) possible permutations." "(1 to: 4) permutationsDo: [:each | Transcript cr; show: each printString]" self asArray permutationsDo: aBlock Exactly the same comment is found in SequenceableCollections. Are you sure that Pharo has something different? "with a SINGLE COPY of the receiver" is pretty important. The thing is that the number of permutations is so astronomically large that it really never makes sense to retain all of them in memory. Suppose an array of n elements takes n+2 words, then holding all of the permutations of 1..k would take (k+2)*k! + k! + 2 = k!(k+3)+2 words. For k = 5 10 15 20 that's 962 47174402 23538138624002 55956746188062720002 words. If we assume a 64-bit laptop with 16 GiB of memory, k=12 is already too big. Yet it is perfectly reasonable to iterate over all 12! permutations. Another thing about iterating over permutations is that straightforward algorithms take O(1) time per permutation, but not if you copy every time. I don't think I've ever found a use for #permutationsDo: that didn't need to be turned into a specialised backtracking algorithm with cutoffs pushed as early as possible.
+1 for what Richard says. Moreover, if you know that n is small, and you really want copies of all th permutations, then adding a copy message to your block is really simple. But if the permutationsDo: method made the copy, then it would be useless except for very small values of n. The comment that Richard quotes is in Pharo too. There is a good reason for the current behaviour, and it is documented.
participants (3)
-
Andrew Black -
Andy Burnett -
Richard O'Keefe