Chọn công cụ Python theo công việc và chi phí

Trong ngày hội sách, Lan nhận 12 phiếu ghi mã sách. Bạn cần đếm mã lặp, xếp phiếu vào hàng và tìm nhanh mã theo khoảng. Mỗi việc cần một thao tác khác nhau, dù dữ liệu đều là số.

Hãy bắt đầu từ thao tác được lặp nhiều nhất

Một chương trình có thể phải thêm, tìm, lấy hoặc đếm. Cùng một dữ liệu, mỗi yêu cầu có thể phù hợp với một cấu trúc khác. Hãy xác định thao tác, số lần lặp và giới hạn trước khi chọn.

Hình sau mô tả đường chọn công cụ cho ba nhu cầu. Các nhánh khác trong bảng vẫn cần cân nhắc giới hạn riêng.

Một lời gọi thư viện ngắn không chứng minh cả chương trình nhanh. Nếu sinh một triệu phương án rồi xử lý từng phương án, chi phí xử lý vẫn được cộng một triệu lần. Bài 2 hướng dẫn cách ước lượng tổng chi phí.

Đếm một lượt với Counter

Tần suất (frequency) của một giá trị là số lần giá trị đó xuất hiện. Counter nhận một dãy và lưu số lần cho từng khóa. Giá trị của khóa chưa có là 0 khi truy cập bằng dấu ngoặc vuông.

Dữ liệu gồm sáu mã, trong đó 4 xuất hiện ba lần. Ví dụ sau còn hỏi mã 9 chưa xuất hiện.

from collections import Counter
ma = [4, 2, 4, 3, 4, 2]
dem = Counter(ma)
print(dem[4], dem[2], dem[9])

3 2 0

Mỗi mã đóng góp đúng một lần vào bộ đếm của chính nó. Vì vậy kết quả sau một lượt là tần suất của cả dãy. Với n mã và k mã khác nhau, cách này thường dùng O(n) thời gian trung bình và O(k) bộ nhớ.

Với n = 10000, một lượt xử lý khoảng 10000 mã. Nếu hỏi lại tần suất cho 10000 mã bằng cách quét cả dãy mỗi lần, có thể cần 100 triệu lượt so sánh. Việc tra cứu bằng bảng băm có chi phí trung bình, không phải bảo đảm tuyệt đối cho mọi dữ liệu.

Khi cần mã phổ biến nhất, quy tắc hòa phải rõ ràng. Đề sau chọn mã nhỏ nhất khi hai mã có cùng số lần xuất hiện.

7
4 2 4 2 7 2 4

from collections import Counter
n = int(input())
ma = list(map(int, input().split()))
dem = Counter(ma)
chon = min(dem, key=lambda x: (-dem[x], x))
print(chon, dem[chon])

2 3

Khóa so sánh (-dem[x], x) ưu tiên tần suất lớn, rồi mã nhỏ. Với dữ liệu không rỗng, min luôn chọn một mã đã có. Không dùng most_common(1) để tự suy ra quy tắc hòa theo giá trị số.

Counter có thể chứa giá trị đếm bằng không hoặc âm nếu bạn tự sửa. Với bài đếm thuần từ dữ liệu đầu vào, các khóa xuất hiện có tần suất dương. Truy cập một khóa thiếu bằng dem[x] không tự thêm khóa đó.

Gom phần tử có cùng khóa bằng defaultdict

Đếm chỉ cho biết số lượng. Khi cần giữ danh sách các phần tử trong từng nhóm, bạn có thể dùng giá trị mặc định (default value) là một danh sách rỗng. defaultdict(list) gọi list() khi truy cập bằng ngoặc vuông tới khóa chưa có.

Ba bạn đăng ký hai ca. Mỗi lần thêm tên, nhóm tương ứng đã có danh sách để nhận tên.

from collections import defaultdict
dang_ky = [('sang', 'An'), ('chieu', 'Binh'), ('sang', 'Chi')]
nhom = defaultdict(list)
for ca, ten in dang_ky:
    nhom[ca].append(ten)
print(nhom['sang'])
print(nhom['chieu'])

['An', 'Chi']
['Binh']

Mỗi tên được thêm một lần vào đúng khóa của nó. Thứ tự tên trong mỗi nhóm là thứ tự được thêm. Với n bản ghi, việc gom thường mất O(n) thời gian trung bình và O(n) bộ nhớ cho các tên.

