Python cho người Việt

Python cho người Việt

Python One-Liner

written by Phạm Thị Minh Hoài, on Jan 22, 2010 11:30:00 PM.

Python One-Liner là trường phái viết Python trên một dòng. Theo đó mỗi một hành động xác định được viết bởi các lệnh cô đọng gom lại trên một dòng duy nhất. Hành động xác định không phải là những hành động quá phức tạp, nhưng cũng không quá đơn giản. Ví dụ việc trao đổi giá trị giữa hai biến có thể coi là một hành động xác định như vậy. Python cho phép thực hiện điều này trên một dòng với một lệnh duy nhất, và với tôi đó là một trong những lệnh Python đẹp nhất:

>>> a, b = b, a

Python One-Liners cũng chính là tập hợp các mẹo (trick) Python nhằm giải quyết các bài toán nhỏ một cách ngắn gọn theo phương châm “do a lot with a little.”. Điều này thường khó thực hiện ở các ngôn ngữ khác. Nhưng chúng có thể thực hiện được trong Python do đặc trưng ngôn ngữ hỗ trợ cách viết như vậy. Chẳng hạn cách dùng hàm lambda, List Comprehensions, map, filter, zip, dict, set, … đã xây dựng những đặc trưng ngôn ngữ cho phép viết các mã ngắn gọn hơn các ngôn ngữ khác.

Trong bài viết này tôi sẽ tổng hợp một số các bài toán đơn giản mà triển khai Python có thể được viết trên một dòng. Chúng là các bài toán cơ bản có liên quan đến list. Tôi hi vọng những bạn chưa biết về các công thức trong bài này sẽ tìm thấy nhiều điểm lý thú, và qua đó càng hiểu được sức mạnh và sự hấp dẫn tuyệt vời của Python. Các công thức này một số được tôi thường xuyên sử dụng, một số được sưu tầm và các bạn có thể tìm thấy ở đâu đó trên internet.

1. Làm phẳng một list

Cho một list dạng hai chiều như sau: L = \[[1,2,3],[4,5,6], [7], [8,9]\] hãy biến nó thành dạng một chiều dạng [1, 2, 3, 4, 5, 6, 7, 8, 9]. Đây là một số lời giải một dòng của bài toán này:

>>> L = [[1,2,3],[4,5,6], [7], [8,9]]
>>> sum(L, [])
>>> reduce(lambda x, y: x + y, L)
>>> list(itertools.chain(L))  #import itertools.
>>> [item for sublist in L for item in sublist]

Python cung cấp cho bạn một tập hợp phong phú các cú pháp và hàm dựng sẵn cho phép bạn giải cùng một bài toán theo nhiều cách khác nhau. Trong các lời giải trên lời giải cuối cùng là nhanh nhất và nó cũng dễ hiểu nhất. Chi tiết các lời giải trên các bạn có thể xem trên trang: Making a flat list out of list of lists in python. Hàm reduce đã bị loại bỏ kể từ Python 3000 (Suggested by Guido van Rossum), tuy nhiên vẫn được giữa lại trong thư viện functools, do vậy bạn có thể dùng:

>>> functools.reduce(lambda x, y: x + y, L)

Nếu list L không phải là hai chiều, mà có thể chứa các list con đệ quy, bạn có thể dùng hàm sau:

def flatten(seq, a = list()):
    try:                          
        for item in seq:          
            flatten(item, a)      
    except TypeError:             
        a.append(seq)             
    return a

print flatten([[1,2, [3,4], 5], 6, [7, [8, 9]]])

2. Loại bỏ các phần tử trùng nhau trong list

Hãy tạo ra một list mới chứa các phần tử không trùng nhau của L. Một số cách giải trên một dòng:

>>> L = dict.fromkeys(L).keys()  # Python 3.x trả về iterator
>>> L = list(set(L))
>>> [x for i, x in enumerate(L) if i==L.index(x)]

