On 29/03/2015 19:03, Marko Rauhamaa wrote:
BartC <b...@freeuk.com>:
As Chris mentioned, when I say 'faster than C', I mean X running my
algorithm was faster then C running Marko's algoritim (on Ian's data).
This was just an illustration of algorithm being more important than
language.
Be careful with the benchmark comparisons. Ian's example can be solved
with the identical algorithm in eight different ways (four corners, left
or right). I ran the example with my recent Python solver and got these
times in the eight cases:
884 s
2.5 s
13 s
499 s
5.9 s
128 s
1360 s
36 s
(That suggests a slight modification to the original strategy: solve it
in each of the eight ways "in parallel" and the worst case should be
significantly alleviated.)
Well, in this case all the benchmarks ran the same algorithm on the same
data, which makes them a better test of the implementations than of the
algorithm.
I've mentioned a (possibly) significantly faster algorithm which I
believe to be still brute-force (now in Python here:
http://pastebin.com/CKmHmBKm).
But I realise it could just be luck in approaching the solution from a
literally different angle and encountering the answer sooner. (I think
both stop as soon as they find any valid solution.)
What I've done is try it on 3 rotations as well as the original (+90,
+180, +270 degrees, but haven't bothered with flips and reflections).
While the original took 13 seconds (using my algorithm in Python), the
rotations took 18, 49 and 87 seconds respectively.
Since the original time in PyPy took 90-odd seconds, I was about to
acknowledge that mine might not be that much faster after all. Then I
realised I was using Python 3.1 not PyPy! Python 3.1 took 28 minutes on
original hard puzzle using your code, and 13-87 seconds with mine.
So I think this other algorithm is still much faster. I've no idea why,
especially since it messes about concatenating strings and converting
them to and from integers.
--
Bartc
--
https://mail.python.org/mailman/listinfo/python-list
