Re: Determining uniqueness in a string.

A combination of all ten digits uniquely is a permutation which can be generated using Algorithm::FastPermute.

So given that the code has to execute for thousands of candidate combinations, it seems it might be better to store all the permutations as the keys of a hash (with value 1 throughout) only once and start accepting candidates to check just by looking up in the hash. If using Linux, an additional optimisation could be to store the pre-calculated set of permutations in a Storable on the /shm (persistent shared memory) device, so that the hash of valid permutations doesn't even need to be calculated between runs of the program and can be loaded directly from persistent shared memory at the beginning of any given run.

-M

Free your mind

Comment on Re: Determining uniqueness in a string.

Replies are listed 'Best First'.
Re^2: Determining uniqueness in a string. by BrowserUk (Patriarch) on Oct 03, 2005 at 15:40 UTC
If you have 350 MB available for storing the hash, this works out to be about 60% faster than tye's regex (excluding generation and build time). Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal? "Science is about questioning the status quo. Questioning authority". The "good enough" maybe good enough for the now, and perfection maybe unobtainable, but that should not preclude us from striving for perfection, when time, circumstance or desire allow.	[reply] [d/l]
Re^2: Determining uniqueness in a string. by Perl Mouse (Chaplain) on Oct 03, 2005 at 15:20 UTC
There will be 10! entries in the the hash. Extrapolating the size it takes to store 10!/10, 10!/5 and 10!/2 10 character strings in a hash, I estimate the needed size to be around 170Mb. Trying to stuff 10! of those strings in a hash cause all the machines I tried it on to swap - with top showing a memory usage of around half a Gb of the running program. `Perl --((8:>*`	[reply]
Re^3: Determining uniqueness in a string. by Moron (Curate) on Oct 03, 2005 at 15:51 UTC
I had thought of that - but 170 Mb would be okay for all my machines - one compromise might be to store say 5 digits (10P5) with a simple array of the remaining 5 being referenced as the value, e.g.: `$hash{ '01234' } = \( 5..9 );` [download] This would reduce the storage by a factor of more than a hundred, while requiring that the last half of the digits would then need to be compared with the array being also pre-stored at each outer node of the hash, but with the same 120x performance for those last digits as compared with processing 10 without prestored results -- total performance improvement should be around 80x in this case (but PLUS the fixed overheads if you don't have linux shared memory to pre-store the solution) -M Free your mind	[reply] [d/l]


good chemistry is complicated, and a little bit messy -LW
	PerlMonks