Tra cứu nhanh bằng bảng tần suất và tổng tiền tố

Minh thống kê 50 000 lượt mượn sách. Mỗi lượt ghi một mã số, và Minh cần biết mỗi mã xuất hiện bao nhiêu lần. Nếu tìm lại cả danh sách cho từng mã, số phép so sánh có thể lên tới hàng tỉ. Một bảng tra cứu giúp Minh giữ lại thông tin ngay khi đọc từng lượt.

Một khóa dẫn tới thông tin cần tìm

Hãy ghi số lần mượn cho các mã 4, 1, 4, 2, 1, 4. Ta cần một chỗ chứa số lần cho từng mã. Bảng băm (hash map) lưu mỗi khóa (key) cùng một giá trị (value). Python cung cấp dict cho công việc này.

Ở đây khóa là mã sách và giá trị là số lượt. Với mỗi mã x, freq.get(x, 0) trả số lượt đã ghi, hoặc 0 nếu chưa có khóa. Sau đó ta tăng số đó lên một.

a = [4, 1, 4, 2, 1, 4]
freq = {}
for x in a:
    freq[x] = freq.get(x, 0) + 1
print(freq)
print(freq.get(8, 0))

{4: 3, 1: 2, 2: 1}
0

Mã 4 được gặp ba lần. Mã 8 chưa có nên câu hỏi thứ hai nhận 0 mà không thêm khóa mới. Trái lại, truy cập trực tiếp một khóa chưa có gây lỗi:

freq = {4: 3}
print(freq[8])

KeyError: 8

Khóa phải có thể băm và giữ giá trị băm ổn định. Số nguyên, chuỗi và bộ tuple gồm các phần tử phù hợp dùng được; list thay đổi được nên không làm khóa. Chọn khóa theo điều cần tra, còn giá trị theo thông tin cần nhớ.

visits = {}
for point in [(1, 2), (0, 0), (1, 2)]:
    visits[point] = visits.get(point, 0) + 1
print(visits[(1, 2)])

2

Tra cứu và cập nhật dict có chi phí trung bình O(1), không phải bảo đảm trong mọi tình huống va chạm. Với 50 000 lượt, cách trên cần khoảng 50 000 lần cập nhật trung bình. Bộ nhớ là O(d), với d là số mã khác nhau.

Một lượt đọc cụ thể cho thấy bảng thay đổi ra sao. Bắt đầu với bảng rỗng, đọc 4 thì chưa có khóa 4 nên lấy mặc định 0. Gán freq[4] = 1 tạo khóa. Đọc 1 tạo khóa 1, rồi lần đọc 4 tiếp theo tăng giá trị đang có lên 2.

Thứ tự xuất hiện trong dữ liệu không phải thứ tự tăng của khóa. Bảng lưu đúng tần suất dù mã âm, bằng 0 hay dương. Nếu cần báo cáo theo thứ tự mã, bạn có thể duyệt sorted(freq) sau khi đếm. Chi phí sắp xếp thêm là O(d log d) với d mã phân biệt.

Khi đề hỏi số lượt của một mã không có trong dữ liệu, freq.get(x, 0) cho 0. Phân biệt điều đó với việc hỏi vị trí đầu tiên. Vị trí 0 là chỉ số hợp lệ, nên không thể dùng nó để biểu thị chắc chắn rằng chưa gặp. Hãy chọn giá trị mặc định theo ý nghĩa của bài toán.

Tần suất giúp so sánh các giá trị công bằng

Tần suất (frequency) của một giá trị là số lần nó xuất hiện. Bạn có thể dùng Counter trong thư viện chuẩn để tạo bảng tần suất từ một dãy. Khi nhiều mã cùng có số lượt cao nhất, đề cần quy định cách chọn; ví dụ này chọn mã nhỏ nhất.

from collections import Counter
a = [5, 2, 5, 3, 2, 2, 5]
freq = Counter(a)
best = min(freq, key=lambda x: (-freq[x], x))
print(best, freq[best])

2 3

Cả 2 và 5 cùng có ba lượt nên chọn 2. Khóa so sánh (-freq[x], x) ưu tiên tần suất lớn, rồi mã nhỏ. Đoạn trên cần dãy không rỗng; nếu rỗng, min không có phần tử để chọn.

