Самый быстрый способ построить кортеж из элементов списка (Python) - PullRequest
0 голосов
/ 26 июня 2018

У меня есть 3 массива NumPy, и я хочу создать кортежи i-го элемента каждого списка. Эти кортежи представляют ключи для словаря, который я определил ранее.

Ex:

List 1: [1, 2, 3, 4, 5]

List 2: [6, 7, 8, 9, 10]

List 3: [11, 12, 13, 14, 15]

Desired output: [mydict[(1,6,11)],mydict[(2,7,12)],mydict[(3,8,13)],mydict[(4,9,14)],mydict[(5,10,15)]]

Эти кортежи представляют ключи словаря, который я определил ранее (по сути, как входные переменные для ранее вычисленной функции). Я читал, что это лучший способ хранить значения функций для поиска.

Мой текущий способ сделать это выглядит следующим образом:

[dict[x] for x in zip(l1, l2, l3)]

Это работает, но, очевидно, медленно. Есть ли способ векторизовать эту операцию или ускорить ее каким-либо образом? Я открыт для изменения способа хранения значений функций, если это необходимо.

РЕДАКТИРОВАТЬ: мои извинения за этот вопрос неясно. У меня действительно есть массивы NumPy. Моя ошибка - ссылаться на них как на списки и отображать их как таковые. Они одинаковой длины.

Ответы [ 2 ]

0 голосов
/ 26 июня 2018

Определите ваши 3 списка. Вы упоминаете 3 массива, но показывает списки (и называете их так же):

In [112]: list1,list2,list3 = list(range(1,6)),list(range(6,11)),list(range(11,16))

Теперь создайте словарь с ключами кортежей:

In [114]: dd = {x:i for i,x in enumerate(zip(list1,list2,list3))}
In [115]: dd
Out[115]: {(1, 6, 11): 0, (2, 7, 12): 1, (3, 8, 13): 2, (4, 9, 14): 3, (5, 10, 15): 4}

Доступ к элементам из этого словаря с помощью вашего кода:

In [116]: [dd[x] for x in zip(list1,list2,list3)]
Out[116]: [0, 1, 2, 3, 4]
In [117]: timeit [dd[x] for x in zip(list1,list2,list3)]
1.62 µs ± 11.2 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Теперь для эквивалента массива - превратите списки в 2d массив:

In [118]: arr = np.array((list1,list2,list3))
In [119]: arr
Out[119]: 
array([[ 1,  2,  3,  4,  5],
       [ 6,  7,  8,  9, 10],
       [11, 12, 13, 14, 15]])

Доступ к тем же элементам словаря. Если бы я использовал column_stack, я мог бы опустить .T, но это медленнее. (преобразование массива быстро)

In [120]: [dd[tuple(x)] for x in arr.T]
Out[120]: [0, 1, 2, 3, 4]
In [121]: timeit [dd[tuple(x)] for x in arr.T]
15.7 µs ± 21.2 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Обратите внимание, что это существенно медленнее. Итерация по массиву медленнее, чем итерация по списку. Вы не можете получить доступ к элементам словаря в каком-либо виде «векторизации» - вы должны использовать итерацию Python.

Я могу улучшить итерацию массива, сначала превратив его в список:

In [124]: arr.T.tolist()
Out[124]: [[1, 6, 11], [2, 7, 12], [3, 8, 13], [4, 9, 14], [5, 10, 15]]
In [125]: timeit [dd[tuple(x)] for x in arr.T.tolist()]
3.21 µs ± 9.67 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Время построения массива:

In [122]: timeit arr = np.array((list1,list2,list3))
3.54 µs ± 15.4 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [123]: timeit arr = np.column_stack((list1,list2,list3))
18.5 µs ± 11.4 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

С чистым Python itemgetter (с версии 3.6.3) экономия отсутствует:

In [149]: timeit operator.itemgetter(*[tuple(x) for x in arr.T.tolist()])(dd)
3.51 µs ± 16.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

и если я переместу определение получателя из цикла времени:

In [151]: %%timeit idx = operator.itemgetter(*[tuple(x) for x in arr.T.tolist()]
     ...: )
     ...: idx(dd)
     ...: 
