Как мне отойти от школы мысли «за петлей»?

79

Это довольно концептуальный вопрос, но я надеялся получить хороший совет по этому вопросу. Я занимаюсь программированием с массивами ( NumPy ); Мне часто приходится сопоставлять элементы в двух или более массивах разных размеров, и первое, на что я обращаюсь - это цикл for или, что еще хуже, вложенный цикл for. Я хочу как можно больше избегать циклов for, потому что они медленные (по крайней мере, в Python).

Я знаю, что для многих вещей с NumPy есть предопределенные команды, которые мне просто нужно исследовать, но есть ли у вас (как у более опытных программистов) общий мыслительный процесс, который приходит на ум, когда вам приходится что-то повторять?

Поэтому у меня часто бывает что-то подобное, что ужасно, и я хочу этого избежать:

small_array = np.array(["one", "two"])
big_array = np.array(["one", "two", "three", "one"])

for i in range(len(small_array)):
    for p in range(len(big_array)):
        if small_array[i] == big_array[p]:
            print "This item is matched: ", small_array[i]

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

репа
источник
10
Вы ищете функциональное программирование : лямбда-выражения, функции высшего порядка, генерация выражений и т. Д. Google тем.
Килиан Фот
42
I want to avoid for-loops as much as possible because they are slow (at least in Python).Похоже, вы решаете не ту проблему здесь. Если вам нужно перебрать что-то, вам нужно перебрать что-то; Вы получите аналогичный удар по производительности независимо от того, какую конструкцию Python вы используете. Если ваш код медленный, это не потому, что у вас есть forциклы; это потому, что вы выполняете ненужную работу или работу на стороне Python, что может быть сделано на стороне C. В вашем примере вы делаете дополнительную работу; Вы могли бы сделать это с одним циклом вместо двух.
Довал
24
@Doval К сожалению нет - в NumPy . Цикл Python for, выполняющий поэлементное сложение, может быть в несколько раз (!) Медленнее, чем векторизованный оператор NumPy (который не только написан на C, но использует инструкции SSE и другие приемы) для реалистичных размеров массива.
46
Некоторые из приведенных выше комментариев, похоже, неправильно понимают вопрос. При программировании в NumPy вы получите наилучшие результаты, если сможете векторизовать свои вычисления, то есть заменить явные циклы в Python операциями с целыми массивами в NumPy. Это концептуально сильно отличается от обычного программирования на Python и требует времени для изучения. Поэтому я думаю, что для ОП целесообразно попросить совета о том, как научиться делать это.
Гарет Рис
3
@PieterB: Да, все верно. «Векторизация» - это не то же самое, что «выбор лучшего алгоритма». Они представляют собой два отдельных источника трудностей при разработке эффективных реализаций, и поэтому лучше думать о них по одному.
Гарет Рис

Ответы:

89

Это общая концептуальная трудность при обучении эффективному использованию NumPy . Обычно обработка данных в Python лучше всего выражается в терминах итераторов , чтобы сохранить низкое использование памяти, чтобы максимизировать возможности параллелизма с системой ввода / вывода, а также обеспечить повторное использование и комбинацию частей алгоритмов.

Но NumPy переворачивает все это наизнанку: наилучший подход состоит в том, чтобы выразить алгоритм в виде последовательности операций с целым массивом , чтобы минимизировать количество времени, затрачиваемого на медленный интерпретатор Python, и максимизировать количество времени, затрачиваемого на процедуры быстрой компиляции NumPy.

Вот общий подход, который я использую:

  1. Сохраняйте исходную версию функции (которая, как вы уверены, является правильной), чтобы вы могли проверить ее на соответствие улучшенным версиям как на правильность, так и на скорость.

  2. Работа изнутри: то есть начните с самого внутреннего цикла и посмотрите, можно ли векторизовать; затем, когда вы это сделаете, выйдите на один уровень и продолжайте.

  3. Потратьте много времени на чтение документации NumPy . Там много функций и операций, и они не всегда блестяще названы, поэтому стоит их узнать. В частности, если вы обнаружите, что думаете: «Если бы существовала функция, которая выполняла то-то и то-то», тогда стоит потратить десять минут на ее поиск. Обычно это где-то там.

Там нет замены для практики, поэтому я собираюсь дать вам несколько примеров проблем. Цель каждой проблемы - переписать функцию так, чтобы она была полностью векторизована : то есть, чтобы она состояла из последовательности операций NumPy над целыми массивами, без собственных циклов Python (без операторов forили whileоператоров, без итераторов или пониманий).

Проблема 1

def sumproducts(x, y):
    """Return the sum of x[i] * y[j] for all pairs of indices i, j.

    >>> sumproducts(np.arange(3000), np.arange(3000))
    20236502250000

    """
    result = 0
    for i in range(len(x)):
        for j in range(len(y)):
            result += x[i] * y[j]
    return result

Проблема 2

def countlower(x, y):
    """Return the number of pairs i, j such that x[i] < y[j].

    >>> countlower(np.arange(0, 200, 2), np.arange(40, 140))
    4500

    """
    result = 0
    for i in range(len(x)):
        for j in range(len(y)):
            if x[i] < y[j]:
                result += 1
    return result

Проблема 3

def cleanup(x, missing=-1, value=0):
    """Return an array that's the same as x, except that where x ==
    missing, it has value instead.

    >>> cleanup(np.arange(-3, 3), value=10)
    ... # doctest: +NORMALIZE_WHITESPACE
    array([-3, -2, 10, 0, 1, 2])

    """
    result = []
    for i in range(len(x)):
        if x[i] == missing:
            result.append(value)
        else:
            result.append(x[i])
    return np.array(result)

Спойлеры ниже. Вы получите гораздо лучшие результаты, если сами попробуете, прежде чем смотреть на мои решения!

Ответ 1

np.sum (x) * np.sum (y)

Ответ 2

np.sum (np.searchsorted (np.sort (x), y))

Ответ 3

np.where (x == отсутствует, значение, x)

Гарет Рис
источник
Подождите, есть ли опечатка в последнем ответе или NumPy изменяет то, как Python интерпретирует код?
Изката
1
@Izkata Само по себе ничего не изменяет, но логические операции, применяемые к массивам, определены для возврата логических массивов.
Сапи
@sapi Ах, я пропустил то, что происходит в doctests, думал, что это было простоlist
Izkata
Может быть, должен быть способ встраивать APL?
Мне нравится, как вы даете домашнее задание.
Корай Тугай
8

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

Для нетривиальных размеров малого массива и большого массива (скажем, small = 100 элементов и big = 10.000 элементов) один из способов сделать это - отсортировать небольшой массив, затем выполнить итерацию по большому массиву и использовать двоичный поиск для поиска подходящих элементов. в небольшом массиве.

Это сделало бы максимальную сложность по времени O (N log N) (а для маленьких маленьких массивов и очень больших больших массивов это ближе к O (N)), где ваше решение с вложенным циклом равно O (N ^ 2)

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

Питер Б
источник
-3

Вы можете использовать словарь, чтобы значительно оптимизировать производительность

Это еще один пример:

locations = {}
for i in range(len(airports)):
    locations[airports["abb"][i][1:-1]] = (airports["height"][i], airports["width"][i])

for i in range(len(uniqueData)):
    h, w = locations[uniqueData["dept_apt"][i]]
    uniqueData["dept_apt_height"][i] = h
    uniqueData["dept_apt_width"][i] = w
Якуб Барес
источник
2
Это совершенно очевидно, что мы все еще пользуемся школой мысли «для петли».
8bittree