Với L = [5,6,1,1,1,2,2,2,3,3,3] hai lời giải trên cho kết quả [1, 2, 3, 5, 6]. Lời giải cuối cùng cho kết quả [5, 6, 1, 2, 3]. Như vậy trong một số tình huống lời giải cuối cùng tốt hơn, do nó vẫn giữa được thứ tự các phần tử như ban đầu. Tuy vậy lời giải cuối cùng chạy rất chậm. Hãy xem kết quả đo thời gian chạy của các lời giải như sau:

>>> from timeit import Timer
>>> Timer("list(set(L))", "L = range(10**4)").timeit(10)
0.030437396173560671
>>> Timer("dict.fromkeys(L).keys()", "L = range(10**4)").timeit(10)
0.027800167602894277
>>> Timer("[x for i, x in enumerate(L) if i==L.index(x)]", "L = range(10**4)").timeit(10)
25.005568798618903

Việc so sánh thời gian chạy giữa các Python One-Liner rất hay được các tác giả thực hiện. Chúng đánh giá khả năng sử dụng thực tế của mỗi công thức. Lời giải cuối cùng như các bạn thấy dù có ưu điểm song không thể dùng được khi có test xấu trên 10000 phần tử.

3. Đếm số phần tử có trong một list

Nếu chỉ đếm một phần tử thì quá đơn giản, dùng list.count là xong, nhưng nếu để đếm tần số cho nhiều item một lúc thì làm thế nào. Chẳng hạn có L = [5,6,1,1,1,2,2,2,3,3] muốn tạo ra D={5:1, 6:1, 1:3, 2:3, 3:2}.

>>> dict([(x, L.count(x)) for x in set(L)])
>>> {x: L.count(x) for x in set(L)} # dict comprehensions, có từ Python 3.x
>>> collections.Counter(L) # import collections, có từ Python 3.x

Lời giải số một tuy dài nhưng có thể chạy trên hầu hết các bản Python > 2.4. Lời giải số hai chẳng qua là từ 1 ra nhưng với cú pháp mới của Python 3.x nó dễ hiểu và đơn giản hơn. Lời giải cuối cùng đơn giản đến mức bạn chỉ cần có import collections. Module collections chứa các phương tiện cho phép bạn viết các mã Python ngắn gọn, và chạy rất nhanh. Một ví dụ khác về cách dùng Counter trong module collections, đoạn mã này cho phép đếm tần số xuất hiện của các ký tự trong một string:

>>> collections.Counter("abcabca")
Counter({'a': 3, 'c': 2, 'b': 2})

Càng về sau này các phiên bản Python càng hỗ trợ nhiều hơn các cú pháp và thư viện cho phép bạn viết các mã ngắn gọn hơn. Đây là đặc trưng của Python: “Viết ít hơn làm nhiều hơn”. Việc gia tăng hiểu biết của bạn về các thư viện là một kinh nghiệm quan trọng.

4. Chia một list thành nhiều list

Bài toán chia một list thành nhiều list có thể gặp hai yêu cầu:

  1. Chia list thành nhiều list có độ dài bằng nhau
  2. Chia list thành n list con có độ dài tương đương nhau (với khác biệt kích thước nhỏ nhất).

Vấn đề số một có thể giải quyết bằng các hàm sau:

>>> SplitInto=lambda a,n: [a[i*n:(i+1)*n] \
... for i in range(len(a) % n and len(a)/n + 1 or len(a)/n)]
>>> SplitInto(range(10), 3)
[[0, 1, 2], [3, 4, 5], [6, 7, 8], [9]]

>>> SplitInto = lambda L, n: zip(*[chain(L, repeat(None, n-1))]*n)
>>> SplitInto(range(10), 3)
<zip object at 0x01D607D8>
>>> list(SplitInto(range(10), 3))
[(0, 1, 2), (3, 4, 5), (6, 7, 8), (9, None, None)]

>>> SplitInto = lambda L, n: zip_longest(*[iter(L)]*n)
>>> list(SplitInto(range(10), 3))
[(0, 1, 2), (3, 4, 5), (6, 7, 8), (9, None, None)]
>>> SplitInto = lambda L, n: zip_longest(*[iter(L)]*n, fillvalue=-1)
>>> list(SplitInto(range(10), 3))
[(0, 1, 2), (3, 4, 5), (6, 7, 8), (9, -1, -1)]

