Самый быстрый способ сортировки нескольких списков - Python

Question

У меня есть два списка, x и y, и я хочу сортировать x и переставлять y по перестановке x-сортировки. Например, при

x = [4, 2, 1, 3] 
y = [40, 200, 1, 30] 

Я хочу, чтобы получить

x_sorted = [1,2,3,4] 
y_sorted = [1, 200, 30, 40] 

Как обсуждалось в предыдущих вопросах, простой способ решить это

x_sorted, y_sorted = zip(*sorted(zip(x,y))) 

Вот мой вопрос: Что такое Самый быстрый способ сделать это?

---

У меня есть три метода для выполнения задачи.

import numpy as np 
x = np.random.random(1000) 
y = np.random.random(1000) 

Метод 1:

x_sorted, y_sorted = zip(*sorted(zip(x,y))) #1.08 ms 

Метод 2:

foo = zip(x,y) 
foo.sort() 
zip(*foo)  #1.05 ms 

метод 3;

ind = range(1000) 
ind.sort(key=lambda i:x[i]) 
x_sorted = [x[i] for i in ind] 
y_sorted = [y[i] for i in ind] #934us 

Есть ли лучший способ, который выполняется быстрее, чем три метода?

---

Дополнительные вопросы.

1. Почему метод 2 не быстрее, чем метод 1, хотя он использует метод сортировки?
2. Если я выполняю метод 2 отдельно, он быстрее. В IPython терминале

У меня есть

%timeit foo = zip(x,y) #1000 loops, best of 3: 220 us per loop 
%timeit foo.sort()  #10000 loops, best of 3: 78.9 us per loop 
%timeit zip(*foo)  #10000 loops, best of 3: 73.8 us per loop 

Answer 1

>>> x = [4, 2, 1, 3] 
>>> y = [40, 200, 1, 30]  
>>> x_sorted, y_sorted = zip(*sorted(zip(x, y), key=lambda a:a[0])) 
>>> x_sorted 
(1, 2, 3, 4) 
>>> y_sorted 
(1, 200, 30, 40) 

Производительность:

>>> timeit('foo = zip(x,y); foo.sort(); zip(*foo)', 'from __main__ import x, y', number=1000) 
1.0197240443760691 
>>> timeit('zip(*sorted(zip(x,y)))', 'from __main__ import x, y', number=1000) 
1.0106219310922597 
>>> timeit('ind = range(1000); ind.sort(key=lambda i:x[i]); x_sorted = [x[i] for i in ind]; y_sorteds = [y[i] for i in ind]', 'from __main__ import x, y', number=1000) 
0.9043525504607857 
>>> timeit('zip(*sorted(zip(x, y), key=lambda a:a[0]))', 'from __main__ import x, y', number=1000) 
0.8288150863453723 

Чтобы увидеть полную картину:

>>> timeit('sorted(x)', 'from __main__ import x, y', number=1000) 
0.40415491505723367   # just getting sorted list from x 
>>> timeit('x.sort()', 'from __main__ import x, y', number=1000) 
0.008009909448446706   # sort x inplace 

метод @falsetru - Самый быстрый для np.Массивы

>>> timeit('order = np.argsort(x); x_sorted = x[order]; y_sorted = y[order]', 'from __main__ import x, y, np', number=1000) 
0.05441799872323827 

Как @AshwiniChaudhary предложил в комментариях, для списков есть способ ускорить его с помощью itertools.izip вместо zip:

>>> timeit('zip(*sorted(izip(x, y), key=itemgetter(0)))', 'from __main__ import x, y;from operator import itemgetter;from itertools import izip', number=1000) 
0.4265049757161705 

Answer 2

Использование numpy.argsort:

>>> import numpy as np 
>>> x = np.array([4,2,1,3]) 
>>> y = np.array([40,200,1,30]) 
>>> order = np.argsort(x) 
>>> x_sorted = x[order] 
>>> y_sorted = y[order] 
>>> x_sorted 
array([1, 2, 3, 4]) 
>>> y_sorted 
array([ 1, 200, 30, 40]) 

---

>>> timeit('order = np.argsort(x); x_sorted = x[order]; y_sorted = y[order]', 'from __main__ import x, y, np', number=1000) 
0.030632019043 

ПРИМЕЧАНИЕ

Это имеет смысл, если входные данные уже Numpy массивы.

Answer 3

Вы не синхронизации это правильно

%timeit foo.sort() 

После 1-го цикла, это уже отсортирован для остатка. Timsort очень эффективен для предварительно отсортированных списков.

Я был немного удивлен тем, что использование Романом ключевой функции было намного быстрее. Вы можете улучшить это далее с помощью itemgetter

from operator import itemgetter 
ig0 = itemgetter(0) 
zip(*sorted(zip(x, y), key=ig0)) 

Это примерно 9% быстрее, чем при использовании функции лямбды для списков 1000 элементов