Mảng là gì?

Một ứng dụng thời tiết hiển thị nhiệt độ cả tuần cần bảy con số. Nó có thể dùng bảy biến riêng, monday, tuesday và cứ thế tiếp, nhưng khi đó không vòng lặp nào duyệt qua chúng được, và thêm ngày thứ tám nghĩa là phải viết code mới. Mảng gom cả bảy số vào một cái tên, temperatures, trong các ô đánh số từ 0 đến 6.

Mảng hoạt động thế nào

Mảng giữ các phần tử nằm cạnh nhau trong một khối bộ nhớ, và mỗi phần tử chiếm cùng một số byte. Cách sắp xếp này giúp máy tính tìm ra bất kỳ phần tử nào chỉ với một phép tính:

address of element i = start address + i × element size

Giả sử một mảng số nguyên 32 bit (mỗi số 4 byte) bắt đầu ở địa chỉ bộ nhớ 1000. Phần tử 0 ở 1000, phần tử 1 ở 1004, phần tử 2 ở 1008 và phần tử 3 ở 1012. Truy cập phần tử 3 hay phần tử 3.000.000 đều chỉ tốn đúng một bước, vì thế việc đọc mảng theo chỉ số được gọi là thời gian hằng số, viết là O(1).

Module array của Python lưu số thô theo đúng cách này, nên bạn có thể tự kiểm tra phép tính:

from array import array

scores = array("i", [90, 75, 88, 62])
print(scores.itemsize, "bytes per element")
print(len(scores) * scores.itemsize, "bytes in total")

start = 1000  # pretend the array starts at address 1000
for index in range(len(scores)):
    address = start + index * scores.itemsize
    print("scores[" + str(index) + "] =", scores[index], "at address", address)

4 bytes per element
16 bytes in total
scores[0] = 90 at address 1000
scores[1] = 75 at address 1004
scores[2] = 88 at address 1008
scores[3] = 62 at address 1012

Công thức này cũng giải thích vì sao hầu hết các ngôn ngữ đếm từ 0. Chỉ số (index) là một độ lệch: phải bỏ qua bao nhiêu phần tử tính từ đầu. Phần tử đầu tiên cách điểm bắt đầu 0 phần tử, nên chỉ số của nó là 0, và phần tử cuối của một mảng độ dài n có chỉ số n − 1. Một số ít ngôn ngữ như Lua, MATLAB, R và Fortran lại bắt đầu từ 1.

Dùng mảng trong Python

Phần lớn code Python dùng list có sẵn làm mảng. Bạn tạo nó bằng dấu ngoặc vuông, đọc và sửa phần tử theo chỉ số, và lấy độ dài bằng len():

temperatures = [18, 21, 25, 23, 19]

print(temperatures[0])   # first element
print(temperatures[2])   # third element
print(temperatures[-1])  # last element
print(len(temperatures))

temperatures[1] = 22     # change one element
temperatures.append(20)  # add one at the end
print(temperatures)

18
25
19
5
[18, 22, 25, 23, 19, 20]

Chỉ số âm đếm từ cuối lên, nên temperatures[-1] là phần tử cuối cùng. Cách viết tắt này là của riêng Python; C và Java không có chỉ số âm.

Chi phí của các thao tác trên mảng

Cách lưu liền nhau làm một số thao tác rất nhanh và một số khác chậm. Chi phí tăng theo n, số phần tử:

Chèn vào đầu mảng chậm vì mọi phần tử phải dời đi một ô để lấy chỗ. Tìm kiếm trong mảng chưa sắp xếp nghĩa là tìm kiếm tuyến tính qua từng phần tử, còn mảng đã sắp xếp cho phép tìm kiếm nhị phân, mỗi bước chia đôi khoảng còn lại.

Duyệt qua mảng

Mảng và vòng lặp luôn đi cùng nhau: vòng lặp ghé qua lần lượt từng phần tử, gọi là lặp. Cùng vài dòng code đó xử lý được mảng 5 phần tử hay 5 triệu phần tử.

prices = [4.50, 12.00, 3.25, 8.75]

total = 0
for price in prices:
    total = total + price

print("Total:", total)
print("Most expensive:", max(prices))

Total: 28.5
Most expensive: 12.0

Mảng trong các ngôn ngữ khác

Trong C, mảng có kích thước cố định, được đặt khi khai báo, và chứa các giá trị thô cùng một kiểu. sizeof cho biết kích thước của nó tính bằng byte:

int scores[5] = {90, 75, 88, 62, 100};   /* 5 × 4 bytes = 20 bytes */

Mảng trong Java cũng có độ dài cố định, và các phần tử mới bắt đầu bằng giá trị mặc định, chẳng hạn 0 với số. Khi cần một mảng Java có thể lớn lên, bạn dùng ArrayList:

int[] scores = new int[5];   // five elements, all 0
scores[0] = 90;

Mảng trong JavaScript tự do lớn lên, thu nhỏ và có thể trộn nhiều kiểu, như [1, "two", true].

Những mảng có thể lớn lên, như list của Python, ArrayList của Java và std::vector của C++, được gọi là mảng động. Chúng giữ sẵn chỗ trống ở cuối. Khi hết chỗ, chúng cấp phát một khối lớn hơn, sao chép mọi phần tử sang đó rồi tiếp tục. Việc sao chép hiếm đến mức thao tác thêm vào cuối vẫn nhanh nếu tính trung bình.

Mảng cũng có thể chứa các mảng khác. grid[row][col] đọc một ô của mảng hai chiều, cách bố trí dùng cho bàn cờ trong game, bảng tính và hình ảnh. Hướng dẫn mảng nhiều chiều trong C cho thấy chúng nằm trong bộ nhớ ra sao.

Lỗi thường gặp

Lệch một đơn vị. Mảng 3 phần tử có các chỉ số 0, 1 và 2, nên chỉ số 3 đã vượt quá cuối mảng. Python dừng lại và báo lỗi:

scores = [90, 75, 88]
print(scores[3])

IndexError: list index out of range

Java ném ra ArrayIndexOutOfBoundsException, còn JavaScript lặng lẽ trả về undefined. C không kiểm tra gì cả: đọc vượt quá cuối mảng là hành vi không xác định, có thể trả về giá trị rác hoặc làm chương trình crash với lỗi segmentation fault.

Sao chép bằng phép gán. Trong Python, Java và JavaScript, b = a không sao chép mảng; cả hai tên cùng trỏ tới một mảng, nên sửa b cũng là sửa a. Dùng a.copy() trong Python hoặc [...a] trong JavaScript để có một bản sao thật. Trang về biến giải thích lý do.

Học tiếp ở đâu

Mảng chỉ hữu ích khi có vòng lặp để duyệt qua, nên hãy đọc tiếp lặp là gì, và byte là gì để hiểu đơn vị đằng sau kích thước phần tử ở trên. Hướng dẫn list trong Python đi qua cắt list, sắp xếp và các phương thức của list, còn mô phỏng danh sách liên kết cho thấy cấu trúc đánh đổi việc truy cập theo chỉ số nhanh để lấy việc chèn nhanh.