未加星标

Jaime Buelta: $7.11 in four prices and the Decimal type, revisited

字体大小 | |
[开发(python) 所属分类 开发(python) | 发布者 店小二03 | 时间 2017 | 作者 红领巾 ] 0人收藏点击收藏

I happen to take a look tothis old post in this blog. The post is7 years old, but still presents an interesting problem.

“A mathematician purchased four items in a grocery store. He noticed that when he added the prices of the four items, the sum came to $7.11, and when he multiplied the prices of the four items, the product came to $7.11.”


Jaime Buelta: .11 in four prices and the Decimal type, revisited
Today’s exchange

I wanted to check my old solutions again, with the things that I learn in the last years. At that time, I was still a newbie in python, and there are certainly interesting points to check again.

Python 2 vs Python 3

The first interesting difference is the fact that Python3 is now quite mature, and there’s really no excuse for not using it as a default for small exercises or new projects.

The code can actually be adapted into running both in Python 2 and 3 to make comparisons:

import operator from itertools import combinations from functools import reduce from decimal import Decimal def solve(number, step, number_of_numbers): integer_range = int(number / step) all_numbers = (Decimal(i) * step for i in range(1, integer_range + 1)) multiples = 1 / (step ** number_of_numbers) correct_numbers = (i for i in all_numbers if (number * multiples % i) == 0) def check(numbers): """Check the numbers added and multiplied are the same""" return (sum(numbers) == number == reduce(operator.mul, numbers)) # only combinations are required, as order is irrelevant results = [p for p in combinations(correct_numbers, number_of_numbers) if check(p)] return results print(solve(number=Decimal('7.11'), step=Decimal('0.01'), number_of_numbers=4))

I changed a couple of things, like the usage of filter and reduce and better usage of list comprehensions, but the code is very similar. Obtain the numbers that are multiples or the total (as they are the only possible ones to fulfil the criteria), and then try all combinations.

I removed the internal time check, using instead the UNIX one, callingit at bash:

$ time python2.7 711.py [(Decimal('1.20'), Decimal('1.25'), Decimal('1.50'), Decimal('3.16'))] real 1m26.020s user 1m22.199s sys 0m1.124s $ time python3.6 711.py [(Decimal('1.20'), Decimal('1.25'), Decimal('1.50'), Decimal('3.16'))] real 0m1.148s user 0m0.955s sys 0m0.030s

The time difference is quite staggering. 1 second vs 90. They clearly have spend time in optimise Decimal in Python3

Crunching numbers

For the second version of the code, the code is like this

def calc(): for w in range(711): for x in range(711 - w): for y in range(711 - w - x): z = 711 - x - y - w if (w * x * y * z == 711000000): print("w: %d x: %d y: %d z: %d" % (w, x, y, z)) return

wich, this time, is actually slower in python3, and slower than the first solution.

time python2.7 711_v2.py w: 120 x: 125 y: 150 z: 316 real 0m7.963s user 0m7.362s sys 0m0.291s $ time python3.6 711_v2.py w: 120 x: 125 y: 150 z: 316 real 0m13.193s user 0m11.955s sys 0m0.461s

But, there are two tricks that can be used in this case.

The first one is a simple replacement for PyPy, which indeed speeds up things.

$ time pypy 711_v2.py w: 120 x: 125 y: 150 z: 316 real 0m2.413s user 0m0.177s sys 0m0.094s

Not sure why, but the results where from ~200ms up to 4 seconds, which is quite a variability.

And the second one is to use Cython to compile the code into a C extension. This requires making two files:

# This compiles the extension automatically import pyximport; pyximport.install() from c711v3 import calc calc()

and a c711v3.pyx file, with the Cython code.

def calc(): # define the variables as C types cdef int w, x, y, z for w in range(711): for x in range(711 - w): for y in range(711 - w - x): z = 711 - x - y - w if (w * x * y * z == 711000000): print("w: %d x: %d y: %d z: %d" % (w, x, y, z)) return

This speeds up the process sensibly, to a quarter of a second:

$ time python 711_v3.py w: 120 x: 125 y: 150 z: 316 real 0m0.223s user 0m0.138s sys 0m0.070s

Not bad from 90 seconds at the start!

Conclussions Python3 has a lot of optimisations, sometimes in non-obvious places. It should be the version to go unless there are legacy requirements. It’s also quite simple to keep code compatible with Python2 and Python3 for easy stuff. I can look at code I wrote 7 years ago and find ways of improving it… Good to feel like I know more. PyPy is another useful tool that should be considered. It’s also getting better and betters and now it has as well Python3 compatibility. Also, mybloghas been around for a while (though I don’t update it as often as I should) Creating C extensions with Cython is very easy when dealing with certain bottlenecks. And I still find joy in coding small exercises!

本文开发(python)相关术语:python基础教程 python多线程 web开发工程师 软件开发工程师 软件开发流程

主题: Python
分页:12
转载请注明
本文标题:Jaime Buelta: $7.11 in four prices and the Decimal type, revisited
本站链接:http://www.codesec.net/view/532518.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 开发(python) | 评论(0) | 阅读(52)