digitalmars.D.learn - Permutation Sort Algorithm Very Slow
- Agora (16/16) Jun 07 2014 Hi.
- Chris Cain (7/8) Jun 07 2014 One of the main reasons is because the number of permutations an
- Ali GOREN (7/15) Jun 07 2014 Thank you. I can not resolve it in quicker time, right?
- Chris Cain (14/20) Jun 07 2014 You might be able to come up with a faster way to permute, but
- Ali GOREN (3/27) Jun 07 2014 Thank you Chris. Now I understand. I thought myself incorrectly
- monarch_dodra (19/20) Jun 08 2014 Depends what exactly you want to achieve. This will achieve the
Hi. I've found some code import std.stdio, std.algorithm; void permutationSort(T)(T[] items) pure nothrow { while (items.nextPermutation) {} } void main() { auto data = [2, 7, 4, 3, 5, 1, 0, 9, 8, 6, -1]; data.permutationSort; data.writeln; } This code is running very slow Runtime Seconds: 5-6 Why is running slow? Sorry for my bad english :( :) Thank you :)
Jun 07 2014
On Saturday, 7 June 2014 at 21:40:08 UTC, Agora wrote:Why is running slow?One of the main reasons is because the number of permutations an array has is n!. Thus the expected runtime is O(n!). That's a slow, slow algorithm in general. In particular, your array with length 11 has 39,916,800 permutations (although it, obviously, doesn't have to go through *all* of those to get the sorted sequence in this case).
Jun 07 2014
Thank you. I can not resolve it in quicker time, right? Also: dlang online compiler and dpaste: return code: 9 killed why? thank you On Saturday, 7 June 2014 at 21:57:31 UTC, Chris Cain wrote:On Saturday, 7 June 2014 at 21:40:08 UTC, Agora wrote:Why is running slow?One of the main reasons is because the number of permutations an array has is n!. Thus the expected runtime is O(n!). That's a slow, slow algorithm in general. In particular, your array with length 11 has 39,916,800 permutations (although it, obviously, doesn't have to go through *all* of those to get the sorted sequence in this case).
Jun 07 2014
On Saturday, 7 June 2014 at 22:01:25 UTC, Ali GOREN wrote:Thank you. I can not resolve it in quicker time, right?You might be able to come up with a faster way to permute, but it's mostly pointless because it will always be very slow. Use std.algorithm.sort if you want to sort quickly, as that uses an algorithm that is O(n log n) Compare: 11! = 39,916,800 11 log_2 11 = ~38 So the best you could really expect to do is be around a million times slower than a regular sort.Also: dlang online compiler and dpaste: return code: 9 killed why?Probably because it took too long. There's probably a pretty short timelimit on the execution of your program in the online things because they are shared resources.thank youNo problem :)
Jun 07 2014
Thank you Chris. Now I understand. I thought myself incorrectly but this was a normal. On Saturday, 7 June 2014 at 22:09:11 UTC, Chris Cain wrote:On Saturday, 7 June 2014 at 22:01:25 UTC, Ali GOREN wrote:Thank you. I can not resolve it in quicker time, right?You might be able to come up with a faster way to permute, but it's mostly pointless because it will always be very slow. Use std.algorithm.sort if you want to sort quickly, as that uses an algorithm that is O(n log n) Compare: 11! = 39,916,800 11 log_2 11 = ~38 So the best you could really expect to do is be around a million times slower than a regular sort.Also: dlang online compiler and dpaste: return code: 9 killed why?Probably because it took too long. There's probably a pretty short timelimit on the execution of your program in the online things because they are shared resources.thank youNo problem :)
Jun 07 2014
On Saturday, 7 June 2014 at 22:01:25 UTC, Ali GOREN wrote:Thank you. I can not resolve it in quicker time, right?Depends what exactly you want to achieve. This will achieve the same result in a fraction of the time. void main() { auto data = [2, 7, 4, 3, 5, 1, 0, 9, 8, 6, -1]; sort(data); data.writeln; } But it's not "permutation sort". Honestly, I've never *heard* of "permutation sort". In any case, it's one of the worst sorts I've ever heard of. If you want to use a bad algorithm, you could also go for bogosort: void main() { auto data = [2, 7, 4, 3, 5, 1, 0, 9, 8, 6, -1]; while (!isSorted(data)) randomShuffle(data); data.writeln; }
Jun 08 2014
On Sunday, 8 June 2014 at 08:44:42 UTC, monarch_dodra wrote: of.If you want to use a bad algorithm, you could also go for bogosort: void main() { auto data = [2, 7, 4, 3, 5, 1, 0, 9, 8, 6, -1]; while (!isSorted(data)) randomShuffle(data); data.writeln; }I'm partial to MiracleSort[1] myself. void main() { import core.thread; immutable period = 1.seconds; auto data = [2, 7, 4, 3, 5, 1, 0, 9, 8, 6, -1]; while (!isSorted(data)) { Thread.sleep(period); } data.writeln(); } [1]:
Jun 08 2014
monoarch_dodra I solved BogoSort import std.stdio, std.algorithm, std.random; void bogoSort(T)(T[] data) { while (!isSorted(data)) randomShuffle(data); } void main() { auto array = [2, 7, 41, 11, 3, 1, 6, 5, 8]; bogoSort(array); writeln(array); } https://github.com/agoren/AlgorithmSolved/blob/master/BogoSort/main.d
Jun 08 2014