Bỏ qua để đến nội dung

Chương 17. Kỹ thuật lập trình nâng cao

Để biết chương trình có chạy kịp không, ta đếm số phép tính theo kích thước dữ liệu n, bỏ qua hằng số, và viết bằng ký hiệu O lớn:

Độ phức tạpVí dụn lớn nhất chạy kịp 1 giây (Python)
O(1)công thức, truy cập a[i], tra từ điểnmọi n
O(log n)tìm kiếm nhị phân, lũy thừa nhanhmọi n
O(n\sqrt{n})kiểm tra số nguyên tốkhoảng 1013
O(n)một vòng lặp qua dãykhoảng 106 đến 107
O(n log n)sắp xếp sortkhoảng 106
O(n2)hai vòng lặp lồng nhaukhoảng 3 × 103
O(2n)duyệt mọi tập conkhoảng 20
O(n!)duyệt mọi hoán vịkhoảng 9

Python thực hiện được khoảng 107 phép tính đơn giản mỗi giây, chậm hơn C++ khoảng 10 đến 50 lần. Vì vậy với Python, chọn thuật toán đúng độ phức tạp càng quan trọng: thuật toán O(n2) với n = 105 cần 1010 phép tính, không ngôn ngữ nào chạy kịp; nhưng O(n log n) thì Python làm được trong khoảng nửa giây.

Các hàm có sẵn của Python (sum, sorted, max, str.join, các thao tác trên set, dict) viết bằng C, chạy nhanh hơn nhiều lần so với vòng lặp tự viết làm cùng việc. Dùng chúng khi có thể.

input() và print() khá chậm khi gọi hàng trăm nghìn lần. Ba kỹ thuật hay dùng:

  1. Đọc toàn bộ một lần: data = sys.stdin.buffer.read().split() cho danh sách mọi “từ” của dữ liệu vào (dạng bytes, int() đổi được trực tiếp), rồi lấy dần bằng một chỉ số.
  2. Đọc từng dòng nhanh: input = sys.stdin.readline (dòng đọc được giữ \n ở cuối).
  3. In một lần: gom kết quả vào danh sách, cuối cùng in "\n".join(...) (hoặc sys.stdout.write(...)) thay vì gọi print cho từng dòng.
import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
pos = 2 + n # vị trí của số tiếp theo cần đọc
answers = []
for _ in range(q):
left, right = int(data[pos]), int(data[pos + 1])
pos += 2
answers.append(max(a[left - 1:right]))
sys.stdout.write("\n".join(map(str, answers)) + "\n")
main()
8
8
-2

Một mẹo nữa đã gặp ở chương 8: đặt phần chính trong hàm main(). Trong hàm, Python truy cập biến cục bộ nhanh hơn biến toàn cục, và phép ghép xâu += không bị chậm.

Bài toán: cho dãy n số và q câu hỏi “tổng các số từ vị trí l đến r là bao nhiêu?”. Cộng trực tiếp mỗi câu hỏi mất O(n), tổng cộng O(n × q) = 1010 với n = q = 105.

Ý tưởng: tính trước prefix[i] là tổng i số đầu tiên (prefix[0] = 0). Khi đó tổng đoạn [l, r] (đánh số từ 1) bằng prefix[r] - prefix[l - 1]: lấy tổng r số đầu trừ đi tổng l − 1 số đầu.

from itertools import accumulate
a = [3, -1, 4, 1, 5, 9]
prefix = [0] * (len(a) + 1)
for i in range(1, len(a) + 1):
prefix[i] = prefix[i - 1] + a[i - 1]
print(prefix)
print(prefix[4] - prefix[1]) # a2 + a3 + a4 = -1 + 4 + 1
print([0] + list(accumulate(a))) # cách viết ngắn
[0, 3, 2, 6, 7, 12, 21]
4
[0, 3, 2, 6, 7, 12, 21]

Tính mảng cộng dồn mất O(n), mỗi câu hỏi O(1), tổng cộng O(n + q). Hàm accumulate của module itertools tính dãy tổng dồn, chạy nhanh hơn vòng lặp tự viết.

Mảng hiệu: cộng một giá trị vào cả đoạn

