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 !