Bạn có chắc chắn muốn xóa bài viết này không ?
Bạn có chắc chắn muốn xóa bình luận này không ?
Học Python với Project Euler
Python là một ngôn ngữ rất linh hoạt trong xử lý số và xâu chuỗi, hồi mới học Python tôi hay dùng Project Euler để luyện tập. Ở bài viết này tôi sẽ viết lại quá trình học Python thông qua bài đầu tiên của Project Euler.
Multiples of 3 and 5
Đề bài của bài đầu tiên rất đơn giản
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Vậy là chỉ cần tìm tất cả các số là bội của 3 hoặc 5 (hoặc cả 2) và tính tổng trong một khoảng cho trước
Mảng trừu tượng
Lời giải đầu tiên như sau
>>> sum([n for n in xrange(10) if (n%3==0)or(n%5==0)])
23
>>> sum([n for n in xrange(1000) if (n%3==0)or(n%5==0)])
233168
Rất trực tiếp phải không? Ở đây xrange(10)
sẽ tạo ra một mảng các số tự nhiên từ 0 đến 9, (n%3==0)or(n%5==0)
là yêu cầu của đề bài, và cuối cùng thì [n for n in .... if ....]
là cách viết của Mảng trừu tượng trong Python.
Hàm filter
Python có hàm filter theo phong cách functional programming. Áp dụng filter thì sẽ có một cách giải khác
>>> sum(filter(lambda x:(x%3==0)or(x%5==0),xrange(10)))
23
>>> sum(filter(lambda x:(x%3==0)or(x%5==0),xrange(1000)))
233168
Ở đây hàm truyền vào cho filter là một lambda
: lambda x:(x%3==0)or(x%5==0)
, trả lại giá trị true/false dựa trên biểu thức (x%3==0)or(x%5==0)
(yêu cầu của đề bài)
Xrange với step
Nếu có kinh nghiệm với hàm xrange của Python, bạn sẽ biết xrange có thể được truyền đối số thứ 3 là step.
>>> xrange(0,10,3)
[0, 3, 6, 9]
>>> xrange(0,10,5)
[0, 5]
Với việc sử dụng step thì điều kiện là bội của 3 và của 5 có thể được thể hiện dễ dàng hơn:
>>> set(xrange(0,10,3))|set(xrange(0,10,5))
set([0, 3, 5, 6, 9])
set
ở đây là phép toán tập hợp, set(x)|set(y)
sẽ lấy phần hợp của 2 tập hợp, chúng ta không cần quan tâm đến chuyện loại trừ phần giao (những số là bội của cả 3 và 5). Đáp án khi dùng set
trờ thành
>>> sum(set(xrange(0,10,3))|set(xrange(0,10,5)))
23
>>> sum(set(xrange(0,1000,3))|set(xrange(0,1000,5)))
233168
Sử dụng toán học
3 lời giải trên đều không có gì sai cả, tuy nhiên xét cho cùng thì vẫn là giải pháp brute-force (vét không gian tìm kiếm). Nếu ta có thể dùng toán học để giải quyết thì chắc chắn performance sẽ tăng lên rất nhiều
Để ý rằng để tính tổng các bội của 3 dưới 10 (Tổng của [0,3,6,9]
), ta có thể thấy:
0+3+6+9 = 3*(0+1+2+3)
Như vậy có thể lấy thừa số chung là 3 và tính tổng các số liên tiếp trong ngoặc để nhân lại
Vậy hàm tính tổng các bội của một số trong một khoảng định sẵn có thể viết lại như sau
>>> def sum_below(total_range,multiplier):
... limit = ( total_range + multiplier - 1 ) / multiplier
... return multiplier*limit*(limit-1)/2
...
>>> sum_below(10,3)
18
>>> sum_below(10,5)
5
Ở đây multiplier
là thừa số chung và total_range
là khoảng định sẵn. Sử dụng hàm trên sẽ cho kết quả
>>> sum_below(1000,3) + sum_below(1000,5) - sum_below(1000,15)
233168
So sánh performance
Thử đặt 4 cách giải trên lên bàn cân và đo kết quả, ở đây tôi thử cho khoảng từ 1000 lên thành 1000,000
from time import time
def sum_below(total_range,multiplier):
limit = ( total_range + multiplier - 1 ) / multiplier
return multiplier*limit*(limit-1)/2
start = time()
print sum([n for n in xrange(1000000) if (n%3==0)or(n%5==0)])
print("#1: ", time() - start)
start = time()
print sum(filter(lambda x:(x%3==0)or(x%5==0),xrange(1000000)))
print("#2: ", time() - start)
start = time()
print sum(set(xrange(0,1000000,3))|set(xrange(0,1000000,5)))
print("#3: ", time() - start)
start = time()
print sum_below(1000000,3) + sum_below(1000000,5) - sum_below(1000000,15)
print("#4: ", time() - start)
Đặt tên file trên là sample.py
và thực thi sẽ cho kết quả
$ python sample.py
233333166668
('#1: ', 0.2514638900756836)
233333166668
('#2: ', 0.2607719898223877)
233333166668
('#3: ', 0.10638189315795898)
233333166668
('#4: ', 0.00011491775512695312)
Ta thấy performance vượt trội của cách cuối cùng.
Một câu kết luận ai cũng biết nhưng đã được chứng minh trong TH cụ thể này: thuật toán tốt bao giờ cũng cho performance vượt trội so với brute-force !





