Efficient "Object with weights" structure

Question

I need to find an "efficient" data structure / set of algorithms to do the following things:

I have a list of objects. I need to assign them weights and later on increase or decrease these weights.

For instance: We have the hashmaps {o1}, {o2}, {o3}. The {o}'s don't have any particullar structure, just random json.

I am looking for a way of saying: Increase the weight of o1 by 1. Increase the weight of o2 by 1. Increase the weight of o1 by 1. Now give me the results sorted by their weight.

I am using Python. So far I have tried using a normal hashmap to store them, but the problem is that I can't just hash the {o}'s. I thought of hashing the pointer of the {o}'s in memory, but it seems I don't have access to it in Python.

Answer 1

You could of course store the weight in each object, or store a directory of instances in the class, if you create or control the classes.

If not, you may be interested in the Counter class, a dictionary that maps into numeric values. It can be extended to map objects to weights. Here's a sketch:

from collections import Counter

class Weights(object):
    def __init__(self):
        self.counts = Counter()
        self.objs = dict()
    def __setitem__(self, item, value):
        _id = id(item)
        self.counts[_id] = value
        self.objs[_id] = item
    def __getitem__(self, item):
        _id = id(item)
        return self.counts[_id]
    def keys(self):
        return [ self.objs[i] for i in self.counts.keys() ]  
    def items(self):
        return [ (self.objs[i], c) for (i, c) in self.counts.items() ]
    def most_common(self, n=None):
        return [ (self.objs[i], c) for (i, c) in self.counts.most_common(n) ]


o1, o2, o3 = [ object() for i in range(3) ]

weight = Weights()

weight[o1] = 3
weight[o2] = 4.4
weight[o3] = 1.1
weight[o2] += 1.1
print weight.most_common() # tuples sorted by highest weight first

It yields something like:

[(<object object at 0x106cd30b0>, 5.5), (<object object at 0x106cd30c0>, 3), (<object object at 0x106cd30d0>, 1.1)]

(The first item in each tuple is the corresponding object.)

While Counter requires a hashable value as a key, Weights maps each object into its id (which is inherently hashable), internally. While this is just a sketch (some other Counter methods are not provided), it does the sort of object tracking you sought.

Answer 2

Use a class

class Thing(object):
    def __init__(self, o):
        self.o = o
        self.weight = weight

You can make a list of Things, or a dict, or whatever works for you.

Answer 3

I am looking for a way of saying: Increase the weight of o1 by 1. Increase the weight of o2 by 1. Increase the weight of o1 by 1. Now give me the results sorted by their weight.

This seems like a job for a priority queue, where the priority_number is the weight you want to assign.

Answer 4

For sorting you can override __lt__ and others compare function:

import heapq

class Item(object):
    def __init__(self, o, weight):
        self.o = o
        self.weight = weight

    def increase_weight(self, amount=1):
        self.weight += amount

    def __lt__(self, other):
        return self.weight < other.weight

    def __str__(self):
        return '<Item o={o} weight={weight}>'.format(
            o=self.o, weight=self.weight
        )
    __repr__ = __str__

items = [
    Item('o1', 1),
    Item('o2', 5),
    Item('o3', 4),
    Item('o4', 3),
]

items.sort()
print items

items[0].increase_weight(5)
items.sort()
print items