Binary search algorithm with 2 keys for indexing in python

Question

In my application, I have a dictionary (hash map) of objects. Each object has several attributes, including 'uuid', 'name', and 'level'. uuid is the only unique field and serves as the dictionary key. I would like to be able to list these objects based on their name in ascending alphabetical order, and if the names are the same, then by level in ascending numerical order. To do this, I am trying to maintain a list (array) of uuid's (so I don't have to store entire objects), where I can simply iterate through the list, referencing the appropriate object from the uuid at each particular index. So when I add an object to the dictionary, the list must be updated. I am trying to use a binary search algorithm to first find the index of the list whose uuid matches the appropriate name, then matches the appropriate level. My code is getting me close, but still getting semantic errors. Here it is. Can anyone help me adjust this or point me in the right direction? (I have only given pseudocode to simplify understanding)

min = 0
max = numRecords - 1 #numRecords is the number of objects in the dictionary
mid = 0
while max >= min:
    mid = (min + max) / 2   
    if dict[uuid].name() == dict[list[mid]].name():
        if dict[uuid].level() == dict[list[mid]].level():
            break
        elif dict[uuid].level() < dict[list[mid]].level():
            if mid != 0 and dict[uuid].name() == dict[list[mid - 1]].name():
                max = mid - 1           
            else:
                break
        else:
            if mid != numRecords-1 and dict[uuid].name() == dict[list[mid+1]].name():
                min = mid + 1
            else:
                break
    elif dict[uuid].name() > dict[list[mid]].name():
        min = mid + 1
    else:
        max = mid - 1

list = list[:mid] + [uuid] + list[mid:]

GrantJ · Accepted Answer · 2014-04-10 23:12:32Z

2

You could use the SortedList type in the Python sortedcontainers module. You can store your objects as a tuple of (name, level, uuid) and the sorted list will automatically maintain them in sorted order. You can do lookups using bisect.

For example:

from sortedcontainers import SortedList
sl = SortedList((name, value, uuid) for name, value, uuid in data)

# Now iterating sl will list objects in ascending order by name, value, uuid.

# If you want to lookup a particular name:

index = sl.bisect((name,))

Because a shorter tuple automatically compares less than a longer tuple, the bisect will return the index of the given name (or the index where such a name should be inserted). You can also delete from a SortedList by index.

The sortedcontainers module is pure-Python and fast.

answered Apr 10, 2014 at 23:12

GrantJ

8,7793 gold badges59 silver badges49 bronze badges

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

Collectives™ on Stack Overflow

Binary search algorithm with 2 keys for indexing in python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related