Как распараллелить этот запрос в Python (так же, как PLINQ)?

avatar
Sergio0694
8 апреля 2018 в 11:05
159
1
0

У меня возникли проблемы с запросом, который я написал на Python (пришлось использовать его для TensorFlow), который работает нормально, но слишком медленно, так как входной набор данных довольно большой. Выполнение запроса может занять более 5 минут, и, проверив диспетчер задач, я могу подтвердить, что он действительно работает на одном ядре.

Вот код:

# Assume words is a list of strings
for i, pair in enumerate(sorted(
    ((word, words.count(word))          # Map each word to itself and its count
        for word in set(words)),        # Set of unique words (remove duplicates)
    key=lambda p: p[1],                 # Order by the frequency of each word
    reverse=True)):                     # Descending order - less frequent words last

    # Do stuff with each sorted pair

Что я здесь делаю, так это просто беру входной список words, избавляюсь от дубликатов, затем сортирую слова в порядке убывания в зависимости от их частоты во входном тексте.

Если бы мне нужно было написать это на C# с помощью PLINQ, я бы сделал что-то вроде этого:

var query = words.AsParallel().Distinct()
            .OrderByDescending(w => words.Count(s => s.Equals(w)))
            .Select((w, i) => (w, i));

Я не смог найти простого способа переписать реализацию paralell на Python с использованием, возможно, встроенных библиотек. Я видел несколько руководств по расширению Pool, но похоже, что это всего лишь эквивалент параллельной операции Select, так что я все еще не понимаю, как реализовать операции Distinct и OrderByDescending в Python, параллельно.

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

Спасибо!

Источник

Ответы (1)

avatar
roganjosh
8 апреля 2018 в 14:47
0

Проблема с вашим текущим подходом в основном связана с words.count(word) внутри цикла for. Это означает, что вы перебираете весь список для каждого уникального слова в set(words) и считаете только одно слово... вместо этого вы можете использовать Counter и сделать один проход вашего списка. Объект Counter — это словарь, который вы можете использовать для своего ключа при сортировке с частотой поиска O(1). Даже для 1000 "слов" в моем примере ускорение драматическое... для более длинных вводов мне надоело ждать завершения timeit :)

import string
from collections import Counter
import numpy as np # Just to create fake data

# Create some fake data
letters = list(string.ascii_lowercase)
new_words = [''.join(list(np.random.choice(letters, 3, replace=True))) 
             for x in range(1000)]


def original(search_list):
    """ Your current approach """
    for i, pair in enumerate(sorted(
    ((word, search_list.count(word)) 
        for word in set(search_list)),
    key=lambda p: p[1],
    reverse=True)):    
        pass


def new_approach(search_list):
    freq = Counter(search_list)
    search_list = sorted(search_list, key=lambda x: freq[x], reverse=True)
    new_list = []
    checked = set()
    for item in search_list:
        if item not in checked:
            new_list.append(item)
            checked.add(item)

Для списка из 1000 "слов":

%timeit original(new_words)
26.6 ms ± 289 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)


%timeit new_approach(new_words)
833 µs ± 30 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

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

РЕДАКТИРОВАТЬ:

Как указано в ОП, мы можем пропустить промежуточный список и установить его, просто отсортировав объект счетчика:

def new_approach(search_list):
    freq = Counter(search_list)
    search_list = enumerate(sorted(freq, key=lambda x: freq[x], reverse=True))

Новое время:

%timeit new_approach(new_words)
438 µs ± 6.31 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Sergio0694
8 апреля 2018 в 16:16
0

Спасибо, класс Counter идеально подходит для решения этой проблемы! Однако я не понимаю код, который вы разместили, я имею в виду, почему вы вызываете sorted в исходном search_list, который содержит дубликаты? Не лучше ли просто вызвать sorted для объекта freq (поскольку словарь может повторяться), а затем просто enumerate для этого отсортированного списка? В конце концов, мне просто нужно перебрать эти уникальные слова в порядке убывания, я не уверен, почему вы создаете эти две дополнительные переменные new_list и checked.

roganjosh
8 апреля 2018 в 16:20
0

@ Sergio0694 хороший вопрос! Сначала см. это... Затем я изучил реализации упорядоченных наборов, и это добавляет партию сложности, которую я не считал необходимой. Последние версии Python сохраняют порядок как точку реализации, а не то, на что можно положиться... сейчас это меняется в выпусках (3.6/3.7).

Sergio0694
8 апреля 2018 в 16:23
0

Я не говорил о порядке сортировки словаря (поскольку словари по определению не имеют определенного порядка ключей), я имею в виду: почему бы вам просто не вызвать enumerate(sorted(freq, key=lambda x: freq[x], reverse=True)) вместо повторения исходного списка , а затем создать эти два дополнительных списка/набора позже? Отсортированный список, возвращаемый sorted, уже должен быть тем, что я искал (независимо от конкретного порядка словаря, который, как вы сказали, зависит от конкретной реализации), верно?

roganjosh
8 апреля 2018 в 16:33
0

@ Sergio0694 Sergio0694 Думаю, вы вполне правы, я не могу сейчас протестировать 2.7. Пока я не буду в этом уверен, мне все равно придется генерировать список ключей из словаря, а затем сортировать его, поэтому я не уверен, что вы много выиграете. Я не хочу обновлять ответ, пока не смогу проверить.

roganjosh
8 апреля 2018 в 16:38
1

@ Sergio0694 Sergio0694 Я не вижу, как на самом деле это будет отличаться в P 2.7, поэтому я обновлю ответ, указав время. Спасибо, что указали на это.