Cha đẻ của việc phân tích thuật toán

Trở về cuốn sách

Phân tích thuật toán là một nhánh nghiên cứu trong ngành khoa học máy tính, với nhiệm vụ tìm hiểu hiệu năng của các thuật toán, đặc biệt là thời gian chạy và yêu cầu dung lượng bộ nhớ.

Hãy xem thêm http://en.wikipedia.org/wiki/Analysis_of_algorithms.

Mục đích thực dụng của phân tích thuật toán là nhằm dự báo hiệu năng của những thuật toán khác nhau để dẫn đường cho quyết định thiết kế.

Trong cuộc vận động tranh cử Tổng thống Hoa Kì năm 2008, ứng cử viên Barack Obama bị đột xuất hỏi về phân tích khi ông viếng thăm Google. Giám đốc điều hành Eric Schmidt đã hỏi đùa ông về “cách hiệu quả nhất để sắp xếp một triệu số nguyên 32-bit.” Obama dường như đã được “phím” trước, bởi ông đã trả lời ngay, “Tôi nghĩ rằng sắp xếp sủi bọt là cách làm sai lầm.” Xem http://www.youtube.com/watch?v=k4RRi_ntQc8.

Điều này đúng: về khái niệm thì sắp xếp sủi bọt là đúng, nhưng nó rất chậm khi dùng cho các bộ số liệu lớn. Có lẽ phương án mà Schmidt muốn biết là “sắp xếp theo cơ số” (http://vi.wikipedia.org/wiki/Sắp_xếp_theo_cơ_số).

Mục tiêu của phân tích thuật toán là so sánh hợp lý được các thuật toán với nhau, tuy nhiên có một số vấn đề nảy sinh:

• Hiệu năng tương đối của thuật toán có thể phụ thuộc vào đặc tính của phần cứng, bởi vậy một thuật toán có thể nhanh hơn trên Máy tính A, và một thuật toán khác trên Máy tính B. Lời giải chung cho vấn đề này là cần quy định một mô hình máy rồi phân tích số bước, hay số phép tính, mà một thuật toán cần thực hiện trên một mô hình máy định trước.
• Hiệu năng tương đối có thể phụ thuộc vào đặc điểm chi tiết của bộ dữ liệu. Chẳng hạn, có những thuật toán chạy nhanh hơn nếu bộ dữ liệu đã phần nào được sắp xếp; và những thuật toán khác chạy chậm hơn trong trường hợp này. Một cách làm thông dụng để tránh điều này đó là phân tích trường hợp xấu nhất. Đôi khi cần thiết phải phân tích trường hợp trung bình, nhưng làm như vậy thường khó hơn, và có thể không rõ ràng xem phải chọn tính trung bình từ những trường hợp nào.
• Hiệu năng tương đối cũng phụ thuộc vào kích thước bài toán. Một thuật toán sắp xếp chạy nhanh với danh sách ngắn thì có thể chậm với danh sách dài. Giải pháp thông thường cho điều này là biểu diễn thời gian chạy (hay số lượng phép tính) dưới dạng một hàm theo kích thước bài toán, rồi so sánh các hàm này một cách tiệm cận khi kích thước bài toán tăng lên.

Một điều hay ở cách so sánh này là nó rất thích hợp để phân loại đơn giản các thuật toán. Chẳng hạn, nếu tôi biết rằng thời gian chạy của Thuật toán A có xu hướng tỉ lệ thuận với kích thước số liệu đầu vào, n, và Thuật toán B có xu hướng tỉ lệ với n2, thì tôi sẽ dự kiến rằng A chạy nhanh hơn B với những giá trị n lớn.

Kiểu phân tích như thế này luôn kèm theo những mẹo nhỏ, nhưng sau này ta sẽ đề cập đến chúng.

3.1 Bậc tăng trưởng

Giả dụ rằng bạn đã phân tích hai thuật toán và biểu diễn thời gian thực hiện chúng dưới dạng biểu thức của kích thước đầu vào: Thuật toán A cần 100n+1 bước để giải bài toán kích thước n; Thuật toán B cần n2 + n + 1 bước.

Bảng sau đây cho thấy thời gian chạy của hai thuật toán này với các kích thước bài toán khác nhau:

Kích cỡ số liệu vào Thời gian thực hiện Thời gian thực hiện của thuật toán A của thuật toán B 10 1 001 111 100 10 001 10 101 1 000 100 001 1 001 001 10 000 1 000 001 > 1010

Với n=10, Thuật toán A coi vẻ rất tệ; nó thực hiện lâu gấp gần 10 lần Thuật toán B. Nhưng với n=100 hai thuật toán này đã gần như nhau; và với các giá trị lớn hơn thì A sẽ tốt hơn nhiều.

Lý do cơ bản là với những giá trị lớn của n, bất kì hàm nào có chứa số hạng n2 sẽ tăng trưởng nhanh hơn một hàm chỉ chứa số hạng dẫn đầu là n. Số hạng dẫn đầu là số hạng với lũy thừa cao nhất.

Với Thuật toán A, số hạng cao nhất có một hệ số lớn là 100, vốn là lý do tại sao B thực hiện tốt hơn A với những giá trị n nhỏ. Song bất kể hệ số có ra sao, thì sẽ luôn có một giá trị n nào đó mà a n2 > b n.

Lý luận tương tự cũng đúng với những số hạng không dẫn đầu. Ngay cả nếu thời gian thực hiện của A là n + 1000000, thì nó vẫn tốt hơn Thuật toán B với những giá trị n đủ lớn.

Nhìn chung, ta trông đợi một thuật toán với số hạng dẫn đầu nhỏ hơn sẽ là thuật toán tốt đối với những bài toán lớn; song với các bài toán nhỏ hơn, có thể sẽ có một điểm giao cắt tại đó thuật toán kia tốt hơn. Vị trí của điểm giao cắt này phụ thuộc vào chi tiết của thuật toán, các số liệu đầu vào, và phần cứng, do vậy điều này thường bị bỏ qua trong việc phân tích thuật toán. Song không vì vậy mà bạn có thể quên đi.

Nếu hai thuật toán có cùng số hạng dẫn đầu thì khó nói thuật toán nào tốt hơn. Một lần nữa, kết quả lại phụ thuộc vào những chi tiết bên trong. Bởi vậy đối với việc phân tích thuật toán, các hàm có cùng số hạng dẫn đầu sẽ được coi là tương đương, cho dù chúng có các hệ số khác nhau.

Một bậc tăng trưởng là một tập hợp các hàm số mà động thái tăng trưởng tiệm cận của chúng được coi là tương đương. Chẳng hạn, 2n, 100n và n + 1 đều thuộc cùng một bậc tăng trưởng, và được viết là O(n) theo cách kí hiệu O lớn và thường được gọi là tuyến tính vì mỗi hàm trong tập hợp này đều tăng tuyến tính với n.

Tất cả các hàm với bậc dẫn đầu n2 thì thuộc vào O(n2); chúng là hàm bậc hai.

Bảng sau đây cho thấy một vài bậc tăng trưởng thường gặp nhất trong phân tích thuật toán, xếp theo thứ tự tăng dần mức độ tồi tệ.

Bậc tăng trưởng Tên gọi O(1) hằng số O(logb n) logarit (với b bất kì) O(n) tuyến tính O(n logb n) “n log n” O(n2) bậc hai O(n3) bậc ba O(cn) lũy thừa (với c bất kì)

Đối với các số hạng logarit thì cơ số của logarit không ảnh hưởng gì; việc chuyển đổi cơ số tương đương với việc nhân với một hằng số, vốn không làm thay đổi bậc tăng trưởng. Tương tự, tất cả các hàm lũy thừa đều thuộc vào cùng một bậc tăng trưởng bất kể cơ số bằng bao nhiêu. Các hàm lũy thừa tăng trưởng rất nhanh, bởi vậy thuật toán lũy thừa chỉ hữu dụng với những bài toán cỡ nhỏ.

Bài tập 1. Hãy đọc trang Wikipedia về cách kí hiệu O lớn: http://en.wikipedia.org/wiki/Big_O_notation rồi trả lời các câu hỏi sau:

1. Bậc tăng trưởng của n3 + n2 bằng bao nhiêu? Của 1000000 n3 + n2? Của n3 + 1000000 n2?
2. Bậc tăng trưởng của (n2 + n) · (n + 1) bằng bao nhiêu? Trước khi bắt đầu tính nhân, hãy nhớ rằng bạn chỉ cần số hạng dẫn đầu.
3. Nếu f có cỡ O(g), với một hàm g chung nào đó, thì ta có thể kết luận gì về af+b?
4. Nếu f1 và f2 có cỡ O(g), thì có thể kết luận gì về f1 + f2?
5. Nếu f1 có cỡ O(g) và f2 cỡ O(h), thì có thể kết luận gì về f1 + f2?
6. Nếu f1 có cỡ O(g) và f2 cỡ O(h), thì có thể kết luận gì về f1 · f2?

Những lập trình viên quan tâm đến hiệu năng thì thường khó nuốt trôi kiểu phân tích thế này. Họ lập luận như sau: đôi khi các hệ số và các số hạng theo sau vẫn tạo nên sự khác biệt thực sự. Đôi khi những chi tiết của phần cứng, ngôn ngữ lập trình và các đặc tính của đầu vào tạo nên sự khác biệt lớn. Và với những bài toán nhỏ thì sự tiệm cận như vậy không liên quan gì.

Nhưng nếu bạn nhớ những giải thích đó, thì phân tích thuật toán là một công cụ hữu hiệu. Ít ra là với các bài toán lớn, những thuật toán “tốt hơn” thì vẫn ưu việt, và nhiều khi là hơn nhiều. Sự khác biệt giữa hai thuật toán có cùng bậc tăng trưởng thì thường là một hằng số, nhưng khác biệt giữa thuật toán hay và thuật toán dở thì vô hạn!

B.2 Phân tích các phép tính cơ bản trong Python

Hầu hết các phép tính số học đều có thời gian thực hiện là hằng số; phép nhân thường lâu hơn là công trừ, và phép chia còn lâu hơn nữa, nhưng các thời gian thực hiện như vậy không phụ thuộc vào độ lớn các toán hạng. Ngoại lệ là các số nguyên rất lớn; khi đó thời gian thực hiện tăng theo số các chữ số..

Phép chỉ số—đọc và ghi các phần tử trong một dãy hay một từ điển—cũng có thời gian hằng số, bất kể kích thước của cấu trúc dữ liệu.

Một vòng lặp for duyệt một dãy hoặc một từ điển thì cũng thường tuyến tính, miễn sao các phép tính trong vòng lặp là không đổi theo thời gian. Chẳng hạn, phép cộng các phần tử trong một danh sách thì tuyến tính:

total = 0
for x in t:
    total += x

Hàm dựng sẵn sum cũng tuyến tính, vì nó thực hiện việc tương tự, nhưng hàm này có xu hướng nhanh hơn vì nó được thực hiện bằng cách hiệu qủa hơn; nói theo ngôn ngữ phân tích thuận toán thì nó có số hạng đầu là nhỏ hơn.

Nếu bạn dùng cùng vòng lặp nêu trên để gộp một danh sách các chuỗi kí tự, thì thời gian chạy lại có dạng hàm bậc hai vì phép nối chuỗi là tuyến tính.

Phương thức nối chuỗi join thường nhanh hơn vì nó là tuyến tính theo tổng chiều dài của các chuỗi thành phần.

Một quy tắc sơ bộ là nếu phần thân vòng lặp có bậc O(na) thì cả vòng lặp có bậc O(na+1). Một ngoại lệ là nếu bạn chứng tỏ được rằng vòng lặp sẽ thoát ra sau một số lần lặp không đổi. Nếu vòng lặp chỉ chạy k lần bất kể độ lớn n, thì vòng lặp có bậc O(na), kể cả với k lớn.

Nhân với k thì không làm thay đổi bậc tăng trưởng, nhưng chia cho k cũng vậy. Do đó, nếu phần thân vòng lặp có bậc O(na) và nó chạy n/k lần, thì vòng lặp có bậc O(na+1), ngay cả với k lớn.

Hầu hết các phép tính chuỗi và bộ (tuple) đều là tuyến tính, ngoài trừ chỉ số và len, vốn có thời gian hằng số. Các hàm lập sẵn min và max đều là tuyến tính. Thời gian chạy của một phép tính cắt lát (slice) thì tỉ lệ thuận với chiều dài của kết qủa, nhưng không phụ thuộc vào kích thước của đầu vào.

Tất cả những phương thức chuỗi đều tuyến tính, nhưng nếu độ dài các chuỗi bị giới hạn bởi hằng số—các phép tính với từng kí tự riêng lẻ—thì chúng được coi như là thời gian không đổi.

Hầu hết các phương thức danh sách đều tuyến tính, song cũng có những ngoại lệ:

• Việc thêm một phần tử vào cuối danh sách thì thường có thời gian hằng số; khi hết chỗ trống thì nó thường được sao chép vào chỗ rộng hơn, nhưng tổng thời gian cho n phép tính thì bằng O(n), do vậy ta nói rằng thời gian “giảm” cho một phép tính thì bằng O(1).
• Việc xóa bỏ một phần tử khỏi cuối danh sách thì có thời gian hằng số.
• Việc sắp xếp có bậc O(n logn).

Hầu hết các phép tính và phương thức với từ điển có thời gian hằng số, song có những ngoại lệ:

• Thời gian chạy của copy thì tỉ lệ thuận với số phần tử, nhưng không phải kích thước của các phần tử này (nó sao chép các tham chiếu tới, chứ không phải nội dung của phần tử).
• Thời gian chạy của update thì tỉ lệ thuận với kích cỡ từ điển tham biến, chứ không phải từ điển được cập nhật.
• keys, values và items đều tuyến tính vì chúng trả lại những danh sách mới; iterkeys, itervalues và iteritems lại có thời gian không đổi vì chúng trả lại các đối tượng lặp (iterator). Nhưng nếu bạn lặp qua các đối tượng iterator này, thì vòng lặp sẽ tuyến tính. Việc sử dụng các hàm “iter” có thể tiết kiệm được chút thời gian, song không thể thay đổi bậc tăng trưởng, trừ khi số lượng các phần tử bạn truy cập đến bị giới hạn.

Hiệu năng của các từ điển là một trong những điều kì diệu nhỏ trong khoa học máy tính. Ta sẽ xem cơ chế hoạt động của chúng trong Mục .

Bài tập 2. Đọc trang Wikipedia về các thuật toán sắp xếp ở http://en.wikipedia.org/wiki/Sorting_algorithm rồi trả lời những câu hỏi sau:

1. Một phép “sắp xếp so sánh là gì?” Với phép sắp xếp so sánh, bậc tăng trưởng tốt nhất với trường hợp xấu nhất thì bằng bao nhiêu? Với thuật toán sắp xếp bất kì, thì bậc tăng trưởng nêu trên bằng bao nhiêu?
2. Bậc tăng trưởng của phép sắp xếp nổi bọt bằng bao nhiêu, và tại sao Barack Obama lại nghĩ “dùng cách này là sai lầm?”
3. Bậc tăng trưởng của phép sắp xếp (radix) là bao nhiêu? Trước khi dùng nó ta cần điều kiện sẵn như thế nào?
4. Thế nào là phép sắp xếp ổn định và tại sao ta cần xét đến nó khi thực hành?
5. Thuật toán sắp xếp dở nhất (mà được đặt tên) là gì?
6. Thư viện ngôn ngữ lập trình C dùng thuật toán sắp xếp nào? Python dùng thuật toán nào? Các thuật toán này có ổn định không? Có thể bạn phải dùng Google để tìm câu trả lời.
7. Đa số các phép sắp xếp không so sánh đều là tuyến tính, vậy tại sao Python dùng một phép sắp xếp O(n logn)?

B.3 Phân tích các thuật toán tìm kiếm

Phép tìm kiếm là một thuật toán nhận vào một tập hợp cùng một phần tử mục tiêu và xác định xem liệu mục tiêu đó có nằm trong tập hợp, và thường trả lại chỉ số của mục tiêu.

Thuật toán tìm kiếm đơn giản nhất là “tìm kiếm tuyến tính,” cách này duyệt các phần tử trong tập hợp theo thứ tự, và dừng lại khi nó tìm được mục tiêu. Trong trường hợp xấu nhất, cần phải duyệt toàn bộ tập hợp, bởi vậy thời gian chạy là tuyến tính.

Toán tử in cho các dãy đều sử dụng phép tìm kiếm tuyến tính; và các phương thức chuỗi như find và count cũng vậy.

Nếu các phần tử của dãy đã được sắp xếp thì bạn có thể sử dụng phép tìm kiếm phân đôi, vốn có bậc O(logn). Tìm kiếm phân đôi cũng tương tự như thuật toán mà có thể bạn đã dùng để tra từ trong cuốn từ điển (quyển sách từ điển thực sự chứ không phải là cấu trúc từ điển). Thay vì bắt đầu từ đầu và lần lượt kiểm tra từng phần tử, bạn bắt đầu ở giữa và kiểm tra xem liệu từ cần tìm đứng trước hay sau đó. Nếu đứng trước thì bạn tìm kiếm nửa đầu của dãy. Còn không thì tìm kiếm nửa sau. Bằng cách nào đi nữa, bạn cũng cắt giảm số lượng các phần tử đi một nửa.

Nếu dãy hiện có 1,000,000 phần tử, thì sẽ mất khoảng 20 bước để tìm thấy từ đang cần, hoặc kết luận rằng không có. Như vậy là nhanh hơn khoảng 50,000 lần so với tìm kiếm tuyến tính.

Bài tập 3. Hãy viết một hàm có tên bisection nhận vào một danh sách đã sắp xếp cùng một gía trị mục tiêu, rồi trả lại chỉ số của gía trị này trong danh sách, nếu có, hoặc None nếu không. Hoặc bạn có thể đọc tài liệu của module có tên bisect và dùng module này!

Tìm kiếm phân đôi có thể nhanh hơn hẳn tìm kiếm tuyến tính, nhưng nó lại yêu cầu dãy phải theo thứ tự, tức là có thể cần thêm việc.

Có một cấu trúc dữ liệu khác, gọi là hashtable thậm chí còn nhanh hơn—nó có thể tìm kiếm trong một thời gian hằng số—và nó không cần các giá trị phải được sắp xếp. Các từ điển Python đều được thực hiện theo bảng băm; đó là lý do mà hầu hết các phép tính với từ điển, kể cả toán tử in, đều có thời gian hằng số.

B.4 Bảng băm

Để lý giải cách hoạt động của các bảng băm và vì sao hiệu năng của nó tốt vậy, tôi bắt đầu bằng một phiên bản với ánh xạ và cuối cùng sẽ cải thiện nó để đạt tới một bảng băm.

Tôi dùng Python để giới thiệu cách thực hiện, nhưng trong thực tế bạn không phải viết mã Python như vậy; bạn chỉ cần dùng một từ điển! Vì thế, phần còn lại của chương này bạn hình dung như chưa tồn tại từ điển và bạn muốn thực hiện một cấu trúc dữ liệu để ánh xạ từ khóa đến gía trị. Các phép tính mà bạn cần thực hiện gồm:

add(k, v): Thêm một phần tử mới trong đó ánh xạ từ khóa k tới gía trị v. Với một từ điển Python, d, phép tính này được viết là d[k] = v. get(target): Tra tìm và trả lại giá trị tương ứng với khóa target. Với một từ điển Python, d, phép tính này được viết d[target] hoặc d.get(target).

Đến giờ, tôi coi rằng mỗi khóa chỉ xuất hiện một lần. Cách thực hiện đơn giản nhất cho giao diện này sẽ sử dụng một danh sách các bộ (tuple), trong đó mỗi bộ là một cặp khóa-trị.

class LinearMap(object):

def __init__(self):
    self.items = []
def add(self, k, v):
    self.items.append((k, v))
def get(self, k):
    for key, val in self.items:
        if key == k:
            return val
    raise KeyError

add điền thêm một bộ khoá-trị vào danh sách các phần tử, phương thức này tiêu tốn thời gian hằng số.

get dùng một vòng lặp for để tìm kiếm trong danh sách: nếu tìm thấy khoá đích thì nó trả lại giá trị tương ứng; còn không nó phát lỗi KeyError. Vậy get là tuyến tính.

Một cách làm khác là duy trì trật tự trong danh sách xếp theo khoá. Khi đó, get có thể dùng một phép tìm kiếm phân đôi, vốn có bậc O(logn). Nhưng việc chèn thêm một phần tử mới vào giữa danh sách thì lại có bậc tuyến tính, bởi vậy cách này có thể không phải là lựa chọn tốt nhất. Đã có những cấu trúc dữ liệu khác (xem http://en.wikipedia.org/wiki/Red-black_tree) có thể thựuc hiện add và get thời gian logarit, nhưng thế vẫn chưa tốt bằng thời gain hằng số, vậy ta hãy tiếp tục.

Một cách để cải thiện LinearMap là bẻ gãy danh sách các cặp khoá trị thành các danh sách nhỏ. Sau đây là một phiên bản có tên BetterMap, vốn là một danh sách gồm 100 LinearMap. Như ta sẽ thấy ngay, bậc tăng trưởng của get vẫn là tuyến tính, nhưng BetterMap đã tiến một bước về phía các bảng băm:

class BetterMap(object):

def __init__(self, n=100):
    self.maps = []
    for i in range(n):
        self.maps.append(LinearMap())
def find_map(self, k):
    index = hash(k) % len(self.maps)
    return self.maps[index]
def add(self, k, v):
    m = self.find_map(k)
    m.add(k, v)
def get(self, k):
    m = self.find_map(k)
    return m.get(k)

init tạo một danh sách gồm n các LinearMaps.

find_map được dùng bởi add và get để hình dung ra ánh xạ nào để đặt phần tử mới nào, hoặc ánh xạ nào để tìm kiếm trong đó.

find_map dùng một hàm lập sẵn có tên hash, hàm này nhận gần như bất kì đối tượng Python nào rồi trả lại một số nguyên. Một hạn chế của cách làm này là nó chỉ làm việc được với các khoá băm được. Những kiểu biến chuyển như danh sách và từ điển thì không băm được.

Khi xét sự bằng nhau giữa hai đối tượng băm được thì chúng trả lại cùng giá trị băm. Nhưng điều ngược lại thì không nhất thiết đúng: hai đối tượng khác nhau vẫn có thể trả lại cùng giá trị băm.

find_map sử dụng toán tử phần dư (modulus) để gói các giá trị băm vào trong khoảng từ 0 đến len(self.maps), bởi vậy kết quả là một chỉ số hợp lệ trong danh sách. Dĩ nhiên, điều này nghĩa là nhiều giá trị băm khác nhau sẽ gói vào cùng một chỉ số. Nhưng nếu hàm băm trải các phần tử khá đều đặn (đây chính là nhiệm vụ được thiết kế của các hàm băm), thì ta sẽ dự trù khoảng n/100 phần tử trong mỗi LinearMap.

Vì thời gian chạy của LinearMap.get tỉ lệ thuận với số phần tử nên ta dự trù BetterMap nhanh hơn khoảng 100 lần so với LinearMap. Bậc tăng trưởng vẫn là tuyến tính, nhưng hệ số đầu thì nhỏ hơn. Vậy là tốt, nhưng chưa bằng được một bảng băm.

Sau cùng, đây là ý tưởng cốt lõi để làm cho các bảng băm chạy nhanh: nếu bạn có thể giữ cho độ dài tối đa của các LinearMap trong giới hạn, thì LinearMap.get có thời gian là hằng số. Những gì bạn cần làm là theo dõi số phần tử và khi số phần tử trong mỗi LinearMap vượt một giới hạn, chỉnh cỡ bảng băm bằng cách thêm các LinearMap.

Sau đây là một phiên bản của bảng băm:

class HashMap(object):

def __init__(self):
    self.maps = BetterMap(2)
    self.num = 0
def get(self, k):
    return self.maps.get(k)
def add(self, k, v):
    if self.num == len(self.maps.maps):
        self.resize()
    self.maps.add(k, v)
    self.num += 1
def resize(self):
    new_maps = BetterMap(self.num * 2)
    for m in self.maps.maps:
        for k, v in m.items:
            new_maps.add(k, v)
    self.maps = new_maps

Mỗi HashMap chứa một BetterMap; init bắt đầu chỉ với 2 LinearMap và khởi tạo num, vốn theo dõi số các phần tử.

get chỉ chuyển đến BetterMap. Công việc thực sự xảy ra trong add, ở đó số các phần tử và kích cỡ của BetterMap được kiểm tra: nếu hai số này bằng nhau thì số trung bình các phần tử trong mỗi LinearMap là 1, bởi vậy nó gọi resize.

resize tạo mới một BetterMap, lớn gấp đôi cái cũ, và rồi “băm lại” các phần tử từ ánh xạ cũ sang ánh xạ mới.

Băm lại là cần thiết vì sự thay đổi các LinearMap thay đổi mẫu số của phép tính modulus trong find_map. Điều đó có nghĩa là một số đối tượng đã dùng để gói vào trong cùng LinearMap sẽ bị tách ra (chính là điều ta mong muốn phải không?).

Việc băm lại có thời gian tuyến tính, bởi vậy resize là tuyến tính, vốn dường như là dở, vì tôi đã hứa rằng add sẽ có thời gian hằng số. Nhưng nhớ rằng không phải lần nào ta cũng co giãn, bởi vậy add thường chỉ có thời gian hằng số và chỉ đôi lúc tuyến tính. Tổng lượng công việc để chạy add n lần thì tỉ lệ với n, do vậy thời gian trung bình của mỗi add là thời gian hằng số!

Để xem cách này hoạt động thế nào, hãy nghĩ về việc bắt đầu với một HashTable rỗng và thêm một dãy các phần tử. Ta bắt đầu với 2 LinearMap, bởi vậy 2 phép thêm (add) đầu tiên đều nhanh (không cần phải co giãn). Cứ cho rằng mỗi cái chiếm 1 đơn vị công việc. Add tiếp theo yêu cầu phải co giãn, bởi vậy ta phải băm lại hai phần tử đầu (cứ cho là 2 đơn vị công việc nữa) và rồi thêm phần tử thứ ba (một đơn vị nữa). Thêm một đơn vị nữa thì tốn 1 đơn vị, bởi vậy đến giờ có 6 đơn vị công việc cả thảy cho 4 phần tử.

add tiếp theo tốn 5 đơn vị, nhưng ba cái tiếp theo mỗi cái chỉ một đơn vị, do vậy 8 phép add đầu chiếm tổng số 14 đơn vị.

add tiếp theo tốn 9 đơn vị, nhưng sau đó ta có thể thêm 7 đơn vị cho phép co giãn tiếp theo, vì vậy tổng số là 30 đơn vị cho 16 phép add đầu tiên.

Sau 32 phép add, tổng chi phí là 62 đơn vị, và tôi hi vọng rằng bạn đã hình dung ra một dạng thức. Sau n phép add, trong đó n là một luỹ thừa của 2, tổng chi phí là 2n−2 đơn vị, vì vậy số công việc trung bình của mỗi add thấp hơn 2 một chút. Khi n là luỹ thừa của 2, đó là trường hợp tốt nhất; với những giá trị khác của n số công việc trung bình cao hơn một chút, nhưng không quan trọng. Điều quan trọng rằng đó là O(1).

Hình minh hoạ cho hoạt động của cách này. Mỗi khối biểu diễn một đơn vị công việc. Các cột cho thấy tổng công việc của từng phép add theo thứ tự từ trái sang phải: hai add đầu tốn 1 đơn vị, add thứ ba tốn 3 đơn vị, v.v.

Hình B.1: Chi phí của phép cộng bảng băm.

Phần việc dư thêm để băm lại xuất hiện như một dãy các táp cao dần với khoảng cách ngày càng xa. Bây giờ nếu bạn xô đổ các tháp này, san đều chi phí co giãn cho tất cả phép add, bạn có thể thấy một cách hình ảnh rằng tổng chi phí sau n phép add là 2n − 2.

Một đặc điểm quan trọng của thuật toán này là khi ta co giãn HashTable nó tăng theo cấp số nhân; tức là ta nhân kích cỡ với một hằng số. Nếu bạn tăng kích cỡ theo cấp số cộng—tức là mỗi lần chỉ cộng một số không đổi—thì thời gian trung bình cho mỗi add là tuyến tính.

Bạn có thể tải về phiên bản HashMap của tôi từ http://thinkpython/code/Map.py, nhưng nhớ rằng không có lý gì bạn phải dùng nó; nếu bạn muốn có ánh xạ, hãy dùng từ điển của Python.

Ai là cha đẻ của thuật toán?

Alan Turing.

Người được xem là cha đẻ của máy tính và ngành khoa học máy tính hiện đại là ai?

Sinh ngày 23-6-1912 tại London, nhà toán học tài ba người Anh Alan Turing được biết đến như cha đẻ của ngành khoa học máy tính và trí tuệ nhân tạo (AI). Ông là người phát minh máy Turing (Turing machine), hình thái đơn giản nhất của một chiếc máy điện toán.

Ai là người phát minh ra những con số?

Người Ai Cập đã phát minh ra hệ thống chữ số được mã hóa đầu tiên, và người Hy Lạp theo sau bằng cách ánh xạ các số đếm của họ lên bảng chữ cái Ionia và Doric.

Phát minh toán học nên tặng nào được ghi công cho người Ai Cập?

Toán học Ai Cập cổ đại được đánh dấu bởi nhân vật truyền thuyết Thoth, người được coi là đã đặt ra mẫu tự Ai Cập, hệ thống chữ số, toán học và thiên văn học, là vị thần của thời gian.