CODEWITHSUNDEEP
pythonlistsorting
user1532369
user1532369

Reputation: 179

Sorting the contents of one list via the contents of another (Python)

I have two lists which have been created by .csv files. The first consists of a branch id number and a list of corresponding flows. The second is the order in which I wish to have the branche ids and their corrsponding flows sorted. They are as follows:

branch_flows = [['1234-2321-1', [55, 76, 3, 55, 6]],
                ['1546-2645-1', [4, 6, 56, 3, 4]],
                // ...
                ['4123-1234-1', [6, 12, -4, 7, 9]]
               ]

and 

ordered_branches = ['1234-2321-1',
                    '1234-4123-1',
                    // ...
                    '1546-2645-1']

I am wondering how to sort branch_flows the same way ordered_branches is ordered, but for the flows to stay related to the same ids after sorting? The main difficulty being that some of the branch ids in branch_flows first two parts are reversed, but I need them to be sorted as if they were not.

e.g. looking to the lists above, desired output would be having branch_flows sorted in a way that the final list in branch_flows was placed second in the sorted list (as 1234-4123-1 in ordered_branches can equal both 1234-4123-1 AND 4123-1234-1 in branch_list, as the order in branch_flows can sometimes be the reverse of that in ordered_branches).

I originally tried to use dictionarys as look up tables but ran into trouble with the reading reverse order part. Help much appreciated!

Upvotes: 2

Views: 670

Answers (2)

Vatine
Vatine

Reputation: 21288

On the surface of things, it looks as if you could do this with one dict-build and two list traversals (you already have the sorted order, after all).

Something like:

flow_dict = {}
for flow in branch_flow:
    # Sometimes, there's a reversal of the two parts of the key.
    key_parts = flow[0].split('-')
    flow_dict['-'.join(key_parts)] = flow
    flow_dict['-'.join([key_parts[1], key_parts[0], key_parts[2])] = flow

branch_flows = [flow_dict[key] for key in ordered_branches]

Building the dict should be O(n) (N inserts, each at amortized O(1)), traversing the ordered list should be O(n) and fetching the values from the dict should be O(1)). This is likely better than anything you could do by sorting.

Upvotes: 2

ecatmur
ecatmur

Reputation: 157484

You need to construct an appropriate key function to the Python sort function.

Ignoring the reversed-order issue, it's quite easy:

def key(branch):
    id, flows = branch
    return ordered_branches.index(id)

Considering the reversed-order issue, we can use:

def key(branch):
    id, flows = branch
    try:
        return ordered_branches.index(id)
    except ValueError:
        parts = id.split('-')
        id = '-'.join((parts[1], parts[0], parts[2]))
        return ordered_branches.index(id)

Now you can sort branch_flows as sorted(branch_flows, key=key).

You can speed this up by turning ordered_branches into a dictionary:

order_dict = dict((x, i) for i, x in enumerate(ordered_branches))

and instead of ordered_branches.index(id) use order_dict[id] (also change ValueError to KeyError).

As a time-space tradeoff you could construct the reversed-order ids in the dict:

def reverse_id(id):
    parts = id.split('-')
    return '-'.join((parts[1], parts[0], parts[2]))
order_dict = dict((x, i) for i, x in enumerate(ordered_branches))
order_dict.update((reverse_id(x), i) for x, i in order_dict.items())

Now your key function just looks like:

def key(branch):
    id, flows = branch
    return order_dict[id]

Upvotes: 3

Related Questions