Phần tiêu đề “Mảng hiệu: cộng một giá trị vào cả đoạn”

Bài toán ngược: q thao tác “cộng v vào mọi phần tử từ l đến r”, cuối cùng in dãy. Cộng trực tiếp mỗi thao tác mất O(n).

Ý tưởng: ghi lại “từ vị trí l bắt đầu cộng v” và “từ vị trí r + 1 thôi cộng v” vào mảng hiệu diff: diff[l] += v, diff[r + 1] -= v. Sau mọi thao tác, cộng dồn diff từ trái sang phải được lượng cần cộng vào từng vị trí.

n = 6
a = [0] * n
diff = [0] * (n + 1)
for left, right, value in [(2, 4, 5), (3, 6, 1)]: # vị trí đánh số từ 1
diff[left - 1] += value
diff[right] -= value
added = 0
for i in range(n):
added += diff[i]
a[i] += added
print(a)
[0, 5, 6, 6, 1, 1]

Mỗi thao tác O(1), cuối cùng một lần cộng dồn O(n).

Kiểm tra từng số từ 1 đến N có phải số nguyên tố không bằng cách thử ước tới √ mất O(NN\sqrt{N}). Sàng Eratosthenes làm nhanh hơn nhiều: viết các số từ 2 đến N; lấy số nhỏ nhất chưa bị gạch (là số nguyên tố p), gạch mọi bội của p; lặp lại.

def sieve(limit):
"""Danh sách is_prime với is_prime[k] = True khi k là số nguyên tố, k từ 0 đến limit."""
is_prime = [True] * (limit + 1)
is_prime[0] = is_prime[1] = False
p = 2
while p * p <= limit:
if is_prime[p]:
for multiple in range(p * p, limit + 1, p): # bắt đầu từ p * p
is_prime[multiple] = False
p += 1
return is_prime
is_prime = sieve(50)
print([k for k in range(51) if is_prime[k]])
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Hai điểm cần hiểu:

  • Bắt đầu gạch từ p × p: các bội nhỏ hơn như 2p, 3p đã bị gạch bởi các số nguyên tố nhỏ hơn p.
  • Chỉ cần p × p ≤ N: một hợp số k ≤ N có ước nguyên tố không vượt quá k\sqrt{k} ≤ N\sqrt{N}, nên đã bị gạch.

Độ phức tạp khoảng O(N log log N), gần như O(N). Với N = 106, hàm trên chạy khoảng 0,1 giây. Có thể nhanh hơn nữa bằng cách gạch cả một lát cắt trong một lệnh: is_prime[p * p::p] = bytearray(len(range(p * p, limit + 1, p))) với is_prime là bytearray (xem lời giải bài SANGNT).

Kết hợp với mảng cộng dồn: count[k] là số số nguyên tố không vượt quá k, thì số số nguyên tố trong đoạn [l, r] là count[r] - count[l - 1].

Tìm x trong dãy đã sắp xếp: so x với phần tử giữa; nhỏ hơn thì chỉ cần tìm ở nửa trái, lớn hơn thì nửa phải. Mỗi bước loại một nửa, nên dãy 106 phần tử chỉ cần khoảng 20 bước: O(log n).

Module bisect có sẵn hai hàm:

HàmTrả về
bisect_left(a, x)vị trí đầu tiên có a[i] >= x (số phần tử nhỏ hơn x)
bisect_right(a, x)vị trí đầu tiên có a[i] > x (số phần tử nhỏ hơn hoặc bằng x)
from bisect import bisect_left, bisect_right
a = [1, 3, 3, 5, 8, 13]
print(bisect_left(a, 3), bisect_right(a, 3)) # vị trí của các số 3: từ 1 đến trước 3
print(bisect_right(a, 3) - bisect_left(a, 3)) # số lần xuất hiện của 3
print(bisect_right(a, 6)) # số phần tử <= 6
print(bisect_left(a, 4) < len(a) and a[bisect_left(a, 4)] == 4) # 4 có trong dãy?
1 3
2
4
False

Tự viết tìm kiếm nhị phân (tìm vị trí đầu tiên có a[i] >= x):

