1. Giới thiệu về "Efficient arrays"

Kiểu dữ liệu list có thể chứa đựng bất kỳ cái gì thuộc bất kỳ cấu trúc nào. Khái niệm về list (hay danh sách) trong Python gần gũi với ý niệm về cái túi (a bag). Một bag có thể chứa bánh kẹo, hoa quả, quần áo... Điểm khác biệt là list thì có thứ tự, các phần tử được truy cập qua một index duy nhất.

Về điểm này list khác với khái niệm về array - hay mảng trong các ngôn ngữ thông thường khác. Chẳng hạn trong VB.NET một array là một danh sách có thứ tự các phần tử có cùng cấu trúc. Bạn luôn luôn phải chỉ rõ kiểu của phần tử trong mỗi array qua khai báo array of type.

Chính vì list có thể chứa bất kỳ phần tử thuộc bất kỳ cấu trúc nào mà một số thao tác phụ thuộc vào cấu trúc dữ liệu trên mỗi phần tử có thể chậm đi đáng kể. Hay một số thao tác thông thường có sẵn trong các ngôn ngữ khác đã không được triển khai trong Python do kiểu dữ liệu có thể khác nhau giữa các phần tử. Chẳng hạn việc sắp xếp một danh sách sẽ chậm đi do phải xác định chính xác kiểu dữ liệu của mỗi phần tử khi so sánh. Việc đọc một list từ file text hoặc từ một string sẽ không được triển khai bằng các hàm built-in.

Python hỗ trợ bạn tạo ra các list hiệu quả và chặt chẽ hơn bằng khái niệm "Efficient arrays" có trong thư viện array. Tuy nhiên module này chỉ hỗ trợ kiểu dữ liệu số và ký tự. Bạn không thể dùng các "Efficient arrays" cho các string hay boolean.

Ví dụ:

>>> from array import array
>>> array('I', range(10))
array('I', [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> array.array('u', "hello")
array('u', 'hello')

Ví dụ 1 khai báo một mảng (hay array) các số nguyên unsiged int chứa các giá trị từ 0 đến 9. 'I' gọi là type code - một giá trị quy định kiểu của mỗi item trong mảng. Đoạn mã phía sau đó khai báo một array của các ký tự unicode. Dưới đây là danh sách các type code được hỗ trợ trong Python 3.1:

Như trong tài liệu Python viết. Kích thước thực sự của một số type code như 'i', 'I', 'l', 'L' phụ thuộc vào kiến trúc máy tính triển khai python (thông thường là sự khác biệt giữa kiến trúc 32 bit và 64 bit - xem thêm: Integer - computer science). Kiểu của mỗi phần tử trong mảng chính xác là kiểu của ngôn ngữ C tương ứng trong bảng, vì vậy kích thước của mảng luôn có thể xác định chính xác. Điều này khác với list. Khi nhận được một list rất khó để xác định chính xác kích thước bộ nhớ của nó. Module array có các hàm buffer_info() và itemsize cho phép thực hiện điều này. Hàm buffer_info() cho kết quả một tuple chứa địa chỉ bộ nhớ và số phần tử của mảng. Hàm itemsize cho biết kích thước của mỗi phần tử theo byte. Để tính kích thước bộ nhớ mà python cấp phát cho mảng dùng biểu thức: x.buffer_info()[1] * x.itemsize. Ví dụ:

>>> x = array.array('u', "python")
>>> x.itemsize
2
>>> x.buffer_info()
(29756264, 6)
>>> x.buffer_info()[1]*x.itemsize
12

Các mảng quy định rõ kiểu giá trị nó chứa, vì vậy không thể lưu các giá trị vượt phạm vi cho phép hoặc các giá trị không đúng kiểu. Python báo lỗi khi xảy ra sự kiện này:

>>> array.array("L", [2**32])
Traceback (most recent call last):
  File "<interactive input>", line 1, in <module>
OverflowError: python int too large to convert to C unsigned long

>>> array('I', [])
array('I')
>>> array('I', [None])
Traceback (most recent call last):
  File "<interactive input>", line 1, in <module>
TypeError: an integer is required

Trong python 3.* type code 'c' không còn được sử dụng do từ Python 3.0 trở đi kiểu dữ liệu string luôn luôn là unicode.

>>> array('c', ['a'])
Traceback (most recent call last):
  File "<interactive input>", line 1, in <module>
ValueError: bad typecode (must be b, B, u, h, H, i, I, l, L, f or d)

Type code 'u' cũng sẽ khác nhau về kích thước trên các hệ điều hành khác nhau, khi chúng triển khai UCS2 (2 byte) hoặc UCS4 (4 byte). Để biết máy bạn dùng UCS mấy gõ lệnh sau:

>>> import sys
>>> sys.maxunicode
65535

Đó là UCS2, trên hệ thống mà Python được compile với UCS4 kết quả phải lớn hơn.

Module array có hầu hết các phương thức tương tự list:

>>> dir(array('d', []))
['__add__', '__class__', '__contains__', '__copy__', '__deepcopy__', '__delattr__', '__delitem__',
'__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__gt__', '__hash__',
'__iadd__', '__imul__', '__init__', '__iter__', '__le__', '__len__', '__lt__', '__mul__', '__ne__',
'__new__', '__reduce__', '__reduce_ex__', '__repr__', '__rmul__', '__setattr__', '__setitem__',
'__sizeof__', '__str__', '__subclasshook__', 'append', 'buffer_info', 'byteswap', 'count', 'extend',
'fromfile', 'fromlist', 'fromstring', 'fromunicode', 'index', 'insert', 'itemsize', 'pop', 'remove',
'reverse', 'tofile', 'tolist', 'tostring', 'tounicode', 'typecode']

Trong danh sách trên ta thấy array không có phương thức sort giống như list. Để sắp xếp các array, bạn có thể dùng hàm sorted. Hàm sorted là hàm built-in, khác với list.sort nó tạo ra list mới và không thay đổi list gốc.

>>> from array import array
>>> example = array('d', [math.pi, math.e, math.log(10)])
>>> sorted(example)
[2.302585092994046, 2.718281828459045, 3.141592653589793]
>>> sorted(example, reverse = True)
[3.141592653589793, 2.718281828459045, 2.302585092994046]

2. "Efficient arrays" nhanh hơn list như nào?

Trong phần này chúng ta sẽ thực hiện một số kiểm tra performance giữa array và list trên một số thao tác điển hình. Chỉ một số thao tác được kiểm tra, kết quả thời gian có thể khác nhau với các phiên bản Python, hay các cấu hình máy khác. Tuy nhiên tôi cố gắng đặt các kiểm tra trong cùng một tập các điều kiện thí nghiệm, và chỉ xem xét tương quan giữa các con số nhằm rút ra một kết luận nào đó.

Đầu tiên là sắp xếp - thao tác cơ bản đặc trưng cho một list.

>>> from timeit import Timer
>>> Timer("a.sort()", "import random;a=list(range(10**4)); \
... random.shuffle(a)").timeit(100)
0.05681145858943637
>>> Timer("sorted(a)", "import random;a=list(range(10**4)); \
... random.shuffle(a)").timeit(100)
0.7554756694498792
>>> Timer("sorted(a)", "import random,array;a=array.array('L', range(10**4));\
... random.shuffle(a)").timeit(100)
0.8100354453472391

Ví dụ trên so sánh thời gian thực hiện của list.sort, sorted trên list, và sorted trên array khi sắp xếp mảng số nguyên 32 bit có 10 ngàn item. Chúng ta thấy thậm chí việc sắp xếp trên mảng bằng hàm sorted chậm hơn nhiều so với trên list.sort trong trường hợp này. Test này được thực hiện trên Python 3.1 với máy Pentium Dual Core 1.7MHz. Trên các phiên bản Python 2.x bạn chỉ cần viết a = range(10**4) thay vì a = list(range(10**4)) Tiếp tục khảo sát với số phần tử đến 100 ngàn, 1 triệu, 10 triệu phần tử:

>>> Timer("a.sort()", "import random;a=range(10**5);random.shuffle(a)").timeit(100)
1.0628812891800408
>>> Timer("sorted(a)", "import random;a=range(10**5);random.shuffle(a)").timeit(100)
13.890136599318794
>>> Timer("sorted(a)", "import random,array;a=array.array('L', range(10**5));\
... random.shuffle(a)").timeit(100)
14.082001048258462

>>> Timer("a.sort()", "import random;a=range(10**6);random.shuffle(a)").timeit(1)
1.8611051722955381
>>> Timer("sorted(a)", "import random;a=range(10**6);random.shuffle(a)").timeit(1)
1.9412927927796773
>>> Timer("sorted(a)", "import random,array;a=array.array('L', range(10**6));\
... random.shuffle(a)").timeit(1)
2.2266062190747107

>>> Timer("a.sort()", "import random;a=range(10**7);random.shuffle(a)").timeit(1)
25.894550537010218
>>> Timer("sorted(a)", "import random;a=range(10**7);random.shuffle(a)").timeit(1)
26.986440155994387
>>> Timer("sorted(a)", "import random,array;a=array.array('L', range(10**7));\
... random.shuffle(a)").timeit(1)
30.602503383151088

Hàm sort của list là in-place vì vậy nó nhanh hơn sorted do không phải thực hiện các thao tác cấp phát bộ nhớ để tạo list mới như sorted. Nó nhanh hơn đáng kể khi số phần tử là nhỏ. Trong test trên đây là khoảng 13 lần với 10 ngàn item và 100 ngàn item. Số các thao tác cấp phát bộ nhớ tăng tuyến tính theo số phần tử, trong khi số các phép so sánh tăng theo n*logn (hoặc nếu tốt hơn n*loglogn). Vì vậy khi tăng số lượng các item thì số các phép so sánh tăng nhanh hơn số các thao tác cấp phát bộ nhớ. Ở trên 1 triệu phần tử các phép toán so sánh chiếm đa số thời gian xử lý. Ta có thể thấy thời gian thực thi ở các hàm là tương đương nhau. Trên mức 10 triệu phần tử sự khác biệt không còn đáng kể nữa.

Hàm sorted thực thi trên array thường sẽ chậm hơn trên list trong sai khác thời gian tương đối nhỏ. Nguyên nhân có thể được giải thích là do sorted không tạo ra một array mà luôn luôn tạo ra một list. Rõ ràng sorted trên một array nhưng trả lại list sẽ chậm hơn khi sorted trên list trả lại list. Các Efficient arrays muốn nhanh hơn list thực sự cần một sort của riêng chúng.

Chuyển qua các thao tác khác với list. Chẳng hạn với hàm sum một list các số nguyên

>>> Timer("sum(x)", "x=range(1000)").timeit(10000)
0.60629310370359235
>>> Timer("sum(x)", "import array; x = array.array('d', range(1000))").timeit(10000)
0.74805731663627739

>>> Timer("sum(x)", "x=range(10000)").timeit(1000)
0.60768722812650822
>>> Timer("sum(x)", "import array; x = array.array('d', range(10000))").timeit(1000)
0.75720026176844613

>>> Timer("sum(x)", "x=range(10**5)").timeit(100)
1.1360591999478515
>>> Timer("sum(x)", "import array; x = array.array('d', range(10**5))").timeit(100)
0.73434230670147826

>>> Timer("sum(x)", "x=range(10**6)").timeit(10)
1.9724225132735
>>> Timer("sum(x)", "import array; x = array.array('d', range(10**6))").timeit(10)
0.73678350503251977

>>> Timer("sum(x)", "x=range(10**7)").timeit(10)
20.701364808722474
>>> Timer("sum(x)", "import array; x = array.array('d', range(10**7))").timeit(10)
7.399070781130149

Hàm sum với array chậm hơn khi số phần tử nhỏ và càng ngày càng nhanh hơn khi số phần tử lớn hơn. Test sau đây cũng chỉ ra join các string là nhanh hơn hàm tounicode của array.

>>> array('u', map(chr, range(65, 90))).tounicode()
'ABCDEFGHIJKLMNOPQRSTUVWXY'
>>> "".join(map(chr, range(65, 90)))
'ABCDEFGHIJKLMNOPQRSTUVWXY'
>>> Timer("array.array('u', map(chr, range(65, 90))).tounicode()", "import array").timeit()
14.721977927611988
>>> Timer("''.join(map(chr, range(65, 90)))", "").timeit()
8.788942485645748

Để loại bỏ các phần tử trùng nhau của một list từ python 2.4 trở đi bạn có thể dùng lệnh L = list(set(L)). Ví dụ:

>>> list(set([5,5,1,2,3,2,3]))
[1, 2, 3, 5]
>>> array('L', set([1,2,3,1,2,3]))
array('L', [1, 2, 3])

Ví dụ sau so sánh thời gian loại trùng của array và list sử dụng cú pháp này:

>>> Timer("array('L', set(x))", "from array import array; \
...  x = array('L', range(10**5))").timeit(10)
0.3053085107321749
>>> Timer("list(set(x))", "x = range(10**5)").timeit(10)
0.25598173543039593

>>> Timer("array('L', set(x))", "from array import array; \
... x = array('L', range(10**6))").timeit(10)
3.901955860623275
>>> Timer("list(set(x))", "x = range(10**6)").timeit(10)
2.275834090902208

>>> Timer("array('L', set(x))", "from array import array; \
... x = array('L', range(10**7))").timeit(1)
3.823739795026995
>>> Timer("list(set(x))", "x = range(10**7)").timeit(1)
2.216846163641094

Như vậy sử dụng array sẽ không hiệu quả bằng list trong tình huống này.

Việc đảo ngược một list cũng luôn luôn nhanh hơn đảo ngược một array. Ví dụ:

>>> Timer("x.reverse()", "x = range(10**7)").timeit(10)
0.30343171366575916
>>> Timer("x.reverse()", "import array; x = array.array('L', range(10**7))").timeit(10)
4.0138636612646224

Trên python 3.* bạn phải viết x = list(range(10**7)) do hàm range trong python 3.* trả về iterator chứ không phải list.

Với phép toán nhân list lại chậm hơn array. Ví dụ:

>>> Timer("100000*x", "from array import array; \
... x=array('u', u'hello world')").timeit(10)
0.077855393644313153
>>> Timer("100000*x", "x=list(u'hello world')").timeit(10)
0.20222266310884152

Dùng array sẽ kỳ hiệu quả hơn trong phép cộng:

>>> Timer("x + y", "from array import array;\
... x=array('L', range(10*7));y=x[:]").timeit(100)
0.00019484576660033781
>>> Timer("x + y", "x=range(10*7);y=x[:]").timeit(100)
0.0005318282637745142
>>> Timer("x + y", "from array import array;\
... x=array('L', range(1000));y=x[:]").timeit()
2.354171564954413
>>> Timer("x + y", "x=range(1000);y=x[:]").timeit()
20.363064586337714

Như vậy là không phải lúc nào array cũng nhanh hơn list. Ít nhất là trong thao tác đảo ngược mảng và sắp xếp. Trong hầu hết các tính toán với danh sách kích thước nhỏ, dùng list sẽ tiện và nhanh hơn.