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