Sáng kiến kinh nghiệm THPT: Một số phương pháp tối ưu hóa mã nguồn Python giúp cải thiện hiệu suất chương trình và giảm tải tài nguyên

Chia sẻ: _ _ | Ngày: | Loại File: DOCX | Số trang:49

Thêm vào BST

Báo xấu

1
lượt xem 0
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài "Một số phương pháp tối ưu hóa mã nguồn Python giúp cải thiện hiệu suất chương trình và giảm tải tài nguyên" nêu ra các định hướng giúp học sinh có thể tiếp cận một số cách tối ưu hóa mã nguồn để tăng tốc độ xử lý chương trình. Giúp học sinh tiếp cận ngôn ngữ lập trình Python sớm và tốt hơn. Từ đó bồi dưỡng học sinh năng lực giải quyết vấn đề trong giải toán Tin học, đồng thời rèn luyện và nâng cao kĩ năng lập trình cho các em. Đặc biệt là học sinh tham gia dự thi học sinh giỏi cấp tỉnh THCS, THPT hoặc thi vào các trường chuyên.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sáng kiến kinh nghiệm THPT: Một số phương pháp tối ưu hóa mã nguồn Python giúp cải thiện hiệu suất chương trình và giảm tải tài nguyên

SỞ GD&ĐT NGHỆ AN TRƯỜNG THPT MƯỜNG QUẠ -------------- SÁNG KIẾN KINH NGHIỆM ĐỀ TÀI MỘT SỐ PHƯƠNG PHÁP TỐI ƯU HÓA MÃ NGUỒN PYTHON GIÚP CẢI THIỆN HIỆU SUẤT CHƯƠNG TRÌNH VÀ GIẢM TẢI TÀI NGUYÊN Lĩnh vực: Tin học Người thực hiện: Nguyễn Hồng Dương Số điện thoại: 0357563745 Email: hongduong6688mq@gmail.com Năm thực hiện: 2023 - 2024 Năm học: 2023 – 2024 1
MỤC LỤC Trang PHẦN I: ĐẶT VẤN ĐỀ......................................................................................... 2 1. Lý do chọn đề tài.............................................................................................2 2. Mục tiêu nghiên cứu của đề tài........................................................................3 3. Nhiệm vụ nghiên cứu của đề tài......................................................................3 4. Đối tượng nghiên cứu của đề tài..................................................................... 3 5. Phạm vi nghiên cứu của đề tài.........................................................................3 6. Tính mới của đề tài..........................................................................................3 PHẦN II: NỘI DUNG NGHIÊN CỨU..................................................................4 1. Cơ sở lý luận....................................................................................................4 1.1. Giới thiệu......................................................................................................4 1.1.1. Con trỏ là gì?............................................................................................. 4 1.1.2. Làm thế nào để sử dụng thuật toán hai con trỏ?........................................5 1.2. Một số dạng về thuật toán hai con trỏ..........................................................6 1.2.1. Hai con trỏ, một con trỏ ở đầu và một con trỏ ở cuối di chuyển vào giữa cho đến khi cả 2 gặp nhau................................................................................... 6 1.2.2. Một con trỏ di chuyển chậm và một con trỏ di chuyển với tốc độ nhanh hơn 9 1.2.3.............................................................................................................Hai con trỏ di chuyển trên hai mảng hoặc xâu...............................................11 2. Cơ sở thực tiễn.............................................................................................. 15 2.1. Thực trạng của vấn đề trước khi áp dụng đề tài.........................................15 2.1.1.............................................................................................................Đặc điểm tình hình..........................................................................................15 2.1.2.............................................................................................................Thự c trạng trước khi nghiên cứu....................................................................16 2.1.3.............................................................................................................Các giải pháp giải quyết vấn đề......................................................................17 2.2. So sánh cài đặt thuật toán 2 con trỏ và một số thuật toán khác..................17 2.3. Rèn luyện kỹ năng vận dụng thuật toán 2 con trỏ để giải một số bài toán cơ bản đến nâng cao............................................................................................... 28 2.3.1. Một số bài tập về 2 con trỏ, một con trỏ ở đầu và một con trỏ ở cuối di chuyển vào giữa cho đến khi cả 2 gặp...............................................................28 2.3.2. Một số bài tập về một con trỏ di chuyển chậm và một con trỏ di chuyển với tốc độ nhanh hơn.........................................................................................31 2.3.3. Hai con trỏ di chuyển trên hai mảng hoặc xâu........................................36 2.4. Bài tập tự giải có hướng dẫn...................................................................... 41 PHẦN III: KẾT LUẬN.........................................................................................48 1. Với mục tiêu đề ra đề tài đã làm được.......................................................... 48 2. Hướng phát triển của đề tài........................................................................... 48 3. Kiến nghị và đề xuất......................................................................................48 2
TÀI LIỆU THAM KHẢO....................................................................................50 ĐỀ TÀI: “ Một số phương pháp tối ưu hóa mã nguồn Python giúp cải thiện hiệu suất chương trình và giảm tải tài nguyên” PHẦN I. ĐẶT VẤN ĐỀ 1.1. Lí do chọn đề tài Cuộc cách mạng công nghệ 4.0 đã và đang làm thay đổi mọi lĩnh vực khoa học và đời sống. Các ngành nghề dựa vào thành quả của lĩnh vực công nghệ cao như Công nghệ Nano, Công nghệ Sinh học và đặc biệt là Công nghệ Thông tin ngày càng phát triển vượt bậc cả về lượng lẫn về chất. Để góp phần cho ngành Công nghệ thông tin có ảnh hưởng mạnh mẽ như vậy, thì việc lựa chọn ngôn ngữ lập trình trong các lĩnh vực mũi nhọn như Trí tuệ nhân tạo (AI), học máy (Machine Learning), khai phá dữ liệu (Data Mining), học sâu (Deep Learning) trở nên vô cùng quan trọng và cần thiết. Một trong những ngôn ngữ đáp ứng được hầu hết các tiêu chí của tất cả nhà lập trình khó tính nhất đó chính là ngôn ngữ lập trình Python. Ngôn ngữ lập trình Python có nhiều ưu điểm nổi trội như dễ nhớ, dễ viết, khả năng xử lí số liệu lớn, phức tạp rất tốt, thư viện có nhiều hàm, đáp ứng được nhiều kiểu dữ liệu mới của Machine Learning, AI, Data Mining, Deep Learning. Ngày nay, máy tính có khả năng tự học mà không cần phải lập trình một cách rõ ràng. Ngành Khoa học máy tính hiện có nhiều ứng dụng sâu rộng vào cuộc sống hằng ngày như đánh cờ, nhận diện khuôn mặt, chẩn đoán y khoa, phát hiện thẻ tín dụng giả, dự đoán kết quả trận đấu, nhận diện giọng nói, phân loại các chuẩn DNA, tóm tắt văn bản, trả lời tự động,… Chính vì thế, ngôn ngữ lập trình Python giờ đã trở thành một yếu tố không thể thiếu khi nhắc đến AI, Machine Learning, Data Mining, Deep Learning và ngược lại. Ngôn ngữ lập trình Python vừa đáp ứng được yêu cầu của các bài toán lập trình cổ điển trước đây và các bài toán lập trình mới. Tuy nhiên, các tài liệu về lập trình Python ở nước ta còn thiếu. Đó là rào cản lớn cho những người muốn sử dụng ngôn ngữ này trong lập trình. Ngoài ra, Trong chương trình giáo dục phổ thông 2018 thì ngôn ngữ lập trình pascal không được đưa vào dạy học thay vào đó là ngôn ngữ lập trình Python. Ngoài Python thì C++ cũng là ngôn ngữ lập trình hiện nay rất phổ biến trong chương trình dạy học cũng như tính ứng dụng của 2 ngôn ngữ này rất nhiều, nhất là trong các kỳ thi tin học trẻ, thi vào chuyên tin, học sinh giỏi tỉnh… Bên cạnh đó ngôn ngữ lập trình Python thường được biết đến với sự thuận lợi trong việc đọc và viết mã, nhưng đôi khi nó cũng có thể chạy chậm so với một số 3
ngôn ngữ khác. Dưới đây là một số nguyên nhân chính làm cho Python có thể chạy chậm: - Ngôn ngữ thông dịch (interpreted language): Python được thực thi dưới dạng thông dịch, điều này có thể làm giảm hiệu suất so với các ngôn ngữ được biên dịch trước khi chạy. Trong quá trình thực thi, Python cần dịch mã nguồn thành mã máy tại thời điểm chạy, làm tăng độ trễ. - Dynamic typing: Sự đa dạng về kiểu dữ liệu có thể tạo ra độ trễ trong quá trình kiểm tra kiểu dữ liệu tại thời điểm thực thi. Mỗi khi một biến được sử dụng, Python phải kiểm tra kiểu dữ liệu của nó và thích ứng với thay đổi kiểu. - Global Interpreter Lock (GIL): GIL là một cơ chế bảo vệ ngăn chặn nhiều luồng Python chạy đồng thời trong môi trường đa luồng. Điều này có thể làm giảm hiệu suất đặc biệt đối với các ứng dụng đa luồng, vì chỉ một luồng được thực hiện tại một thời điểm, giảm tính song song của chương trình. - Thuật toán quản lý bộ nhớ: Python sử dụng garbage collection (thu gom rác) để tự động giải phóng bộ nhớ không sử dụng, nhưng quá trình này có thể tạo ra độ trễ và làm giảm hiệu suất của chương trình, đặc biệt là trong các ứng dụng đòi hỏi xử lý nhanh. - Thư viện lớn và đa dạng: Mặc dù thư viện đa dạng của Python là một điểm mạnh, nhưng đôi khi việc sử dụng quá nhiều thư viện có thể tăng kích thước của ứng dụng và làm chậm quá trình tải và khởi chạy. - Tự động kiểm tra lỗi (dynamic error checking): Python thực hiện nhiều kiểm tra lỗi tại thời điểm chạy, điều này có thể làm chậm chương trình so với các ngôn ngữ có kiểm tra lỗi tại thời điểm biên dịch. - Các thư viện tham số nặng: Trong các lĩnh vực như machine learning và scientific computing, một số thư viện Python có thể có tham số nặng và phức tạp, làm giảm hiệu suất đặc biệt đối với các tác vụ tính toán lớn. Các vấn đề trên không đồng nghĩa với việc Python không phù hợp cho mọi ứng dụng. Python thường được chọn lựa cho tính dễ đọc, đồng nhất, và tích hợp tốt với nhiều thư viện, trong khi vẫn có những nỗ lực để tối ưu hóa hiệu suất của nó thông qua các dự án và cải tiến kỹ thuật. Trong đề tài này, tôi chủ yếu tập trung khai thác những hạn chế của ngôn ngữ Python và trên cơ sở đó tìm ra các giải pháp mới giúp học sinh trong quá trình học cũng như trong các cuộc thi tin học trẻ, thi học sinh giỏi tỉnh,... cải thiện tốc độ xử lý 4
chương trình. Do đó, tôi quyết định viết sáng kiến kinh nghiệm: “ Một số phương pháp tối ưu hóa mã nguồn Python giúp cải thiện hiệu suất chương trình và giảm tải tài nguyên” Để hoàn thành nhiệm vụ của đề tài, tôi đã nghiên cứu rất nhiều sách và các chuyên đề Tin học dành cho học sinh giỏi, các tài liệu trên các trang web. Tuy nhiên rất ít tài liệu trình bày cụ thể về cách sử dụng thuật toán này một cách đầy đủ và dễ hiểu. 1.2. Mục tiêu và nhiệm vụ nghiên cứu 1.2.1. Mục tiêu nghiên cứu - Đề tài nêu ra các định hướng giúp học sinh có thể tiếp cận một số cách tối ưu hóa mã nguồn để tăng tốc độ xử lý chương trình. - Giúp học sinh tiếp cận ngôn ngữ lập trình Python sớm và tốt hơn. - Từ đó bồi dưỡng học sinh năng lực giải quyết vấn đề trong giải toán Tin học, đồng thời rèn luyện và nâng cao kĩ năng lập trình cho các em. Đặc biệt là học sinh tham gia dự thi học sinh giỏi cấp tỉnh THCS, THPT hoặc thi vào các trường chuyên. 1.2.2 Nhiệm vụ nghiên cứu. - Đề tài phân tích một số thư viện, hàm và tối ưu hóa các thuật toán trong các dạng toán quen thuộc, so sánh độ phức tạp thuật toán và định hướng lựa chọn thuật toán tối ưu trong các trường hợp dữ liệu cụ thể nhằm giải bài toán hiệu quả nhất. - Minh họa bằng các ví dụ cụ thể. Đồng thời liên hệ các đề thi vào trường chuyên, đề thi học sinh giỏi tỉnh thời gian qua. 1.3. Đối tượng và phạm vi nghiên cứu. 1.3.1. Đối tượng nghiên cứu. - Độ phức tạp thuật toán và giải pháp lựa chọn các thư viện và thuật toán tối ưu để cải thiện hiệu suất chương trình và giảm tải tài nguyên trong các dạng bài toán quen thuộc trên ngôn ngữ lập trình Python. - Phương pháp bồi dưỡng năng lực giải quyết vấn đề cho học sinh. 1.3.2 Phạm vi nghiên cứu. Chương trình Tin học THCS, THPT để bồi dưỡng học sinh giỏi Tin học và thi vào trường chuyên THPT. 1.4. Tính mới của đề tài. Việc nghiên cứu về các phương pháp cải thiện mã nguồn Python để tăng hiệu suất chương trình và giảm tải tài nguyên trên máy tính là một đề tài còn mới mẻ chưa được đề cập nhiều trong các sách báo và trong các buổi tập huấn chuyên môn mà tôi được tập huấn. Trong các buổi tập huấn giảng viên chưa nêu cụ thể được các phương pháp để ngôn ngữ Python chạy nhanh hơn so với ngôn ngữ C++. Đây là một hạn chế 5
rất lớn ảnh hưởng đến kết quả trong các cuộc thi học sinh giỏi cấp tỉnh và các cuộc thi khác. Đề tài đã nêu được một số biện pháp mới và có các ví dụ minh họa đơn giản, dễ hiểu cho người đọc nhất là đối với các đối tượng mới tiếp xúc với ngôn ngữ Python. Tối ưu hóa mã nguồn không chỉ là quá trình cải thiện hiệu suất của chương trình mà còn là một quá trình sáng tạo, đòi hỏi sự sáng tạo và chiến lược trong việc cân nhắc giữa các yếu tố như đọc hiểu mã, bảo trì, và hiệu suất thực thi PHẦN II: NỘI DUNG NGHIÊN CỨU 1. Cơ sở lý luận Trong quá trình ôn luyện đội tuyển, học sinh được dạy khá nhiều về các phương pháp tối ưu thuật toán như: phương pháp tham lam, chia để trị (sắp xếp nhanh, chặt nhị phân…), quay lui, quy hoạch động, Z Algorithm, KMP… Nhưng nếu không biết kết hợp với những kỹ thuật khác, không biết cách tổ chức dữ liệu, những phương pháp này xét về phương diện độc lập sẽ không đạt được sự tối ưu cao nhất và không có ý nghĩa Các phương pháp được giới thiệu trong sáng kiến đều là những phương pháp rất cơ bản, đơn giản và rất dễ tiếp cận đồng thời đem lại một hiệu quả rất đáng kể trong việc giảm độ phức tạp thuật toán, tiến tới một thuật toán tối ưu nhất và quan trọng nhất là giúp chương trình viết bằng ngôn ngữ Python chạy nhanh hơn một cách đáng kể. 2. Cơ sở thực tiễn Trên thực tế đã có một số tài liệu đề cập đến những kỹ thuật để tăng tốc chương trình, tuy nhiên chưa đi sâu vào phân tích cách tư duy, cách lựa chọn và cài đặt chương trình tối ưu, đặc biệt việc tổng hợp lại các phương pháp giúp học sinh có thể so sánh các cách giải, các kết quả, độ phức tạp còn rất ít, hệ thống bài tập cũng không nhiều. 3. Nội dung 3.1. Phương pháp sử dụng các thư viện tối ưu. Python có nhiều thư viện được viết bằng C, như NumPy và Pandas, cho phép thực hiện các phép toán số học và xử lý dữ liệu nhanh chóng. Sử dụng các thư viện này có thể giúp tăng tốc độ chương trình. Thay vì tự viết mã từ đầu, sử dụng các thư viện đã được tối ưu hóa bằng C như NumPy cho các phép toán số học và Pandas cho xử lý dữ liệu. 3.1.1. Thư viện NumPy: NumPy là một thư viện quan trọng cho xử lý mảng và ma trận trong Python. Nó cung cấp các phép toán mảng hiệu suất cao và giúp tối ưu hóa xử lý dữ liệu số học. a. Cách tạo mảng và một số thao tác với mảng 6
import numpy as np arr1d = np.array([1, 2, 3, 4, 5]) # Tạo một mảng 1 chiều arr2d = np.array([[1, 2, 3], [4, 5, 6]]) # Tạo một mảng 2 chiều # Tạo một mảng với giá trị tăng dần arr_range = np.arange(0, 10, 2) # Từ 0 đến 10, bước nhảy là 2 # Truy cập phần tử của mảng print(arr1d[0]) # In ra phần tử đầu tiên của mảng arr1d print(arr2d[1, 2]) # In ra phần tử ở hàng 2, cột 3 của mảng arr2d # Cắt mảng (slicing) print(arr1d[1:3]) # In ra các phần tử từ vị trí thứ 1 đến vị trí thứ 2 (không bao gồm vị trí thứ 3) # Thay đổi hình dạng của mảng reshaped_arr = arr1d.reshape(5, 1) # Chuyển mảng arr1d thành mảng 5x1 b. Một số bài tập đơn giản Bài tập 1: Cho 1 mảng 1 chiều “arr1d”. Hãy tính tổng, trung bình, tìm giá trị lớn nhất, nhỏ nhất của mảng. import numpy as np total = np.sum(arr1d) mean_value = np.mean(arr1d) max_value = np.max(arr1d) min_value = np.min(arr1d) print("Tổng của các phần tử trong mảng là:", total) Bài tập 2: Ma trận và tích vô hướng Cho hai ma trận matrix1 và matrix2. Hãy tính tích vô hướng của chúng và in kết quả ra màn hình. import numpy as np matrix1 = np.array([[1, 2], [3, 4]]) matrix2 = np.array([[5, 6], [7, 8]]) dot_product = np.dot(matrix1, matrix2) print("Tích vô hướng của hai ma trận là:\n", dot_product) Bài tập 3: Hàm toán học Cho một mảng 1D arr1d. Hãy tính giá trị căn bậc hai của từng phần tử trong mảng và in kết quả ra màn hình. import numpy as np arr1d = np.array([1, 2, 3, 4, 5]) sqrt_values = np.sqrt(arr1d) print("Căn bậc hai của các phần tử trong mảng là:", sqrt_values). Một số hàm thông dụng khác: # Hàm mũ exponential_values = np.exp(arr1d) # Hàm căn bậc hai 7
sqrt_values = np.sqrt(arr1d) # Hàm lượng giác sin_values = np.sin(arr1d) cos_values = np.cos(arr1d) Bài tập 4: Tạo mảng với giá trị ngẫu nhiên Tạo một mảng 2D có kích thước 3x3 với các phần tử là các số ngẫu nhiên trong khoảng từ 0 đến 1 và in mảng ra màn hình. import numpy as np random_array = np.random.rand(3, 3) print("Mảng với các phần tử ngẫu nhiên:\n", random_array) Bài tập 5: Sắp xếp mảng Cho một mảng 1D arr1d. Hãy sắp xếp các phần tử trong mảng theo thứ tự tăng dần và in kết quả ra màn hình. import numpy as np arr1d = np.array([3, 1, 4, 2, 5]) sorted_array = np.sort(arr1d) print("Mảng sau khi sắp xếp là:", sorted_array) # Phép toán trên mảng arr_addition = arr1d + 10 arr_multiplication = arr1d * 2 # Tính toán trên mảng nhiều chiều arr_sum_axis0 = np.sum(arr2d, axis=0) # Tính tổng theo cột arr_sum_axis1 = np.sum(arr2d, axis=1) # Tính tổng theo hàng 3.1.2. Thư viện Cython: Cython là một ngôn ngữ mở rộng của Python cho phép viết mã C hoặc C++ tối ưu hóa và tích hợp nó với mã nguồn Python. Nó giúp tăng hiệu suất của mã nguồn thông qua việc biên dịch mã nguồn Python thành mã máy tối ưu. Cách cài đặt Cython để tối ưu hóa một hàm Cài đặt Cython: Trước tiên, bạn cần cài đặt Cython. Bạn có thể cài đặt nó thông qua pip bằng cách chạy lệnh sau trong terminal hoặc command prompt: pip install cython Tạo tệp .pyx: Bạn cần tạo một tệp có phần mở rộng là .pyx chứa mã Cython của bạn. Đây là nơi bạn sẽ viết mã tương tự như Python, nhưng bạn cũng có thể sử dụng các tính năng của Cython để tối ưu hóa mã của mình. Biên dịch tệp .pyx: Bạn cần biên dịch tệp .pyx thành mã C bằng Cython. Bạn có thể làm điều này bằng cách chạy lệnh sau trong terminal hoặc command prompt: cythonize i your_file.pyx #Trong đó, your_file.pyx là tên của tệp .pyx của bạn. 8
Sử dụng module đã được biên dịch: Sau khi biên dịch, một tệp .c sẽ được tạo ra, cùng với một tệp mở rộng .so (hoặc .pyd trên Windows). Bạn có thể nhập module này vào Python và sử dụng các chức năng và lớp được định nghĩa trong đó giống như bạn nhập bất kỳ module Python nào khác. Ví dụ cụ thể: Tạo một tệp có tên sum.pyx và viết mã Cython trong đó: # sum.pyx def sum_up_to_n(n): cdef int result = 0 for i in range(1, n+1): result += i return result Biên dịch tệp .pyx thành một module Python bằng Cython: cythonize i sum.pyx Sau khi biên dịch, bạn có thể sử dụng module này trong Python như sau: import sum total = sum.sum_up_to_n(100) print("Tổng các số từ 1 đến 100 là:", total) Khi chạy mã Python trên, bạn sẽ nhận được kết quả là: Tổng các số từ 1 đến 100 là: 5050 Trong ví dụ này, chúng ta đã sử dụng Cython để tạo một hàm sum_up_to_n hiệu quả hơn cho việc tính tổng các số từ 1 đến n. Điều này giúp tăng tốc độ tính toán so với việc sử dụng một hàm Python thông thường. 3.1.3. Thư viện Numba: Numba là trình biên dịch đúng lúc dành cho Python, hoạt động tốt nhất trên mã sử dụng mảng, hàm và vòng lặp NumPy. Cách phổ biến nhất để sử dụng Numba là thông qua bộ sưu tập các trang trí có thể được áp dụng cho các hàm của bạn để hướng dẫn Numba biên dịch chúng. Khi một lệnh gọi được thực hiện đến một hàm được trang trí bằng Numba, nó sẽ được biên dịch thành mã máy “đúng lúc” để thực thi và sau đó tất cả hoặc một phần mã của bạn có thể chạy ở tốc độ mã máy gốc! Numba là một thư viện giúp tối ưu hóa mã Python thông qua việc biên dịch các hàm thành mã máy JIT (JustInTime). Numba thường thích hợp cho các phép toán số học và các vòng lặp. Ví dụ: from numba import jit 9
@jit(nopython=True) def example_function(x): return x * x Bài tập với Numba: Bài 1: Tính tổng của một danh sách các số: from numba import jit @jit(nopython=True) def sum_of_list(numbers): result = 0 for num in numbers: result += num return result numbers = list(range(1000000)) print("Sum result:", sum_of_list(numbers)) Bài tập 2: Tính tổng của dãy Fibonacci Viết một chương trình sử dụng thư viện Numba để tính tổng của n số Fibonacci đầu tiên, trong đó n được nhập từ bàn phím. Gợi ý: Sử dụng decorator @jit để tối ưu hóa hàm tính số Fibonacci. Tính tổng của n số Fibonacci và in kết quả. from numba import jit @jit def fibonacci(n): if n
3.2.1. Phương pháp Sử dụng SET Sử dụng set thay vì list trong Python có thể mang lại nhiều lợi ích, nhất là khi bạn cần loại bỏ các phần tử trùng lặp hoặc quan tâm đến việc kiểm tra sự tồn tại của một phần tử trong tập hợp một cách hiệu quảSử dụng set thay vì list để kiểm tra sự tồn tại nhanh hơn. nếu bạn chỉ quan tâm đến tính tồn tại của phần tử và không cần thứ t ự. Cách sử dụng set như sau: 1. Khởi tạo một set: my_set = {1, 2, 3, 4, 5} hoặc sử dụng hàm set(): my_set = set([1, 2, 3, 4, 5]) 2. Thêm phần tử vào set: my_set.add(6) 3. Loại bỏ phần tử khỏi set: my_set.remove(3) 4. Kiểm tra sự tồn tại của phần tử trong set: if 4 in my_set: print("4 có trong set.") 5. Lấy độ dài của set: length = len(my_set) 6. Kết hợp hai set: set1 = {1, 2, 3} set2 = {3, 4, 5} union_set = set1.union(set2) 7. Giao của hai set: intersection_set = set1.intersection(set2) 8. Hiệu của hai set: difference_set = set1.difference(set2) 9. Kiểm tra set con hoặc set cha: is_subset = set1.issubset(set2) is_superset = set1.issuperset(set2) 10. Chuyển đổi set thành list và ngược lại: my_list = list(my_set) new_set = set(my_list) 11. Xóa tất cả phần tử trong set: my_set.clear() Chú ý: Nhớ rằng các phần tử trong set là duy nhất và không theo thứ tự, điều này có thể dẫn đến thứ tự khác nhau khi bạn in set. Bài tập minh họa: Bài tập 1: Tính tổng của các phần tử duy nhất 11
Viết một hàm nhận vào một danh sách và trả về tổng của các phần tử duy nhất trong danh sách. def unique_elements_sum(input_list): unique_set = set(input_list) return sum(unique_set) # Test my_list = [1, 2, 3, 2, 4, 5, 6, 4] result = unique_elements_sum(my_list) print(result) #kết quả : 21 Bài tập 2: Kiểm tra hai set có phần tử chung hay không Viết một hàm nhận vào hai set và trả về True nếu chúng có ít nhất một phần tử chung, ngược lại trả về False. def has_common_element(set1, set2): return len(set1.intersection(set2)) > 0 # Test set_a = {1, 2, 3, 4} set_b = {3, 4, 5, 6} result = has_common_element(set_a, set_b) print(result) Bài tập 3: Đếm số lần xuất hiện của mỗi phần tử trong danh sách Viết một hàm nhận vào một danh sách và trả về một từ điển, trong đó key là phần tử và value là số lần xuất hiện của phần tử đó trong danh sách. def count_occurrences(input_list): element_count = {} for element in input_list: element_count[element] = element_count.get(element, 0) + 1 return element_count # Test my_list = [1, 2, 3, 2, 4, 5, 6, 4] result = count_occurrences(my_list) print(result) 12
3.2.2. Đối với các tìm kiếm phức tạp, xem xét việc sử dụng collections module, như defaultdict hoặc Counter. collections module trong Python cung cấp các lớp đặc biệt hữu ích hơn so với các kiểu dữ liệu cơ bản như list, tuple, set và dict. Dưới đây là một số cách sử dụng các lớp quan trọng trong collections module: 1. Counter: Đếm số lần xuất hiện của các phần tử trong iterable. “Counter” là một subclass của dict cung cấp công cụ mạnh mẽ cho việc đếm đối tượng không chỉ trong danh sách mà còn trong bất kỳ iterables nào. “Counter” tự động đếm số lần mỗi phần tử xuất hiện và lưu trữ chúng dưới dạng một dictionary. Điều này làm cho việc thực hiện các tìm kiếm phức tạp như tìm kiếm phần tử xuất hiện nhiều nhất, tìm kiếm phần tử không xuất hiện trong danh sách trở nên đơn giản và hiệu quả hơn. from collections import Counter my_list = [1, 2, 3, 2, 4, 5, 6, 4] counter = Counter(my_list) # In số lần xuất hiện của mỗi phần tử print(counter) # Truy cập số lần xuất hiện của một phần tử cụ thể print(counter[2]) # In ra phần tử xuất hiện nhiều nhất print("Phần tử xuất hiện nhiều nhất là:", counter.most_common(1)[0][0]) 2. defaultdict: Một subclass của dict cho phép đặt giá trị mặc định cho các key mới. “defaultdict” là một subclass của dict trong Python, cho phép bạn khởi tạo một giá trị mặc định cho các key không tồn tại. Điều này thường hữu ích khi bạn muốn đếm số lần xuất hiện của mỗi phần tử trong một dãy hoặc theo dõi các tần suất xuất hiện của các phần tử. Ví dụ, bạn có thể sử dụng defaultdict(int) để tạo một dictionary với giá trị mặc định là 0 cho mỗi key. from collections import defaultdict # Khởi tạo defaultdict với giá trị mặc định là list rỗng my_dict = defaultdict(list) # Thêm một phần tử vào dict 13
my_dict['key'].append(1) my_dict['key'].append(2) Ví dụ minh họa: Đếm số lần xuất hiện của mỗi chữ cái trong một chuỗi: from collections import defaultdict text = "hello world" char_count = defaultdict(int) for char in text: char_count[char] += 1 print(char_count) 3. namedtuple: Tạo một tuple có tên giúp làm cho code dễ đọc hơn. Một số lợi ích của việc sử dụng “namedtuple” bao gồm: Dễ đọc và dễ hiểu: Bạn có thể truy cập trường bằng tên thay vì chỉ số, điều này làm cho mã của bạn dễ đọc hơn và dễ hiểu hơn. Tiết kiệm bộ nhớ: namedtuple tiêu tốn ít bộ nhớ hơn so với lớp thông thường vì nó không cần lưu trữ thông tin về các phương thức. Khả năng thay đổi dữ liệu: Mặc dù namedtuple là không thay đổi (immutable), nhưng bạn vẫn có thể thay đổi giá trị của các trường bằng cách tạo một thực thể mới hoặc sử dụng phương thức _replace. Cú pháp để tạo một “namedtuple” như sau from collections import namedtuple # Cú pháp: namedtuple('Tên', ['trường1', 'trường2', ...]) TênBảnGhi = namedtuple('TênBảnGhi', ['trường1', 'trường2', ...]) # Định nghĩa namedtuple Person = namedtuple('Person', ['name', 'age', 'gender']) # Tạo một đối tượng Person person = Person(name='John', age=30, gender='Male') # Truy cập các trường bằng tên print(person.name) print(person.age) Ví dụ minh họa: Quản lý thông tin sách trong thư viện Viết một chương trình Python để quản lý thông tin về các sách trong thư viện bằng cách sử dụng namedtuple. Chương trình của bạn cần có các tính năng sau: 1. Tạo namedtuple có tên là Book với các trường sau: id: Mã số sách (kiểu int) title: Tiêu đề sách (kiểu str) 14
author: Tác giả của sách (kiểu str) genre: Thể loại của sách (kiểu str) year: Năm xuất bản của sách (kiểu int) 2. Tạo một danh sách books chứa thông tin của một số sách (ít nhất 5 sách). 3. Viết hàm print_book_info để in ra thông tin của mỗi sách trong danh sách books. 4. Viết hàm find_books_by_author để tìm tất cả các sách của một tác giả cụ thể và trả về danh sách các sách đó. 5. Thực hiện một số thao tác trên danh sách books như thêm sách mới, xóa sách, sửa thông tin của sách, và in ra số lượng sách hiện có trong thư viện. from collections import namedtuple # 1. Tạo namedtuple Book = namedtuple('Book', ['id', 'title', 'author', 'genre', 'year']) # 2. Tạo danh sách books books = [ Book(id=1, title='To Kill a Mockingbird', author='Harper Lee', genre='Fiction', year=1960), Book(id=2, title='1984', author='George Orwell', genre='Science Fiction', year=1949), Book(id=3, title='Pride and Prejudice', author='Jane Austen', genre='Romance', year=1813), Book(id=4, title='The Great Gatsby', author='F. Scott Fitzgerald', genre='Fiction', year=1925), Book(id=5, title='The Catcher in the Rye', author='J.D. Salinger', genre='Fiction', year=1951) ] # 3. Hàm in ra thông tin sách def print_book_info(books): for book in books: print(f"ID: {book.id}, Title: {book.title}, Author: {book.author}, Genre: {book.genre}, Year: {book.year}") # 4. Hàm tìm sách theo tác giả def find_books_by_author(books, author): author_books = [book for book in books if book.author == author] return author_books # 5. Thực hiện các thao tác khác trên danh sách books # Thêm sách mới new_book = Book(id=6, title='Harry Potter and the Sorcerer\'s Stone', author='J.K. Rowling', genre='Fantasy', year=1997) books.append(new_book) 15
# Xóa sách books.remove(find_books_by_author(books, 'Jane Austen')[0]) # Sửa thông tin sách book_to_edit = find_books_by_author(books, 'J.D. Salinger')[0] if book_to_edit: books.remove(book_to_edit) updated_book = Book(id=5, title='The Catcher in the Rye', author='J.D. Salinger', genre='Comingofage', year=1951) books.append(updated_book) # In ra số lượng sách hiện có trong thư viện print("Số lượng sách hiện có trong thư viện:", len(books)) # In ra thông tin tất cả sách print_book_info(books) 4. deque: Doubleended queue, hữu ích khi bạn cần thực hiện các thao tác thêm và loại bỏ ở cả hai đầu của hàng đợi một cách hiệu quả, ví dụ như việc triển khai hàng đợi, stack, hoặc các thuật toán đòi hỏi việc làm việc với dữ liệu ở cả hai đầu. from collections import deque my_deque = deque([1, 2, 3, 4, 5]) my_deque.append(6) # Thêm phần tử vào cuối my_deque.appendleft(0) # Thêm phần tử vào đầu my_deque.pop() # Xóa phần tử từ cuối print(my_deque) ví dụ minh họa: Cho một chuỗi, viết một chương trình Python để tìm chuỗi con dài nhất mà không có ký tự nào được lặp lại. Ví dụ: Nếu chuỗi nhập vào là: "abcabcbb", kết quả sẽ là "abc", vì "abc" là chuỗi con dài nhất không có ký tự lặp lại. from collections import deque def longest_unique_substring(input_str): max_length = 0 max_substring = "" seen = set() char_deque = deque() for char in input_str: while char in seen: seen.remove(char_deque.popleft()) char_deque.append(char) seen.add(char) if len(char_deque) > max_length: max_length = len(char_deque) 16
max_substring = ''.join(char_deque) return max_substring # Nhập chuỗi từ người dùng input_str = input("Nhập vào một chuỗi: ") # Tìm chuỗi con dài nhất không có ký tự lặp lại result = longest_unique_substring(input_str) print("Chuỗi con dài nhất không có ký tự lặp lại là:", result) Bài tập vận dụng: Bài 1: Tìm chuỗi con có số lần xuất hiện nhiều nhất trong một đoạn văn bản. from collections import defaultdict, Counter import re def find_most_common_substring(text, substring_length): # Sử dụng defaultdict để đếm số lần xuất hiện của mỗi chuỗi con substring_count = defaultdict(int) # Lấy tất cả các chuỗi con có độ dài là substring_length từ đoạn văn bản substrings = [text[i:i+substring_length] for i in range(len(text) substring_length+1)] # Đếm sự xuất hiện của từng chuỗi con for substring in substrings: substring_count[substring] += 1 # Sử dụng Counter để tìm chuỗi con có số lần xuất hiện nhiều nhất most_common_substring_count = Counter(substring_count) most_common_substring = most_common_substring_count.most_common(1)[0][0] occurrences = most_common_substring_count[most_common_substring] # In kết quả print(f"Most common substring: '{most_common_substring}' with {occurrences} occurrences.") # Test sample_text = "ababcababababcabc" substring_length = 3 find_most_common_substring(sample_text, substring_length) Trong ví dụ này, chúng ta sử dụng defaultdict để đếm số lần xuất hiện của mỗi chuỗi con có độ dài là substring_length. Sau đó, chúng ta sử dụng Counter để tìm ra chuỗi con có số lần xuất hiện nhiều nhất. Việc sử dụng defaultdict giúp chúng ta tránh tình trạng key chưa tồn tại trong từ điển, và Counter giúp đơn giản hóa việc tìm kiếm chuỗi con có số lần xuất hiện nhiều nhất. Bài 2: Đếm số lần xuất hiện của các từ trong một đoạn văn bản, bỏ qua các từ phổ biến (stop words): 17
Viết một chương trình sử dụng defaultdict và Counter để đếm số lần xuất hiện của các từ trong một đoạn văn bản. Tuy nhiên, bạn sẽ bỏ qua các từ phổ biến (stop words) như "the", " and", "is", v.v. In ra 10 từ có số lần xuất hiện nhiều nhất (loại bỏ stop words). from collections import defaultdict, Counter def count_words_without_stopwords(text, stop_words): # Sử dụng defaultdict để đếm số lần xuất hiện của mỗi từ word_count = defaultdict(int) # Tách các từ từ đoạn văn bản words = text.lower().split() # Đếm sự xuất hiện của từng từ, bỏ qua stop words for word in words: if word not in stop_words: word_count[word] += 1 # Sử dụng Counter để tìm 10 từ có số lần xuất hiện nhiều nhất top_words = Counter(word_count).most_common(10) # In kết quả print("Top 10 words without stop words:") for word, count in top_words: print(f"{word}: {count}") # Test sample_text = "This is a sample text, and it contains some common words like 'the' and 'is'." stop_words = {'the', 'and', 'is', 'it', 'in', 'a', 'this', 'to', 'of', 'like'} count_words_without_stopwords(sample_text, stop_words) Trong bài tập này, defaultdict được sử dụng để đếm số lần xuất hiện của từng từ, và Counter được sử dụng để tìm ra 10 từ có số lần xuất hiện nhiều nhất (loại bỏ stop words). Bạn có thể cải tiến chương trình bằng cách thêm vào danh sách stop words hoặc điều chỉnh các yếu tố khác theo yêu cầu của mình. Sử dụng defaultdict hoặc Counter trong collections module cho các tác vụ đếm hoặc theo dõi thông tin về sự xuất hiện của các phần tử. Dưới đây là ví dụ về cách sử dụng defaultdict và Counter từ module collections để thực hiện các tác vụ đếm hoặc theo dõi thông tin về sự xuất hiện của các phần tử: Sử dụng defaultdict để đếm sự xuất hiện của các phần tử: from collections import defaultdict # Khởi tạo defaultdict với giá trị mặc định là 0 element_count = defaultdict(int) # Danh sách các phần tử my_list = [1, 2, 3, 2, 4, 5, 6, 4] # Đếm sự xuất hiện của các phần tử trong danh sách for element in my_list: 18
element_count[element] += 1 # In số lần xuất hiện của mỗi phần tử print(element_count) # Truy cập số lần xuất hiện của một phần tử cụ thể print(element_count[2]) Sử dụng Counter để đếm sự xuất hiện của các phần tử: from collections import Counter # Danh sách các phần tử my_list = [1, 2, 3, 2, 4, 5, 6, 4] # Sử dụng Counter để đếm sự xuất hiện của các phần tử element_count = Counter(my_list) # In số lần xuất hiện của mỗi phần tử print(element_count) # Truy cập số lần xuất hiện của một phần tử cụ thể print(element_count[2]) Cả hai phương thức đều giúp bạn dễ dàng đếm sự xuất hiện của các phần tử trong một iterable và cung cấp thông tin chi tiết về số lần xuất hiện của từng phần tử. Chọn defaultdict khi bạn muốn tự định nghĩa giá trị mặc định cho key mới, và chọn Counter khi bạn chỉ quan tâm đến việc đếm sự xuất hiện của các phần tử. Bài 3: Đếm số lần xuất hiện của mỗi từ trong một đoạn văn bản: Cho một đoạn văn bản, hãy viết một chương trình sử dụng defaultdict hoặc Counter để đếm số lần xuất hiện của mỗi từ. In ra các từ và số lần xuất hiện tương ứng. from collections import defaultdict, Counter import re def count_word_occurrences(text): # Sử dụng defaultdict để đếm số lần xuất hiện của mỗi từ word_count = defaultdict(int) # Lọc ra các từ từ đoạn văn bản words = re.findall(r'\b\w+\b', text.lower()) # Đếm sự xuất hiện của từng từ for word in words: word_count[word] += 1 # In kết quả for word, count in word_count.items(): print(f"{word}: {count}") # Test sample_text = "This is a sample text. This text contains some sample words." count_word_occurrences(sample_text) 19
3.3. Phương pháp tối ưu hóa các vòng lặp. Tránh sử dụng vòng lặp lồng nhau nếu có thể, vì chúng có thể làm gia tăng độ phức tạp của chương trình. Sử dụng comprehensions (list comprehensions, dictionary comprehensions) để làm giảm độ dài và tăng hiệu suất của mã nguồn. 3.3.1. Sử dụng List Comprehension: Thay vì sử dụng vòng lặp lồng nhau để tạo ra một danh sách mới, bạn có thể sử dụng List Comprehension. Cho phép tạo các list mới một cách nhanh chóng và dễ đọc. Cú pháp List Comprehension có dạng: new_list = [expression for item in iterable if condition] Trong đó: expression là biểu thức được tính toán để tạo ra các phần tử của list mới. item là biến lặp qua từng phần tử trong iterable. iterable là một iterable như list, tuple, hoặc range. condition là một điều kiện để lọc ra các phần tử (không bắt buộc). Ví dụ 1: Tạo list chứa bình phương của các số từ 1 đến 10: squares = [x**2 for x in range(1, 11)] print(squares) Ví dụ 2: Lọc ra các số chẵn từ 1 đến 20: even_numbers = [x for x in range(1, 21) if x % 2 == 0] print(even_numbers) Ví dụ 3: Tạo list chứa các chữ cái viết thường từ một chuỗi: string = "Hello World" lowercase_letters = [char for char in string if char.islower()] print(lowercase_letters) Ví dụ 4: Tạo list chứa các tuple là cặp (số, bình phương của số) từ 1 đến 5: pairs = [(x, x**2) for x in range(1, 6)] print(pairs) Ví dụ 5: Chuyển đổi các phần tử trong list thành kiểu dữ liệu khác: numbers = ['1', '2', '3', '4', '5'] int_numbers = [int(x) for x in numbers] print(int_numbers) List comprehension là một cách nhanh chóng và súc tích để tạo list mới từ các iterable và điều kiện lọc. Nó giúp mã của bạn trở nên ngắn gọn và dễ đọc hơn. Bài tập vận dụng: 20