ok@quintus (08/25/88)
In message <615@mannix.iros1.UUCP>, Paul Tarau @ l'Universite de Montreal presented an "all permutations" predicate, and said >However, I think it is not as fast as it could be. Does someone >know about a faster and/or shorter 'all_permutations' program? In message <1172@tuhold>, Thom Fruehwirth @ TU Vienna presented his version, which he says is "much faster and shorter". As for its size, that depends on how you measure it. Here are four measurements: Version Tarau's Fruehwirth's # of predicates 4 4 # of clauses 8 7 # of identifiers 73 71 (things starting with a letter) # of characters 630 338 (when converted to the same layout style) The principal size difference between them is that Tarau used longer predicate and variable names. As for speed, when one says that method A is faster than method B, one has to be clear about which implementation one is using. On a Sun 3/50 using Quintus Prolog release 2.4, for example, Tarau's version is about 1.7 times faster than Fruehwirth's (well, I tweaked it a bit). Tarau correctly describes this operation as "very space-consuming". Suppose that a list cell costs 8 bytes, that there is no sharing, and that you have a virtual address space of 128 Mbytes. How long a list can you store all the permutations of? The space required for all the permutations of a list of N elements is 8.N.N! For N=9, this comes to about 26 Mbytes. For N=10, this comes to about 290 Mbytes. (I made the mistake of trying N=9 with "limit core 8M". Makes a great torture test for the garbage collector.) Time is not the only cost.
thom@tuhold (Thom Fruehwirth) (08/26/88)
In a recent posting on the topic Richard O'Keefe corrected my claim that the version I presented is "much faster and shorter" (I meant "(much faster) and shorter" not "much (faster and shorter)"). I have to agree with him. I wasn't careful enough when comparing the two different versions (the other one by Tarau). It also seems that certain operations (cut, unifying, clause selection), especially their timings, depend heavily on the Prolog implementation one uses. (mine is AAIS Prolog on the Macintosh). So one (including me) has to be carefull with "absolute" claims. You can only be sure that something is the case in your specific hardware/software configuration. Thanks to Richard for pointing that out. Thom