Lưu ý khác biệt giữa nhom[khoa] và nhom.get(khoa). Cách thứ nhất có thể tạo một nhóm rỗng mới. get trả giá trị mặc định được truyền vào, hoặc None, mà không gọi hàm tạo nhóm.

from collections import defaultdict
nhom = defaultdict(list)
print(nhom.get('toi'))
print('toi' in nhom)
print(nhom['toi'])
print('toi' in nhom)

None
False
[]
True

Đừng viết defaultdict(list()): tham số cần là hàm tạo list, không phải danh sách đã tạo. Mỗi khóa thiếu được nhận một danh sách riêng. Nếu nhiều khóa cùng trỏ đến một danh sách dùng chung, thêm vào một nhóm sẽ làm các nhóm khác đổi theo.

Dùng deque cho hàng đợi hai đầu

Hàng đợi (queue) phục vụ theo thứ tự đến trước, ra trước. deque còn cho phép thêm và lấy ở cả hai đầu. append thêm cuối, appendleft thêm đầu, popleft lấy đầu và pop lấy cuối.

Ba phiếu vào hàng theo thứ tự 7, 2, 5. Khi phiếu 7 được phục vụ, hai phiếu còn lại giữ thứ tự cũ.

from collections import deque
hang = deque([7, 2, 5])
print(hang.popleft())
hang.append(9)
print(list(hang))

7
[2, 5, 9]

popleft() trả và xóa đầu hàng, nên mỗi phiếu được phục vụ đúng thứ tự hiện có. Gọi thao tác lấy trên hàng rỗng gây IndexError. Hãy kiểm tra if hang nếu đề cho phép hàng rỗng.

Các thao tác ở hai đầu của deque có chi phí xấp xỉ O(1). Với list.pop(0), các phần tử còn lại phải dịch chỗ. Nếu xóa lần lượt n phần tử đầu danh sách, số lượt dịch là n(n-1)/2.

Đoạn sau đo thời gian thực trên máy đang chạy. Kết quả thời gian có thể thay đổi theo máy và tải hệ thống. Hai vòng đều xử lý cùng số phần tử, nhưng phép đo nhỏ không thay thế phân tích độ phức tạp.

from collections import deque
from time import perf_counter
n = 10000
a = list(range(n))
t = perf_counter()
while a:
    a.pop(0)
print('list:', round(perf_counter() - t, 4), 'giây')
b = deque(range(n))
t = perf_counter()
while b:
    b.popleft()
print('deque:', round(perf_counter() - t, 4), 'giây')

list: 0.0048 giây
deque: 0.0003 giây

Với n = 10000, cách dùng list dịch tổng cộng 49.995.000 vị trí. deque thực hiện 10000 lần lấy đầu. Không suy ra tốc độ chính xác từ phép đếm này, vì mỗi thao tác có chi phí thực khác nhau.

Sinh phương án nhỏ mà không lưu tất cả

Bộ lặp (iterator) lần lượt tạo phần tử khi bạn yêu cầu. Các hàm trong itertools giúp duyệt phương án mà không cần giữ toàn bộ kết quả cùng lúc. Điều đó tiết kiệm bộ nhớ, nhưng không làm giảm số phương án phải xét.

Chọn hai trong bốn mã không xét thứ tự tạo sáu cặp. Đổi vai trò hai mã trong một cặp không tạo lựa chọn mới.

from itertools import combinations
for cap in combinations([1, 3, 5, 7], 2):
    print(cap)

(1, 3)
(1, 5)
(1, 7)
(3, 5)
(3, 7)
(5, 7)

combinations chọn theo vị trí đầu vào. Nếu hai vị trí chứa cùng giá trị, hai kết quả nhìn giống nhau vẫn có thể xuất hiện. Với bốn vị trí, số cặp là 4 × 3 / 2 = 6.

Khi thứ tự quan trọng, permutations tạo các cách sắp xếp. product chọn độc lập cho từng vị trí, nên có thể dùng lại cùng giá trị.

from itertools import permutations, product
print(list(permutations([1, 2, 3], 2)))
print(list(product([0, 1], repeat=2)))

