Các thủ thuật Python cho Competitive Coding (Lập trình thi đấu)

Python là một trong những ngôn ngữ ưa chuộng cho các thử thách lập trình thi đấu. Đa số bài toán dễ dàng giải quyết trong thời gian hợp lý bằng Python.

Đối với bài toán phức tạp, viết code Python đủ nhanh thường là thách thức. Dưới đây là các cấu trúc code Pythonic giúp cải thiện hiệu suất trong competitive coding:

1. Nối chuỗi (String concatenation)

Không nên dùng:

str1 = ""
some_list = ["Welcome ", "To ", "Tutorialspoint "]
for x in some_list:
    str1 += x
print(str1)

Cách này gây overhead thời gian lớn. Nên dùng join():

str1 = ""
some_list = ["Welcome ", "To ", "Tutorialspoint "]
print(str1.join(some_list))

2. Hàm Map

Thường có input dạng: 1234567

Để lấy list số:

list(map(int, input().split()))

Luôn dùng input() bất kể loại input, sau đó chuyển đổi bằng map.

>>> list(map(int, input("enter numbers:").split()))
enter numbers:1 2 3 4 5 6 7
[1, 2, 3, 4, 5, 6, 7]

map là hàm built-in đẹp, rất tiện lợi. Nên nhớ.

3. Module Collections

Muốn loại bỏ duplicate từ list. Trong Java cần HashMap, nhưng Python chỉ cần:

>>> print(list(set([1,2,3,4,3,4,5,6])))
[1, 2, 3, 4, 5, 6]

Cẩn thận với extend() và append() khi gộp list:

>>> a = [1, 2, 3, 4]
>>> b = [5, 6, 7]
>>> a.extend(b)  # gộp thành một list
>>> a
[1, 2, 3, 4, 5, 6, 7]
>>> a.append(b)  # tạo list của list
>>> a
[1, 2, 3, 4, [5, 6, 7]]

4. Cấu trúc ngôn ngữ (Language constructs)

Nên viết code trong hàm, dù Python hỗ trợ code thủ tục.

def main():
    for i in range(2**3):
        print(x)
main()

Tốt hơn:

for x in range(2**3):
    print(x)

Lưu trữ biến local nhanh hơn biến global do triển khai CPython.

5. Sử dụng thư viện chuẩn (Standard library)

Nên dùng built-in functions và standard library package nhiều nhất có thể. Thay vì:

newlist = []
for x in somelist:
    newlist.append(myfunc(x))

Dùng:

newlist = map(myfunc, somelist)

Cũng hãy dùng itertools (thư viện chuẩn), nhanh hơn cho các tác vụ phổ biến. Ví dụ: permutation cho vòng lặp chỉ vài dòng code.

>>> import itertools
>>> iter = itertools.permutations(["a","b","c"])
>>> list(iter)
[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

6. Generators

Generators là cấu trúc tuyệt vời để giảm cả memory footprint và độ phức tạp thời gian trung bình.

def fib():
    a, b = 0, 1
    while 1:
        yield a
        a, b = b, a+b