Эффективный способ перемешать списки в списке в Python - PullRequest
Новая
       31

Эффективный способ перемешать списки в списке в Python

6 голосов
/ 29 февраля 2020

Это похоже на вопрос, который уже должен был быть задан ранее, но я не смог его найти. Итак, вот и все.

Данные:
- мастер list (длина ~ = 16 000 000) подсписков (каждый имеет длину до 500 элементов) из str

Цель:
- эффективно перетасовать каждый из подсписков в основном списке.

Я попытался стритовать for -l oop, понимание списка, pandas Series.apply(), pandarallel и dask dataframe .apply() и .map_partition() методы.

A for -l oop занимает около 15 минут .
pd.series.apply(), dask.series.apply() и dask.series.map_partition() - все это удалось сделать чуть более 6 минут .

Мой вопрос «могу ли я добиться более быстрого перетасовки»? Допускается как создание новой копии, так и перетасовка на месте.

Ниже приведена моя попытка: 

def normal_shuffle(series):
    output = series.tolist()
    length = len(output)
    for i in range(length):
        random.Random().shuffle(output[i])
    return output

def shuffle_returned(a_list):
    new_list = a_list
    random.shuffle(new_list)
    return new_list

def shuffle_partition(a_partition):
    return a_partition.apply(shuffle_returned)

%time shuffled_for = normal_shuffle(test_series)
%time shuffled_apply = test_series.apply(shuffle_returned)

pandarallel.initialize(progress_bar=False, nb_workers=8)
%time shuffled_parallel_apply = test_series.parallel_apply(shuffle_returned)

test_ddf = ddf.from_pandas(test_series, npartitions=16)
test_ddf = test_ddf.reset_index(drop=True)

shuffled_ddf = test_ddf.apply(shuffle_returned, meta="some_str")
%time shuffled_ddf.persist()

shuffled_by_parttion_ddf = test_ddf.map_partitions(shuffle_partition, meta="productId")
%time shuffled_by_parttion_ddf.persist()

Теперь я пытаюсь использовать распределенный dask, чтобы увидеть, могу ли я каким-то образом пошатнуть обучение модели. и перемешивание данных, так что время обучения и время перемешивания накладываются друг на друга и достигают лучшей общей эффективности времени.

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

ОБНОВЛЕНИЕ

Перепробовав некоторые из предложенных вариантов, следующее оказалось самым быстрым, что я смог достичь, что также удивительно просто! 

%time [np.random.shuffle(x) for x in alist]

CPU times: user 23.7 s, sys: 160 ms, total: 23.9 s
Wall time: 23.9 s

Однопоточность numpy это путь к go здесь, кажется!

1 Ответ

0 голосов
/ 29 февраля 2020

@ TerryH - вам не нужно .shuffle() содержимое RAM-памяти aListOfSTRINGs вообще, этого должно быть достаточно для генерации np.random.permutation( len( aListOfListsOfSTRINGs[ ith ] ) ), чтобы создать рекламу -хо c, по цене, но O(1) ~ 260 [us] за список, потраченный ALAP, новый случайный порядок, правильный размер для косвенного доступа к str -члены i-го числа - aListOfSTRINGs
(зачем перемещать дорогостоящие данные ввода-вывода ОЗУ, чтобы "читать" по порядку где-то позже, когда нет необходимости в данных коснулся, пока ALAP не "считывает" из блоков, обслуживаемых кешем, используя косвенную адресацию компонентов?)

Для Реальных затрат от sh до go параллельно , вам может понравиться это сообщение, с интерактивным графическим инструментом.

Поскольку @ user2357112 поддерживает Monica , прокомментированный ниже,
перетасовка была направлена ​​на внутри aListOfSTRINGs, не on aListOfListsOfSTRINGs, Mea Culpa * 1 050 *

Q : " Можно ли добиться перетасовки быстрее "?

Да. Много. ... 150 x раз - значительно меньше 2.5 [s] достижимо с помощью достаточно правильных инструментов

Q : "... как Я могу сделать операцию перетасовки более эффективной ?"

На месте .shuffle() занимает менее ~ 23 [s] на list( L ) более 16 000 000 элементов в простых инструментах Py2.7 

from zmq import Stopwatch; aClk = Stopwatch() #_______________________ a [us] Stopwatch
pass;    import random

