Mảng động
Mảng động
Thêm một phần tử thường tốn đúng một phép. Nhưng thỉnh thoảng hệ phải xin một vùng nhớ mới và chép toàn bộ mảng sang. Vậy trung bình ra bao nhiêu, và vì sao câu trả lời lại là một hằng số?
Bạn đã dùng nó rồi, dù có thể chưa để ý. vector của C++, ArrayList của Java, list của Python: cả ba đều là mảng động, tức một mảng liên tục trong bộ nhớ nhưng biết tự lớn lên khi bạn thêm phần tử. Mảng thường thì không làm được vậy. Khi bạn xin hệ điều hành một vùng nhớ n ô, bạn nhận đúng n ô nằm cạnh nhau, và không có cách nào bảo nó nới thêm một ô ở cuối, vì ô kế bên rất có thể đã thuộc về người khác. Bài con trỏ và cấp phát động nói kỹ chỗ này.
Nên mảng động làm một chuyện rất thô: khi hết chỗ, nó xin hẳn một vùng mới, to hơn, chép toàn bộ phần tử cũ sang, trả lại vùng cũ, rồi mới ghi phần tử mới. Đó là một thao tác đắt. Chép 512 phần tử để thêm được đúng một phần tử nghe không giống một cấu trúc dữ liệu tốt chút nào.
Chuyện đáng ngạc nhiên là: trung bình ra thì nó vẫn rẻ, rẻ tới mức coi như hằng số. Và điều đó chỉ đúng nếu bạn lớn lên theo kiểu nhân. Đổi sang kiểu cộng thêm một hằng số, thứ nghe có vẻ tiết kiệm hơn, thì cả cấu trúc sụp thành bậc hai. Sim dưới đây đếm từng phép cho bạn thấy, và mọi tham số đều sửa được.
1 · Cấu hình mảng ✎ sửa được
trần(sức chứa cũ × 2,00). Hệ số phải lớn hơn 1,10: nhân 1 thì mảng không bao giờ lớn thêm.2 · Sổ cái sau khi thêm 1.000 phần tử
Với kiểu nhân 2,00, chi phí khấu hao không thể vượt 3,00 phép cho mỗi phần tử, dù n lớn tới đâu. Chặn này là 1 + f / (f - 1): các sức chứa cách nhau theo cấp số nhân nên tổng số phần tử phải chép nhỏ hơn n × f / (f - 1). Đang đo được 2,02.
3 · Các lần dời rơi vào đâu
| lần | xảy ra ở phần tử thứ | sức chứa cũ | sức chứa mới | chép bao nhiêu | tổng đã chép | ô trống ngay sau đó | vùng đã trả về có đủ chứa không |
|---|---|---|---|---|---|---|---|
| 1 | 5 | 4 | 8 | 4 | 4 | 3 (37,5%) | ✗ chưa đủ (0 so với 8) |
| 2 | 9 | 8 | 16 | 8 | 12 | 7 (43,8%) | ✗ chưa đủ (4 so với 16) |
| 3 | 17 | 16 | 32 | 16 | 28 | 15 (46,9%) | ✗ chưa đủ (12 so với 32) |
| 4 | 33 | 32 | 64 | 32 | 60 | 31 (48,4%) | ✗ chưa đủ (28 so với 64) |
| 5 | 65 | 64 | 128 | 64 | 124 | 63 (49,2%) | ✗ chưa đủ (60 so với 128) |
| 6 | 129 | 128 | 256 | 128 | 252 | 127 (49,6%) | ✗ chưa đủ (124 so với 256) |
| 7 | 257 | 256 | 512 | 256 | 508 | 255 (49,8%) | ✗ chưa đủ (252 so với 512) |
| 8 | 513 | 512 | 1.024 | 512 | 1.020 | 511 (49,9%) | ✗ chưa đủ (508 so với 1.024) |
4 · Chi phí khấu hao khi n lớn dần
n. Thanh dài theo chi phí khấu hao, cao nhất trong bảng là 2,02 phép cho mỗi phần tử.n.5 · Chỗ nhớ đang bỏ trống
Tỉ lệ bỏ trống dao động chứ không đứng yên: ngay sau một lần dời thì mảng vừa xin gấp 2,00 lần chỗ mà mới dùng có một phần, rồi nó đầy dần cho tới lần dời sau. Với hệ số 2, ngay sau khi dời thì gần đúng một nửa vùng nhớ đang trống, và con số đó tiến sát 50% khi mảng lớn lên. Ở cấu hình đang chạy, đỉnh đo được là 49,9%. Nên hỏi “mảng động lãng phí bao nhiêu bộ nhớ” mà không nói rõ đang đứng ở đâu trong chu kỳ thì câu trả lời nào cũng đúng một nửa.
6 · Vùng nhớ vừa trả về có dùng lại được không
- Nó đếm phần tử: một lần ghi tính một phép, một lần chép cũng tính một phép. Đó là quy ước của phân tích khấu hao, không phải phép đo thời gian. Chép 1.000 số nguyên bằng một lệnh sao chép khối nhanh hơn hẳn 1.000 lần gọi hàm khởi tạo sao chép của một đối tượng nặng, mà ở đây hai chuyện đó cùng ra 1.000.
- Nó giả định mỗi lần hết chỗ là phải dời. Bộ cấp phát thật đôi khi nới được vùng cũ tại chỗ và không phải chép gì cả, lúc đó con số ở đây là chặn trên chứ không phải số thật.
- Preset mang tên thư viện chỉ mô hình hoá quy tắc lớn lên đã công bố trong mã nguồn, kèm tên hàm và ngày ghi. Nó không chạy mã của thư viện đó. Cổng kiểm số canh phép tính, không canh chuyện phiên bản hiện tại của thư viện có còn làm đúng như vậy hay không.
- Nó không nói gì về xoá phần tử. Phần lớn thư viện không thu nhỏ sức chứa khi bạn xoá, và một chiến lược thu nhỏ đặt sai ngưỡng còn tạo ra chu kỳ dời qua dời lại rất tốn kém. Đó là một bài khác.
Quy ước đếm, nói trước cho rõ
Trước khi đọc con số nào, phải thống nhất đang đếm cái gì. Ở đây: ghi một phần tử tính một phép, chép một phần tử cũng tính một phép. Thêm n phần tử vào một mảng chưa bao giờ phải dời thì tốn đúng n phép. Mỗi lần phải dời thì cộng thêm đúng số phần tử đang có.
Đây là quy ước, không phải phép đo thời gian. Chép 1.000 số nguyên bằng một lệnh sao chép khối nhanh hơn hẳn 1.000 lần gọi hàm khởi tạo sao chép của một đối tượng nặng, mà ở đây cả hai đều ra 1.000. Bạn sẽ gặp lại cách đếm này ở bài đếm phép tính: nó bỏ qua hằng số nhân để nhìn ra dáng tăng trưởng, và cái giá của việc bỏ qua đó là nó không nói gì về nanô giây.
Mốc dời nằm ở đâu, chính xác
Ở trạng thái mở bài, mảng có sức chứa ban đầu 4, mỗi lần hết chỗ thì nhân đôi, và bạn thêm 1.000 phần tử.
Điều đầu tiên cần đóng đinh là mốc biên, vì đây là chỗ người ta hay nhầm một đơn vị. Việc dời xảy ra khi mảng đã đầy rồi, tức ngay trước khi ghi phần tử thứ sức chứa + 1. Cụ thể với sức chứa 4:
- thêm đúng 4 phần tử: chưa phải dời lần nào, sức chứa vẫn là 4 và không còn ô trống nào
- thêm phần tử thứ 5: phải dời, chép 4 phần tử cũ sang vùng mới 8 ô
- thêm tới đúng phần tử thứ 8: vẫn mới dời một lần, vì 8 ô vừa đủ
- phần tử thứ 9 mới kích hoạt lần dời thứ hai, và lần này chép 8 phần tử chứ không phải 4
Nhìn cột “xảy ra ở phần tử thứ” trong bảng: 5, 9, 17, 33, 65, 129, 257, 513. Tám lần, và khoảng cách giữa hai lần liên tiếp gấp đôi mỗi lần. Dải vạch ở mục 3 vẽ đúng chuyện đó: các vạch dồn về đầu rồi thưa dần tới mức gần như biến mất ở nửa sau.
Cộng lại thì ra một con số nhỏ đến bất ngờ
Tổng số phần tử bị chép qua cả 8 lần là 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 = 1.020. Cộng với 1.000 lần ghi là 2.020 phép cho 1.000 phần tử, tức 2,02 phép cho mỗi phần tử.
Chỗ đáng nhìn kỹ nằm ở tổng 1.020. Nó nhỏ hơn 1.024, tức nhỏ hơn chính sức chứa cuối cùng. Đó không phải trùng hợp: khi các sức chứa là một cấp số nhân công bội 2 thì tổng tất cả các số hạng trước luôn nhỏ hơn số hạng kế tiếp. Nói cách khác, toàn bộ công việc chép của cả lịch sử cộng lại vẫn chưa bằng một lần chép cuối cùng. Đó là toàn bộ lý do mảng động rẻ.
Tổng quát hơn, với hệ số nhân f, chi phí khấu hao luôn nhỏ hơn 1 + f / (f - 1). Với f = 2 thì chặn đó là 3: thêm một phần tử không bao giờ tốn quá 3 phép tính trung bình, dù mảng có dài tới đâu. Kéo núm số phần tử và nhìn cột chi phí khấu hao ở mục 4:
n | 4 | 8 | 16 | 32 | 128 | 512 | 1.000 |
|---|---|---|---|---|---|---|---|
| khấu hao | 1,00 | 1,50 | 1,75 | 1,88 | 1,97 | 1,99 | 2,02 |
Nó phẳng ra. Đó chính là nội dung của chữ “khấu hao hằng số”: có những phần tử phải trả giá rất đắt, riêng phần tử thứ 513 tốn 513 phép, nhưng khi chia đều cho cả dãy thì con số đứng lại và không leo theo n.
Con số dao động trong khoảng chứ không hội tụ về một điểm, và đó là điều đúng cần nói. Ngay sau một lần dời thì chi phí khấu hao vọt lên gần chặn 3, rồi tụt dần về gần 2 khi mảng lấp đầy vùng vừa xin. Nó chỉ chắc chắn một chuyện: không bao giờ vượt 3.
Đổi sang cộng thêm hằng số, và mọi thứ sụp
Bấm preset cộng thêm 8 ô. Cùng một mảng, chỉ khác chỗ mỗi lần hết chỗ thì xin thêm đúng 8 ô thay vì nhân đôi. Nghe rất tiết kiệm: không bao giờ bỏ trống nhiều.
Với 2.000 phần tử: 250 lần dời, 250.000 phần tử bị chép, chi phí khấu hao 126,00 phép cho mỗi phần tử. So với 2,02 của kiểu nhân đôi.
Nhưng con số 126 chưa phải là chỗ tệ nhất. Chỗ tệ nhất là nó không đứng yên:
n | 128 | 256 | 512 | 1.024 | 2.000 |
|---|---|---|---|---|---|
| khấu hao | 9,00 | 17,00 | 33,00 | 65,00 | 126,00 |
Mỗi lần n gấp đôi thì chi phí trung bình cũng gấp đôi. Một chi phí trung bình mà lại phụ thuộc vào n thì tổng công việc đi theo n². Lý do dễ thấy khi viết ra: số lần dời tỉ lệ với n / 8, và lần dời thứ k chép khoảng 8k phần tử, nên tổng là một cấp số cộng, tức bậc hai. Thêm một triệu phần tử theo kiểu này là một vòng lặp chạy cả nghìn tỉ phép.
Đây là lý do không thư viện thật nào lớn lên theo kiểu cộng hằng số, và cũng là cái bẫy phổ biến nhất khi sinh viên tự viết mảng động lần đầu.
Bộ nhớ bỏ trống: cái giá của việc nhân
Nhân đôi rẻ về thời gian, nhưng nó không miễn phí. Ngay sau một lần dời, mảng vừa xin gấp đôi chỗ mà mới dùng có một nửa, nên gần đúng một nửa vùng nhớ đang nằm không. Ở cấu hình mở bài, đỉnh trống đo được là 49,9%, rơi vào ngay sau khi thêm phần tử thứ 513: lúc đó mảng giữ 513 phần tử trong một vùng 1.024 ô.
Con số đó tiến sát 50% chứ không chạm tới, và điều này đúng theo công thức chứ không phải theo may mắn: ngay sau khi nhân đôi từ c lên 2c, mảng giữ c + 1 phần tử nên tỉ lệ trống là (c - 1) / 2c, luôn nhỏ hơn một nửa. Kéo số phần tử lên 20.000 thì con số hiện ra thành 50,0%, nhưng đó chỉ là làm tròn: giá trị thật là 16.383 / 32.768, vẫn dưới một nửa.
Còn tỉ lệ trống lúc này, ở n bằng 1.000, chỉ là 2,3%. Không mâu thuẫn gì cả: 1.000 tình cờ nằm sát ngay dưới 1.024 nên mảng gần như đầy. Tỉ lệ bỏ trống dao động theo chu kỳ giữa gần một nửa và gần không. Nên hỏi “mảng động lãng phí bao nhiêu bộ nhớ” mà không nói đang đứng ở đâu trong chu kỳ thì câu trả lời nào cũng đúng một nửa.
Đổi hệ số thì đổi luôn cái giá này. Hệ số 1,5 cho đỉnh trống 33,3%, hệ số 4 cho đỉnh trống 74,9%. Cả hai đều bám sát chặn (f - 1) / f, tức một phần ba và ba phần tư, mà vẫn nằm dưới nó, vì ngay sau khi nhân từ c lên f × c thì mảng đã giữ c + 1 phần tử chứ không phải c. Đây là một cuộc đánh đổi rất sòng phẳng: hệ số càng lớn thì càng ít lần chép nhưng càng nhiều chỗ nằm không.
Vì sao nhiều thư viện thật chọn 1,5 chứ không phải 2
Bấm preset Java ArrayList. Sức chứa đầu 10, mỗi lần nhân 1,5. Với 1.000 phần tử: 12 lần dời, chép 2.711 phần tử, khấu hao 3,71 phép cho mỗi phần tử, tức đắt hơn hẳn 2,02 của kiểu nhân đôi. Bù lại sức chứa cuối là 1.368 nên chỉ bỏ trống 26,9%, và đỉnh trống thấp hơn nhiều.
Nhưng lý do thật sự người ta chọn 1,5 nằm ở chỗ khác, và nó không phải lý do số học. Nhìn cột cuối của bảng, cột “vùng đã trả về có đủ chứa không”.
Với hệ số 2, cột đó ghi “chưa đủ” ở mọi hàng, mãi mãi. Vừa chứng minh ở trên rồi: tổng mọi sức chứa cũ luôn nhỏ hơn sức chứa kế tiếp. Nghĩa là các vùng nhớ bạn đã trả lại cho hệ, dù có nằm liền nhau đi nữa, không bao giờ gộp lại đủ lớn cho lần xin tiếp theo. Bộ nhớ trả về cứ nằm đó không dùng được, và vùng mới phải lấy từ chỗ khác.
Với hệ số 1,5 thì từ lần dời thứ 5 trở đi, cột đó lật sang “đủ”. Kéo hệ số lên 1,6 thì phải tới lần thứ 9 mới lật. Lên 1,7 thì không bao giờ lật nữa. Ngưỡng nằm đâu đó giữa 1,6 và 1,65, và tỉ lệ vàng 1,618 rơi đúng vào khoảng đó, đúng như hệ thức truy hồi báo trước: điều kiện 1 + r + ... + r^(k-2) ≥ r^k chỉ giữ được về lâu dài khi r² - r - 1 ≤ 0.
Một cảnh báo nhỏ về cách đọc mấy con số “lần thứ 5”, “lần thứ 9” ấy: chúng chỉ có nghĩa khi mảng kịp dời đủ nhiều lần. Đặt sức chứa ban đầu 1.024 với hệ số 1,6 rồi thêm 20.000 phần tử thì cột đó không lật lần nào, đơn giản vì mảng mới dời được vài lần đã vượt qua n. Ngưỡng là chuyện của dãy vô hạn, còn sim thì luôn dừng ở một n hữu hạn.
Và đây là chỗ phải dừng lại nói cho rõ. Sim chứng minh được phần số học: tổng các vùng đã trả về có lớn bằng vùng đang xin hay không. Nó không chứng minh được là bộ cấp phát thật sẽ gộp mấy vùng đó lại rồi giao cho bạn. Muốn vậy thì các vùng phải nằm liền nhau, bộ cấp phát phải có cơ chế gộp mảnh, và còn phụ thuộc cả vào việc chương trình có xin cấp phát thứ gì khác xen vào giữa hay không. Đó là lý do cấp phát bộ nhớ, không phải lý do toán học, nên sim này chỉ cho bạn thấy điều kiện cần chứ không kết luận được điều gì về hiệu năng thật. Muốn biết thì phải đo, và bài hiệu năng tập hợp trong Java là chỗ nói về việc đo đó.
Vài chi tiết nữa đáng biết, cũng để bạn khỏi đọc sim quá lời:
- Sức chứa ban đầu không phải hằng số thiêng liêng. Preset libstdc++ mô hình hoá
vectorrỗng bắt đầu từ sức chứa 0 rồi lần thêm đầu tiên xin đúng 1 ô: 10 lần dời, chép 1.023 phần tử, khấu hao vẫn 2,02. Gần như không khác gì bắt đầu từ 4. Sức chứa ban đầu chỉ ảnh hưởng tới mấy lần dời đầu, không ảnh hưởng tới dáng tăng trưởng. listcủa Python không thuộc cả hai kiểu ở đây. Nó cộng thêm khoảng một phần tám sức chứa hiện tại rồi làm tròn, viết trong hàmlist_resizecủa CPython. Đó là kiểu nhân với một hệ số rất nhỏ cộng thêm một hằng số, và sim này không mô hình hoá đúng được nó, nên đừng lấy con số ở đây gán cho Python.- Hệ số nhân bằng 1 là một lỗi thật, không phải một lựa chọn tồi. Nhân 1 thì sức chứa không bao giờ lớn thêm, vòng lặp “lớn lên cho tới khi đủ chỗ” chạy mãi không dừng. Sim chặn hệ số ở 1,1 và nói ra là nó đã chặn, chứ không âm thầm sửa. Phần tính bên trong còn một chốt nữa: nếu ai đó gọi thẳng nó với hệ số 1 thì nó từ chối chạy kèm lý do, thay vì treo máy. Tự viết mảng động thì đây đúng là cái bẫy sẽ làm chương trình của bạn đứng hình mà không báo lỗi gì.
- Xoá phần tử là một câu chuyện khác. Phần lớn thư viện không thu nhỏ sức chứa khi bạn xoá. Nếu có thu nhỏ mà đặt sai ngưỡng thì sinh ra chu kỳ dời qua dời lại rất tốn kém, và sim này không đụng tới chuyện đó.
Thêm một phần tử vào mảng động thường tốn một phép, thỉnh thoảng tốn cả nghìn, nhưng chia đều ra thì vẫn là hằng số. Điều kiện để chuyện đó xảy ra là sức chứa phải lớn lên theo kiểu nhân: khi ấy tổng công việc chép của cả lịch sử vẫn nhỏ hơn một lần chép cuối, và chi phí khấu hao bị chặn dưới 1 + f / (f - 1), tức 3 với hệ số 2. Đổi sang cộng thêm hằng số thì chi phí trung bình leo theo n và tổng công việc thành bậc hai, đó là cái bẫy chết người. Cái giá phải trả cho việc nhân là bộ nhớ bỏ trống dao động tới gần một nửa. Còn chuyện vì sao nhiều thư viện chọn 1,5 thay vì 2 thì thuộc về cách bộ cấp phát tái dùng vùng nhớ đã trả về, và không phép đếm nào ở đây chứng minh được nó.
- 1Một mảng động có sức chứa ban đầu 4 và nhân đôi mỗi khi hết chỗ. Bạn thêm đúng 8 phần tử. Hệ đã phải dời mảng sang vùng nhớ mới mấy lần?
- 2Một mảng động mỗi lần hết chỗ thì xin thêm đúng 8 ô. Ở n bằng 1.000 phần tử, chi phí khấu hao đo được là 63,5 phép cho mỗi phần tử. Ở n bằng 2.000 thì bạn chờ đợi con số nào?
- 3Nhiều thư viện thật chọn hệ số 1,5 thay vì 2. Sim này chứng minh được điều gì về lựa chọn đó, và không chứng minh được điều gì?