def lower_bound(a, x):
low, high = 0, len(a) # đáp số nằm trong đoạn [low, high]
while low < high:
middle = (low + high) // 2
if a[middle] >= x:
high = middle # middle có thể là đáp số
else:
low = middle + 1 # đáp số nằm sau middle
return low
print(lower_bound([1, 3, 3, 5, 8, 13], 4), lower_bound([1, 3, 3, 5, 8, 13], 100))
3 6

Nhiều bài hỏi “giá trị lớn nhất (hoặc nhỏ nhất) thỏa mãn điều kiện”. Nếu điều kiện có tính đơn điệu (giá trị L thỏa mãn thì mọi giá trị nhỏ hơn L cũng thỏa mãn), ta tìm kiếm nhị phân trên chính đáp số: thử giá trị giữa, thỏa mãn thì đáp số ở nửa trên, không thì ở nửa dưới.

Ví dụ: tìm số nguyên lớn nhất L có L2 ≤ N (căn bậc hai nguyên của N), không dùng math.isqrt:

def integer_sqrt(n):
low, high = 0, n # L = low thỏa mãn; mọi L > high không thỏa mãn
while low < high:
middle = (low + high + 1) // 2 # làm tròn lên để vòng lặp luôn tiến
if middle * middle <= n:
low = middle
else:
high = middle - 1
return low
print(integer_sqrt(17), integer_sqrt(10**18), integer_sqrt(0))
4 1000000000 0

Chú ý middle = (low + high + 1) // 2 (làm tròn lên): khi high = low + 1, làm tròn xuống sẽ cho middle = low, nhánh low = middle không làm thay đổi gì và vòng lặp chạy mãi.

Với dãy số dương, tìm đoạn liên tiếp dài nhất có tổng không vượt quá S. Thử mọi đoạn mất O(n2). Kỹ thuật hai con trỏ: con trỏ phải right lần lượt mở rộng đoạn; mỗi khi tổng vượt S thì con trỏ trái left tiến lên để thu hẹp. Vì các số dương, khi right tăng thì left không bao giờ phải lùi lại.

a = [2, 1, 3, 1, 1, 4, 2]
limit = 6
left = 0
window_sum = 0
best = 0
for right in range(len(a)):
window_sum += a[right]
while window_sum > limit:
window_sum -= a[left]
left += 1
best = max(best, right - left + 1)
print(best)
4

Mỗi con trỏ chỉ tiến, mỗi con trỏ đi tối đa n bước, nên tổng cộng O(n) dù có vòng while lồng trong vòng for. Đoạn tìm được là 1, 3, 1, 1 (tổng 6).

  • Đếm độ phức tạp trước khi viết code; Python khoảng 107 phép tính mỗi giây.
  • Đọc nhanh sys.stdin.buffer.read().split(), in một lần bằng "\n".join(...); phần chính trong main().
  • Mảng cộng dồn: tổng đoạn [l, r] là prefix[r] - prefix[l - 1]. Mảng hiệu: diff[l] += v, diff[r + 1] -= v.
  • Sàng Eratosthenes: gạch bội của p từ p × p, chỉ cần p × p ≤ N.
  • bisect_left, bisect_right trên dãy đã sắp xếp; tìm kiếm nhị phân trên kết quả khi điều kiện đơn điệu.
  • Hai con trỏ trên dãy dương: O(n).

Chương này có 6 bài tập thực hành:

  • Bài 17.1. Tổng đoạn
  • Bài 17.2. Đếm số nhỏ hơn hoặc bằng
  • Bài 17.3. Số nguyên tố trong đoạn
  • Bài 17.4. Cộng trên đoạn
  • Bài 17.5. Đoạn con dài nhất
  • Bài 17.6. Cắt gỗ

Đề bài chi tiết (có ví dụ), lời giải từng bài (ý tưởng, các bước, lỗi hay gặp) kèm code Python, bộ test chấm tự động bằng Themis và bài giảng PowerPoint của chương này có trong bộ giáo trình Python đầy đủ.

Thầy cô và các em muốn mua bộ tài liệu đầy đủ vui lòng liên hệ tác giả Th.S Trần Huy Phúc:

Th.S Trần Huy Phúc

Th.S Trần Huy Phúc

Principal Software Engineer @Adnovum & Bumbii Academy