CODEWITHSUNDEEP
performancepermutationprocessorsheaps-algorithm
Andy
Andy

Reputation: 1

High volumes, long running. Life’s too short

Need help. Possibly even psychiatric help, for even attempting this!

This process promises to run for ever. Need advice on how to improve it from a performance point of view and any ideas about how to get the data processed more efficiently so that the job can complete.

I am Permuting 60 short strings. They are paired with a second set of 60 which are effectively static. So everything gets paired with everything. Then the paired values will be used to do some database searches. This processing is not yet in place and will, of course, add even more demand. I have implemented Heap’s Permutation algorithm(https://en.wikipedia.org/wiki/Heap%27s_algorithm) in VB.Net and I’m satisfied that it is running efficiently.

Foolishly, I kicked it off with 20 string pairs. 3 days later it had not finished. I put in some diagnostic reporting and collected elapsed times for permuting 5 to 14 elements. 5 is finished in 0.00975 seconds. Fine. Even 11, with a factorial value of 39,916,800, the number of permutations, finished in a respectable 5.6 seconds. The data I collected was consistent and as I expected. I ran the job with 14 elements. It took 3h:22m:14s.

From this data, I project that the 20 element permutation that I attempted to run, would have taken roughly 10738 years. Life’s too short…

While it was running, I observed that Windows 10 Scheduler was allocating a steady 11.5% to 20.5% of the CPU, the default. So, about 16% on average. Had it been able to allocate 100%, I imagine the process would have finished 6 times faster. My machine is a Lenovo laptop with processor Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz 1.99GHz. Not a fast machine.

So, I want to push the number of elements to permute to 60. On my current machine, that would take billions of years, I imagine.

Any suggestions for very fast, multiple, parallel, processors gratefully received.

Any ideas for restructuring, splitting, parallel processing of the data also welcome. It is not an exercise however, and the 60 elements are real life elements. For testing purposes I will run a reduced set. For the real thing, I need permutations for all 60. Each permutation, as it is generated, needs to be present and available in full for the additional processing that needs to take place.

Am I asking too much? Thanks in advance for your advice and experience.

Upvotes: -1

Views: 81

Answers (1)

mascoj
mascoj

Reputation: 1329

Let's just start with the most obvious problem here.

60! is an insanely large number. Let me repeat, insanely large.

60! bits is (according to Wolfram Alpha) ≈ 80000 × information entropy of a solar-mass black hole ( ≈ 1×10^77 b )

So even if your data was stored as 1 bit per permutation, you'd need a universe to store it.

Generating all permutations of 60 objects is tractably infeasible for any computing resource, given from now until the heat-death of the universe.

Upvotes: 2

Related Questions