![]() A different approach is to not worry about maintaining a sorted list and search through the list for the item with the smallest priority value during peek and pop. The one you see here is to maintain a sorted list and always pop from the end. Prioritize speed in insert rather than peek/ popįor list-backed priority queues, we have two basic approaches. We'll want to keep all of these implementations side-by-side for testing speed later. Ensure the queue works with negative or floating point prioritiesįor each of the below tasks, copy the priority queue into a new file first before modifying.Ensure the error cases from the previous section are all handled correctly.Ensure items with same priority go through the queue First In First Out.Ensure the queue works with many of items inserted in different orders.Change that by adding tests for the following cases: There's one simple test included as an example, but it definitely doesn't thoroughly test the data structure. In this case, we'd like those items to go through the queue in a FIFO order. This example doesn't consider the case when multiple items in the queue have equal priority. Testing / Correctness Improvements Handle priority equality correctly ![]() Consider what information a consumer of this queue might want to see when they print it out. Update it to print a string that is easier to read and provides better insight into the state of the structure. The _str_ method of PriorityQueue is not great because it's not very human readable and it would print a very long string if the queue had a lot of items in it. Write a better string representation of the queue You can make more varieties of specific exceptions. Think of errors that can occur during insert and use the same technique of raising a custom exception to handle those gracefully as well. Here are the python docs on raising custom exceptions.Īdd an EmptyQueueException and raise it appropriately in peek and pop. It would be more helpful to a future consumer of this queue if we handled that error and raised a specific exception that clearly indicates the problem. Right now, if you try to pop or peek from an empty queue, an error that's specific to the internal implementation of the queue will bubble up. Then, modify the insert method to compare items in self.storage to to_insert directly using <. Implement a method def _lt_(self, other): in the class Item. This allows us to compare instances of a class directly using operators like <, =, and others. ![]() Right now, we use a separate comparison function standard_priority_func to compare Item priorities during insertion.Ī cool feature of classes in most languages is operator overriding. ![]() Our priority queue uses instances of the Item class to store values alongside priorities. Code Quality Improvements Override the < operator for Item Run the test with python pq.py and notice how no matter the order that we insert items into the queue, they always come out in the order "A", "B", "C".īelow is a list of ways that we can improve the structure. In this queue, lower numbers for priority come first. The simple_test() method very simply demonstrates the purpose of a priority queue. Read through the file pq.py and make sure you understand everything that's going on. It doesn't handle edge cases well and it certainly isn't the most efficient. This is a very simple implementation of a priority queue. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |