Hàng đợi ưu tiên trong python
Sử dụng Heaps và Hàng đợi ưu tiến với module heapqHeaps và hàng đợi ưu tiên ít được biết đến nhưng rất ngạc nhiên nó là kiến trúc dữ liệu rất có hữu dụng. Với cá vấn đề liên quan tới tìm kiếm phần tử tốt nhất trong dataset, họ thường đưa ra một phướng án dễ sử dụng và hiệu quả cao. Module Show Hàng đợi ưu tiên công cụ mạnh mẽ có thể giải quyết các vấn đề đa dạng như lập lịch gửi email, tìm đường ngắn nhất, hoặc merge các log file. Tập trình có nhiều bài toán cần tối ưu hóa và để tìm ra phương án tốt nhất để giải quyết bài toán. Heaps là gì ?Heap là concrete data structure (cấu trúc dữ liệu cụ thể), trong khi hàng đợi ưu tiên (priority queues) là cấu trúc dữ liệu trừu tượng. Một cấu trúc dữ liệu trừu tượng xác định interface, trong khi concrete data structure định nghĩa cách triển khai nó. Cấu trúc dữ liệu cụ thể được chỉ định để đảm bảo hiệu suất. Đảm bảo hiệu suất xác định mối quan hệ giữa kích thước của cấu trúc dữ liệu và thời gian hoạt động. Việc hiểu những điều đó cho phép bạn dự đoán sẽ mất bao nhiêu lâu để một chương trình chạy được với một lượng dữ liệu đầu vào. Cấu trúc dữ liệu, Heaps và Hàng đợi ưu tiênCấu trúc dữ liệu trựu tượng xác định các hoạt động và mối quan hệ giữa chúng. Trong hàng đợi ưu tiên, nó xác định 3 hoạt động là:
Hàng đợi ưu tiên được sử dụng phổ biến để tối ưu hóa thực hiện một tác vụ, trong đó nhiệm vụ chính là thực hiện tác vụ với độ ưu tiên cao. Sau một nhiệm vụ được hoàn thành, độ ưu tiên của nó sẽ giảm xuống và nó được đưa về hàng đợi. Có 2 quy ước khác nhau để xác định hộ ưu tiên của một đối tượng:
Module Concrete data structures thực hiện các hoạt động được định nghĩa bên trong một cấu trúc dữ liệu trừu tượng và được chỉ định rõ về đảm bảo hiệu suất. Việc triển khai heaps trong hàng đợi ưu tiên đảm bảo rằng cả pushing và poping phần tử đều là phép toàn thời gian logarithmic. Điều này có nghĩa là thời gian cần thực hiển để push và pop là log cơ số 2 của số các phần tử. Phép toán loga tăng nhập. log cơ số 2 của 15 khoảng 4, log cơ số 2 của nghìn tỷ là 40. Điều đó nghĩa là nếu thuật toán đủ nhanh với 15 phần từ, thi nó cũng chỉ chậm đi 10 lần với nghìn tỷ phần tử. Chi tiết về HeapsHeap khai triển một hàng đợi ưu tiên như một cây nhị phân hoàn chỉnh. Trong nhị phân cây, mỗi nút sẽ có hai con. Thuộc tính hoàn chỉnh nghĩa là độ sâu của cây is log cơ số 2 của số phần tử, được làm tròn lên. Dưới đây là một ví dụ về cây nhị phân hoàn chỉnh: Trong ví dụ cụ thể, tất cả các cấp độ đều hoàn chỉnh. Mỗi nút trừ nút sâu nhất thì sẽ có đúng 2 con. Ở đây có 7 nút ở 3 cấp (tầng) khác nhau. Log cơ số 2 của 7 là 2.8073549 làm tròn lên là 3. Node trên cùng gọi là nút gốc (root). Hiệu suất đảm bảo trong một heap phụ thuộc vào cách các phần tử thấm (percolate) lên trên hay xuốn dưới của cây. Kết quả thực tế của số phép so sánh thực hiện trong một heap là loga cơ số hai của sô phần tử trong cây. Trong một heap, giá trị của một node bất kỳ sẽ luôn nhỏ hơn giá trị của các node con. Đây cũng là chính chất của heap. Tính chất này khác với tìm kiếm nhị phân, trong đó chỉ nút bên trái sẽ có giá trị nhỏ hơn node cha. Ví dụ, để push một phần tử vào 1 heap. Python thêm một node mới vào vị trí tiếp theo. Nếu lớp cuối cùng chưa đầy, thì node sẽ được thêm vào vị trí tiếp theo ở tầng đó. Và ngược lại, một tầng mới sẽ được tạo và khi đó phần tử sẽ được thêm vào lớp đó. Khi nút mới được thêm, Python sẽ so sánh nó với cha của nó. Nếu thuộc tính heap là violated, thì node này và cha của nó sẽ được hoán đổi cho nhau, và việc kiểm tra sẽ tiếp tục lại ở tầng con cha. Điều này tiếp diễn cho tới khi đảm bảo thuộc tính của heap hoặc tới được nút gốc. Tương tự, khi pop phần tử nhỏ nhất, Python sẽ biết rằng do tính chất heap, phần tử đó sẽ nằm ở đầu cây. Nó sẽ thay thế phần tử này với phần tử cuối cùng ở lớp sấu nhất và sau đó kiểm tra lại tính chất của heap. Sử dụng hàng đợi ưu tiênHeap là một cách để khai triển cho hàng đợi ưu tiên, rất hữu dụng cho các chương trình tìm kiếm một phẩn tử. Ví dụ bạn có thể sử dụng hàng đợi ưu tiên cho các công việc sau:
Nhiều công việc khác dùng tới hàng đợi ưu tiên như lập lịch gửi mail. Tưởng tưởng một hệ thống có rất nhiều loại email, và mỗi loại cần gửi với tần suất nhất định. Ví dụ một loại email sẽ gửi đi sau mỗi 5p và một lại email khác cần gửi đi sau mõi 4 phút. Scheduler có thể thêm cả 2 loại email vào hàng đợi và xác định thời gian tiếp email cần gửi. Dựa vào thời gian nhỏ nhất, nó sẽ xác định cái gì sẽ được gửi đi tiếp theo, tính toán thời gian nghỉ giữa hiệp. Sau khi scheduler tỉnh dậy, nó sẽ xử lý email, lấy email từ hàng đợi và tính toán thời gian tiếp theo, put email vào hàng đợi. Heap trong module heapMặc dù bạn thấy head được mô tả trước đó là dạng cây, nhưng điều bạn cần nhớ là nó là một cây nhị phân hoàn chỉnh. Sự hoàn chỉnh nghĩa là nó luôn luôn xác định số phần tử ở mỗi lớp trừ
lớp cuối cùng. Vì điều này, heap có thể được khai triển dưới dạng list. Đó là điều mà module Có ba quy tắc xác định mối quan hệ giữa phần tử có index
Quy tắc trên nói cho cho bạn viết cách hình dung một
cây nhị phân hoàn trình dưới dạng list. Hãy nhớ là một phần tử sẽ luôn có một cha, nhưng có thể có những phản tử không có con. Nếu Tính chất heap (heap property) nghĩa là nếu
Nó có thể raise Nói một cách khác, một phần tử sẽ luôn nhỏ thơn các phần tử có index gấp đôi index của nó cộng 1, hoặc cộng 2. Dưới đây là một hình ảnh minh họa: Các mũi tên đu từ phần tử Các toán tử cơ sởModule
Mặc dù 7 đứng sau 8, danh sách này vẫn tuân theo tính chất của heap. Ví dụ Cách hoạt động cơ bản của Từ phần tử đầu tiên, bạn không dùng tới hàm nào để tìm ra phần tử có giá trị nhỏ nhất vì phần tử này chính là phần tử nhỏ nhất ở vị trí a[0]. Để pop phần tử nhỏ nhất mà vẫn đảm bảo tích nhất của heap, ta có thể dùng hàm
Hàm sẽ trả về phần tử dầu là
Sau khi push 4 vào heap, bạn sẽ pop ra 3 phần tử từ a. Vì 2 và 3 đã có trong heap và nhỏ hơn 4, nên chúng bị lấy ra đầu tiên. Các phép toánVì hàng đợi ưu tiên thường được sử dụng để gộp các chuỗi đã sắp xếp nên module này cũng cung câp thêm phương thức là
Đầu vào của hàm Để debug và xác nhận code hoạt động đúng thì bạn có thể in ra 10 phần tử email chuẩn bị gửi như sau:
Lưu ý, cách gửi Các vấn đề Heaps có thể xử lýNhư bạn đã thấy trước đây, heaps
rất tốt cho việc hợp nhất các chuỗi có thứ tự. Hai ứng dụng mà bạn có thể biết tới là lập lịch và hợp nhất các file log. Tuy nhiên còn nhiều ứng dụng hơn cho nó. Heaps có thể xác định
Đoạn code trển sử dụng
Ở đây Ví dụ: Tìm đường điVí dụ sau đây là ví dụ thực tế cho việc sử dụng Giả sử một con robot cần xác định hướng trong một mê cung hai chiều. Con robot cần đi từ gốc tọa độ (phía trên góc trái) tơi đích là phía dưới bên phải. Con robot đó có một bản đồ được lưu trong bộ nhớ và có thể vẽ ra các con đường trước khi đi. Mục tiêu là con robot cần hoàn thành mê
cùng này nhanh nhất có thể. Thuật toán ta sẽ sử dụng là thuật toán
Ở mỗi bước, chúng ta sẽ xử lý 4 hành động:
Các bước trên được chạy cho tới khi điểm đích được thêm vào trong tập Vậy bạn đã hiểu thuật toan, bây giờ hãy viết những dòng code. Trước tiên, ta cần
thêm thư viện
Bạn sẽ sử dụng các hàm mà
Ở đây ta sử dụng 3 dấu nháy để hiển thị một vùng mà robot có thể di chuyển một cách trực quan nhất. VBản đồ nay dduocj tối ưu hóa để dễ hiểu với người đọc. Dấu chấm là các điểm có thể đi còn X là chướng ngại vật, va vào chết luôn. Hàm đâu tiên bạn cần viết là convert bản đồ này sang một thứ gì đó dễ phân tích hơn
Hàm này nhận một bản đồ và trả về 1 tuple với 3 phần tử:
Điều đó cho phép phần còn lại của mã có thể hoạt động trên cấu trúc dữ liệu máy tính. Danh sách
Hàm
Hàm này nhận vào 2 tham số:
Để hợp lệ, vị trí đó cần nằm trong ranh giới của bản đồ và không phải là một chướng ngại vật, Phương thúc này kiểm tra Tiếp tới, ta viết thêm 1 hàm nữa là lấy ra thằng hàng xóm của nó
Hàm này sẽ tả về tất cả các tọa độ hợp lệ xung quanh điểm hiện tại. Cuối cùng là hàm quan trọng nhất, hàm tìm đường đi
Tóm tắt lại, để tìm đường đi ngắn nhất thì ta cần có 3 loại dữ liệu sau:
Một phần tử bên trong Một heap là tập hợp độ dài những đoạn đường và được quản lý với sự trợ giúp của Ở mỗi bước, bạn sẽ xem xét các điểm với các đoạn ngắn đã biết. Đây là nơi
heap thực hiện với Sau đó bạn xem xét các hàng xóm chưa được xét và nếu việc đi qua nút hiện tại có cải tiến, thì bạn sẽ thêm nó vào Đây là hàm
Nếu thuật toán trên sử dụng cho robot thì không sau, tuy nhiến nếu bạn muốn biết con đường nó ntn thì chúng ta cần thêm đoạn code để show nó:
Hàm này nhận vào
Tổng kếtBây giờ bạn đã biết như thế nào là heap và hàng đợi ưu tiên,
những vấn đề nào cần dùng chúng. Đồng thời bạn tìm hiểu được cách sử dụng module Tham khảo:https://realpython.com/python-heapq-module/ |