Học Python với Project Euler
Python
37
Project Euler
1
White

Gà đi bộ viết ngày 27/05/2015

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ứ 3step.

>>> 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 !

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Gà đi bộ

3 bài viết.
2 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
6 5
Gần đây thấy sự kiện AngelHack Việt Nam 2015 quảng cáo rầm rộ trên FB, trong đó có một đoạn nói rằng, nếu giải được bài toán do họ đặt ra thì có th...
Gà đi bộ viết hơn 2 năm trước
6 5
White
3 0
Fabric Fabric là một tool chạy các tác vụ shell trên môi trường với cấu trúc và độ dễ hiểu của Python. Tôi hay dùng Fabric để thay thế cho các bas...
Gà đi bộ viết 2 năm trước
3 0
Bài viết liên quan
White
1 0
Mở đầu Như đã nói ở bài trước, mình đang nghiên cứu về Spark nên cần log lại một số thứ để dành sau này dùng đến :smile: Đối tượng hướng đến vẫn ...
Phạm Quốc Thắng viết hơn 1 năm trước
1 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
3 bài viết.
2 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!