482 ns ± 1.85 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
0 голосов
/ 26 июня 2018

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

>>> l1 = np.array([1, 2, 3, 4, 5])
>>> l2 = np.array([6, 7, 8, 9, 10])
>>> l3 = np.array([11, 12, 13, 14, 15])

Если это так, вы можете сложить их в двумерный массив:

>>> ll = np.stack((l1, l2, l3))

И тогда вы можете просто перенести это:

>>> lt = ll.T

Это лучше, чем векторизация; это постоянное время. NumPy просто создает другое представление тех же данных с другим шагом, поэтому оно читает в порядке столбцов, а не строк.

>>> lt
array([[ 1,  6, 11],
       [ 2,  7, 12],
       [ 3,  8, 13],
       [ 4,  9, 14],
       [ 5, 10, 15]])

Как указывает Мирадуло, вы можете сделать оба этих действия за один шаг с помощью column_stack:

>>> lt = np.column_stack((l1, l2, l3))

Но я подозреваю, что вы на самом деле захотите ll как самостоятельное значение. (Хотя, признаюсь, я просто догадываюсь, что вы пытаетесь сделать ...)


И, конечно, если вы хотите зациклить эти строки как одномерные массивы вместо выполнения дальнейшей векторизации, вы можете:

>>> for row in lt:
...:     print(row)
[ 1  6 11]
[ 2  7 12]
[ 3  8 13]
[ 4  9 14]
[ 5 10 15]

Конечно, вы можете преобразовать их из одномерных массивов в кортежи, просто вызвав tuple в каждой строке. Или ... каким бы ни было mydict (это не похоже на словарь - здесь нет пар ключ-значение, только значения), вы можете сделать это.

>>> mydict = collections.namedtuple('mydict', list('abc'))
>>> tups = [mydict(*row) for row in lt]
>>> tups
[mydict(a=1, b=6, c=11),
 mydict(a=2, b=7, c=12),
 mydict(a=3, b=8, c=13),
 mydict(a=4, b=9, c=14),
 mydict(a=5, b=10, c=15)]

Если вас беспокоит время поиска кортежа клавиш в диктовке, itemgetter в модуле operator имеет версию с C-ускорением. Если keys - это np.array, или tuple, или что-то еще, вы можете сделать это:

for row in lt:
    myvals = operator.itemgetter(*row)(mydict)
    # do stuff with myvals

Тем временем я решил собрать вместе расширение C, которое должно быть максимально быстрым (без обработки ошибок, потому что Я ленивый Это должно быть чуть-чуть быстрее - этот код будет вероятно, segfault, если вы дадите ему что-нибудь кроме dict и кортежа или списка):

static PyObject *
itemget_itemget(PyObject *self, PyObject *args) {
  PyObject *d;
  PyObject *keys;
  PyArg_ParseTuple(args, "OO", &d, &keys);    
  PyObject *seq = PySequence_Fast(keys, "keys must be an iterable");
  PyObject **arr = PySequence_Fast_ITEMS(seq);
  int seqlen = PySequence_Fast_GET_SIZE(seq);
  PyObject *result = PyTuple_New(seqlen);
  PyObject **resarr = PySequence_Fast_ITEMS(result);
  for (int i=0; i!=seqlen; ++i) {
    resarr[i] = PyDict_GetItem(d, arr[i]);
    Py_INCREF(resarr[i]);    
  }
  return result;
}

Время поиска 100 случайных ключей из словаря 10000 ключей на моем ноутбуке с python.org CPython 3.7 на macOS:

  • itemget.itemget: 1,6 мкс
  • operator.itemgetter: 1,8 мкс
  • понимание: 3,4 мкс
  • чистый Python operator.itemgetter: 6,7 мкс

Итак, я уверен, что все, что вы делаете, будет достаточно быстрым - это всего лишь 34 нс / ключ, который мы пытаемся оптимизировать. Но если это действительно слишком медленно, operator.itemgetter делает достаточно хорошую работу, перемещая цикл в C и разрезая его примерно пополам, что довольно близко к наилучшему результату, который вы могли ожидать. (Трудно представить, что все-таки можно зацикливать связку ключей в штучной упаковке в хеш-таблице намного меньше чем 16 нс / ключ.)

...