hi all!
below is the description and source of a proggy that does permutation of a
dataset, i found one routine doing this in the forum here, but is so slow that
good old c had to come in to the rescue...
compare the speed of this proggy to that in the forums here and you'll be blown
away! the pb routine is so lame in comparison, well, uhm, that there is no
comparison! the one from the forum runs way slower, even on 200mhz pentium
system under nt2000.
here's the code from the
forum: http://www.powerbasic.com/support/pb...ad.php?t=22353
anyways, now that the mood is set, check out this proggy by paul and think it
over, can you write something better, faster?
the algorithm used is fairly simple. for each item i in a set of n items:
remove item i from the data set;
find all permutations of the remaining n - 1 items;
insert item i back into the set in its original position
the recursive function perm() shows this algorithm. each permutation is printed
as it is found.
the rest of the code is relatively lengthy, but merely supports the above
algorithm by providing it with appropriate data structures. two data structures
are provided:
a data set, an ordered list allowing two operations:
removing an item from a given position, and
inserting an item into a given position
a stack to hold the current permutation, which like all stacks allows two
operations:
pushing an item onto the top of the stack, and
popping an item off the top of the stack
in order to understand the algorithm used to find the permutations, it is not
necessary to delve into the details of these functions or data structures any
more than it is necessary to understand exactly how a printf() call produces
output on your screen. the main() and perm() functions describe the algorithm
completely.
functions to:
initialize and free memory used by the data set,
print out the contents of the stack, and
retrieve the number of data items from the command line
are also provided.
----------------------------------------------
usage:
pass the number of data items to the command line as the single argument. an
example session is shown below:
perm 3
permutations of 3 items:
abc
acb
bac
bca
cab
cba
6 permutations in all.
---------------------------------------------
executable size (in kb)14.256!
compiled and executed on an intel 166mhz pentium processor
with 32mb ram, running linux kernel 2.2.5-15
here you see the performance of the algorithm, where it becomes apparent
that the output (to screen etc) consumes more time than algorithm itself.
so instead of printing it, keeping it in an array eliminates the output
delays. one can then print the array with all permutations once the
program has done its job.
performance (with output):
=========================
invocation permutations (secs)
./perm 1 1 -
./perm 2 2 -
./perm 3 6 -
./perm 4 24 -
./perm 5 120 -
./perm 6 720 0.05
./perm 7 5,040 0.36
./perm 8 40,320 2.97
./perm 9 362,880 27.64
performance (no output):
=======================
invocation permutations (secs)
./perm 1 1 -
./perm 2 2 -
./perm 3 6 -
./perm 4 24 -
./perm 5 120 -
./perm 6 720 -
./perm 7 5,040 0.015
./perm 8 40,320 0.12
./perm 9 362,880 1.06
./perm 10 3,628,800 10.61
./perm 11 39,916,800 116.61
so here's the challenge:
show off pb and write it in pb/dll so it is at least as fast as the
c program, preferably even faster (if that can be done in pb)
the code should be pb only! however it would be cool to see what a
real assembler guru can do to speed it up even more once it's done...
jax
ps: i just aquired pb/dll a little while ago and am still trying to
figure it all out, however i know c since decades, so i figure it would
be easier to start with it. now i am exploring if bying pb was worth it
or not, seems to me that there are some serious speed penalties in
using pb. however, mayhaps there is a better solution ala pb style and i
am just not into it enough yet?
next post is c-source
------------------
below is the description and source of a proggy that does permutation of a
dataset, i found one routine doing this in the forum here, but is so slow that
good old c had to come in to the rescue...
compare the speed of this proggy to that in the forums here and you'll be blown
away! the pb routine is so lame in comparison, well, uhm, that there is no
comparison! the one from the forum runs way slower, even on 200mhz pentium
system under nt2000.
here's the code from the
forum: http://www.powerbasic.com/support/pb...ad.php?t=22353
anyways, now that the mood is set, check out this proggy by paul and think it
over, can you write something better, faster?
the algorithm used is fairly simple. for each item i in a set of n items:
remove item i from the data set;
find all permutations of the remaining n - 1 items;
insert item i back into the set in its original position
the recursive function perm() shows this algorithm. each permutation is printed
as it is found.
the rest of the code is relatively lengthy, but merely supports the above
algorithm by providing it with appropriate data structures. two data structures
are provided:
a data set, an ordered list allowing two operations:
removing an item from a given position, and
inserting an item into a given position
a stack to hold the current permutation, which like all stacks allows two
operations:
pushing an item onto the top of the stack, and
popping an item off the top of the stack
in order to understand the algorithm used to find the permutations, it is not
necessary to delve into the details of these functions or data structures any
more than it is necessary to understand exactly how a printf() call produces
output on your screen. the main() and perm() functions describe the algorithm
completely.
functions to:
initialize and free memory used by the data set,
print out the contents of the stack, and
retrieve the number of data items from the command line
are also provided.
----------------------------------------------
usage:
pass the number of data items to the command line as the single argument. an
example session is shown below:
perm 3
permutations of 3 items:
abc
acb
bac
bca
cab
cba
6 permutations in all.
---------------------------------------------
executable size (in kb)14.256!
compiled and executed on an intel 166mhz pentium processor
with 32mb ram, running linux kernel 2.2.5-15
here you see the performance of the algorithm, where it becomes apparent
that the output (to screen etc) consumes more time than algorithm itself.
so instead of printing it, keeping it in an array eliminates the output
delays. one can then print the array with all permutations once the
program has done its job.
performance (with output):
=========================
invocation permutations (secs)
./perm 1 1 -
./perm 2 2 -
./perm 3 6 -
./perm 4 24 -
./perm 5 120 -
./perm 6 720 0.05
./perm 7 5,040 0.36
./perm 8 40,320 2.97
./perm 9 362,880 27.64
performance (no output):
=======================
invocation permutations (secs)
./perm 1 1 -
./perm 2 2 -
./perm 3 6 -
./perm 4 24 -
./perm 5 120 -
./perm 6 720 -
./perm 7 5,040 0.015
./perm 8 40,320 0.12
./perm 9 362,880 1.06
./perm 10 3,628,800 10.61
./perm 11 39,916,800 116.61
so here's the challenge:
show off pb and write it in pb/dll so it is at least as fast as the
c program, preferably even faster (if that can be done in pb)
the code should be pb only! however it would be cool to see what a
real assembler guru can do to speed it up even more once it's done...
jax
ps: i just aquired pb/dll a little while ago and am still trying to
figure it all out, however i know c since decades, so i figure it would
be easier to start with it. now i am exploring if bying pb was worth it
or not, seems to me that there are some serious speed penalties in
using pb. however, mayhaps there is a better solution ala pb style and i
am just not into it enough yet?
next post is c-source
------------------
Comment