FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

Implemented PriorityQueue and Queue in utils.py by goswami-rahul · Pull Request #828 · aimacode/aima-python · GitHub

  1. aimacode
  2. aima-python

Repository navigation

Implemented PriorityQueue and Queue in utils.py - #828

Closed
goswami-rahul wants to merge 9 commits into
aimacode:masterfrom
goswami-rahul:patch-2
ConversationCommits (9)ChecksFiles changed
Closed

Implemented PriorityQueue and Queue in utils.py#828
goswami-rahul wants to merge 9 commits into
aimacode:masterfrom
goswami-rahul:patch-2

Conversation

goswami-rahul commented Mar 8, 2018 •
edited
Loading

Copy link
Copy Markdown
Contributor
  • Defined the abstract methods in the Queue abstract class.
  • Implemented the PriorityQueue methods. (on the TODO list)
  • Implemented the FIFOQueue methods.
  • Changed the 2 usages of PriorityQueue to comply with new changes.
    The __init__ method of the PriorityQueue is changed.
    Old:
 def __init__(self, order=min, f=lambda x: x):
        self.A = []
        self.order = order
        self.f = f

New:

    def __init__(self, order='min', f=lambda x: x):
        self.q = []

        if order == 'min':
            self.f = f
        elif order == 'max':            # now item with max f(x)
            self.f = lambda x: -f(x)    # will be popped first
        else:
            raise ValueError("order must be either 'min' or max'.")

This change is because it can be seen that the argument passed before i.e. min is a built-in function,
There is no specific use of min function in any method. It is just used as a flag to indicate that make a min PriorityQueue.
This functionality is achieved better when the order argument is str rather than a function.
There are 2 uses of this class, both of which are also updated in this PR.
Also now the PriorityQueue attribute self.order is not required.

Any suggestions or feedbacks are appreciated.

goswami-rahul commented Mar 8, 2018 •
edited
Loading

Copy link
Copy Markdown
Contributor Author

I don't understand what the __getitems__ method is doing? I have opened an issue (#829) regarding the same.
I have not changed this method for now.

goswami-rahul commented Mar 9, 2018 •
edited
Loading

Copy link
Copy Markdown
Contributor Author

@MrDupin @norvig
The Stack() too should be a subclass of Queue basically with all the methods wrapped inside the subclass. I think defining Stack as a subclass would be programming approach.
I can also include the changes made in the Stack in this PR, but I need your suggestions.
Should I open an issue regarding this?

antmarakis commented Mar 10, 2018 •
edited
Loading

Copy link
Copy Markdown
Collaborator

I have previously tried to make changes to the Queues, but each time I realized that it's not a big issue. Students don't come here for this, so we should just have something simple that works.

I am not sure what to do with this, sorry. It can go any way.

For now focus on the Queues and if Mr. Norvig likes the changes, work on the Stack.

norvig reviewed Mar 20, 2018
View reviewed changes
Comment thread utils.py
@@ -662,41 +663,39 @@ def __missing__(self, key):


class hashabledict(dict):

norvig Mar 20, 2018

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

I understand the motivation for a hashable dict. It is too bad Python doesn't have frozendict like frozenset.

But the implementation here is O(n) to compare or hash. Given that, a simpler representation is:

class hdict(dict):
    def __hash__(self): return 1

norvig reviewed Mar 20, 2018
View reviewed changes
Comment thread utils.py
@@ -724,73 +739,94 @@ def Stack():


class FIFOQueue(Queue):

norvig Mar 20, 2018

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

The code here is fine, but I think we can just use collections.deque.

goswami-rahul Mar 21, 2018

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

But then we have to change every uses of FIFOQueue and replace its pop with popleft. I thought the idea behind these classes here was to be able to use PriorityQueue and FIFOQueue (and maybe Stack) with a the same code and just change in the constructor.

norvig Mar 21, 2018

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

Yes, @goswami-rahul you are correct that the motivation of a single interface was to make the various queues the same, so that they could be interchangeable, and we could highlight the similarities. This was a priority in the 1st and 2nd edition of the book (and the code goes all the way back to then). But in the 3rd (and soon 4th) edition, we accept that each search function is somewhat different, and so it is ok, and maybe even preferably, to have popleft instead of pop.

norvig reviewed Mar 20, 2018
View reviewed changes
Comment thread utils.py
return item in self.q


class PriorityQueue(Queue):

norvig Mar 20, 2018

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

Probably easier to use heapq.

goswami-rahul commented Mar 21, 2018

Copy link
Copy Markdown
Contributor Author

So should I remove all these classes and refactor all their instances with collections.deque.?

goswami-rahul mentioned this pull request Mar 23, 2018
Merged

goswami-rahul commented Mar 23, 2018

Copy link
Copy Markdown
Contributor Author

new changes in #878

rajatjain1997 mentioned this pull request Feb 10, 2019
Closed
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Show hidden characters
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

norvig norvig left review comments

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

Back | FazBrowse Home | New Git URL