Mỗi lượt được đếm đúng một lần, sau đó mỗi mã khác nhau được so sánh một lần. Vì d <= n, thời gian trung bình là O(n) và bộ nhớ O(d). Với 50 000 lượt, số lượt duyệt vẫn tỉ lệ với 50 000, không phải bình phương số đó.

Tập hợp trả lời câu hỏi đã gặp hay chưa

Nếu chỉ cần biết một mã đã xuất hiện, tập hợp (set) đủ dùng. Nó không lưu số lần của mã. Hãy tìm phần tử lặp đầu tiên theo thứ tự đọc:

a = [7, 3, 9, 3, 7]
seen = set()
for x in a:
    if x in seen:
        print(x)
        break
    seen.add(x)
else:
    print("khong trung")

3

Trước khi đọc một phần tử, seen chứa đúng các giá trị đã đọc trước đó. Do đó lần đầu kiểm tra đúng là lần lặp đầu tiên. Nếu thêm x trước khi kiểm tra, ngay cả phần tử đầu cũng bị nhận nhầm là lặp.

Tra cứu và thêm vào set mất O(1) trung bình. Với n phần tử, thời gian trung bình O(n) và bộ nhớ O(d). Nếu cần biết số lần thay vì chỉ sự hiện diện, hãy chọn bảng tần suất.

Phần bù tìm cặp ở hai vị trí khác nhau

Cho dãy số và đích k, ta hỏi có hai vị trí khác nhau sao cho tổng bằng k hay không. Khi xét x, giá trị còn thiếu là phần bù (complement) k - x. Tập seen chứa các số ở những vị trí trước đó.

a = [5, 1, 3, 8]
k = 9
seen = set()
found = False
for x in a:
    if k - x in seen:
        found = True
        break
    seen.add(x)
print(found)

True

Khi xét 8, phần bù 1 đã nằm trong seen. Hai số đến từ hai vị trí khác nhau. Nếu đích là 10 và dãy chỉ có [5], kết quả phải là False; thêm 5 trước khi hỏi sẽ dùng một vị trí hai lần.

Vì mọi cặp có một vị trí đứng sau, khi xét vị trí sau ta sẽ tìm được vị trí trước nếu cặp thỏa. Ta chỉ kiểm tra các số đã gặp, nên không tạo cặp cùng vị trí. Mỗi số được xử lý một lần: trung bình O(n) thời gian và O(d) bộ nhớ.

Muốn đếm tất cả cặp i < j, một tập hợp không đủ vì có thể có nhiều vị trí cùng giá trị. Lưu số lần của từng giá trị đã gặp:

a = [2, 2, 3, 2]
k = 4
freq = {}
answer = 0
for x in a:
    answer += freq.get(k - x, 0)
    freq[x] = freq.get(x, 0) + 1
print(answer)

3

Ba số 2 tạo ba cặp vị trí. Khi xét mỗi số, mọi phần bù đã gặp đóng góp một cặp mới; không cặp nào được đếm lại. Thứ tự hỏi trước, ghi sau cũng ngăn cặp rỗng ở cùng vị trí.

Xét thêm một ví dụ khi có nhiều phần bù giống nhau. Với [1, 1, 3] và k = 4, khi đọc 3, bảng đã ghi số 1 hai lần. Cả hai vị trí đó đều tạo một cặp với vị trí đang xét. Nếu chỉ lưu set, ta biết có số 1 nhưng không biết có hai vị trí, nên thiếu một cặp.

Bảng trên đếm theo chỉ số chứ không gộp những cặp có cùng giá trị. Ví dụ các cặp (0, 2) và (1, 2) đều hợp lệ. Mỗi cặp được tính khi xét chỉ số lớn hơn, nên không cần chia kết quả cho 2. Đếm mọi cặp có thứ tự rồi chia 2 là một cách khác, nhưng cần xử lý việc tự ghép.

Nếu đề chỉ hỏi có cặp hay không, dùng set và dừng ngay khi thấy một phần bù. Nếu đề yêu cầu đếm, dùng dict tần suất và tiếp tục đến hết dãy. Nếu đề yêu cầu in chỉ số, giá trị trong bảng có thể là vị trí đã gặp. Mỗi yêu cầu thay đổi thông tin cần lưu, dù khóa tra vẫn là giá trị số.

Hiệu tuyệt đối cần hai hướng tra cứu

Cho k >= 0, bạn cần đếm các cặp chỉ số i < j sao cho abs(a[i] - a[j]) == k. Khi đọc x, một số trước đó có thể bằng x - k hoặc x + k. Bảng tần suất lưu số vị trí đã đọc của mỗi giá trị.

Với k = 2, số 5 ghép được với cả 3 và 7. Nếu k = 0, hai khóa cần tra đều bằng x, nên chỉ cộng tần suất đó một lần. Sau khi tra, ta mới ghi x để tránh ghép một vị trí với chính nó.

a = [3, 7, 5, 3]
k = 2
freq = {}
answer = 0
for x in a:
    answer += freq.get(x - k, 0)
    if k != 0:
        answer += freq.get(x + k, 0)
    freq[x] = freq.get(x, 0) + 1
print(answer)

3

Ở lượt đọc 5, cả 3 lẫn 7 đều đóng góp một cặp. Ở lượt cuối, số 3 ghép với số 5 đã đọc. Mỗi cặp được tính đúng một lần khi xét vị trí sau; không cặp nào dùng lại cùng vị trí. Với 100 000 số, mỗi lượt cần tối đa hai lần tra: thời gian trung bình O(n) và bộ nhớ O(d) với d giá trị khác nhau.

a = [4, 4, 4]
freq = {}
answer = 0
for x in a:
    answer += freq.get(x, 0)
    freq[x] = freq.get(x, 0) + 1
print(answer)

3

Ba vị trí tạo ba cặp, không phải sáu. Với k dương, x - k và x + k khác nhau nên không có vị trí nào bị tính ở cả hai lượt tra.

Khóa chuẩn hóa gom các từ đảo chữ

Hai từ là từ đảo chữ (anagrams) nếu chúng có cùng số lần xuất hiện của từng chữ cái. Chẳng hạn "aab" và "aba" cùng nhóm, nhưng "abb" thuộc nhóm khác. Khóa chuẩn hóa (canonical key) đại diện chung cho mọi từ trong một nhóm.

Sắp xếp các chữ cái rồi nối lại tạo khóa chung: "".join(sorted(w)). Hai từ có cùng khóa khi và chỉ khi chúng có cùng các chữ với cùng số lần. Ta đếm số từ theo khóa; với một từ mới, số từ trước đó trong nhóm chính là số cặp mới.

words = ["aab", "aba", "abb", "baa", "bab"]
freq = {}
pairs = 0
for w in words:
    key = "".join(sorted(w))
    pairs += freq.get(key, 0)
    freq[key] = freq.get(key, 0) + 1
print(max(freq.values()), pairs)

3 4

Nhóm aab có ba từ, nhóm abb có hai từ. Các nhóm lần lượt đóng góp ba cặp và một cặp. Mỗi từ chỉ ghép với các từ trước đó trong cùng nhóm, nên không trùng cặp.

Không dùng set(w) làm khóa đảo chữ. Nó bỏ số lần xuất hiện, nên "aab" và "abb" cùng cho tập chữ {a, b} dù không phải đảo chữ. Một khóa khác là bộ 26 số đếm theo thứ tự từ a tới z:

def signature(w):
    counts = [0] * 26
    for ch in w:
        counts[ord(ch) - ord("a")] += 1
    return tuple(counts)

print(signature("aab") == signature("aba"))
print(signature("aab") == signature("abb"))

True
False

Với từ dài m, sắp xếp tốn O(m log m); tạo bộ đếm tốn O(m + 26) và chỉ áp dụng như trên cho chữ thường a–z. Với tổng độ dài L và n từ, cách đếm tốn trung bình O(L + 26n) thời gian. Bảng lưu tối đa n khóa gồm 26 số, nên bộ nhớ bổ sung là O(26n) trong trường hợp mọi nhóm khác nhau.

Ví dụ 100 000 từ có tổng một triệu chữ cần khoảng một triệu lượt đếm ký tự và 2,6 triệu ô đếm khởi tạo. Chi phí băm được tính trung bình; bộ 26 số của mỗi từ phải được tạo trước khi tra. Nếu dùng khóa đã sắp xếp, tổng chi phí là O(sum(m log m)) và bộ nhớ phụ thuộc tổng độ dài các khóa khác nhau.

Tổng tiền tố biến tổng đoạn thành một lần tra

Một đoạn con liên tiếp (contiguous subarray) gồm các phần tử nằm liền nhau. Để đếm đoạn có tổng k, tra tần suất tiền tố bằng tổng hiện tại trừ k; xem Bài 12. Ví dụ sau dùng tiền tố rỗng và tra trước khi cập nhật:

