You have nondeterminism in your code, which will make it very difficult to have fair benchmarks. Case in point, CPython produces different results to PyPy.
We can fix this by removing said nondeterminism. I believe your only significant source is
for g in dictofnos:
since iteration order is arbitrary. I changed this to
for g in sorted(dictofnos, reverse=True):
I'm using reverse since it seems to give more outputs than the other way around, which I assume is preferred.
Now we can get useful timings. The first thing to try is how fast PyPy is:
$$
\begin{array}{ll}
\text{runtime} & \text{time}/s \\
\hline
\text{CPython} & 3.1\\
\text{PyPy} & 110 \\
\end{array}
$$
Well, it seems we're done making it faster. Let's fix some other things instead.
Firstly, your code is mixing IO with logic. We can fix this by yield
ing results out to the caller. This allows us to keep IO happening as soon as we already do, but let the caller do it. In checksquare
, return
the needed values (there are two places). In powers
, write
out = checksquare(templist)
if out is not None:
yield out
Then let the caller do the writing. You don't want the function to do the writing to call powers
directly, because that recouples IO and logic (albeit to a much lesser extent) - just pass powers
into the function.
Further, just print
the output. When running the program, it's trivial to redirect to a file. Thus, printing it makes a lot more sense than hardcoding the file you're printing to. I recommend from __future__ import print_function
at this point as well.
Lots of your documentation is in comments above functions rather than docstrings. You should write docstrings instead, and use clearer, more declarative language.
Before we fix checksquare
's documentation, though, notice that it's really taking two parameters:
checksquare([[first_argument], some, more, lists])
This would be a lot clearer as
checksquare(first_argument, [some, more, lists])
So I replaced it with
def checksquare(squaresum, triplets):
But this just makes it obvious that squaresum
is never used by the function, so shouldn't be passed in in the first place. This means that the comment for the function is also a lie!
So what is checksquare
doing? Idunno, let's work it out.
dictofnos
tells me nothing about its purpose, but I can see that it's a mapping from numbers inside the triplets to counts of some kind. This suggests a Counter
, though that doesn't clarify a lot. The comment doesn't really help either. I'll call it counts
for now.
Note that (triplets[e])[f]
is just triplets[e][f]
, but the first loop can just be
for triplet in triplets:
counts.update(triplet)
Personally I'd just initialize it with
counts = Counter(chain.from_iterable(triplets))
and skip that step, though.
I'm going to change our deterministic iteration to
for val, count in counts.most_common():
because this produces even more outputs and ends up easier. val
is another problematic name, but it's better than g
.
The if count == 1
check should become
if count != 1:
continue
Then
if counts[(triplets[h])[j]] == 0:
pass
does nothing, so should be removed. It's also impossible for it to happen.
Now I tidied up the next loop:
# Remove any value that is NOT repeated
for val, count in counts.most_common():
if count != 1:
continue
for triplet_idx in range(len(triplets)):
if val not in triplets[triplet_idx]:
continue
for to_remove in triplets[triplet_idx]:
counts[to_remove] -= 1
triplets.remove(triplets[triplet_idx])
triplets.append([])
for i in range(len(triplets)):
if len(triplets[i]) != 3:
triplets.remove(triplets[i])
It's really odd that you're writing
triplets.append([])
and immidiately trying to remove them. Luckily you never seem to do this twice, because if you did your removal would have shifted off the index that you were checking next! But it's still safer and faster to write
triplets = filter(bool, triplets)
Note that bool
is sufficient because the only list lengths are 0 or 3.
There's another remove
that causes the shift problem:
triplets.remove(triplets[triplet_idx])
triplets.append([])
Since triplet_idx
goes up by one each time and you shift the value down, you end up skipping this one! Try
triplets[triplet_idx] = []
instead. In fact, by this point we should just create a new list in one step:
for val, _ in counts.most_common():
if counts[val] != 1:
continue
def new_triplets():
for triplet in triplets:
if val in triplet:
for to_remove in triplet:
counts[to_remove] -= 1
else:
yield triplet
triplets[:] = new_triplets()
But this still isn't great as it takes \$\mathcal{O}(n^2)\$ time - we're iterating over every value, and for each of those over every triplet. Rather try the other way around:
def new_triplets():
for triplet in triplets:
if any(counts[val] == 1 for val in triplet):
for val in triplet:
counts[val] -= 1
else:
yield triplet
triplets[:] = new_triplets()
Note that this doesn't actually correspond to an order done the previous way, since triplets are discarded in order, not by an arbitrary sort of their elements.
Then there is:
if 0 in counts.values():
[setof0s.append(k) for k in counts if counts[k] == 0]
elif 1 in counts.values():
return checksquare(triplets)
# The final loop is deleting entries in the dict which are removed
# (hence the use of setof0s).
for l in setof0s:
del counts[l]
This should really be:
if 0 in counts.values():
# Remove elements with count of zero
counts += Counter()
elif 1 in counts.values():
return checksquare(triplets)
This makes no sense to me, though - why is 1 in counts.values()
allowed when 0 in counts.values()
?
You can avoid recursion by using a loop:
while True:
counts = Counter(chain.from_iterable(triplets))
# Remove any value that is NOT repeated
def new_triplets():
...
triplets[:] = new_triplets()
if 0 in counts.values():
# Remove zero elements in counts
counts += Counter()
break
if 1 not in counts.values():
break
And you can move counts =
outside of the loop.
counts = Counter(chain.from_iterable(triplets))
while 1 in counts.values():
# Remove any value that is NOT repeated
def new_triplets():
...
triplets[:] = new_triplets()
if 0 in counts.values():
# Remove zero elements in counts
counts += Counter()
break
Finally, for this function
if len(triplets) != 0:
return counts, triplets
is just
if triplets:
return counts, triplets
but I'd just remove the if triplets
because the caller can do that and it makes the return type uniform.
On to powers
. We have numberrange
, which should be squaresum_limit
or inlined. floor
is unneeded. Instead of a / 4.0
you can from __future__ import division
and do a / 4
. Use tuples instead of lists for triplets
. Remove temp
; it buys you nothing.
I'd like to give more advice about powers
but I really don't get what its search strategy is. A lot of the inner loop doesn't make a lot of sense to me. If I were to search for triples such that a = b ** 2 + c ** 2 + d ** 2
and b <= c <= d
, I'd do
def limit(n, a, b=0, c=0):
space = a - b**2 - c**2
return int(space ** 0.5 / n)
def get_triplets():
for b in range(limit(3, a) + 1):
for c in range(b, limit(2, a, b) + 1):
d = limit(1, a, b, c)
if a == b ** 2 + c ** 2 + d ** 2:
yield a, b, c
triplets = list(get_triplets())
but this produces all possible such triples, whereas yours only produces a small subset that I don't really understand, in an order I don't really understand.
So this is what I have. I'm not sure it'll match what you were aiming for, though, as I don't really get what your code does.
from __future__ import division, print_function
from collections import Counter
from itertools import chain
def checksquare(triplets):
counts = Counter(chain.from_iterable(triplets))
while 1 in counts.values():
# Remove any value that is NOT repeated
def new_triplets():
for triplet in triplets:
if any(counts[val] == 1 for val in triplet):
for val in triplet:
counts[val] -= 1
else:
yield triplet
triplets[:] = new_triplets()
if 0 in counts.values():
# Remove zero elements in counts
counts += Counter()
break
return dict(counts), triplets
def powers(max_squaresum):
def limit(n, a, b=0, c=0):
space = a - b**2 - c**2
return int(space ** 0.5 / n)
for a in range(3 * ((max_squaresum + 1) ** 2)):
def get_triplets():
for b in range(limit(3, a) + 1):
for c in range(b, limit(2, a, b) + 1):
d = limit(1, a, b, c)
if a == b ** 2 + c ** 2 + d ** 2:
yield a, b, c
triplets = list(get_triplets())
if len(triplets) >= 8:
counts, triplets = checksquare(triplets)
if triplets:
yield a, counts, triplets
def display_output(values):
for squaresum, counts, triplets in values:
print()
print([squaresum])
print(dict(counts))
print(triplets)
display_output(powers(100))
findList
for example is quite complex and a short description of the algorithm could be nice. \$\endgroup\$output.txt
. \$\endgroup\$