CODEWITHSUNDEEP
pythonlistsorting
Ólafur Aron
Ólafur Aron

Reputation: 352

Relative order of elements in list

I'm writing a function that takes in a list of integers and returns a list of relative positioned elements.

That is to say, if my input into said function is [1, 5, 4] the output would be [0, 2, 1], since 1 is the lowest element, 5 is the highest and 4 in the middle, all elements are unique values, or a set()

But code speaks, the function i have so far is

def relative_order(a):
    rel=[]
    for i in a:
        loc = 0
        for v in a:
            if i > v:
                loc += 1
        rel.append(loc)
    return rel

It does work, but since i'm sending big lists into this function, and i have to compare each element to all elements in each iteration it's taking ~5sec with a list of 10.000 elements.

My question is how can i improve the speed on said function and maybe be a bit more Pythonic, i tried comprehension lists, but my Python skills are lacking and i only came up with an imperative way of implementing this problem.

Upvotes: 9

Views: 5526

Answers (5)

akk
akk

Reputation: 269

Your question is about sorting. I would recommend the use of Numpy or 'Numeric Python'. Numpy is a Python module that is optimised for "fast, compact, multidimensional array faciliities". It is the package of choice for scientific computing in Python. http://www.numpy.org/

import numpy as np

input_array = np.array([1, 5, 4])
sorted_indices = np.argsort(input_array)

print sorted_indices
#[0 2, 1]

I have also added profiler output based on an array of size 50000. It shows this method is (around 4x) faster than using the Python sorted function as per earlier answers.

ncalls  tottime  percall  cumtime  percall filename:lineno(function)

    1    0.009    0.009    0.009    0.009 {method 'argsort' of 'numpy.ndarray' objects}
    1    0.034    0.034    0.034    0.034 {sorted}

Warning: Commentary suggested the answer is not inline with the authors function. This is true. I guess the whole point of argsort is that:

sorted_array = input_array[sorted_indices]

gives you a sorted array.

The OP is, curious to my mind, asking for a result which requires a sorted array to be available via:

for i, val in enumerate(sorted_indices):
    sorted_array[val] = input_array[i]

Upvotes: -1

Óscar López
Óscar López

Reputation: 236034

This can be written as a list comprehension like this:

lst = [1, 5, 4]
s = sorted(lst)    
[s.index(x) for x in lst]
=> [0, 2, 1]

And here's another test, using @frb's example:

lst = [10, 2, 3, 9]
s = sorted(lst)    
[s.index(x) for x in lst]
=> [3, 0, 1, 2]

Upvotes: 12

Dyno Fu
Dyno Fu

Reputation: 9044

def relative_order(a):
    l = sorted(a)
    # hash table of element -> index in ordered list
    d = dict(zip(l, range(len(l))))
    return [d[e] for e in a]

print relative_order([1, 5, 4])
print relative_order([2, 3, 1])
print relative_order([10, 2, 3, 9])

[0, 2, 1]
[1, 2, 0]
[3, 0, 1, 2]

the algorithm should be as efficient as sort, but use additional space.

Upvotes: 1

Jon Clements
Jon Clements

Reputation: 142176

Here's another go that should be more efficient that keeping .index'ing into the list as it's stated that no duplicate values will occur, so we can do the lookup O(1) instead of linear... (and actually meets the requirements):

>>> a = [10, 2, 3, 9]
>>> indexed = {v: i for i, v in enumerate(sorted(a))}
>>> map(indexed.get, a)
[3, 0, 1, 2]

Upvotes: 11

Anon
Anon

Reputation: 21

The method you have a̶n̶d̶ ̶t̶h̶e̶ ̶c̶u̶r̶r̶e̶n̶t̶ ̶a̶n̶s̶w̶e̶r̶ takes order n^2 time.

This should work in log(n) time:

def relative_order(a):
    positions = sorted(range(len(a)), key=lambda i: a[i])
    return sorted(range(len(a)), key = lambda i: positions[i])

It's still order log(n) and so should work for your large lists too.

Edit:

Outside of lambda.

Upvotes: 1

Related Questions