a = [2, -1, 1, -2]
k = 2
freq = {0: 1}
pref = 0
answer = 0
for x in a:
    pref += x
    answer += freq.get(pref - k, 0)
    freq[pref] = freq.get(pref, 0) + 1
print(answer)

2

Hai đoạn được tìm là [2] và [2, -1, 1]; số âm không ảnh hưởng đến phép trừ hai tiền tố.

Vị trí đầu tiên cho đoạn tổng không dài nhất

Bây giờ đề hỏi độ dài lớn nhất, không hỏi số đoạn. Hai tiền tố bằng nhau tạo ra đoạn giữa chúng có tổng 0. Ở mỗi vị trí cuối, tiền tố bằng nó xuất hiện càng sớm thì đoạn càng dài.

Vì vậy first lưu vị trí đầu tiên của từng tổng tiền tố, thay vì số lần xuất hiện. Quy ước tiền tố trước dãy có chỉ số -1 để đoạn bắt đầu ở chỉ số 0 được tính đúng.

a = [1, -1, 2, -2, 3]
first = {0: -1}
pref = 0
best = 0
for i, x in enumerate(a):
    pref += x
    if pref in first:
        best = max(best, i - first[pref])
    else:
        first[pref] = i
print(best)

4

Bốn phần tử đầu có tổng 0. Mỗi vị trí cuối chỉ cần xét lần xuất hiện sớm nhất vì mọi lần sau đều cho đoạn ngắn hơn.

Có một lượt duyệt, mỗi lần tra hoặc ghi trung bình O(1). Tổng thời gian trung bình là O(n), bộ nhớ O(n) trong trường hợp mọi tổng tiền tố khác nhau. Không có đoạn nào thì best giữ giá trị 0.

Ta có thể dò riêng ví dụ trên để thấy vì sao vị trí sớm nhất cần được giữ. Trước dãy, tổng 0 ở chỉ số -1. Sau khi đọc 1 và -1, tổng trở lại 0 ở chỉ số 1. Đoạn từ chỉ số 0 đến 1 có độ dài 1 - (-1) = 2.

Sau hai số tiếp theo, tổng lại là 0 ở chỉ số 3. Nếu vẫn giữ vị trí -1, ta tìm được độ dài 3 - (-1) = 4. Nếu đã ghi đè vị trí 0 thành 1, chương trình chỉ thấy độ dài 2 tại điểm cuối này. Vị trí đầu tiên không bị thay thế dù tổng đó đã xuất hiện nhiều lần.

Đề có thể cho một dãy chỉ gồm số dương. Khi đó không có hai tổng tiền tố bằng nhau và không có đoạn không rỗng tổng 0. Kết quả 0 diễn đạt đúng việc không tìm thấy đoạn; nó không nói rằng có một đoạn rỗng hợp lệ. Nếu cần in cả hai đầu đoạn, hãy lưu thêm các chỉ số tốt nhất lúc cập nhật best.

Chọn thông tin lưu theo câu hỏi

Cùng một dữ liệu có thể cần nhiều cách lưu khác nhau. Với số xuất hiện, khóa là giá trị và nội dung là tần suất. Với đoạn dài nhất, khóa là tổng tiền tố và nội dung là vị trí đầu tiên. Với câu hỏi có hay không, một set đủ dùng.

Bảng băm không tự sắp xếp khóa theo giá trị. Nếu cần duyệt theo thứ tự tăng, hãy cân nhắc sắp xếp như Bài 11. Cách chọn phụ thuộc thao tác đề yêu cầu và cả giới hạn bộ nhớ.

Lỗi thường gặp

Tóm tắt

dict ánh xạ khóa tới thông tin; set chỉ lưu sự hiện diện. Hỏi trước khi cập nhật giúp phân biệt phần tử hiện tại với dữ liệu đã gặp. Hiệu tuyệt đối cần hai hướng tra, riêng k = 0 chỉ tra một lần. Khóa chuẩn hóa giữ đủ số lần từng chữ; vị trí tiền tố đầu tiên giúp tối đa độ dài.

Kiểm tra nhanh

Đọc thêm

• Tài liệu Python về từ điển.
• Tài liệu Python về tập hợp.
• Tài liệu Python về Counter.