#_____________L creation ~ 2.7 [s]___________________________________________
aClk.start(); L = [ strID for strID in xrange( int( 16E6 ) ) ]; aClk.stop()
2721084

print L[:5] #___________________________________________________________proof
[0, 1, 2, 3, 4]

#_____________random.shuffle( L )______________________________________+proof
aClk.start(); random.shuffle( L ); aClk.stop(); print "0:5\t", L[:5]
21473261
0:5     [13868243, 13087869, 13207292, 9344202, 1853783]

#_____________random.shuffle( L )______________________________________+proof
aClk.start(); random.shuffle( L ); aClk.stop(); print "0:5\t", L[:5]
22573922
0:5     [837396, 15032889, 10942767, 14571341, 4867854]

#_______________________________________________________________________proof
>>> len( L )
16000000

На месте .shuffle() принимает ~ 48 [s] на list( L ) более 16 000 000 элементов в простых инструментах Py3.5. 

$ conda activate py3
$ python
...
aClk.start(); L = [ strID for strID in  range( int( 16E6 ) ) ]; aClk.stop()
1959052

#_____________random.shuffle( L )______________________________________+proof
aClk.start(); random.shuffle( L ); aClk.stop(); print( "0:5\t", L[:5] )
45104806
0:5     [15744525, 10635923, 14530509, 10535840, 1465987]

#_____________random.shuffle( L )______________________________________+proof
aClk.start(); random.shuffle( L ); aClk.stop(); print( "0:5\t", L[:5] )
47139358
0:5     [884437, 15420153, 9957947, 8118734, 11960914]

Давайте go получим повышение Реальной производительности: 

import numpy as np

#____________L_as_a32______________16E6________________________~ 74 [ms]
>>> aClk.start(); a32 = np.arange( 16E6, dtype = np.int32 ); aClk.stop()
74054

#_____________np.random.shuffle( a32-bit )______________________________+proof
aClk.start(); np.random.shuffle( a32 ); aClk.stop(); print "0:5\t", a32[:5]
2400786
0:5     [ 2487493 14646705 13717283  5602561  7934593]

aClk.start(); np.random.shuffle( a32 ); aClk.stop(); print "0:5\t", a32[:5]
2368381
0:5     [ 4841042 12882529 12298351  2198866  7054284]

aClk.start(); np.random.shuffle( a32 ); aClk.stop(); print "0:5\t", a32[:5]
2369011
0:5     [14595649  7239135  3339593  9517600  6506681]

#_____________np.random.shuffle( a64-bit )______________________________+proof
aClk.start(); np.random.shuffle( a64 ); aClk.stop(); print "0:5\t", a64[:5]
2424487
0:5     [ 3234133  9224551   971604 13027484   806393]

aClk.start(); np.random.shuffle( a64 ); aClk.stop(); print "0:5\t", a64[:5]
2386873
0:5     [ 3212124 10644428  8192909  2234984 13103406]

aClk.start(); np.random.shuffle( a64 ); aClk.stop(); print "0:5\t", a64[:5]
2376065
0:5     [ 5624301  7741070  8859092 12287465 11721315]

Если вы действительно собираетесь получить Максимальную производительность:

  • сохранить все str данные как есть хранится в aListOfSTRINGs
  • каждый новый aListOfSTRINGs с постоянной стоимостью O(1) в не перетасованном, линейно растущем хранилище постоянного порядка - aListOfListsOfSTRINGs
  • вместо того, чтобы платить ужасно высокие затраты на ввод-вывод памяти, тасуя это хранилище * 112 9 * сделав aListOfListsOfSTRINGs, скорее сохраните aListOfORDINALs (будь то простой массив list или numpy, где просто добавляется len( aListOfListsOfSTRINGs ), всякий раз, когда новый член - aListOfSTRINGs вошел)
  • наслаждайтесь очень быстро и очень эффективно на месте aListOfORDINALs.shuffle(), хорошо под 23 [s] в Py2.7 или < 50 [s] в Py3.5
  • доступ ко всем str -s как
    aListOfListsOfSTRINGs[aListOfORDINALs[Nth_L_inLoLoStr]][Nth_str_inLoStr] в сверхбыстрое время по стоимости O(1), чтобы получить фактические str -s
...