Sáng kiến kinh nghiệm THPT: Một số giải pháp tăng độ chạy code python

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

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 đủ

Sáng kiến "Một số giải pháp tăng độ chạy code python" được hoàn thành với mục tiêu nhằm rèn luyện kỹ năng phân tích bài toán, ứng dụng kiến thức tin học vào giải quyết các bài toán; Hiểu được mỗi quan hệ chặt chẽ giữa các môn tin học nói riêng cũng như giữa các ngành khoa học nói chung; Rèn luyện cho học sinh tư duy logic, khoa học; ham hiểu biết, tìm tòi, sáng tạo, say mê môn học.

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ố giải pháp tăng độ chạy code python

cv SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN TRƯỜNG THPT NGHI LỘC 3 -------------- SÁNG KIẾN KINH NGHIỆM Tên đề tài: MỘT SỐ GIẢI PHÁP TĂNG TỐC ĐỘ CHẠY CODE PYTHON Họ và tên: Hà Thi Hợi MÔN: TIN HỌC Số điện thoại: 0947131136 Năm thực hiện: 2023 - 2024
MỤC LỤC MỤC LỤC ................................................................................................................... 2 PHẦN I. ĐẶT VẤN ĐỀ .............................................................................................. 4 1. LÝ DO CHỌN ĐỀ TÀI .......................................................................................... 4 2. MỤC ĐÍCH NGHIÊN CỨU .................................................................................. 4 3. ĐỐI TƯỢNG, PHẠM VI VÀ THỜI GIAN NGHIÊN CỨU .............................. 5 4. GIẢ THUYẾT KHOA HỌC.................................................................................. 5 5. NHIỆM VỤ VÀ PHƯƠNG PHÁP NGHIÊN CỨU: ........................................... 5 6. ĐÓNG GÓP MỚI CỦA ĐỀ TÀI ........................................................................... 6 PHẦN II. NỘI DUNG NGHIÊN CỨU ..................................................................... 7 CHƯƠNG 1. CƠ SỞ LÝ LUẬN VÀ THỰC TIỄN ................................................. 7 1. CƠ SỞ LÝ LUẬN CỦA ĐỀ TÀI............................................................................ 7 2. CƠ SỞ THỰC TIỄN CỦA ĐỀ TÀI ....................................................................... 8 CHƯƠNG 2. MỘT SỐ GIẢI PHÁP ....................................................................... 10 1. TÌM HIỂU PYTHON............................................................................................ 10 2. MỘT SỐ GIẢI PHÁP TĂNG TỐC ĐỘ CHẠY CODE PYTHON................... 12 2.1.Dùng cấu trúc dữ liệu và thuật toán phù hợp ................................................. 12 2.1.1. Tại sao cấu trúc dữ liệu cần thiết? ................................................................ 12 2.1.2 Tại sao cần dùng thuật toán phù hợp? .......................................................... 17 a. Thuật toán tối ưu .................................................................................................. 17 b. Độ phức tạp của thuật toán và Lựa chọn cách giải thuật ................................ 17 c. Quy trình để viết một thuật toán......................................................................... 19 d. Một số loại thuật toán cơ bản và những điều cần biết ...................................... 20 - Thuật toán sàng nguyên tố với Python ............................................................... 20 - Khi nào cần dùng đến sàng nguyên tố? .............................................................. 23 - Thuật toán sắp xếp của Python ........................................................................... 23 - Thuật toán tìm kiếm tuyến tính .......................................................................... 30 - Thuật toán tìm kiếm nhị phân............................................................................. 32 - Đánh giá độ phức tạp của các thuật toán ........................................................... 35 2.2.Dùng list comprehension thay vì vòng for ....................................................... 36 2
2.3 Hạn chế dùng biến global, Gán kết hợp nhiều biến ........................................ 36 2.4. Nối chuỗi bằng join, sử dụng import hợp lý, dùng 1 thay cho infinity loop 37 MINH HỌA MỘT SỐ CODE ................................................................................. 38 4. KHẢO SÁT SỰ CẤP THIẾT VÀ TÍNH KHẢ THI CỦA CÁC GIẢI PHÁP . 47 5. KHẢ NĂNG ỨNG DỤNG VÀ HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI. ........ 50 PHẦN III. KẾT LUẬN VÀ NHỮNG KIẾN NGHỊ .............................................. 51 PHỤ LỤC 1 ............................................................................................................... 53 PHỤ LỤC 2 ............................................................................................................... 56 1. PHIẾU KHẢO SÁT CÁC GIẢI PHÁP CỦA SÁNG KIẾN ............................. 56 2. HÌNH ẢNH BIỂU ĐỒ KHẢO SÁT TÍNH KHẢ THI VÀ CẤP THIẾT ........ 57 4. 20 ĐOẠN CODE PYTHON NÊN THUỘC LÒNG .......................................... 61 6. TÀI LIỆU THAM KHẢO .................................................................................... 70 DANH MỤC CÁC CHỮ VIẾT TẮT TRONG ĐỀ CƯƠNG ................................ 70 3
PHẦN I. ĐẶT VẤN ĐỀ 1. LÝ DO CHỌN ĐỀ TÀI - Theo chương trình GDPT 2018 thì tin học lớp 10 là học ngôn ngữ lập trình Python. - Python là ngôn ngữ mã nguồn mở và cho phép cộng đồng có thể đóng góp bằng cách bổ sung các module, các kho hàm số, thư viện thuật toán. Điều này làm cho Python phát triển bùng nổ trong giới khoa học và giáo dục đại học. Đặc biệt trong một số ngành mũi nhọn của CNTT như IoT, trí tuệ nhân tạo (AI), dữ liệu lớn (big data) và CMCN 4.0, các phát triển rất nhanh thời gian gần đây của công nghệ đều gắn liền với Python. - Qua việc bồi dưỡng học sinh giỏi và dạy tin học ở trường, bản thân tôi nhận thấy Python là một ngôn ngữ lập trình có cú pháp chặt chẽ, đơn giản dễ hiểu và có nhiều công cụ hỗ trợ . Nhưng tốc độ chạy chương trình chậm hơn rất nhiều so với ngôn ngữ lập trình khác như: C, C++, Pascal... - Để đạt được những kết quả cao trong các kì thi là việc khó. Vì ngoài tiêu chí chấm bài đúng thì còn có giới hạn về thời gian. Làm cách nào giúp cho học sinh nắm được các kiến thức và kỹ năng phân tích các bài bài toán, tìm ra lời giải cho bài toán và lập trình trên ngôn ngữ lập trình chạy nhanh nhất. - Một vấn đề nữa cũng là rào cản đối với việc các học sinh tiếp cận với các đề thi học sinh đó là: kỹ năng đọc đề, phân tích đề, tìm ra lời giải cho bài toán chưa tốt. - Từ thực tế trên, trong quá trình bồi dưỡng và giảng dạy tôi luôn băn khoăn trăn trở làm thế nào để giúp các em tìm ra được lời giải chính xác nhất và nhanh nhất của các bài toán môn Tin học. Điều đó đã thúc đẩy tôi trong quá trình bồi dưỡng HSG và giảng dạy phải tập trung rèn luyện cho học sinh. Đặc biệt tôi quan tâm đến kiến thức để làm tăng tôc độ chạy code trên NNLT python. Vì thế nên tôi đã nghiên cứu và chọn đề tài “Một số giải pháp tăng độ chạy code python” . 2. MỤC ĐÍCH NGHIÊN CỨU Trong phạm vi đề tài của mình, chúng tôi nghiên cứu, tìm tòi một số giải pháp rèn luyện kĩ năng và phát triển năng lực giải quyết bài toán tối ưu trên NNLT python cho học sinh: + Rèn luyện kỹ năng phân tích bài toán, ứng dụng kiến thức tin học vào giải quyết các bài toán . + Hiểu được mỗi quan hệ chặt chẽ giữa các môn tin học nói riêng cũng như giữa các ngành khoa học nói chung. + Rèn luyện cho học sinh tư duy logic, khoa học; ham hiểu biết, tìm tòi, sáng tạo, say mê môn học. + Cũng qua đề tài, tôi muốn cùng đồng nghiệp trao đổi, trau dồi chuyên môn nhằm góp phần nâng cao trình độ chuyên môn nghiệp vụ và khả năng mở rộng kiến thức. 4
3. ĐỐI TƯỢNG, PHẠM VI VÀ THỜI GIAN NGHIÊN CỨU 3.1. Đối tượng nghiên cứu + Học sinh lớp 10 Trường THPT Nghi Lộc 3 + Học sinh trong đội tuyển HSG của Trường THPT Nghi Lộc 3 3.2 Thời gian nghiên cứu Từ Tháng 11 năm 2023 đến 15 tháng 3 năm 2024 3.2. Phạm vi nghiên cứu. + Khả năng học lập trình của học sinh lớp 10 và học sinh trong đội tuyển HSG. trường THPT Nghi Lộc 3 . + Đề xuất một số giải pháp nhằm nâng cao chất lượng học lập trình cho học sinh khối 10 và học sinh trong đội tuyển HSG. 4. GIẢ THUYẾT KHOA HỌC - Nếu đề tài được áp dụng thành công thì sẽ giúp học sinh nâng cao chất lượng học tập bộ môn lập trình trên NNLT python. - Góp phần giúp nhà trường nâng cao chất lượng giáo dục học sinh. Đạc biệt là nâng cao chất lượng đội tuyển HS giỏi. - Giúp cho học sinh có đủ khả năng phân tích và tìm ra cách lập trình tối ưu nhất, chạy nhanh nhất trên NNLT python . 5. NHIỆM VỤ VÀ PHƯƠNG PHÁP NGHIÊN CỨU: 5.1. Nhiệm vụ nghiên cứu Sáng kiến kinh nghiệm có nhiệm vụ sau đây: - Phân tích rõ thực trạng về việc dạy học tin học lớp 10 THPT. - Xây dựng KHDH theo năng lực. - Xây dựng các hoạt động hình thành kiến thức khi dạy học tin học theo định hướng phát triển năng lực cho học sinh lớp 10 THPT - Kết quả thực nghiệm. 5.2. Phương pháp nghiên cứu  Phương pháp thống kê, phân tích - tổng hợp, so sánh - đối chiếu.  Phương pháp nghiên cứu lý luận: Sưu tầm, đọc tài liệu tham khảo, nghiên cứu các văn bản liên quan đến các vấn đề của đề tài này.  Phương pháp nghiên cứu thực tiễn: Quan sát, điều tra - khảo sát, thực nghiệm sư phạm, tổng kết kinh nghiệm, tham vấn chuyên gia. * Nhiệm vụ nghiên cứu:  Nghiên cứu những cơ sở lí luận và thực tiễn của đề tài 5
 Đề xuất các giải pháp, báo cáo thành chuyên đề trong các lần họp chuyên môn để cùng đồng nghiệp bổ sung những thiếu sót của đề tài.  Giao lưu học hỏi, trao đổi kinh nghiệm với đồng môn ở các trường lân cận.  Thực nghiệm dạy học.  Thống kê, phân tích xử lí số liệu từ thực nghiệm sư phạm. 6. ĐÓNG GÓP MỚI CỦA ĐỀ TÀI - Góp phần làm rõ cơ sở lí luận về dạy học phát triển năng lực giải quyết bài toán tối ưu , tăng độ chạy code trên ngôn ngữ lập trình python. - Đưa ra được các giải pháp nâng cao hiệu quả dạy học phát triển năng lực giải quyết bài toán trên NNLT python cho học sinh. - Thông qua việc hướng dẫn giải các bài toán giáo viên rèn luyện kỹ năng xây dựng và lựa chọn thuật toán cho học sinh bằng cách định hướng, uốn nắn, trau chuốt từng lời giải từng bài tập, qua đó góp phần tạo niềm tin và hứng thú học tập. 6
