CODEWITHSUNDEEP
pythonnested-lists
user1789376
user1789376

Reputation: 55

Inserting in order to a nested list

Say I had a nested list like so:

nested_list=[[123,'Aaron','CA'],[124,'Bob','WY'],[125,'John','TX']]
insert_me=[122,'George','AL']

The list is currently sorted (In alphabetical order) by the middle value of each sublist, I want to add the value insert_me in its correct place in the nested list. In order to maintain alphabetical order it needs to be added between the lists with 'Bob' and 'John' in them. I know bisect would normally be used for a task like this with lists but don't understand how I could use bisect for a nested list like this.

Upvotes: 3

Views: 2283

Answers (3)

isedev
isedev

Reputation: 19601

See the example in the Python documentation for bisect:

Unlike the sorted() function, it does not make sense for the bisect() functions to have key or reversed arguments because that would lead to an inefficient design (successive calls to bisect functions would not “remember” all of the previous key lookups).

Instead, it is better to search a list of precomputed keys to find the index of the record in question:

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> keys = [r[1] for r in data]         # precomputed list of keys
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
('blue', 1)
>>> data[bisect_left(keys, 5)]
('red', 5)
>>> data[bisect_left(keys, 8)]
('yellow', 8)

So in your case:

nested_list = [[123,'Aaron','CA'],[124,'Bob','WY'],[125,'John','TX']]
insert_me = [122,'George','AL']                                
keys = [r[1] for r in nested_list]
nested_list.insert(bisect.bisect_left(keys,insert_me[1]),insert_me)
[[123, 'Aaron', 'CA'],
 [124, 'Bob', 'WY'],
 [122, 'George', 'AL'],
 [125, 'John', 'TX']]

To avoid rebuilding the keys everytime, insert new values into keys as well:

keys.insert(bisect_left(keys,insert_me[1]),insert_me[1])

Update:

Did some performance comparison between insert/bisect, append/sorted and heapq solutions:

# elements  heapq   insert/bisect  append/sorted
10,000      0.01s   0.08s           2.43s         
20,000      0.03s   0.28s          10.06s
30,000      0.04s   0.60s          22.81s

Upvotes: 5

halex
halex

Reputation: 16403

I would use a specialization of a heap for your problem. Take the heap class from this answer and your code will be:

import heapq

class MyHeap(object):
    def __init__(self, initial=None, key=lambda x:x):
        self.key = key
        if initial:
            self._data = [(key(item), item) for item in initial]
            heapq.heapify(self._data)
        else:
            self._data = []

    def push(self, item):
        heapq.heappush(self._data, (self.key(item), item))

    def pop(self):
        return heapq.heappop(self._data)[1]

h = MyHeap([[123,'Aaron','CA'],[124,'Bob','WY'],[125,'John','TX']], key=lambda x:x[1])
h.push([122,'George','AL'])
for _ in xrange(4):
    print h.pop()

Every list that you add with push will be in order with respect to the second element (which we control with the key=lambda x:x[1] argument in the constructor). You get the elements in order, one by one by calling pop.

Upvotes: 4

Jroosterman
Jroosterman

Reputation: 418

You could alphabetize the list using sorted().

nested_list=[[123,'Aaron','CA'],[124,'Bob','WY'],[125,'John','TX']]
insert_me=[122,'George','AL']

nested_list.append(insert_me)
nested_list=sorted(nested_list, key=lambda x:x[1])

Sorted()

Upvotes: 2

Related Questions