[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
[(0, 0), (0, 1), (1, 0), (1, 1)]

Độ dài kết quả của permutations với n phần tử phân biệt là n! nếu lấy đủ n. Với n = 8, có 40320 phương án. Với n = 12, có 479001600 phương án, thường quá nhiều để duyệt trong giới hạn ngắn.

Nếu mỗi phương án độ dài n cần xét cả n phần tử, tổng thời gian có thể là O(n × n!). Một bộ sinh không tự loại các phương án không hợp lệ. Bài 3 giải thích cách duyệt toàn bộ và đánh giá số ứng viên.

Tìm hai biên trên dãy đã sắp xếp

Một dãy tăng có thể chứa nhiều bản sao của cùng giá trị. Vị trí chèn (insertion point) là chỉ số để chèn mà vẫn giữ thứ tự. bisect_left chọn trước các phần tử bằng giá trị cần tìm; bisect_right chọn sau chúng.

Dãy sau có ba số 4. Hai biên chia dãy thành phần nhỏ hơn 4, phần bằng 4 và phần lớn hơn 4.

from bisect import bisect_left, bisect_right
a = [1, 4, 4, 4, 7]
x = 4
trai = bisect_left(a, x)
phai = bisect_right(a, x)
print(trai, phai, phai - trai)
print(bisect_left(a, 0), bisect_right(a, 9))

1 4 3
0 5

Mọi phần tử trước biên trái đều nhỏ hơn x. Mọi phần tử từ biên trái đến trước biên phải đều bằng x. Vì thế hiệu hai chỉ số là số lần xuất hiện, kể cả khi không có giá trị đó.

Mỗi lần tìm cần O(log n) phép so sánh. Nếu n = 10000, mỗi lần cần khoảng 14 bước chia đôi. Sắp xếp ban đầu mất O(n log n); q truy vấn sau đó mất O(q log n).

Đếm số phần tử trong đoạn đóng [l, r] bằng biên phải của r trừ biên trái của l. Điều này bao gồm cả hai đầu đoạn và mọi bản sao tại biên.

from bisect import bisect_left, bisect_right
a = sorted([7, 1, 4, 4, 2, 9])
l, r = 2, 4
print(bisect_right(a, r) - bisect_left(a, l))

3

Đừng gọi bisect trên dãy chưa tăng rồi coi kết quả là biên đúng. Ngoài ra, insort tìm vị trí trong O(log n) nhưng chèn vào list có thể mất O(n) do dịch phần tử. Lặp chèn nhiều lần vẫn có thể chậm.

Giữ phần tử nhỏ nhất sẵn sàng bằng heapq

Hàng đợi ưu tiên (priority queue) lấy phần tử theo độ ưu tiên, không theo thứ tự đến. Một đống nhỏ nhất (min-heap) luôn đặt giá trị nhỏ nhất ở đầu. Thứ tự các vị trí còn lại không nhất thiết là thứ tự tăng.

import heapq
h = [8, 3, 6, 3]
heapq.heapify(h)
print(h[0])
heapq.heappush(h, 2)
print(heapq.heappop(h))
print(heapq.heappop(h))

3
2
3

heapify biến danh sách thành đống ngay tại chỗ. Mỗi lần heappop, cấu trúc được sửa để phần tử nhỏ nhất còn lại ở đầu. Vì vậy phép lấy sau luôn trả đúng giá trị nhỏ nhất hiện có.

Với n phần tử, heapify mất O(n). Mỗi lần thêm hoặc lấy tốn O(log n); xem đầu tốn O(1). Nếu chỉ cần sắp xếp một lần và đọc toàn bộ theo thứ tự, sorted có thể đơn giản hơn.

Ví dụ sau đưa số đối vào đống nhỏ nhất để lấy giá trị lớn nhất. Chỉ đổi dấu khi đưa vào và khi lấy ra; không trộn số đã đổi dấu với số chưa đổi.

import heapq
h = []
for x in [5, -2, 9, 9]:
    heapq.heappush(h, -x)
print(-heapq.heappop(h))
print(-heapq.heappop(h))

9
9

Nếu hàng ưu tiên rỗng, heappop báo lỗi. Nếu các phần tử là bộ (ưu_tiên, mã), Python so sánh phần đầu rồi đến phần sau khi hòa. Quy tắc đó chỉ phù hợp nếu đề thực sự yêu cầu ưu tiên theo mã khi hòa.

Lưu kết quả hàm khi cùng trạng thái xuất hiện lại

Ghi nhớ (memoization) lưu kết quả của lời gọi để dùng lại khi gặp cùng tham số. Với lru_cache(maxsize=None), các kết quả không bị loại vì giới hạn số mục. Bộ nhớ vẫn tăng theo số trạng thái đã lưu.

Dãy F có F(0) = 0, F(1) = 1 và F(n) = F(n-1) + F(n-2). Khi tính F(6), nhiều lời gọi cần cùng giá trị nhỏ hơn. Đoạn sau đếm số lần thân hàm thực sự chạy.

from functools import lru_cache
lan_tinh = 0
@lru_cache(maxsize=None)
def f(n):
    global lan_tinh
    lan_tinh += 1
    if n < 2:
        return n
    return f(n - 1) + f(n - 2)
print(f(6), lan_tinh)
print(f(5), lan_tinh)

8 7
5 7

Mỗi f(i) chỉ được tính một lần trong ví dụ chạy tuần tự. Sau đó kết quả được tra lại, nên việc gọi f(5) không tăng số lần tính. Từ 0 đến n có n + 1 trạng thái, nên thời gian và bộ nhớ là O(n) với phép cộng xem là hằng số.

Với số nguyên Fibonacci rất lớn, chi phí cộng cũng tăng theo số chữ số. Độ sâu lời gọi cũng tăng theo n và có thể chạm giới hạn đệ quy. Một vòng lặp giữ hai giá trị thường an toàn hơn cho dãy dài.

Tham số dùng làm khóa phải băm được (hashable), chẳng hạn int, str hoặc một tuple chỉ chứa các phần tử băm được. Một list không băm được. Đoạn sau cố ý gọi sai để quan sát lỗi.

from functools import lru_cache
@lru_cache(maxsize=None)
def tong(a):
    return sum(a)
print(tong([1, 2]))

TypeError: unhashable type: 'list'

Chuyển danh sách thành tuple nếu phù hợp với ý nghĩa dữ liệu. Một hàm có kết quả phụ thuộc biến ngoài thay đổi cũng không an toàn để ghi nhớ chỉ theo tham số cũ. Hãy đưa trạng thái cần thiết vào tham số hoặc xóa bộ nhớ bằng cache_clear() khi phù hợp.

Kết hợp công cụ theo đúng hợp đồng đầu ra

Lan cần trả lời số mã nằm trong mỗi khoảng điểm. Một danh sách đã sắp xếp phục vụ mọi truy vấn, nên không cần sắp xếp lại cho từng khoảng. Dữ liệu gồm số lượng mã, số truy vấn, danh sách mã và từng cặp biên.

6 3
4 1 4 9 2 7
2 4
5 8
10 12

from bisect import bisect_left, bisect_right
n, q = map(int, input().split())
a = sorted(map(int, input().split()))
for _ in range(q):
    l, r = map(int, input().split())
    print(bisect_right(a, r) - bisect_left(a, l))

3
1
0

Mỗi mã nằm trong đoạn đúng khi nó không nhỏ hơn l và không lớn hơn r. Hai biên bao trùm chính xác những vị trí ấy. Với n = q = 10000, tổng chi phí là O(n log n + q log n) thay vì quét 100 triệu cặp mã và truy vấn.

Dữ liệu đầu vào có thể chứa số âm, giá trị lặp hoặc không có mã trong khoảng. Khoảng trong ví dụ là khoảng đóng và giả sử l ≤ r. Nếu đề cho phép l > r, cần làm rõ ý nghĩa trước khi xử lý.

Lỗi thường gặp

Tóm tắt

• Counter đếm; defaultdict(list) gom các giá trị theo khóa.
• deque hỗ trợ thao tác nhanh ở hai đầu; heapq lấy phần tử nhỏ nhất hiện tại.
• bisect tìm biên trên dãy đã sắp xếp; itertools sinh phương án theo nhu cầu.
• lru_cache lưu kết quả theo tham số; số trạng thái và độ sâu vẫn cần vừa giới hạn.
• Chọn theo thao tác, điều kiện và tổng chi phí thay vì chọn theo tên thư viện quen thuộc.

Kiểm tra nhanh

Đọc thêm

• Tài liệu Python: collections
• Tài liệu Python: itertools
• Tài liệu Python: bisect
• Tài liệu Python: heapq
• Tài liệu Python: functools