PHẦN II. NỘI DUNG NGHIÊN CỨU CHƯƠNG 1. CƠ SỞ LÝ LUẬN VÀ THỰC TIỄN 1. CƠ SỞ LÝ LUẬN CỦA ĐỀ TÀI 1.1 Khái niệm bài toán trong tin học , năng lực giải quyết vấn đề. - Bài toán là một việc nào đó mà con người muốn máy tính thực hiện. Các yếu tố của một bài toán: + Input: Thông tin đã biết, thông tin đưa vào máy tính. + Output: Thông tin cần tìm, thông tin lấy ra từ máy tính. - Theo định nghĩa trong đánh giá PISA (2012): “Năng lực giải quyết vấn đề là khả năng của một cá nhân hiểu và giải quyết tình huống vấn đề khi mà giải pháp giải quyết chưa rõ ràng. Nó bao gồm sự sẵn sàng tham gia vào giải quyết tình huống vấn đề đó – thể hiện tiềm năng là công dân tích cực và xây dựng”. - Giải quyết vấn đề là hoạt động trí tuệ được coi là trình độ phức tạp và cao nhất về nhận thức, vì cần huy động tất cả các năng lực trí tuệ của cá nhân. Để giải quyết vấn đề, chủ thể phải huy động trí nhớ, tri giác, lý luận, khái niệm hóa, ngôn ngữ, đồng thời sử dụng cả cảm xúc, động cơ, niềm tin ở năng lực bản thân và khả năng kiểm soát được tình thế - Chúng ta có thể hiểu năng lực năng lực giải quyết vấn đề của học sinh là: Khả năng của học sinh phối hợp vận dụng những kinh nghiệm bản thân, kiến thức, kĩ năng của các môn học trong chương trình trung học phổ thông để giải quyết thành công các tình huống có vấn đề trong học tập và trong cuộc sống của các em với thái độ tích cực. - Năng lực giải quyết vấn đề bao gồm các năng lực thành phần sau: Năng lực hiểu được vấn đề, thu nhận được thông tin từ tình huống thực tiễn; Năng lực chuyển đổi thông tin từ tình huống thực tế về Tin học; Năng lực tìm kiếm chiến lược giải quyết bài toán Tin; Năng lực thực hiện chiến lược để tìm ra kết quả;Năng lực chuyển từ kết quả giải quyết bài toán Tin học sang lời giải của bài toán chứa đựng tình huống thực tiễn; Năng lực đưa ra các bài toán khác. 1.2. Vai trò, ý nghĩa của dạy học phát triển năng lực giải quyết bài toán - Tạo động cơ, gợi động cơ học tập cho học sinh, thông qua các tình huống thực tế, kích thích trí tò mò và mong muốn giải quyết vấn đề của học sinh. - Trực tiếp phát triển năng lực giải quyết vấn đề, đồng thời phát triển các năng lực chung và các năng lực chuyên biệt đặc thù của môn Tin học. - Thực hiện dạy học ứng dụng dụng của Tin học đối với thực tiễn, đây là một trong những định hướng hàng đầu của dạy học ngày nay. 7
- Giúp học sinh thấy được mối quan hệ của Tin học trong thực tiễn, trong đời sống xã hội, phát triển các năng lực về biểu diễn Tin học, năng lực giao tiếp trong quá trình tìm ra các phương pháp nhằm giải quyết vấn đề. - Từ định hướng cho học sinh sưu tầm, thiết kế các bài toán thực tế, từ kiến thức Tin học giúp giáo viên có được nguồn bài tập thực tế phong phú đa dạng trên nhiều lĩnh vựa khác nhau trong cuộc sống và nâng cao trình độ hiểu biết của chính giáo viên đối với môn học, góp phần đổi mới phương pháp dạy học và phương pháp kiểm tra đánh giá kết quả của học sinh. 1.3. Quy trình giải bài toán trên máy tính Hiện nay việc giải bài toán trên máy tính được tiến hành bởi 5 bước như sau: Xác định bài toán → Lựa chọn, thiết kế thuật toán → Viết chương trình → Hiệu chỉnh → Viết tài liệu. Bước 1: Xác định bài toán: mỗi bài toán được đặc tả bởi hai thành phần là Input và Output. Việc xác định bài toán chính là xác định rõ hai thành phần này và mối quan hệ giữa chúng. Các thông tin đó cần được nghiên cứu cẩn thận để có thể lựa chọn thuật toán, cách thể hiện các đại lượng đã cho, các đại lượng phát sinh trong quá trình giải bài toán và ngôn ngữ lập trình thích hợp. Bước 2: Lựa chọn, thiết kế thuật toán: là bước quan trọng nhất để giải một bài toán. Mỗi thuật toán chỉ giải một bài toán nào đó, nhưng có thể có nhiều thuật toán khác nhau cùng giải một bài toán. Do đó người dùng cần thiết kế hoặc chọn một thuật toán phù hợp đã có để giải bài toán cho trước. Bước 3: Viết chương trình: Việc viết chương trình là tổng hợp giữa việc lựa chọn cách tổ chức dữ liệu và sử dụng ngôn ngữ lập trình để điễn đạt đúng thuật toán. Khi viết chương trình ta nên chọn một ngôn ngữ lập trình hoặc một phần mềm chuyên dụng thích hợp với thuật toán. Viết chương trình trong ngôn ngữ nào thì cân phải tuân theo đúng quy định ngữ pháp của ngôn ngữ đó. Bước 4: Hiệu chỉnh là việc thử chương trình với 1 số bộ Input tương ứng với Output đã biết trước, từ đó ta xác định được các lỗi của chương trình. Mỗi bộ Input – Output được gọi là các Test. Bước 5: Viết tài liệu: Tài liệu rất có ích cho người sử dụng chương trình và cho việc đề xuất những khả năng hoàn thiện thêm. Các bước có thể lặp đi lặp lại nhiều lần cho đến khi ta cho rằng chương trình đã làm việc đúng đắn và hiệu quả. 2. CƠ SỞ THỰC TIỄN CỦA ĐỀ TÀI 2.1 Thuận lợi. - Được sự quan tâm sâu sát của ban giám hiệu và tổ bộ môn trong việc định hướng thường xuyên việc đổi mới phương pháp giảng dạy phù hợp chương trình giáo dục phổ thông mới. 8
- Cơ sở vật chất, trang thiết bị đáp ứng tương đối đầy đủ nhu cầu giảng dạy và học tập - Các tiết dạy môn Tin học được bố trí tại phòng học bộ môn thuận lợi việc khai thác thế mạnh công nghệ thông tin. - Đa số học sinh và gia đình các em đã có điện thoại thông minh hoặc là máy tính. Việc học lập trình thì điện thoại hay trên máy tính là thiết bị không thể thiếu. - Với điểm mới quy định trong thông tư 32 ban hành điều lệ trường THCS, THPT và trường phổ thông nhiều cấp học - học sinh được sử dụng điện thoại thông minh trong lớp học nếu giáo viên cho phép đó là bước đột phá, phù hợp với xu thế giáo dục hiện nay.Vì thế điều chỉnh này hữu ích để phát huy những nền tảng đã có sẵn của các nhà trường trong việc ứng dụng CNTT dạy học.Việc cho phép học sinh sử dụng smartphone hay có thể máy tính bảng, ipad trong giờ học-như vậy đây trở thành một dụng cụ học tập hữu ích, hữu dụng. Xa hơn điện thoại thông minh như “cuốn sách điện tử”, người học có thể truy cập, cập nhật những kiến thức mới, hơi thở của thời đại. Giáo viên có thể tương tác, giải đáp những thắc mắc của học sinh một cách nhanh chóng. - Xã hội hiện nay với sự phát triển như vũ bão của công nghệ thì học sinh không khó để tìm được cho mình một ứng dụng học lập trình Python . Có thể kể đến như: Pydroid 3, Python 3, Qpython3L, Coding Python, Learn Python… - Hệ thống và nền tảng tương tác trực tuyến hoàn toàn miễn phí cho phép người dùng học tập, thực hành và đánh giá các kỹ năng lập trình ngay lập tức. Nó trở thành nguồn tài nguyên vô tận để học sinh có thể trau dồi kỹ năng lập trình. Ngoài ra, còn có nhiều trang web dạy học lập trình online, rèn luyện kĩ năng lập trình mà học sinh có thể học được trên điện thoại, học sinh được trực tiếp test code của mình, đánh giá mức độ bài làm của mình như thế nào. 2.2 Khó khăn. - Tại trường THPT Nghi Lôc 3 khó khăn lớn nhất của bộ môn Tin học đó là đang thiếu máy vi tính phục vụ cho việc dạy và học. Hiện tại, trường bố trí 2 phòng máy tính, mỗi phòng có 20 máy tính. Nhưng số máy hoạt động tương đối ổn định chỉ tầm trong 10-15 máy, số còn lại nếu hoạt động đã hết niên hạn sử dụng (trên 5 năm) nhưng chưa được nâng cấp hay thay mới kịp thời. Chưa kể, có nhiều máy vi tính đã được trang cấp hơn 10 năm và được nhà trường nâng cấp theo kiểu “chắp vá” nên nhanh chóng xuống cấp có cấu hình thấp, chạy rất chậm, hay tắt máy giữa chừng ảnh hưởng đến chất lượng bài giảng của giáo viên cũng như việc học thực hành của học sinh. Cũng do thiếu máy nên nhóm Tin học khá “đau đầu” khi xếp lịch học để các tiết thực hành tin học không bị chồng chéo, trùng lặp giữa các lớp. Trước mắt, các giáo viên chỉ còn cách bố trí 2-3 em học trên một máy vi tính, hoặc một lớp chia thành hai nhóm mới có đủ máy để học. Hơn nữa đặc thù của môn Tin học là liên quan đến máy tính. Sau mỗi bài học các em cần được thực hành để hiểu rõ kiến thức và nâng cao kĩ năng. Đặc biệt 9
đối với môn tin thì “Học đi đôi với hành” là cực kì cần thiết và quan trọng. Có học lí thuyết nhiều đến đâu, giỏi đến đâu nhưng không có máy tính để thực hành thì việc học chưa thực sự đạt hiệu quả. - Đối với học sinh, một khó khăn nữa trở thành rào cản là có rất nhiều em không thạo vi tính. Các em lóng ngóng mãi mới vào được các chương trình cơ bản. Hóa ra, lâu nay bộ môn tin học trong trường học được dạy theo kiểu “cưỡi ngựa xem hoa”. Lý do, đây chỉ là môn tự chọn và là môn phụ nên học sinh học chỉ để… đối phó. - Học sinh chưa nhận thức được tầm quan trọng của việc học lập trình nên chưa có sự say mê, hứng thú trong việc học. Các em không biết học từ đâu vì thế giới tin học quá đa dạng, mà nhìn công cụ nào cũng thấy lạ lẫm. Không chỉ với tin học, việc học rất dễ gây cảm giác nhàm chán. Bởi vậy, nản và bỏ cuộc là điều thường thấy nếu học sinh không xác định được mục tiêu rõ ràng. Chưa kể học đi học lại mà không có hiệu quả, học sinh sẽ bắt đầu có suy nghĩ tiêu cực về khả năng của bản thân. - Việc học lập trình tương đối khô khan, giáo viên khó thiết kế bài giảng gây hứng thú cho học sinh. CHƯƠNG 2. MỘT SỐ GIẢI PHÁP 1. TÌM HIỂU PYTHON Python đang trở nên phổ biến trong cộng đồng lập trình nhờ có các đặc tính sau: - Ngôn ngữ thông dịch: Python được xử lý trong thời gian chạy bởi Trình thông dịch Python. - Ngôn ngữ hướng đối tượng: Nó hỗ trợ các tính năng và kỹ thuật lập trình hướng đối tượng. - Ngôn ngữ lập trình tương tác: Người dùng có thể tương tác trực tiếp với trình thông dịch python để viết chương trình. - Ngôn ngữ dễ học: Python rất dễ học, đặc biệt là cho người mới bắt đầu. - Cú pháp đơn giản: Việc hình thành cú pháp Python rất đơn giản và dễ hiểu, điều này cũng làm cho nó trở nên phổ biến. - Dễ đọc: Mã nguồn Python được xác định rõ ràng và có thể nhìn thấy bằng mắt. - Di động: Mã Python có thể chạy trên nhiều nền tảng phần cứng có cùng giao diện. - Có thể mở rộng: Người dùng có thể thêm các mô-đun cấp thấp vào trình thông dịch Python. - Có thể cải tiến: Python cung cấp một cấu trúc cải tiến để hỗ trợ các chương trình lớn sau đó là shell-script. Tại sao ngôn ngữ lập trình Python vô cùng phổ biến Python phổ biến vì nhiều lý do. Dưới đây là một cái nhìn sâu sắc hơn về những gì làm cho nó trở nên linh hoạt và dễ sử dụng cho các lập trình viên: 10
- Nó có cú pháp đơn giản bắt chước ngôn ngữ tự nhiên nên dễ đọc và dễ hiểu hơn. Điều này giúp xây dựng các dự án nhanh hơn và cải thiện chúng tốt hơn. - Nó linh hoạt. Python có thể được sử dụng cho nhiều tác vụ khác nhau, từ phát triển web đến học máy. - Nó thân thiện với người mới bắt đầu, khiến Python trở nên phổ biến đối với các lập trình viên mới vào nghề. - Python là mã nguồn mở, có nghĩa là nó được sử dụng và phân phối miễn phí, kể cả cho mục đích thương mại. - Kho lưu trữ các mô-đun và thư viện của Python - các gói mã mà người dùng bên thứ ba đã tạo để mở rộng khả năng của Python - rất rộng lớn và đang phát triển. - Python có một cộng đồng lớn và tích cực đóng góp vào kho mô-đun và thư viện của Python, đồng thời hoạt động như một nguồn tài nguyên hữu ích cho các lập trình viên khác. Cộng đồng hỗ trợ rộng lớn có nghĩa là nếu các lập trình viên gặp khó khăn, việc tìm ra giải pháp là tương đối dễ dàng; ai đó chắc chắn cũng đã gặp phải vấn đề tương tự trước đây. Lợi thế của Python - Python là một ngôn ngữ dễ đọc và đơn giản để hiểu cho các nhà phát triển chưa bao giờ viết code. Do đó, cộng đồng người dùng Python không ngừng phát triển và lớn mạnh. Có rất nhiều học giả và giáo sư trong cộng đồng người dùng Python. Vì vậy, khi xảy ra sự cố, nhà phát triển có thể tập trung vào vấn đề đó và nhận trợ giúp từ những người khác trong cộng đồng mà không phải lo lắng về sự phức tạp của ngôn ngữ. - Python là một ngôn ngữ lập trình miễn phí và mở. Giấy phép nguồn mở được OSI phê chuẩn mà Python được phát triển theo đó làm cho Python trở thành ngôn ngữ tự do sử dụng và phân phối, kể cả cho mục đích thương mại. Nó sẽ làm giảm chi phí của bạn để bảo trì. Trong khi các nhà phát triển có thể chia sẻ, sao chép và thay đổi nó. Đối với cộng đồng Python, đây là cơ hội để chia sẻ kiến thức với các chuyên gia cấp dưới. - Python vô cùng dễ học - Các lập trình viên nói rằng Python rất dễ sử dụng. Mặc dù khi xây dựng các ứng dụng hoặc trò chơi dành cho thiết bị di động, C++ hoặc bất kỳ ngôn ngữ kịch bản điển hình nào khác có thể dễ sử dụng hơn, nhưng Python sẽ tốt hơn để vì nó dễ dàng xây dựng các ứng dụng phía máy chủ, tự động hóa hệ thống xây dựng và thu thập dữ liệu thử nghiệm. - Python có nhiều lựa chọn thư viện và framework, đây là một trong những lợi thế lớn nhất của Python. Từ NumPy đến TensorFlow, thư viện Python được sử dụng cho mọi thứ từ trực quan hóa dữ liệu, học máy, khoa học dữ liệu, xử lý ngôn ngữ tự nhiên và phân tích dữ liệu phức tạp. - Nó sở hữu một thư viện lớn với khả năng quản lý bộ nhớ và thiết kế trống giúp tăng năng suất của nhà phát triển Python. Nhờ đó, các nhà phát triển có thể quản lý cơ sở 11
dữ liệu, tài liệu, trình duyệt web; thực hiện kiểm tra đơn vị và nhiều chức năng khác. Ngoài ra, Python có thể được sử dụng để phát triển nhiều tác vụ, chẳng hạn như phát triển ứng dụng web và máy tính để bàn, phát triển các hệ thống tính toán phức tạp, hệ thống quản lý hỗ trợ cuộc sống, Internet of Things (IoT), trò chơi, v.v. 2. MỘT SỐ GIẢI PHÁP TĂNG TỐC ĐỘ CHẠY CODE PYTHON 2.1.Dùng cấu trúc dữ liệu và thuật toán phù hợp 2.1.1. Cấu trúc dữ liệu Cấu trúc dữ liệu được sử dụng trong các chương trình để dễ dàng hơn trong việc định vị thông tin và lấy thông tin. Cấu trúc dữ liệu là cách các ngôn ngữ lập trình thể hiện các giá trị cơ bản, chúng chứa các kiểu dữ liệu cơ bản như số, chuỗi, boolean..., nó đưa ra cách thức lưu trữ nhiều giá trị trong một biến số. Cấu trúc dữ liệu cũng được sử dụng để phân nhóm và tổ chức cho các cấu trúc khác. Các kiểu dữ liệu cơ bản trong Python bao gồm kiểu số nguyên (int), kiểu số thực (float), kiểu chuỗi (string) và kiểu logic (boolean). Với các kiểu dữ liệu cơ bản này, chúng ta có thể viết các ứng dụng đơn giản với Python. Với các ứng dụng có số lượng các biến nhiều, dữ liệu lớn chúng ta cần tới các cấu trúc dữ liệu giúp cho việc viết code ngắn gọn và hiệu quả. Trong Python có 4 kiểu cấu trúc dữ liệu cơ bản là List, Tuple, Set và Dictionary. Ở đây tôi chỉ giới thiệu 2 cấu trúc thường dùng là List và Tuple a. Cấu trúc dữ liệu List Định nghĩa và cách sử dụng List List là một tập dữ liệu đơn giản nhất trong Python, một List là một danh sách các thành phần dữ liệu được phân cách bởi dấu phẩy và được bao ngoài bởi dấu ngoặc vuông. List có thể chứa các con số hoặc các chuỗi. Hs = ["Dung","Van","Duc"] Tuoi= [18,16,15] Truy xuất phần tử trong List Mỗi phần tử trong List sẽ có một vị trí nhất định tương ứng với một con số, bắt đầu từ số 0 và tăng dần. Chúng ta có thể truy xuất đến các phần tử trong danh sách với cú pháp: Ten_DS[] Danh sách đa chiều Mỗi phần tử trong danh sách của Python có thể là một danh sách, ví dụ như danh sách sau đây, mỗi phần tử là một danh sách gồm tên và tuổi của bạn bè. HS = [["Dung", 18], ["Van", 14], ["Duc", 23]] 12
print(HS[0][1]) # 18 print(HS[1][0]) # Van Trong Python không giới hạn số chiều của danh sách cũng như số phần tử danh sách có thể chứa, nó chỉ phụ thuộc vào dung lượng bộ nhớ máy tính bạn dùng để chạy ứng dụng. Chú ý, với các danh sách dài, chúng ta nên trình bày mỗi phần tử trên một dòng, như vậy code chương trình sẽ dễ đọc hơn, ví dụ: friends = [ ["Dung", 24], ["Vu", 30], ["Ha", 27], ["Duc", 23], ["Van", 25], ["Nga", 29], ] Một số hàm liên quan đến danh sách Trong quá trình thao tác với danh sách, chúng ta cần: kiểm tra xem danh sách có chứa một phần tử nào đó không, đếm số phần tử hoặc thêm , xóa, sửa phần tử trong danh sách... Các yêu cầu này đều có toán tử hoặc các phương thức được xây dựng sẵn trong đối tượng List. Toán tử in Toán tử in cho phép bạn kiểm tra một phần tử có nằm trong một danh sách hay không. Ví dụ: Kiểm tra xem "Dung" có trong danh sách HS không? HS = ["Dung","Van","Duc"] check = "Dung" in HS print(check) #Kết quả là True Hàm len() Hàm len() trả về số phần tử có trong một danh sách. HS = ["Dung","Van","Duc"] print(f"Danh sách HS có {len(HS)} bạn") #Kết quả là 3 Một số phương thức trên Model List .append() thêm một phần tử vào vị trí cuối cùng trong List: HS = ["Dung","Van","Duc"] 13
HS.append("Ha") new_member = "Trung" HS.append(new_member) print(HS) #Kết quả là ["Dung","Van","Duc","Ha","Trung"] .insert(position, item) chèn một phần tử vào List tại vị trí cho trước. HS = ["Dung","Van","Duc"] HS.insert(1,"Ha") print(HS) #Kết quả là ["Dung","Van","Duc","Ha"] Các phần tử phía sau sẽ có vị trí tăng lên 1, cần chú ý khi truy xuất giá trị các phần tử này. listname[index]=newvalue Thay đổi giá trị một phần tử có vị trí index trong List. HS = ["Dung","Van","Duc"] HS[1] = "Trang" print(HS) #Kết quả là ["Dung","Trang","Duc"] .extend() Kết hợp danh sách với một List khác. HS = ["Dung","Van","Duc"] old_HS = ["Ha","Ngan"] HS.extend(old_HS) print(friends) #Kết quả là ["Dung","Van","Duc","Ha","Ngan"] .remove() Loại bỏ một phần tử khỏi List. HS = ["Dung","Van","Duc"] HS.remove("Van") print(HS) #Kết quả là ["Dung","Duc"] .pop(index) Loại bỏ phần tử ở vị trí index cho trước trong List. HS = ["Dung","Van","Duc"] HS.pop(1) print(HS) #Kết quả là ["Dung","Duc"] del Xóa một phần tử hoặc toàn bộ danh sách HS = ["Dung","Van","Duc"]**** del HS[1] print(HS) #Kết quả là ["Dung","Duc"] 14
del HS print(HS) #Lỗi name 'HS' is not defined .clear() Xóa sạch các phần tử trong danh sách HS = ["Dung","Van","Duc"] HS.clear() print(HS) #Kết quả là [] Chú ý, .clear() khác với del, .clear() xóa toàn bộ các phần tử trong List, còn del xóa luôn cả biến List. .count() Đếm số lần một phần tử xuất hiện trong List. HS = ["Dung","Van","Duc","Dung"] print(f"Có {HS.count('Dung')} người tên Dung trong danh sách member") #Kết quả là 2 .index() Trả về vị trí phần tử trong List HS = ["Dung","Van","Duc"] print(f"Dung ở vị trí thứ {HS.index('Dung')} trong danh sách") #Kết quả là 0 .sort() sắp xếp các phần tử trong List. HS = ["Ha","Trung","Dung"] HS.sort() print(HS) #Kết quả là ["Dung","Ha","Trung"] Mặc định sắp xếp tăng dần với dữ liệu chuỗi sẽ sắp xếp a-z, A-Z, với số 0-9. Để sắp xếp giảm dần sử dụng tham số reverse = True. reverse() Đảo ngược thứ tự các phần tử trong List. HS = ["Dung","Van","Duc", "Huy"] HS.reverse() print(HS) #Kết quả là ["Huy","Duc","Van","Dung"] .copy() Copy toàn bộ List. HS = ["Dung","Van","Duc"] news_HS = HS.copy() news_HS.append("Huy") print(news_HS) #Kết quả là ["Dung","Van","Duc","Huy"] 15
b. Cấu trúc dữ liệu Tuple Python hỗ trợ một cấu trúc dữ liệu cũng tương tự với List có tên là Tuple, chỉ có một khác biệt Tuple là danh sách bất biến, không thể thay đổi nội dung. Tức là ngay sau khi định nghĩa Tuple, bạn không thể thay đổi nó. Khai báo Tuple Định nghĩa một Tuple cũng giống như định nghĩa một List trong Python, chỉ khác là thay vì sử dụng ngoặc vuông chúng ta sử dụng ngoặc tròn. HS = ("Dung","Van","Duc") Chú ý: Python cho phép định nghĩa Tuple mà không cần sử dụng dấu ngoặc thường. Ví dụ: HS = "Dung","Van","Duc" Thậm chí Tuple chỉ có một phần tử: HS = "Dung", Chú ý dấu phẩy, nếu không có dấu phẩy thì đây là định nghĩa một chuỗi. Thao tác với Tuple Tuple là một danh sách đặc biệt, không thể thay đổi khi đã tạo ra, do đó bạn có thể sử dụng tất cả các kỹ thuật, các hàm như với List nhưng loại trừ những hàm tác động thay đổi nội dung. Ví dụ, bạn có thể sử dụng toán tử in, hàm len() với Tuple: HS = ("Dung","Van","Duc") check = "Huy" in HS print(check) #Kết quả là Flase HS = ("Dung","Van","Duc") print(f"Danh sách member có {len(HS)} bạn") #Kết quả là 3 Tất cả các phương thức .append(), .extend(), .clear(), .copy(), .insert(), .pop(), .remove(), .reverse(), .sort() không sử dụng được với cấu trúc dữ liệu Tuple. Chú ý: Không thể thay đổi Tuple nhưng có thể tạo ra một Tuple từ hai Tuple, ví dụ : HS = ("Dung","Van","Duc") HS = HS + ("Trung",) print(HS) #Kết quả là ("Dung","Van","Duc","Trung") 16
Tại sao sử dụng Tuple Tuple có những hạn chế là khi tạo ra không thể thay đổi được tuy nhiên Tuple lại có những ưu điểm sau:  Tuplecó tốc độ xử lý nhanh hơn List, do Tuple được lưu trữ một khối bộ nhớ xác định còn List thì thường xuyên phải thay đổi không gian lưu trữ. Nếu bạn định nghĩa một tập các giá trị là hằng số thì nên chọn Tuple.  Sử dụng Tuple giúp code an toàn hơn, khi đó chế độ "write-protect" giúp cho dữ liệu không thể thay đổi. Do vậy nên lựa chọn cho những dữ liệu dạng hằng số, dữ liệu không thay đổi theo thời gian.  Tuple còn được sử dụng làm khóa trong Dictionary do nó chứa các giá trị không đổi, List không được sử dụng làm khóa cho Dictionary. 2.1.2 Thuật toán và độ phức tạp của thuật toán a. Thuật toán tối ưu Thuật toán chính là những chỉ dẫn để tìm thấy kết quả cho vấn đề một cách tối ưu nhất. Việc tìm ra thuật toán tối ưu là vấn đề quan trọng nhất và có ý nghĩa quyết định cho việc thành công của các lập trình viên Thuật toán tối ưu là yếu tố quyết định đầu tiên ảnh hưởng đến tốc độ chạy code trong tất cả các ngôn ngữ lập trình. b. Độ phức tạp của thuật toán và Lựa chọn cách giải thuật Tại sao thời gian lại quan trọng? Trong 1 số chương trình, sản phẩm phần mềm nếu xử lí quá chậm sẽ gây khó chịu cho người dùng ứng dụng. Thời gian chạy lâu gây tốn CPU, làm giảm số lượng người dùng mà máy tính/máy chủ có thể phục vụ người dùng (với ứng dụng có máy chủ) Do đó, các bài tập ở lớp hay các bài thi học sinh giỏi khi đưa ra đều có giới hạn thời gian để học sinh suy nghĩ, lựa chọn giải thuật phù hợp. Đó là thời gian chạy. Vậy độ phức tạp thuật toán là gì, có liên quan gì tới thời gian chạy? - Độ phức tạp thuật toán là gì? Nói ngắn gọn thì, mỗi một bài toán có giới hạn/kích thước của đầu vào. Độ phức tạp thuật toán là 1 khái niệm/ định nghĩa/ định lượng tương đối thể hiện số phép toán của giải thuật so với kích thước của đầu vào. - Quy tắc xác định độ phức tạp • Độ phức tạp tính toán của giải thuật: O(f(n)) • Việc xác định độ phức tạp tính toán của giải thuật trong thực tế có thể tính bằng một số quy tắc đơn giản sau: 17
– Quy tắc bỏ hằng số: T(n) = O(c.f(n)) = O(f(n)) với c là một hằng số dương – Quy tắc lấy max: T(n) = O(f(n)+ g(n)) = O(max(f(n), g(n))) – Quy tắc cộng: T1(n) = O(f(n)) T2(n) = O(g(n)) T1(n) + T2(n) = O(f(n) + g(n)) Quy tắc nhân: Đoạn chương trình có thời gian thực hiện T(n)=O(f(n)) Nếu thực hiện k(n) lần đoạn chương trình với k(n) = O(g(n)) thì độ phức tạp sẽ là O(g(n).f(n)) - Chọn giải thuật phù hợp Như giải thích ở trên, độ phức tạp thuật toán có thể hiểu là số phép toán thực hiện của một hàm dựa trên kích thước tối đa của dữ liệu. Độ phức tạp thuật toán (trên cùng 1 máy) có thể hiểu là nó tỉ lệ thuận (1 cách tương đối) với thời gian chạy. Ví dụ 1: Một mảng có n phần tử. Hãy tìm phần tử lớn nhất trong mảng Bài này tất nhiên chẳng có cách nào khác, bạn sẽ duyệt toàn bộ phần tử trong mảng (duyêt qua mảng n lần) để tìm ra phần tử lớn nhất. Độ phức tạp thuật toán ở đây có thể hiểu là O(n) (chạy qua n phần tử để tìm kiếm) Một mảng có n phần tử. Hãy sắp xếp mảng theo thứ tự tăng dần Bài này quá quen nhỉ. Bạn thường dùng 2 vòng lặp từ i->n và từ j->n để đổi chỗ. Lúc này độ phức tạp thuật toán là O(n^2) Tuy nhiên với 1 số giải thuật sắp xếp như quicksort, độ phức tạp chỉ là O(n*log(n)). Bạn thử thay n=10, thì giải thuật bên trên có thể hiểu sẽ chạy xấp xỉ là 10*10=100 phép tính, nhưng giải thuật Quicksort thì chỉ dùng khoảng 10 phép tính. Với n rất nhỏ, 100 hay 1000 thì chương trình đều chạy có thời gian xấp xỉ bằng nhau. Thật ra kết quả là có chênh, nhưng quá nhỏ nên các bạn không thấy. Nhưng với n cực lớn, ví dụ 100000 phần tử, thì thuật toán có độ phức tạp O(n^2) với O(nlogn) là cực kì khác biệt. Ví dụ 2: Cho một mảng có n phần tử đã sắp xếp. Hãy tìm xem có phần tử x hay không? Bài này nếu các bạn duyệt từ 1 tới n để tìm xem có x hay không, độ phức tạp vẫn là O(n) Tuy nhiên nếu để ý, do mảng này là mảng đã sắp xếp, nên bạn có thể áp dụng thuật 18
toán tìm kiếm nhị phân. Tức là bạn chặt dãy ra làm 2, xem X lớn hay nhỏ hơn phần tử ở giữa, nếu nhỏ hơn thì tìm kiếm ở đoạn dưới, nếu lớn hơn thì tìm kiếm ở đoạn trên. Cứ như vậy bạn chặt dãy ra làm 2 liên tục, thì số phép tìm kiếm sẽ là log2 của n, sẽ nhanh hơn nhiều lần so với giải thuật tìm kiếm tuần tự bên trên. Và như bạn thấy đó, máy tính của chúng ta có tốc độ là khác nhau. Có thể hiểu là, cùng có 100000 phép tính, thì máy của ông A có thể chạy nhanh hơn máy ông B. Do đó, độ phức tạp giải thuật có thể thể hiện tương đối chính xác thuật toán nào nhanh hay chậm, so với việc đo thời gian chạy trên các máy khác nhau. Ví dụ 3: Tính tổng các số nguyên từ 1 -> n Bài này ai dùng công thức thì 1 dòng là ra: n*(n+1)/2. Giải thuật này có độ phức tạp là O(1) (1 phép toán) Với các bạn dùng vòng lặp từ 1 -> n để tính tổng, độ phức tạp là O(n). Với n bằng 1 tỷ, tương đương bạn thực hiện 1 tỷ lần phép toán cộng Như vậy ta hiểu thời gian chạy chênh lêch lớn như thế nào rồi . Ví dụ 4: Bài toán kiểm tra số nguyên tố Bài này cũng đơn giản thôi. Nhưng nhiều bạn cũng chọn giải thuật phức tạp Các bạn chạy để kiểm tra từ 1->n, độ phức tạp là O(n). Các bạn chạy từ 1- >sqrt(n) (căn bậc 2 của n) thì đã giảm rất nhiều phép toán, nếu bạn nào còn tăng bước nhảy lên bằng 2 (kiểm tra có chia hết cho 2,3, 5, 7, 9, 11, ... thay vì 2,3,4,5,6, ....) thì số phép toán lại giảm thêm nữa. Do đó, ngay từ bài số nguyên tố, việc sử dụng vòng lặp để kiểm tra các bạn đã có thể tối ưu cực nhiều. Bạn có thể thử bài này với số n cực lớn và gọi đi gọi lại nhiều lần để đo độ chênh lệch thời gian nha. Ví dụ 5: Bài toán tính tổng các số nguyên tố nhỏ hơn hay bằng n Bài này cũng giống bài trên. Độ phức tạp giải thuật của việc kiểm tra số nguyên tố giả sử đang là O(n) Nếu với mỗi 1 số từ 1 tới n, bạn lặp lại việc kiểm tra 1 cách thông thường, độ phức tạp thuật toán của giải thuật này là O(n^2) Bài này nếu cho n=1000000, đa phần sẽ ko chạy được. Do số phép toán cực nhiều. Đối với bài này, nếu bạn dùng sàng nguyên tố (ý tưởng là loại bỏ các hợp số), thì độ phức tạp thuật toán xấp xỉ O(nlogn). Hiểu rõ về khái niệm độ phức tạp thuật toán và cách tính toán độ phức tạp của giải thuật (của mình hay của người khác) bạn sẽ tối ưu thuật toán để đáp ứng thời gian chạy tốt hơn ví dụ như làm ứng dụng của bạn chạy nhanh, thời gian phản hồi cao, ... Do đó, với mỗi bài toán hay yêu cầu cụ thể, hãy xem xét độ lớn của tập dữ liệu mà chọn giải thuật cho phù hợp. c. Quy trình để viết một thuật toán Bước 1: Phân tích, phác thảo thuật toán Bước đầu tiên, cần phân tích rõ vấn đề sau đó hình dung được hướng giải quyết và chiến thuật thiết kế thuật toán. Để hoàn thành bước này, chúng ta cần đến những kiến 19
thức căn bản của môn “Cấu trúc dữ liệu và giải thuật”, cụ thể là 5 chiến thuật thiết kế thuật toán sau: Chia để trị – divide and conquer, Giải thuật tham ăn – Greedy Method. Bước 2: Kiểm tra thuật toán Sau khi thiết kế xong thuật toán, chúng ta ta cần triển khai kiểm tra tính đúng đắn của nó bằng cách đưa thuật toán vào máy tính. Sau đó, nhập input, tức tài liệu nguồn vào ở định dạng tương thích. Bước kiểm tra này nhằm giúp đảm bảo thuật toán sẽ hoạt động tốt trên mọi ngôn ngữ lập trình. Bước 3: Đánh giá thuật toán Để biết được thuật toán có hiệu quả hay không chúng ta cần phải đánh giá nó. Ta có thể đánh giá hiệu năng thuật toán với 2 yếu tố là thời hạn thực thi và bộ nhớ sử dụng. Bởi vì trong quá trình chạy thuật toán, CPU cần tiêu tốn thời gian quyết và xử lý để thực thi những phép toán, còn bộ nhớ sẽ là nơi chứa tài liệu và các chương trình thực thi. Bước 4: Test chương trình Việc test chương trình sẽ được thực hiện bởi các Tester và được chia thành 2 giai đoạn là debugging và profiling. Debugging là quá trình thực thi chương trình dựa trên tập dữ liệu mẫu nhằm để xác định các lỗi xảy ra (loại lỗi, vị trí lỗi,…) và khắc phục chúng. Giai đoạn này hầu như không bao giờ phát hiện được 100% lỗi. Profiling là quá trình thực thi chương trình trên một tập dữ liệu mẫu, nhưng trong giai đoạn này người ta sẽ đo thời gian cũng như dung lượng bộ nhớ. d. Một số loại thuật toán cơ bản và những điều cần biết - Thuật toán sàng nguyên tố với Python Thuật toán sàng nguyên tố (Sieve of Eratosthenes) là một phương pháp đơn giản để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một số nguyên n. Phương pháp này hoạt động bằng cách loại bỏ các số hợp số từ danh sách các số nguyên dương nhỏ hơn hoặc bằng n. 20