CODEWITHSUNDEEP
pythonhash
Quazi Farhan
Quazi Farhan

Reputation: 1425

Python hash table design

I want to implement a hash table in python. On the table a class object will be associated with the key value. The problem is I want to use the key value to find the index of the class and update it (which of course is not a problem). But what can I do if I want to sort the table using a particular value of the class.

For example, let us consider, we have three value: document_id, score and rank. There is a class "document" which consists of "score" and "rank". "document_id" will be the key of the table.

I want to update the "score" of various entries of the table, using the key: "document_id". But when updating of the scores are done, I want to sort the list/table using the score and assign rank value to the "rank" variable based on updated score.

Can someone kindly give me some guideline about how can I proceed? Or maybe I should simply make it a list?

The maximum number of item of the table might be upto 25000-30000.

Thanks.

Upvotes: 6

Views: 27852

Answers (3)

Ned Batchelder
Ned Batchelder

Reputation: 375912

Python's dict is already a hash table.

doc_hash = {}
doc_hash[doc.id] = doc

To assign rank:

docs = sorted(doc_hash.itervalues(), key=operator.attrgetter('score'), reverse=True)
for i, doc in enumerate(docs):
    doc.rank = i

Upvotes: 21

cha0site
cha0site

Reputation: 10737

Why not use a OrderedDict?

>>> from collections import OrderedDict

>>> # regular unsorted dictionary
>>> d = {'banana': 3, 'apple':4, 'pear': 1, 'orange': 2}

>>> # dictionary sorted by key
>>> OrderedDict(sorted(d.items(), key=lambda t: t[0]))
OrderedDict([('apple', 4), ('banana', 3), ('orange', 2), ('pear', 1)])

>>> # dictionary sorted by value
>>> OrderedDict(sorted(d.items(), key=lambda t: t[1]))
OrderedDict([('pear', 1), ('orange', 2), ('banana', 3), ('apple', 4)])

>>> # dictionary sorted by length of the key string
>>> OrderedDict(sorted(d.items(), key=lambda t: len(t[0])))
OrderedDict([('pear', 1), ('apple', 4), ('orange', 2), ('banana', 3)])

Upvotes: 4

Nicolas78
Nicolas78

Reputation: 5144

Something like this?

sorted_keys = sorted(d.keys(), key=lambda element: element['score'])
for i in range(len(sorted_keys)):
  d[sorted_keys[i]]['rank'] = i

assigns to each element in d (elements are implied to be dictionaries as well) a rank based on its score.

Upvotes: 0

Related Questions