>>> SplitInto= lambda L, n: [L[i:i+n] for i in range(0, len(L), n)]
>>> SplitInto(range(10), 3)
[[0, 1, 2], [3, 4, 5], [6, 7, 8], [9]]

Lời giải số 1, 4 dùng cho các phiên bản Python từ 2.3 trở đi. Hai lời giải 2, 3 sau đòi hỏi phải có lệnh from itertools import * và chỉ chạy từ Python 3.x trở đi. Chi tiết về các lời giải này các bạn có thể xem thêm: How do you split a list into evenly sized chunks in Python?

Vấn đề số 2 có thể có lời giải sau:

>>> SplitInto = lambda L, n: [L[i::n] for i in range(n)]
>>> SplitInto(range(10), 3) # SplitInto(list(range(10)), 3) với Python 3.x
[[0, 3, 6, 9], [1, 4, 7], [2, 5, 8]]

Lời giải trên là đơn giản đến mức …không cần tìm thêm các lời giải khác làm gì cho mệt. Tuy nhiên nó không chia theo đúng thứ tự. Đây là cách khác phức tạp hơn nhưng giữa nguyên được thứ tự các phần tử:

>>> SplitInto = lambda L, n: [L[int(i*1.0*len(L)/n):int((i+1)*1.0*len(L)/n)] \
... for i in range(n)]
>>> SplitInto(range(10), 3)
[[0, 1, 2], [3, 4, 5], [6, 7, 8, 9]]
>>> SplitInto(range(10), 2)
[[0, 1, 2, 3, 4], [5, 6, 7, 8, 9]]
>>> SplitInto(range(10), 4)
[[0, 1], [2, 3, 4], [5, 6], [7, 8, 9]]

Cách viết này khá dài, nhưng giữa nguyên được thứ tự giữa các phần tử. Các dòng dài chính là đặc trưng của Python One-liner.

5. Kiểm tra một list là tập con của list khác

Cho hai list a, b. kiểm tra xem a có chứa b hay không. Danh sách a chứa danh sách b nếu tất cả các phần tử của b đều có trong a. Cách giải sau đã có lần tôi trình bày, dùng thư viện operator và hàm built-in reduce, có thể dùng với mọi phiên bản Python 2.x:

>>> a = [1,2,3,4,5]
>>> b = [2,3,6]
>>> c = [2,3,4]
>>> reduce(operator.and_, map(a.__contains__, b))
False
>>> reduce(operator.and_, map(a.__contains__, c))
True

Từ Python 2.4 bạn có thể sử dụng set:

>>> set(a+b) == set(a)
False
>>> set(a+c) == set(a)
True
>>> set(c).issubset(a)
True
>>> set(b).issubset(a)
False
>>> set(c) <= set(a)
True
>>> set(b) <= set(a)
False

Từ Python 2.5 bạn có thể viết:

>>> all([x in a for x in b])
False
>>> all([x in a for x in c])
True

Module operator cung cấp cách dùng các toán tử như các hàm. Trong ví dụ 1 thực tế chúng ta dùng toán tử in thông thường. Các toán tử dùng như các hàm cho phép kết hợp với các hàm built-in khác để viết các lệnh Python rất ngắn gọn và thuận tiện. Một ví dụ (được lấy trong tài liệu Python) tính tích vô hướng hai vector:

sum(map(operator.mul, vector1, vector2))

Thật khó để viết ngắn hơn và chạy nhanh hơn như vậy. Các ví dụ trên càng nói rõ hơn điều tôi đã nhấn mạnh ở mục 3: các phiên bản Python càng về sau càng hỗ trợ tốt hơn việc viết các mã ngắn gọn và hiệu quả. Tuy vậy bạn phải cân nhắc lựa chọn giải pháp đúng cho phiên bản Python mà nó sẽ chạy.

6. Sắp xếp nhiều column

Cho các column a,b,c…có cùng kích thước. Hãy sắp xếp chúng theo thứ tự a,b,c.... Nội dung các dòng không thay đổi. Dưới đây là một ví dụ triển khai với 2 cột a, b:

>>> a = [3,3,2,2,1,1]
>>> b = ["c", "b", "b", "a", "c", "a"]
>>> a, b = zip(*sorted(zip(a, b)))
>>> a
(1, 1, 2, 2, 3, 3)
>>> b
('a', 'c', 'a', 'b', 'b', 'c')

Thật tuyệt!!!. Chúng đơn giản đến mức khó có thể ngắn gọn hơn nữa. Công thức trên trọn vẹn trên một dòng có ít hơn 80 ký tự. Tất cả chỉ có 4 lệnh. Ít nhất nó cũng gây cho tôi nhiều sự phấn khích và ngạc nhiên. Và các bạn sẽ thấy trên nhiều forum Python, việc tìm kiếm các “One-Liner” thực sự là thú vị và là trò chơi hấp dẫn của các Python guru.

7. Tổng kết

Khi kích thước dữ liệu đầu vào lớn một số trong các hàm trả về list trên đây cần được thay thế bằng các hàm trạng thái. Chẳng hạn việc chia một list thành nhiều list bằng nhau nên viết thành hàm trạng thái, sẽ dùng ít bộ nhớ và nhanh hơn:

def SplitInto(a, n):
    start = 0
    end = len(a) % n and len(a)/n + 1 or len(a)/n
    
    while start < end:
        yield a[start * n: (start + 1) * n]
        start += 1

Chuẩn viết mã Python là không quá 80 ký tự trên một dòng. Python One-Liner viết hết các lệnh Python trên một dòng, làm cho các line dài hơn bình thường. Mã Python khó đọc và khó hiểu hơn do cách viết cô đọng, các biến được đặt tên ngắn. Với các bài toán không mang tính cơ bản, các bạn nên hạn chế viết theo cách này.

Các chương trình viết trên một dòng không có nghĩa là nhanh nhất. Thậm chí trong đa số các trường hợp để viết trên một dòng người ta phải chọn cách viết mất nhiều thời gian chạy hơn. Do vậy khi kích thước dữ liệu lớn, tốt hơn hết hãy lựa chọn cách viết tối ưu, và chấp nhận mã dài hơn.

Tôi hi vọng rằng các bạn sẽ thích thú với các ví dụ trên đây. Chắc chắn còn nhiều cách giải khác cho mỗi vấn đề mà tôi đã nêu ra. Nếu các bạn tìm thấy chúng xin hãy vui lòng comment để mọi người cùng biết. Điều sau cùng tôi muốn nhấn mạnh là tuy việc tìm kiếm các lời giải một dòng cho mỗi vấn đề chỉ đơn giản là thú vui, ít mang tính ứng dụng - nhưng chúng thực sự sẽ thúc đẩy việc học hỏi và tìm kiếm kinh nghiệm của chúng ta.

Một số bài tập Python có thể triển khai trên một dòng:

  • Tạo ma trận đơn vị kích thước bất kỳ
  • Triển khai sàng Sieve of Eratosthenes
  • Triển khai dãy số Fibonacci.
  • Tạo một list chứa tất cả các hoán vị của một list khác (các phần tử có thể bằng nhau).

Hoaiptm.

Comments

  • Mới tìm hiểu về Python nên chưa hiểu lắm các example của chị,nhưng thấy rất hay và thú vị.Chị tiếp tục phát huy nha.Thank chị nhiều.Ak mà chị cho em xin cái mail,because có 1 số vấn đề về Python muốn hỏi.

    Comment by nguyentranhjep — Jul 14, 2010 7:24:09 PM | # - re

  • Mới tìm hiểu về Python nên chưa hiểu lắm các example của chị,nhưng thấy rất hay và thú vị.Chị tiếp tục phát huy nha.Thank chị nhiều.Ak mà chị cho em xin cái mail,because có 1 số vấn đề về Python muốn hỏi.

    Comment by nguyentranhjep — Jul 14, 2010 7:24:53 PM | # - re

Leave a Reply