Nghiên cứu về các tính năng nâng cao Python (I)
Iterators, Generators và itertools
Hiểu được trình lặp là một điều quan trọng đối với bất kỳ ai muốn hiểu về python một cách sâu sắc hơn. Trong bài này chúng ta sẽ cùng tìm hiểu cách tạo ra các vòng lặp và nguyên lý hoạt động của nó.
Bắt đầu với một ví dụ rất cơ bản về vòng lặp for in mà chúng ta thường dùng trong Python.
listA = ["a","b","c","d"]
for item in listA:
print(item)
a
b
c
d
Rất đơn giản để sử dụng vòng lặp for in vì cú pháp của nó hoàn toàn dễ hiểu. Nhưng vòng lặp for này được tạo ra như thế nào hay đại loại là làm sao tạo ra nó, cái gì tạo ra nó? Ngay bây giờ, tôi có thể trả lời cho bạn, nó được tạo ra từ trình lặp (Iterator). Vậy trình lặp là gì, nó như thế nào? Được rồi, hãy khám phá nó với tôi ở trong bài viết này.
Iterators
Iterator là các đối tượng cho phép ta lấy từng phần tử của nó, hành động này có thể được lặp đi lặp lại.
Bản thân các đối tượng trình lặp được yêu cầu hỗ trợ từ hai phương thức iter() và next(), cùng nhau tạo thành giao thức trình vòng lặp.
__iter__()
Phương thức này trả về chính đối tượng vòng lặp. Điều này là bắt buộc để cho phép cả vùng chứa và trình vòng lặp được sử dụng với câu lệnh for and in.
listA = ["a","b","c","d"]
obj = iter(listA)
obj
<list_iterator at 0x7fa589ced510>
next()
Phương thức này trả về giá trị của đối tượng tiếp theo từ 1 container. Nếu không còn đối tượng nào phía sau nữa,một ngoại lệ sẽ được raise –> StopIteration ngoại lệ.
listA = ["a","b","c","d"]
obj = iter(listA)
print(next(obj)," - lần 1.")
print(next(obj)," - lần 2.")
print(next(obj)," - lần 3.")
print(next(obj)," - lần 4.")
a - lần 1.
b - lần 2.
c - lần 3.
d - lần 4.
Chúng ta thấy rằng, đoạn code trên đóng vai trò như một vòng lặp for thủ công.Để có được từng phần tử trong listA, chúng ta phải liên tục gọi list n lần, với n bằng với số phần tử listA.
Vậy điều gì sẽ xảy ra nếu tôi gọi nó lần thứ 5 khi listA chỉ có 4 phần tử?
print(next(obj)," - lần 5.")
---------------------------------------------------------------------------
StopIteration Traceback (most recent call last)
<ipython-input-73-7a1878073902> in <module>
----> 1 print(next(obj)," - lần 5.")
StopIteration:
Thử đặt vào khối try except …
listA = ["a","b","c","d"]
obj = iter(listA)
count = 1
while True:
try:
print(next(obj)," - lần {}.".format(count))
count += 1
except StopIteration:
print("Không còn đối tượng nào khác tiếp theo ...")
break
a - lần 1.
b - lần 2.
c - lần 3.
d - lần 4.
Không còn đối tượng nào khác tiếp theo ...
Có vẻ mọi thứ đã đẹp hơn với việc sử dụng while và kết thúc nó khi ngoại lệ được raise.Hãy thử sử dụng nó và tạo ra một func for.
def my_for(A : list ):
obj = iter(A)
while True:
try:
print(next(obj))
except StopIteration:
break
my_for(["a","b","c","d"])
a
b
c
d
Thử my_for với một chuỗi string.
my_for("hello")
h
e
l
l
o
Xây dựng Iterator Python
Chúng ta có thể tự xây dựng iterator là một class. Xây dựng Iterator rất dễ dàng trong Python, chúng ta chỉ cần thực hiện các phương thức iter() và next().
class CountIterator(object):
n = 0
def __iter__(self):
return self
def __next__(self):
y = self.n
self.n += 1
return y
counter = CountIterator()
print(next(counter))
print(next(counter))
print(next(counter))
print(next(counter))
print(next(counter))
print(next(counter))
print(next(counter))
print(next(counter))
0
1
2
3
4
5
6
7
Ví dụ trên là một trình lặp vô hạn vừa được khởi tạo …Điều gì sẽ xảy ra nếu chúng ta muốn in tất cả nó ra ? Tất nhien sẽ có kết quả nào được trả về vì nó vẫn đang chạy và không bao giờ dừng lại 🍌
list(counter)
---------------------------------------------------------------------------
KeyboardInterrupt Traceback (most recent call last)
/usr/local/lib/python3.7/dist-packages/IPython/core/interactiveshell.py in run_code(self, code_obj, result, async_)
3325 else:
-> 3326 exec(code_obj, self.user_global_ns, self.user_ns)
3327 finally:
<ipython-input-82-37a36df53a6b> in <module>
----> 1 list(counter)
<ipython-input-79-1d69e15f308c> in __next__(self)
6
----> 7 def __next__(self):
8 y = self.n
KeyboardInterrupt:
During handling of the above exception, another exception occurred:
KeyboardInterrupt Traceback (most recent call last)
KeyboardInterrupt:
Cuối cùng, để chính xác, chúng ta nên thực hiện một sửa đổi ở trên: các đối tượng không có phương thức iter được định nghĩa vẫn có thể lặp lại được nếu chúng định nghĩa getitem. Trong trường hợp này khi hàm tích hợp sẵn của Python, iter sẽ trả về một trình lặp của trình lặp kiểu cho đối tượng, trình này sử dụng getitem để xem qua các mục trong danh sách. Nếu StopIteration hoặc IndexError được đưa ra bởi getitem thì quá trình lặp sẽ dừng lại. Hãy xem một ví dụ về điều này:
class GetIterator(object):
def __init__(self, items:list):
self.items = items
def __getitem__(self, i):
return self.items[i]
counter = GetIterator([1,2,3,4])
get_item = iter(counter)
try:
print(next(get_item))
print(next(get_item))
print(next(get_item))
print(next(get_item))
except IndexError:
raise StopIteration()
1
2
3
4
Hãy xem xét một ví dụ thú vị hơn: thử tạo chuỗi Hofstadter Q cho các điều kiện ban đầu bằng cách sử dụng một trình lặp.
Sử dụng đệ quy tìm tập hợp số Hofstadter Q
def hofstadter(n :int):
if n == 1 or n == 2:
return 1
return hofstadter(n - hofstadter(n-1)) + hofstadter(n -hofstadter(n-2))
for i in range(1,10):
print(hofstadter(i),end = " ")
1 1 2 3 3 4 5 5 6
Chúng ta thấy rằng, với 1 func đệ quy đơn giản đã thu được 1 danh sách chữ số thuộc chuỗi hofstadter Q. Nhưng nếu tăng range lên 1 giá trị cao hơn thì thời gian thực thi sẽ rất lớn vì số lần lặp lại tính toán sẽ tăng lên rất nhiều.
for i in range(1,50):
print(hofstadter(i),end = " ")
Bây giờ, chúng ta cần 1 “bộ nhớ” để ghi lại kết quả tính toán trước đó, để có thể bỏ qua chúng trong những lần chạy tiếp theo,xem ví dụ bên dưới :
cache = {1:1,2:1}
def hofstadter(n :int):
if n in cache:
return cache[n]
cache[n] = hofstadter(n - hofstadter(n-1)) + hofstadter(n -hofstadter(n-2))
return cache[n]
for i in range(1,50):
print(hofstadter(i),end = " ")
1 1 2 3 3 4 5 5 6 6 6 8 8 8 10 9 10 11 11 12 12 12 12 16 14 14 16 16 16 16 20 17 17 20 21 19 20 22 21 22 23 23 24 24 24 24 24 32 24
Bây giờ chúng ta cùng xem xét thời gian thực thi cho cả 2 đoạn code, 1 sử dụng cache và 1 không =. Rất rõ ràng về sự chêch lệnh khá lớn.
Trong thư viện functools của Python đã có tích hợp “bộ nhớ “ này dưới trình trang trí lru_cache.Đoạn code bên dưới sẽ cho thấy cách sử dụng trình trang trí lru_cache có sẵn như thế nào .
from functools import lru_cache
@lru_cache()
def hofstadter(n :int):
if n ==1 or n ==2 :
return 1
return hofstadter(n - hofstadter(n-1)) + hofstadter(n -hofstadter(n-2))
for i in range(1,50):
print(hofstadter(i),end = " ")
1 1 2 3 3 4 5 5 6 6 6 8 8 8 10 9 10 11 11 12 12 12 12 16 14 14 16 16 16 16 20 17 17 20 21 19 20 22 21 22 23 23 24 24 24 24 24 32 24
Lúc này, chúng ta hãy xem xét vấn đề thực sự ở đây, sử dụng trình lặp để giải quyết bài toán để hiểu ra hơn về nó
Sử dụng trình lặp là một trong những phương pháp “hơi cồng kềnh” so với đệ quy. 🦆
class Qsequence(object):
def __init__(self, range_n):
self.range_n = range_n
def __next__(self):
try:
q = self.range_n[-self.range_n[-1]] + self.range_n[-self.range_n[-2]]
self.range_n.append(q)
return q
except IndexError:
raise StopIteration()
def __iter__(self):
return self
Q = Qsequence([1, 1])
print([next(Q) for __ in range(10)])
[2, 3, 3, 4, 5, 5, 6, 6, 6, 8]
Ví dụ: qsequence ([1, 1]) sẽ tạo ra chính xác trình tự Hofstadter. Sử dụng ngoại lệ StopIteration để chỉ ra trình tự không thể đi xa hơn vì chỉ mục không hợp lệ được yêu cầu để tạo phần tử tiếp theo.
Generators
Generators của Python cung cấp một cách thuận tiện để triển khai giao thức Iterators. Nếu phương thức của đối tượng vùng chứa iter() được triển khai dưới dạng trình tạo, nó sẽ tự động trả về đối tượng trình vòng lặp (về mặt kỹ thuật, đối tượng trình tạo) cung cấp các phương thức iter()và next(). Nói một cách đơn giản, generator là một hàm trả về một đối tượng (iterator) mà chúng ta có thể lặp lại (một giá trị tại một thời điểm).
def generator_1():
n = 1
while n < 10:
yield n
# return n
print("//////////////////")
n += 1
print(list(generator_1()))
//////////////////
//////////////////
//////////////////
//////////////////
//////////////////
//////////////////
//////////////////
//////////////////
//////////////////
[1, 2, 3, 4, 5, 6, 7, 8, 9]
ite = generator_1()
print(next(ite))
print(next(ite))
print(next(ite))
print(next(ite))
print(next(ite))
print(next(ite))
print(next(ite))
print(next(ite))
print(next(ite))
print(next(ite))
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-50-4b516d721842> in <module>
1 ite = generator_1()
----> 2 print(next(ite))
3 print(next(ite))
4 print(next(ite))
5 print(next(ite))
TypeError: 'int' object is not an iterator
ite = generator_1()
for i in ite:
print(i)
1
//////////////////
2
//////////////////
3
//////////////////
4
//////////////////
5
//////////////////
6
//////////////////
7
//////////////////
8
//////////////////
9
//////////////////
Tìm các số chia hết cho 3 và nhở hơn 100
def func_1(n:int ):
list_number = []
for i in range(n):
if i % 3 == 0:
list_number.append(i)
return list_number
list(func_1(100))
def generator_2(n:int):
for i in range(n):
if i % 3 ==0:
yield i
g = generator_2(100)
list(g)
Trình tạo là trình lặp được định nghĩa bằng cách sử dụng ký hiệu hàm đơn giản hơn. Cụ thể hơn, bộ tạo là một hàm sử dụng biểu thức năng suất ở đâu đó trong đó. Trình tạo không thể trả về giá trị và thay vào đó mang lại kết quả khi chúng sẵn sàng. Python tự động hóa quá trình ghi nhớ ngữ cảnh của trình tạo, nghĩa là luồng điều khiển hiện tại của nó ở đâu, giá trị của các biến cục bộ của nó là gì, v.v. Mỗi khi trình tạo được gọi bằng cách sử dụng next , nó sẽ mang lại giá trị tiếp theo trong lần lặp. Phương thức iter cũng sẽ được thực hiện tự động, có nghĩa là trình tạo có thể được sử dụng ở bất kỳ nơi nào cần trình lặp. Hãy xem một ví dụ. Việc triển khai này về mặt chức năng tương đương với lớp trình lặp của chúng ta ở trên, nhưng nhỏ gọn và dễ đọc hơn nhiều.
Hãy xem ví dụ dưới đây. Tập hợp số chia hết cho 3 nhỏ hơn tham số n đầu vào.
def test1(n:int):
listA = []
for i in range(n):
if i % 3 == 0:
listA.append(i)
return listA
test1(10)
[0, 3, 6, 9]
def test2(n:int):
for i in range(n):
if i % 3 ==0:
yield i
t = test2(10)
print(type(t))
print(next(t))
print(next(t))
<class 'generator'>
0
3
Ví dụ 2: Tạo một chuỗi vô hạn
Trong Python, để có được một chuỗi hữu hạn qua func range()và bao bọc nó bới list:
string_limit = range(10)
list(string_limit)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Tuy nhiên, nếu bây giờ chúng ta muốn tạo 1 list vô hạn sẽ như thế nào? Ý tưởng đầu tiên là hãy cho 1 con số n thật lớn và đặt nó vào range(), và bây giờ chúng ta có range(n). Nhưng nó không thể nào vô hạn vì chẳng có số n nào cuối cùng cả… 😖. Và trình tạo sẽ giúp ta làm được điều đấy. Xem đoạn code bên dưới để thấy rõ một trình lập vô hạn được tạo như thế nào với trình tạo.
def count_generator():
n = 0
while True:
yield n
n += 1
print(type(count_generator()))
counter = count_generator()
<class 'generator'>
for i in counter:
print(i)
Chũng ta thu được 1 tập hợp số vô hạn…
Các hàm của bộ tạo trông và hoạt động giống như các hàm thông thường, nhưng có một đặc điểm xác định. Các hàm của trình tạo sử dụng yield từ khóa Python thay vì return.
Các phương thức của một trình lặp trình tạo.
generator.next( )
Bắt đầu thực thi một hàm trình tạo hoặc tiếp tục nó ở yield biểu thức được thực thi cuối cùng. Khi một hàm trình tạo được tiếp tục với một next() phương thức, yield biểu thức hiện tại luôn đánh giá là None. Việc thực thi sau đó tiếp tục đến yield biểu thức tiếp theo, nơi trình tạo lại bị đình chỉ và giá trị của giá trị expression_list được trả lại cho next() trình gọi của. Nếu trình tạo thoát ra mà không mang lại giá trị khác, thì một StopIterationngoại lệ sẽ được đưa ra.
def generator_1(n:int):
for i in range(n):
if i % 3 ==0:
yield i
g = generator_1(7)
print(next(g))
print(next(g))
type(g)
0
3
generator
generator.send(value)
để gửi dữ liệu đến generator
Tiếp tục thực thi và “gửi” một giá trị vào hàm trình tạo. Đối value số trở thành kết quả của yield biểu thức hiện tại. Phương send()thức trả về giá trị tiếp theo được tạo bởi trình tạo hoặc tăng lên StopIteration nếu trình tạo thoát ra mà không mang lại giá trị khác. Khi nào send() được gọi để khởi động trình tạo, nó phải được gọi với None làm đối số, vì không có yield biểu thức nào có thể nhận giá trị.
def generator():
total = 0
value = None
while True:
value = yield total
if value is None: break
total += value
g = generator()
next(g) # 0
g.send(6) # 6
# next(g)
g.send(8) # 14
g.send(100) # 114
114
Mọi thứ diễn ra trong đoạn code trên như sau:
- Khi bạn gọi lần đầu tiên next(g), chương trình sẽ chuyển đến yield câu lệnh đầu tiên và trả về giá trị total tại thời điểm đó, là 0. Việc thực thi trình tạo tạm dừng tại thời điểm này.
- Tiếp theo, khi bạn gọi g.send(x), trình thông dịch nhận đối số x và biến nó thành giá trị trả về của yield câu lệnh cuối cùng, được gán cho value. Sau đó, trình tạo vẫn tiếp tục như bình thường, cho đến khi nó mang lại giá trị tiếp theo.
- Cuối cùng khi bạn gọi next(g), chương trình sẽ xử lý điều này như thể bạn đang gửi None tới trình tạo.
generator.throw(type[, value[, traceback]])
raise ngoại lệ generator
Tăng một loại ngoại lệ typetại điểm mà trình tạo bị tạm dừng và trả về giá trị tiếp theo được tạo bởi hàm trình tạo. Nếu trình tạo thoát ra mà không mang lại giá trị khác, thì một StopIterationngoại lệ sẽ được đưa ra. Nếu hàm trình tạo không bắt được ngoại lệ được truyền vào hoặc tạo ra một ngoại lệ khác, thì ngoại lệ đó sẽ truyền đến người gọi.
def generator_1(n:int):
for i in range(n):
if i % 3 ==0:
yield i
g = generator_1(7)
for i in range(20):
print(next(g))
if i == 1:
g.throw(ValueError("hết phần tử đề next rồi bạn ê..."))
0
3
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
<ipython-input-24-44172e2db9d2> in <module>
8 print(next(g))
9 if i == 1:
---> 10 g.throw(ValueError("hết phần tử đề next rồi bạn ê..."))
<ipython-input-24-44172e2db9d2> in generator_1(n)
2 for i in range(n):
3 if i % 3 ==0:
----> 4 yield i
5
6 g = generator_1(7)
ValueError: hết phần tử đề next rồi bạn ê...
generator.close()
Dừng sự lặp lại của generator
Tăng a GeneratorExittại điểm mà chức năng máy phát điện bị tạm dừng. Nếu sau đó hàm trình tạo tăng StopIteration(bằng cách thoát bình thường, hoặc do đã bị đóng) hoặc GeneratorExit(bằng cách không bắt ngoại lệ), thì hàm đóng trả về trình gọi của nó. Nếu bộ tạo mang lại một giá trị, a RuntimeErrorsẽ được nâng lên. Nếu trình tạo ra bất kỳ ngoại lệ nào khác, nó sẽ được truyền tới người gọi. close()không làm gì nếu trình tạo đã thoát do một ngoại lệ hoặc lối ra bình thường.
def generator_1(n:int):
for i in range(n):
if i % 3 ==0:
yield i
g = generator_1(7)
for i in range(20):
# print(next(g))
if i == 1:
g.close()
print(next(g))
0
---------------------------------------------------------------------------
StopIteration Traceback (most recent call last)
<ipython-input-28-0b28f1736bd2> in <module>
9 if i == 1:
10 g.close()
---> 11 print(next(g))
StopIteration:
Bây giờ, hãy thực hiện trình tự Q của Hofstadter bằng cách sử dụng một trình tạo.
def hofstadter_generator(s):
a = s[:]
while True:
try:
q = a[-a[-1]] + a[-a[-2]]
a.append(q)
yield q
except IndexError:
return
hofstadter = hofstadter_generator([1,1])
[next(hofstadter) for _ in range(10)]
[2, 3, 3, 4, 5, 5, 6, 6, 6, 8]
def echo(value=None):
print("Execution starts when 'next()' is called for the first time.")
try:
while True:
try:
value = (yield value)
value += 1
except Exception as e:
value = e
finally:
print("Don't forget to clean up when 'close()' is called.")
generator = echo(1)
print(next(generator))
print(next(generator))
# print(send(generator(2)))
generator.throw(TypeError, "spam")
generator.close()
Execution starts when 'next()' is called for the first time.
1
unsupported operand type(s) for +=: 'NoneType' and 'int'
Don't forget to clean up when 'close()' is called.
itertools
itertools là một module thực hiện một số khối lệnh xây dựng trình vòng lặp lấy cảm hứng từ các cấu trúc từ APL, Haskell và SML… Cùng với nhau, chúng tạo thành một ‘đại số trình lặp’ để có thể tạo các công cụ chuyên dụng một cách ngắn gọn và hiệu quả bằng Python thuần túy. Bạn có thể đọc tất cả các chức năng ở link này . Trong bài viết này chúng ta sẽ có một cách tiếp cận khác. Thay vì giới thiệu itertools cho bạn từng chức năng một theo trình tự thì tôi sẽ cùng các bạn xây dựng các ví dụ thực tế được lựa chon phù để vận dụng các chức năng, từ đó hiểu rõ về nó. Nhìn chung, các ví dụ sẽ bắt đầu đơn giản và tăng dần độ phức tạp.
Để hiểu và dễ dàng tạo một “mục lục”cho quá trình tìm hiểu, chúng ta sẽ cùng đặt ra và trả lời một vài câu hỏi thông thường.
- Tại sao phải dùng itertools, nó có gì hơn việc lập trình logic python thông thường?
Để trả lời câu hỏi này 1 cách thuyết phục, tôi nghĩ chúng ta cần đi qua một vài ví dụ để thấy rõ và đảm bảo sự thuyết phục từ các bạn! Được rồi… đi thôi :))
Vấn đề 1: Tôi có 2 list , listA = [1,2,3,4] và listB = ["a","b","c","d"] .Bây giờ tôi muốn có sự kết hợp giữa các phần listA và listB theo vị trí tương ứng. Cụ thể 1-a,2-b,3-c,4-d.listA = [1,2,3,4]
listB = ["a","b","c","d"]
for i in range(len(listA)):
print(listA[i],listB[i])
1 a
2 b
3 c
4 d
listA = [1,2,3,4]
listB = ["a","b","c","d","e","f"]
for i in range(len(listA)):
print(listA[i],listB[i])
# 1 a
# 2 b
# 3 c
# 4 d
# mong muốn:
# 1 a
# 2 b
# 3 c
# 4 d
# None e
# None f
1 a
2 b
3 c
4 d
listA = [1,2,3,4,5,6]
listB = ["a","b","c","d"]
# for i in range(len(listA)):
# print(listA[i],listB[i])
for i,j in zip(listA,listB):
print(i,j)
1 a
2 b
3 c
4 d
for i in listA:
for j in listB:
print(i, j )
1 a
1 b
1 c
1 d
2 a
2 b
2 c
2 d
3 a
3 b
3 c
3 d
4 a
4 b
4 c
4 d
Bất đầu với ý tưởng sử dụng for range() trích xuất value từ index.
listA = [1,2,3,4]
listB = ["a","b","c","d"]
for i in range(len(listA)):
result = (listA[i],listB[i])
print(result)
(1, 'a')
(2, 'b')
(3, 'c')
(4, 'd')
Bây giờ hãy thử với 2 list có số phần tử khác nhau
listA = [1,2,3,4,5,6]
listB = ["a","b","c","d"]
for i in range(len(listA)):
result = (listA[i],listB[i])
print(result)
(1, 'a')
(2, 'b')
(3, 'c')
(4, 'd')
---------------------------------------------------------------------------
IndexError Traceback (most recent call last)
<ipython-input-14-269ab82e634d> in <module>
3
4 for i in range(len(listA)):
----> 5 result = (listA[i],listB[i])
6 print(result)
IndexError: list index out of range
listA = [1,2,3,4]
listB = ["a","b","c","d","e","f"]
for i in range(len(listA)):
result = (listA[i],listB[i])
print(result)
(1, 'a')
(2, 'b')
(3, 'c')
(4, 'd')
Kết quả nhận được từ sự khác nhau về số lượng phần tử của 2 list sẽ rới vào 2 trường hợp:
- Lỗi Nếu len(listA) > len(listB) ==> listB[i] sẽ không nhận được giá trị từ đó sinh ra lỗi
- Thiếu dữ liệu Nếu len(listA) < len(listB) ==> listB[i] sẽ không nhận đủ giá trị vì for range(len(listA))
Bây giờ hãy thử giải quyết vấn đề này với func zip()
listA = [1,2,3,4]
listB = ["a","b","c","d"]
list(zip(listA,listB))
[(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]
Trường hợp 2 list có số phần tử khác nhau
listA = [1,2,3,4,5,6]
listB = ["a","b","c","d"]
list(zip(listA,listB))
[(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]
listA = [1,2,3,4]
listB = ["a","b","c","d","e","f"]
list(zip(listA,listB))
[(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]
Rất rõ ràng với func zip(), chúng ta sẽ không còn gặp lỗi khi số lượng phần tử của 2 list là khác nhau. Tuy nhiên việc thiếu dữ liệu vẫn xảy ra,nguyên nhân của việc này là do zip()ngừng tổng hợp các phần tử sau khi lặp range() của len(list) ngắn nhất được chuyển cho nó đã hết.Nhưng đừng lo việc đó, ngay bây giờ tôi sẽ chỉ cho bạn cách khắc phục nó …Chúng ta sẽ sử dụng zip_longest từ itertools thay vì zip. Hãy xem ví dụ bên dưới
from itertools import zip_longest
listA = [1,2,3,4]
listB = ["a","b","c","d","e","f"]
list(zip_longest(listA,listB))
[(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd'), (None, 'e'), (None, 'f')]
Như vậy chúng ta đã giải quyết vấn đề trên một cách thuyết phục nhất với zip_longest từ itertools.
Vấn đề 2: Tôi có 1 list và bây giờ tôi muốn phân list a thành m nhóm với mỗi nhóm sẽ tồn tại n phần tử cho trước. Ví dụ: listA = [1,2,3,4,5,6] , n = 3 kết quả sẽ là [(1,2,3),(4,5,6)]Hãy bắt đầu với code python đơn giản nhất.
listA = [1,2,3,4,5,6,7]
n = int(input("nhap n : ")) # 2
for i in range(len(listA) // n):
print(tuple(listA[i*n:(i+1)*n])) # listA[1 : 2]
# lần 1: i = 0
# n = 2
# listA[i*n:(i+1)*n] ----> listA(0:2) ---> [1,2]
# lần 2: i = 1
# n = 2
# listA[i*n:(i+1)*n] ----> listA(2:4) ---> [3,4]
# lần 3: i = 2
# n = 2
# listA[i*n:(i+1)*n] ----> listA(4:6) ---> [5,6]
# [(listA[i*n:(i+1)*n]) for i in range(len(listA) // n)]
nhap n : 2
(1, 2)
(3, 4)
(5, 6)
Bây giờ hãy thử nó với trình lặp.
list_1 = [1,2,3]
list_2= ["a","b","c"]
list(zip(list_1,list_2))
[(1, 'a'), (2, 'b'), (3, 'c')]
b = [1, 2, 3, 4, 5, 6]
n = 2 #và m = 3:
b = iter(b)
print(b)
print(next(b))
print(b)
print(next(b))
list(zip(b,b))
<list_iterator object at 0x7fc81a788fd0>
1
<list_iterator object at 0x7fc81a788fd0>
2
[(3, 4), (5, 6)]
Chưa thực sự ổn mặc dù kết quả cho ra là như mong đợi.
n = [[2,3]] * 2
n
[[2, 3], [2, 3]]
list(zip(*n))
[(2, 2), (3, 3)]
b = [1,2,3,4,5,6]
n = 2
# iters = [iter(b)] * n # [iter(b),iter(b)]
# for i in iters:
# print(i)
# print(iter(b))
# m = iter(b)
# print(m)
# list(zip(*iters))
x,y= iter(b),iter(b)
for i,j in zip(x,y):
print(i,j)
# list(zip(x,x))
1 1
2 2
3 3
4 4
5 5
6 6
b = [1,2,3,4,5,6]
n = 2
x= iter(b)
for i,j in zip(x,x):
print(i,j)
1 2
3 4
5 6
listA = [1,2,3,4,5,6,7]
n = 2
iters = [iter(listA)] * n # b = iter(b) ---> *iters = b,b
# for i in iters:
# print(next(i))
# print(next(i))
list(zip(*iters))
[(1, 2), (3, 4), (5, 6)]
from itertools import zip_longest
listA = [1,2,3,4,5,6,7]
n = 2
iters = [iter(listA)] * n
list(zip_longest(*iters))
[(1, 2), (3, 4), (5, 6), (7, None)]
itertools.combinations
Vấn đề 3: Bạn có ba tờ 20 đô la, năm tờ 10 đô la, hai tờ 5 đô la và năm tờ 1 đô la. Bạn có thể thực hiện bao nhiêu cách đổi cho tờ 100 đô la?bills = [20, 20, 20, 10, 10, 10, 10, 10, 5, 5, 1, 1, 1, 1, 1]
list_str = ["a","b","c"]
from itertools import combinations
list(combinations(bills, 3))
list(combinations(list_str, 2))
[('a', 'b'), ('a', 'c'), ('b', 'c')]
from itertools import combinations
makes_100 = []
for n in range(1, len(bills) + 1):
for combination in combinations(bills, n):
if sum(combination) == 100:
makes_100.append(combination)
set(makes_100)
{(20, 20, 10, 10, 10, 10, 10, 5, 1, 1, 1, 1, 1),
(20, 20, 10, 10, 10, 10, 10, 5, 5),
(20, 20, 20, 10, 10, 10, 5, 1, 1, 1, 1, 1),
(20, 20, 20, 10, 10, 10, 5, 5),
(20, 20, 20, 10, 10, 10, 10)}
Có bao nhiêu cách để thực hiện thay đổi cho tờ 100 đô la bằng cách sử dụng bất kỳ số nào trong số các tờ 50 đô la, 20 đô la, 10 đô la, 5 đô la và 1 đô la?
Vấn đề 4: Cho trước A = ['0', '1', '2'] và n = 2 , mong đợi kết quả đầu ra là: 00 01 02 10 11 12 20 21 22A = ['0', '1', '2']
list_z = []
for i in A:
for j in A:
list_z.append(i + j)
list_z
['00', '01', '02', '10', '11', '12', '20', '21', '22']
Thử generator
def generator_x(A):
for i in A:
for j in A:
yield i+j
list(generator_x(A))
['00', '01', '02', '10', '11', '12', '20', '21', '22']
list comprehensions
[i+j for i in A for j in A]
['00', '01', '02', '10', '11', '12', '20', '21', '22']
Bây giờ thử thay đổi giá trị n = 3
[i+j+t for i in A for j in A for t in A]
A = ['0', '1', '2']
def generator_x(A,n):
if n == 0:
return ""
while n > 0:
for i in range(len(A)):
yield A[len(A)-1 - i ] + A[i]
n -= 1
list(generator_x(A,3))
Ta thấy rằng, ứng với mỗi giá trị n, với cách giải quyết trên cần phải lặp lại for A n lần. Điều này không tốt. Bây giờ thử giải quyết vấn đề này với đệ quy.
def subsets(A):
if not A:
yield []
else:
for s in subsets(A[1:]):
yield s
yield [A[0]] + s
list(subsets(['0', '1', '2']))
[[], ['0'], ['1'], ['0', '1'], ['2'], ['0', '2'], ['1', '2'], ['0', '1', '2']]
A = ["0","1","2"]
from functools import lru_cache
@lru_cache()
def strings(A, n):
if n == 0:
return ['']
return [s + c for s in strings(A, n - 1) for c in A]
strings(tuple(A),15)
def strings_2(A, n):
index_of = {x: i for i, x in enumerate(A)}
s = [A[0]] * n
while True:
yield ''.join(s)
for i in range(1, n + 1):
if s[-i] == A[-1]: # Last letter of alphabet, can not increment
s[-i] = A[0]
else:
s[-i] = A[index_of[s[-i]] + 1] # Modify to next letter
break
else:
break
def perms_1(A):
if not A:
return [[]]
perms = []
for pi in perms_1(A[1:]):
for i in range(len(A)):
perms.append(pi[:i] + [A[0]] + pi[i:])
return perms
perms_1(A)
[['0', '1', '2'],
['1', '0', '2'],
['1', '2', '0'],
['0', '2', '1'],
['2', '0', '1'],
['2', '1', '0']]
list(strings_2(A,15))
[func(i) for i in range(50)]
[1,
1,
2,
3,
5,
8,
13,
21,
34,
55,
89,
144,
233,
377,
610,
987,
1597,
2584,
4181,
6765,
10946,
17711,
28657,
46368,
75025,
121393,
196418,
317811,
514229,
832040,
1346269,
2178309,
3524578,
5702887,
9227465,
14930352,
24157817,
39088169,
63245986,
102334155,
165580141,
267914296,
433494437,
701408733,
1134903170,
1836311903,
2971215073,
4807526976,
7778742049,
12586269025]
A = ['0', '1', '2']
n = 2
strings(A, n)
?????????????
//////////////
?????????????
0 //////////////
1 //////////////
2 //////////////
?????????????
//////////////
?????????????
['00', '01', '02', '10', '11', '12', '20', '21', '22']
itertools.combinations_with_replacement
from itertools import combinations_with_replacement
list(combinations_with_replacement([1, 2], 2))
[(1, 1), (1, 2), (2, 2)]
itertools.permutations
from itertools import permutations
list(permutations('abc'))
[('a', 'b', 'c'),
('a', 'c', 'b'),
('b', 'a', 'c'),
('b', 'c', 'a'),
('c', 'a', 'b'),
('c', 'b', 'a')]
Bộ lặp vô hạn
Thử tạo 1 list số lẻ < 100
[i for i in range(100) if i % 2 == 1]
[j for j in range(1,100,2)]
itertools.count(start=0, step=1)
count lặp vô hạn với 2 tham số đầu vào start và step.
import itertools
for i in itertools.count():
print(i)
if i > 3:
break
0
1
2
3
4
import itertools
for i in itertools.count(0,10):
print(i)
if i > 100:
break
0
10
20
30
40
50
60
70
80
90
100
110
for i in itertools.count(0.1, 1.5):
print(i)
if i > 3:
break
0.1
1.6
3.1
Ta có thể thấy rằng count hỗ trợ thêm vòng lặp while như 1 biến đếm thay vì dem = 0 , dem += 1
dem = 1
while dem < 10:
print(dem)
dem += 2
1
3
5
7
9
from itertools import count
sequence = count(start=1, step=2)
element = next(sequence)
while(element < 10):
print(element)
element = next(sequence)
1
3
5
7
9
Bây giờ hãy xem cách count hoạt động với vài ví dụ sau
from itertools import count
sequence = count(start=1, step=2)
while(next(sequence) < 10):
print(next(sequence))
3
7
11
Rất rõ ràng chúng ta thấy rằng việc gọi next(sequence) < 10 ở condition while đã khiến next(sequence) đã được chạy 2 lần trong while dẫn đến kết quả sẽ là 3,7,11 thay vì 1,3,5,7,9.
Chúng ta cần 1 điều gì đó như thế này nếu vẫn muôn giữ logic trên
sequence = count(start=2, step=1)
while(next(sequence) < 10):
print(next(sequence))
3
5
7
9
Hoạt động chính xác :))
Dùng count với zip
l1 = ['a', 'b', 'c']
l2 = ['x', 'y', 'z']
print(list(zip(itertools.count(), l1, l2)))
[(0, 'a', 'x'), (1, 'b', 'y'), (2, 'c', 'z')]
Dùng count với enumerate
print(list(enumerate(zip(l1, l2))))
[(0, ('a', 'x')), (1, ('b', 'y')), (2, ('c', 'z'))]
names = ['Alice', 'Bob', 'Charlie']
ages = [24, 50, 18]
for i, (name, age) in enumerate(zip(names, ages)):
print(i, name, age)
0 Alice 24
1 Bob 50
2 Charlie 18
itertools.cycle()
Hàm cycle()chấp nhận một trình lặp có thể lặp lại và tạo ra một trình lặp , chứa tất cả các phần tử của có thể lặp. Ngoài các phần tử này, nó chứa một bản sao của mỗi phần tử.
import itertools
itertools.cycle('ABCD')
<itertools.cycle at 0x7febd312ee60>
for i in itertools.cycle('ABCD'):
print(i)
Điều này sẽ chạy cho đến khi chúng ta thúc chương trình một cách cưỡng bức hoặc hết bộ nhớ. Vì vậy chúng ta phải luôn có điều kiện thoát cho cycle().
s = ''
for i in itertools.cycle('ABCD'):
s += i
if len(s) >16:
print(s)
break
ABCDABCDABCDABCDA
itertools.repeat()
repeat(object, num=1)
from itertools import repeat
a = repeat("hello ///////////",5)
list(a)
['hello ///////////',
'hello ///////////',
'hello ///////////',
'hello ///////////',
'hello ///////////']
Bộ lặp hữu hạn
itertools.product()
Combinatoric generators
combinations()
Chúng ta đặt ra vấn đề thế này,có 4 con số 1,2,3,4 có thể lập được bao nhiêu chữ số có 3 chữ số , với con số được lập không trùng lặp ?
import itertools
list_number = [1,2,3,4]
# print(list(itertools.combinations(list_number,3)))
for item in list(itertools.combinations(list_number,3)):
print(list(itertools.permutations(item,3)))
# len(list(itertools.combinations(list_number,3)))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
[(1, 2, 4), (1, 4, 2), (2, 1, 4), (2, 4, 1), (4, 1, 2), (4, 2, 1)]
[(1, 3, 4), (1, 4, 3), (3, 1, 4), (3, 4, 1), (4, 1, 3), (4, 3, 1)]
[(2, 3, 4), (2, 4, 3), (3, 2, 4), (3, 4, 2), (4, 2, 3), (4, 3, 2)]
values = ["Ace", "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King"]
suits = ["Hearts", "Diamonds", "Clubs", "Spades"]
print(list(itertools.product(values, suits)))
[('Ace', 'Hearts'), ('Ace', 'Diamonds'), ('Ace', 'Clubs'), ('Ace', 'Spades'), ('2', 'Hearts'), ('2', 'Diamonds'), ('2', 'Clubs'), ('2', 'Spades'), ('3', 'Hearts'), ('3', 'Diamonds'), ('3', 'Clubs'), ('3', 'Spades'), ('4', 'Hearts'), ('4', 'Diamonds'), ('4', 'Clubs'), ('4', 'Spades'), ('5', 'Hearts'), ('5', 'Diamonds'), ('5', 'Clubs'), ('5', 'Spades'), ('6', 'Hearts'), ('6', 'Diamonds'), ('6', 'Clubs'), ('6', 'Spades'), ('7', 'Hearts'), ('7', 'Diamonds'), ('7', 'Clubs'), ('7', 'Spades'), ('8', 'Hearts'), ('8', 'Diamonds'), ('8', 'Clubs'), ('8', 'Spades'), ('9', 'Hearts'), ('9', 'Diamonds'), ('9', 'Clubs'), ('9', 'Spades'), ('10', 'Hearts'), ('10', 'Diamonds'), ('10', 'Clubs'), ('10', 'Spades'), ('Jack', 'Hearts'), ('Jack', 'Diamonds'), ('Jack', 'Clubs'), ('Jack', 'Spades'), ('Queen', 'Hearts'), ('Queen', 'Diamonds'), ('Queen', 'Clubs'), ('Queen', 'Spades'), ('King', 'Hearts'), ('King', 'Diamonds'), ('King', 'Clubs'), ('King', 'Spades')]
Closures, Decorators và functools
Closures
Closure thường được tạo ra bởi hàm lồng nhau, có thể hiểu là những hàm ghi nhớ không gian nơi mà nó tạo ra.
class Printer:
def __init__(self, message):
self.message = message
def do_it(self):
print(self.message)
p = Printer('hello')
p.do_it()
hello
def make_printer(message):
def nested_printer_func():
print(message)
return nested_printer_func
m = make_printer('hello')
m()
hello
Decorators
def my_decorator(func):
def test():
print("hello you!")
func()
print("hello python!")
return test
def func_test():
print("are you ok?")
md = my_decorator(func_test)
# func_test()
md()
hello you!
are you ok?
hello python!
def my_decorator(func):
def test():
print("hello you!")
func()
print("hello python!")
return test
@my_decorator
def func_test():
print("are you ok?")
func_test()
hello you!
are you ok?
hello python!
def my_decorator(func):
def test():
print("hello you!")
func()
print("hello python!")
return test
@my_decorator
def func_test(name):
print("{}, are you ok?".format(name))
func_test("Nhã Thy")
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-9-ff55a521aa18> in <module>
10 print("{}, are you ok?".format(name))
11
---> 12 func_test("Nhã Thy")
TypeError: test() takes 0 positional arguments but 1 was given
def my_decorator(func):
def test(*args, **kwargs):
print("hello you!")
func(*args, **kwargs)
print("hello python!")
return test
@my_decorator
def func_test(name):
print("{}, are you ok?".format(name))
func_test("Nhã Thy")
hello you!
Nhã Thy, are you ok?
hello python!
import functools
def decorator(func):
@functools.wraps(func)
def wrapper_decorator(*args, **kwargs):
# Do something before
value = func(*args, **kwargs)
# Do something after
return value
return wrapper_decorator
import time
def logged(time_format):
def decorator(func):
def decorated_func(*args, **kwargs):
print("- Running '%s' on %s " % (func.__name__,time.strftime(time_format)))
start_time = time.time()
result = func(*args, **kwargs)
end_time = time.time()
print("- Finished '%s', execution time = %0.3fs " % (func.__name__,end_time - start_time))
return result
decorated_func.__name__ = func.__name__
return decorated_func
return decorator
@logged("%b %d %Y - %H:%M:%S")
def add1(x, y):
time.sleep(1)
return x + y
add1(12,20)
- Running 'add1' on Oct 07 2022 - 08:10:50
- Finished 'add1', execution time = 1.001s
32
@logged("%b %d %Y - %H:%M:%S")
def add2(x, y):
time.sleep(2)
return x + y
add2(20,12)
- Running 'add2' on Oct 07 2022 - 08:16:49
- Finished 'add2', execution time = 2.002s
32
functools
Reduce
def add(a,b):
return a - b
def my_reduce(func, container):
obj = iter(container)
value = next(obj)
print(value,"*************")
for element in obj:
print(element,"//////////////")
value = func(value, element)
print(value,"***2222222")
# lambda value, element : value*element
return value
# lân 1 : value = 1
# element = 3
# value được gắn lại: -2
# lan 2: value = -2
# element = 5
# value dgl = -7
# lân 3 : value = -7
# element = 6
# value được gắn lại: -13
# lân 3 : value = -13
# element = 2
# value được gắn lại: -15
print(my_reduce(add, [1, 3, 5, 6, 2]))
1 *************
3 //////////////
-2 ***2222222
5 //////////////
-7 ***2222222
6 //////////////
-13 ***2222222
2 //////////////
-15 ***2222222
-15
from functools import reduce
reduce(lambda a, b: a+b, [1, 3, 5, 6, 2])
17
tính tích của dãy số từ 1 —> n
n = int(input("n : "))
tich = 1
for i in range(1,n +1):
tich *= i
print(tich)
n : 3
6
from functools import reduce
n = int(input("n : "))
reduce(lambda a, b: a+b,range(1,n+1))
n : 5
15
listC = [1,2,3]
obj1 = iter(listC)
print(next(obj1))
print(next(obj1))
print(next(obj1))
print(next(obj1))
1
2
3
---------------------------------------------------------------------------
StopIteration Traceback (most recent call last)
<ipython-input-40-ad44b0a758b6> in <module>
5 print(next(obj1))
6 print(next(obj1))
----> 7 print(next(obj1))
StopIteration:
Classes và Metaclasses
Classes
Trong ngôn ngữ Python các lớp cũng có thể được hiêủ đơn giản là các đoạn code mô tả cách tạo một đối tượng.Bên cạnh đó các class cũng là các đối tượng nên nó sẽ có các tính chất cơ bản của một đối tượng như bạn có thể gán nó cho một biến, có thể sao chép nó, có thể thêm các thuộc tính và có thể chuyển nó như một tham số hàm.Cùng xem xét các đoạn code ví dụ bên dưới…
class A(object):
pass
type(A)
type
# gán nó cho một biến
my_class = A
type(my_class())
__main__.A
type của my_class là A, nhưng type của A là type. Một cách tổng quát, type của tất cả các class đều là type. type của các built-in classes cũng là type.
def my_func(class_name):
print(type(class_name))
# chuyển nó như một tham số hàm
my_func(A)
<class 'type'>
dir(A)
['__class__',
'__delattr__',
'__dict__',
'__dir__',
'__doc__',
'__eq__',
'__format__',
'__ge__',
'__getattribute__',
'__gt__',
'__hash__',
'__init__',
'__init_subclass__',
'__le__',
'__lt__',
'__module__',
'__ne__',
'__new__',
'__reduce__',
'__reduce_ex__',
'__repr__',
'__setattr__',
'__sizeof__',
'__str__',
'__subclasshook__',
'__weakref__',
'new_attribute']
# thêm các thuộc tính
A.new_attribute = 'test'
print(A.new_attribute)
test
class A(object):
def __init__(self, a):
self.a = a
print(self.a)
my_class_2 = A
list(map(my_class_2,[1,2,3]))
1
2
3
[<__main__.A at 0x7fd3f2ed07d0>,
<__main__.A at 0x7fd3f2ed0b50>,
<__main__.A at 0x7fd3f2ed03d0>]
def my_func(class_obj):
class A(object):
def print_class(self):
print(class_obj)
A.__name__ = class_obj
return A
my_func("B")
__main__.my_func.<locals>.A
Metaclasses
type(name, bases, attrs)
- name: tên của lớp
- bases: tuple của lớp cha (để thừa kế, có thể để trống)
- attrs: từ điển chứa các tên và giá trị thuộc tính
MyClass = type("MyClassTest",(object,),{"a": 0})
type(MyClass)
type
obj = MyClass()
type(obj)
__main__.MyClassTest
obj.a
0
Đoạn mã trên tương đương với class chũng ta thường hay tạo như sau
class MyClassTest(object):
a = 0
x = MyClassTest()
x.a
0
Bây giờ, thử thêm các phương thức cho nó
def method_1(self,a,b):
return a + b
MyClass = type("MyClassTest",(object,),{"a": 0,"add":method_1})
obj = MyClass()
obj.add(3,4)
7
Class trên tương đương với code sau
class MyClassTest(object):
a = 0
def add(self, a,b):
return a +b
x = MyClassTest()
x.add(3,4)
7
class MyClassTest(object):
a = 0
def __init__(self,x,y):
self.x = x
self.y = y
def add(self, a,b):
return a + b
# class trên tưowng đương với đoạn mã bên dưới
def my_init(self,a,b):
return a + b
def method_1(self,a,b):
return a + b
MyClass = type("MyClassTest",(object,),{"a": 0,"__init__":my_init,"add":method_1})
Kế thừa
class Test:
pass
class MyClassTest(Test):
a = 0
def __init__(self,x,y):
self.x = x
self.y = y
def add(self, a,b):
return a + b
# class trên tưowng đương với đoạn mã bên dưới
def my_init(self,a,b):
return a + b
def method_1(self,a,b):
return a + b
MyClass = type("MyClassTest",(Test,),{"a": 0,"__init__":my_init,"add":method_1})
MyClass = type("MyClassTest",(object,),{"my_attribute": a})
Thuộc tính metaclass
Metaclass là lớp của một lớp. Một lớp xác định cách một thể hiện của lớp (tức là một đối tượng) hoạt động trong khi một siêu kính định nghĩa cách một lớp hoạt động. Một lớp là một thể hiện của một siêu kính.
# minimax_simplenim.py
def minimax(state, max_turn):
if state == 0:
return 1 if max_turn else -1
possible_new_states = [
state - take for take in (1, 2, 3) if take <= state
]
if max_turn:
scores = [
minimax(new_state, max_turn=False)
for new_state in possible_new_states
]
return max(scores)
else:
scores = [
minimax(new_state, max_turn=True)
for new_state in possible_new_states
]
return min(scores)
def possible_new_states(state):
return [state - take for take in (1, 2, 3) if take <= state]
def evaluate(state, is_maximizing):
if state == 0:
return 1 if is_maximizing else -1
minimax(6, max_turn=False)
-1
state = 6
for take in (1, 2, 3):
new_state = state - take
score = minimax(new_state, max_turn=False)
print(f"Move from {state} to {new_state}: {score}")
# from 6 to 5: 1
# from 6 to 4: -1
# from 6 to 3: -1
Move from 6 to 5: 1
Move from 6 to 4: -1
Move from 6 to 3: -1
def best_move(state):
for take in (1, 2, 3):
new_state = state - take
score = minimax(new_state, max_turn=False)
if score > 0:
break
return score, new_state
best_move(6)
(1, 5)
best_move(5)
(-1, 2)
best_move(4)
(1, 1)
from functools import reduce
def minimax(n = 0, add = 0):
while add < 30 :
n = int(input("n : "))
yield n
add = reduce(lambda x,y:x+y,list(minimax()))
print(add)
minimax()
<generator object minimax at 0x7f9c6ae719d0>
total = 30
lista = []
while True:
n = int(input("n = "))
if 0<n<4:
lista.append(n)
print(sum(lista))
else:
print("nhap lai : ")
if sum(lista) == total:
break
n = 1
1
n = 3
4
n = 2
6
n = 3
9
n = 1
10
n = 3
13
n = 3
16
n = 2
18
n = 3
21
n = 2
23
n = 3
26
n = 1
27
n = 3
30
#!/usr/bin/env python3
from math import inf as infinity
from random import choice
import platform
import time
from os import system
"""
An implementation of Minimax AI Algorithm in Tic Tac Toe,
using Python.
This software is available under GPL license.
Author: Clederson Cruz
Year: 2017
License: GNU GENERAL PUBLIC LICENSE (GPL)
"""
HUMAN = -1
COMP = +1
board = [
[0, 0, 0],
[0, 0, 0],
[0, 0, 0],
]
def evaluate(state):
"""
Function to heuristic evaluation of state.
:param state: the state of the current board
:return: +1 if the computer wins; -1 if the human wins; 0 draw
"""
if wins(state, COMP):
score = +1
elif wins(state, HUMAN):
score = -1
else:
score = 0
return score
def wins(state, player):
"""
This function tests if a specific player wins. Possibilities:
* Three rows [X X X] or [O O O]
* Three cols [X X X] or [O O O]
* Two diagonals [X X X] or [O O O]
:param state: the state of the current board
:param player: a human or a computer
:return: True if the player wins
"""
win_state = [
[state[0][0], state[0][1], state[0][2]],
[state[1][0], state[1][1], state[1][2]],
[state[2][0], state[2][1], state[2][2]],
[state[0][0], state[1][0], state[2][0]],
[state[0][1], state[1][1], state[2][1]],
[state[0][2], state[1][2], state[2][2]],
[state[0][0], state[1][1], state[2][2]],
[state[2][0], state[1][1], state[0][2]],
]
if [player, player, player] in win_state:
return True
else:
return False
def game_over(state):
"""
This function test if the human or computer wins
:param state: the state of the current board
:return: True if the human or computer wins
"""
return wins(state, HUMAN) or wins(state, COMP)
def empty_cells(state):
"""
Each empty cell will be added into cells' list
:param state: the state of the current board
:return: a list of empty cells
"""
cells = []
for x, row in enumerate(state):
for y, cell in enumerate(row):
if cell == 0:
cells.append([x, y])
return cells
def valid_move(x, y):
"""
A move is valid if the chosen cell is empty
:param x: X coordinate
:param y: Y coordinate
:return: True if the board[x][y] is empty
"""
if [x, y] in empty_cells(board):
return True
else:
return False
def set_move(x, y, player):
"""
Set the move on board, if the coordinates are valid
:param x: X coordinate
:param y: Y coordinate
:param player: the current player
"""
if valid_move(x, y):
board[x][y] = player
return True
else:
return False
def minimax(state, depth, player):
"""
AI function that choice the best move
:param state: current state of the board
:param depth: node index in the tree (0 <= depth <= 9),
but never nine in this case (see iaturn() function)
:param player: an human or a computer
:return: a list with [the best row, best col, best score]
"""
if player == COMP:
best = [-1, -1, -infinity]
else:
best = [-1, -1, +infinity]
if depth == 0 or game_over(state):
score = evaluate(state)
return [-1, -1, score]
for cell in empty_cells(state):
x, y = cell[0], cell[1]
state[x][y] = player
score = minimax(state, depth - 1, -player)
state[x][y] = 0
score[0], score[1] = x, y
if player == COMP:
if score[2] > best[2]:
best = score # max value
else:
if score[2] < best[2]:
best = score # min value
return best
def clean():
"""
Clears the console
"""
os_name = platform.system().lower()
if 'windows' in os_name:
system('cls')
else:
system('clear')
def render(state, c_choice, h_choice):
"""
Print the board on console
:param state: current state of the board
"""
chars = {
-1: h_choice,
+1: c_choice,
0: ' '
}
str_line = '---------------'
print('\n' + str_line)
for row in state:
for cell in row:
symbol = chars[cell]
print(f'| {symbol} |', end='')
print('\n' + str_line)
def ai_turn(c_choice, h_choice):
"""
It calls the minimax function if the depth < 9,
else it choices a random coordinate.
:param c_choice: computer's choice X or O
:param h_choice: human's choice X or O
:return:
"""
depth = len(empty_cells(board))
if depth == 0 or game_over(board):
return
clean()
print(f'Computer turn [{c_choice}]')
render(board, c_choice, h_choice)
if depth == 9:
x = choice([0, 1, 2])
y = choice([0, 1, 2])
else:
move = minimax(board, depth, COMP)
x, y = move[0], move[1]
set_move(x, y, COMP)
time.sleep(1)
def human_turn(c_choice, h_choice):
"""
The Human plays choosing a valid move.
:param c_choice: computer's choice X or O
:param h_choice: human's choice X or O
:return:
"""
depth = len(empty_cells(board))
if depth == 0 or game_over(board):
return
# Dictionary of valid moves
move = -1
moves = {
1: [0, 0], 2: [0, 1], 3: [0, 2],
4: [1, 0], 5: [1, 1], 6: [1, 2],
7: [2, 0], 8: [2, 1], 9: [2, 2],
}
clean()
print(f'Human turn [{h_choice}]')
render(board, c_choice, h_choice)
while move < 1 or move > 9:
try:
move = int(input('Use numpad (1..9): '))
coord = moves[move]
can_move = set_move(coord[0], coord[1], HUMAN)
if not can_move:
print('Bad move')
move = -1
except (EOFError, KeyboardInterrupt):
print('Bye')
exit()
except (KeyError, ValueError):
print('Bad choice')
def main():
"""
Main function that calls all functions
"""
clean()
h_choice = '' # X or O
c_choice = '' # X or O
first = '' # if human is the first
# Human chooses X or O to play
while h_choice != 'O' and h_choice != 'X':
try:
print('')
h_choice = input('Choose X or O\nChosen: ').upper()
except (EOFError, KeyboardInterrupt):
print('Bye')
exit()
except (KeyError, ValueError):
print('Bad choice')
# Setting computer's choice
if h_choice == 'X':
c_choice = 'O'
else:
c_choice = 'X'
# Human may starts first
clean()
while first != 'Y' and first != 'N':
try:
first = input('First to start?[y/n]: ').upper()
except (EOFError, KeyboardInterrupt):
print('Bye')
exit()
except (KeyError, ValueError):
print('Bad choice')
# Main loop of this game
while len(empty_cells(board)) > 0 and not game_over(board):
if first == 'N':
ai_turn(c_choice, h_choice)
first = ''
human_turn(c_choice, h_choice)
ai_turn(c_choice, h_choice)
# Game over message
if wins(board, HUMAN):
clean()
print(f'Human turn [{h_choice}]')
render(board, c_choice, h_choice)
print('YOU WIN!')
elif wins(board, COMP):
clean()
print(f'Computer turn [{c_choice}]')
render(board, c_choice, h_choice)
print('YOU LOSE!')
else:
clean()
render(board, c_choice, h_choice)
print('DRAW!')
exit()
if __name__ == '__main__':
main()
board = list(range(10))
def drawBoard(board):
print(board[7] , ' | ' , board[8] , ' | ' , board[9])
print('-----------')
print(board[4] , ' | ' , board[5] , ' | ' , board[6])
print('-----------')
print(board[1] , ' | ' , board[2] , ' | ' , board[3])
drawBoard(board)
7 | 8 | 9
-----------
4 | 5 | 6
-----------
1 | 2 | 3
import random
def drawBoard(board):
#Thực hiện in ra bàn cờ
print(board[7] + '|' + board[8] + '|' + board[9])
print('-+-+-')
print(board[4] + '|' + board[5] + '|' + board[6])
print('-+-+-')
print(board[1] + '|' + board[2] + '|' + board[3])
def inputPlayerLetter():
#Cho phép người chơi nhập ký tự mà họ muốn sử dụng
#Trả về tập hợp kiểu List với ký tự mà người chơi chọn làm phần tử đầu tiên
letter = ''
while not (letter == 'X' or letter == 'O'):
print('Do you want to be X or O?')
letter = input().upper()
if letter == 'X':
return ['X', 'O']
else:
return ['O', 'X']
def whoGoesFirst():
#Chọn ngẫu nhiên bất kỳ cho phép người chơi đi trước hay không
if random.randint(0, 1) == 0:
return 'computer'
else:
return 'player'
def makeMove(board, letter, move):
board[move] = letter
def isWinner(bo, le):
#Trả về True nếu người chơi thắng
return ((bo[7] == le and bo[8] == le and bo[9] == le) or
(bo[4] == le and bo[5] == le and bo[6] == le) or
(bo[1] == le and bo[2] == le and bo[3] == le) or
(bo[7] == le and bo[4] == le and bo[1] == le) or
(bo[8] == le and bo[5] == le and bo[2] == le) or
(bo[9] == le and bo[6] == le and bo[3] == le) or
(bo[7] == le and bo[5] == le and bo[3] == le) or
(bo[9] == le and bo[5] == le and bo[1] == le))
def getBoardCopy(board):
#Sao chép bàn cờ
boardCopy = []
for i in board:
boardCopy.append(i)
return boardCopy
def isSpaceFree(board, move):
#Trả về True nếu nước đi còn chỗ trống
return board[move] == ' '
def getPlayerMove(board):
#Lấy nước đi của người chơi
move = ' '
while move not in '1 2 3 4 5 6 7 8 9'.split() or not isSpaceFree(board, int(move)):
print('What is your next move? (1-9)')
move = input()
return int(move)
def chooseRandomMoveFromList(board, movesList):
#Trả về một nước đi hợp lệ
#Trả về None nếu không còn nước đi hợp lệ
possibleMoves = []
for i in movesList:
if isSpaceFree(board, i):
possibleMoves.append(i)
if len(possibleMoves) != 0:
return random.choice(possibleMoves)
else:
return None
def getComputerMove(board, computerLetter):
#Xác định nước đi cho máy
if computerLetter == 'X':
playerLetter = 'O'
else:
playerLetter = 'X'
#Giải thuật cho máy chơi
#Kiểm tra xem nước đi tiếp theo có thắng được hay không
for i in range(1, 10):
boardCopy = getBoardCopy(board)
if isSpaceFree(boardCopy, i):
makeMove(boardCopy, computerLetter, i)
if isWinner(boardCopy, computerLetter):
return i
#Kiểm tra xem người chơi có thể thắng trong nước đi tiếp theo hay không
for i in range(1, 10):
boardCopy = getBoardCopy(board)
if isSpaceFree(boardCopy, i):
makeMove(boardCopy, playerLetter, i)
if isWinner(boardCopy, playerLetter):
return i
#Chọn một nước đi ở các góc bàn cờ nếu trống
move = chooseRandomMoveFromList(board, [1, 3, 7, 9])
if move != None:
return move
#Chọn nước đi ở giữa
if isSpaceFree(board, 5):
return 5
#Chọn một trong các nước đi ở các cạnh bên của bàn cờ
return chooseRandomMoveFromList(board, [2, 4, 6, 8])
def isBoardFull(board):
#Trả về True nếu các nước đi không còn, ngược lại trả về False
for i in range(1, 10):
if isSpaceFree(board, i):
return False
return True
print('Welcome to Tic Tac Toe!')
while True:
#Thiết lập lại bàn cờ
theBoard = [' '] * 10
playerLetter, computerLetter = inputPlayerLetter()
turn = whoGoesFirst()
print('The ' + turn + ' will go first.')
gameIsPlaying = True
while gameIsPlaying:
if turn == 'player':
drawBoard(theBoard)
move = getPlayerMove(theBoard)
makeMove(theBoard, playerLetter, move)
if isWinner(theBoard, playerLetter):
drawBoard(theBoard)
print('Hooray! You have won the game!')
gameIsPlaying = False
else:
if isBoardFull(theBoard):
drawBoard(theBoard)
print('The game is a tie!')
break
else:
turn = 'computer'
else:
move = getComputerMove(theBoard, computerLetter)
makeMove(theBoard, computerLetter, move)
if isWinner(theBoard, computerLetter):
drawBoard(theBoard)
print('The computer has beaten you! You lose.')
gameIsPlaying = False
else:
if isBoardFull(theBoard):
drawBoard(theBoard)
print('The game is a tie!')
break
else:
turn = 'player'
print('Do you want to play again? (yes or no)')
if not input().lower().startswith('y'):
break
from google.colab import drive
drive.mount('/content/drive')
Mounted at /content/drive