3

I'm using python to manage a queue of strings to process. It has a couple of requirments:

  • Each string is matched to a priority and is processed based solely on that value.
  • Strings can be added to this queue dynamically but no duplicate Strings are allowed in the queue. If a duplicate is submitted then it must be identified and ignored.

So is there any python datatype that will allow something like this? Or do I have to write my own?

If there isn't a native one then, I'm thinking of maintaining two structures.

  1. A heapq which will maintain the strings and their priority
  2. A list which maintains a hash of the strings to check whether the string is already stored

As long as these do not fall out of sync it should solve the problem.

Improve this question
2
  • 2
    why not a dictionary? or ordereddict? Commented May 25, 2011 at 16:12
  • 3
    @utdmr: Sorting a dictionary by values is not that great. Commented May 25, 2011 at 16:12

2 Answers 2

Reset to default
5

That sounds like a reasonable approach. I would use a set instead of a list since it has more efficient membership checking and you don't need to maintain order (since you do it in the heapq)

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Definitely should use a set
2

An ordered dictionary may be of help.

See this page (an ordered dictionary) where it states:

The ordered dictionary keeps keys in insertion order. This is sometimes called a created order dictionary.

There are potential use cases for dictionaries that keep their keys in order, but the ordering being based on other criteria.

You are free to change the order using the setkeys method, but you may prefer a dictionary that used these different criteria. For example you might need a dictionary that kept keys in order of the last accessed key.

Improve this answer

1 Comment

So I would have the priority of the strings as the keys and the values as the strings, and I can then sort based on the value of the keys? How would I check whether the string already exists in the queue?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.