Блог

Главная - Вопросы по программированию - Какой наиболее эффективный способ перебора набора с некоторыми условиями?

Какой наиболее эффективный способ перебора набора с некоторыми условиями?

#python #optimization #set #conditional-statements #list-comprehension

#python #оптимизация #набор #условные операторы #понимание списка

Вопрос:

У меня настроено моделирование, в котором у меня есть набор кортежей. Каждый кортеж содержит индексы для определенной позиции в моем массиве numpy.

В какой-то момент мне приходится перебирать этот набор кортежей, чтобы применить 3 условия для фильтрации индексов, а затем я выбираю случайный кортеж. Мой код выглядит следующим образом:

 def fillASRS(arr, fillLevel):
    toFill = round(float(vol*(fillLevel/100)))
    shape = arr.shape
    arr_1D = arr.reshape(-1)
    inds = np.random.choice(arr_1D.size, toFill, replace = False)
    arr_1D[inds] = 1
    arr_3D = np.array(arr_1D.reshape(shape))
    arr_3D.astype(np.int8)
    return arr_3D

warehouse = np.zeros([ASdepth,ASheight,ASlength])
warehouse = warehouse.astype(np.int8)
fillASRS(warehouse, z)
zeros = set(map(tuple,np.argwhere(warehouse==0)))

Это выполняется в начале, мой 3D-массив numpy создается и заполняется единицами и 0, и создается мой набор позиций, в которых массив равен 0.

После этого мой код выглядит так:

 def reloc_findSpot(coords):
    new_arr=[ele for ele in zeros if ele[0]==coords[0] if 1 not in warehouse[:ele[0],ele[1],ele[2]] if (warehouse[-(ASdepth-1-ele[0]):,ele[1],ele[2]] == warehouse[-(ASdepth-1-coords[0]):,coords[1],coords[2]]).all]
    random_idx=np.random.randint(len(new_arr))
    relocSpot = new_arr[random_idx]
    return relocSpot

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

Выполнение моей программы занимает очень много времени (я выполняю 1000-100000 итераций в зависимости от теста), и когда я ее профилировал, она сказала мне, что большая часть моего времени выполнения тратится на понимание этого списка, как показано здесь:

    Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.038    0.038   10.004   10.004 c:UsersEduardoDesktopThesis DocsSIMULATIONSimulation_Test.py:247(start)
      526    0.009    0.000    9.662    0.018 c:UsersEduardoDesktopThesis DocsSIMULATIONSimulation_Test.py:232(relocation)
      526    0.003    0.000    9.652    0.018 c:UsersEduardoDesktopThesis DocsSIMULATIONSimulation_Test.py:374(reloc_findSpot)
      526    9.643    0.018    9.643    0.018 c:UsersEduardoDesktopThesis DocsSIMULATIONSimulation_Test.py:375(<listcomp>)
      500    0.013    0.000    5.330    0.011 c:UsersEduardoDesktopThesis DocsSIMULATIONSimulation_Test.py:140(retrieval_Iteration)
      500    0.012    0.000    4.627    0.009 c:UsersEduardoDesktopThesis DocsSIMULATIONSimulation_Test.py:108(storage_Iteration)
     1000    0.051    0.000    0.269    0.000 c:UsersEduardoDesktopThesis DocsSIMULATIONSimulation_Test.py:363(rnd_findSpot)
     1000    0.187    0.000    0.204    0.000 C:UsersEduardoAppDataLocalProgramsPythonPython38-32librandom.py:315(sample)

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

При необходимости дополнительная информация:

  • Мой склад представляет собой трехмерный массив numpy с 1 и 0
  • Набор кортежей обновляется с указанием местоположений 0 и 1 по мере изменения этих значений на протяжении всего моего моделирования.
  • Третье условие в моем понимании списка дает мне достаточно близкие результаты, но я не очень уверен в своем понимании сравнения фрагментов данных.

Спасибо за вашу помощь!

Комментарии:

1. Можете ли вы попробовать использовать np.fromiter((x for x in arr if condition), dtype=arr.dtype) ? Я считаю, что это намного быстрее, чем делать [x for x in arr if condition] . Пожалуйста, попробуйте и прокомментируйте, если работает

2. Если вам нужна помощь в понимании списка, я предлагаю вам предоставить некоторые минимальные образцы входных данных, которые можно использовать в качестве входных данных для понимания списка. Затем мы можем поработать над альтернативой пониманию списка, передать те же входные данные альтернативе и, наконец, проверить, идентичен ли результат списку, полученному с помощью понимания списка. Это единственный способ двигаться вперед, потому что за пределами вашего reloc_findSpot() мы не будем иметь понятия, какой именно список был создан вашим пониманием списка.

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

4. Я думаю, что добился некоторого прогресса в понимании вашего списка, но одна вещь меня озадачивает. В конце вашего понимания списка есть all . Предполагалось ли, что это вызов np.ndarray.all() ? Если да, то почему это просто all , а не all() так?

5. Я считаю, что all это ошибка программирования, и ее необходимо исправить all() . Но это обязательно изменит результаты. Вы упомянули, что в настоящее время у вас есть «достаточно близкие результаты», но я считаю, что они могут стать неактуальными после этого исправления. Это означает, что вам необходимо повторно проверить и подтвердить правильность , прежде чем решать проблему скорости. Вариант (А) Вы хотите отказаться от 3-го условия и оптимизировать понимание списка для ускорения?, ИЛИ вариант (Б) Сделайте паузу здесь и вернитесь после проверки того, что 3-е условие после исправления все еще дает «достаточно близкие результаты»?

Ответ №1:

Это частичное решение, которое даст умеренное улучшение скорости.

Он по-прежнему использует понимание списка, но перебирает гораздо меньший диапазон «кортежей». (Итераций будет гораздо меньше)

Я упоминаю «кортежи» в двойных кавычках, потому что в этом решении zeros больше set tuple нет объектов. Вместо zeros этого это 2-мерный numpy массив формы (N,3) для некоторого большого N .

Подробные сведения:

Шаг 1 из 3:

Замените строку zeros = set(map(tuple,np.argwhere(warehouse==0))) на это:

 zeros = np.argwhere(warehouse==0)

Шаг 2 из 3:

В reloc_findSpot() , перед пониманием списка, введите эту строку:

 filt_zeros = zeros[zeros[:,0] == coords[0]]

Шаг 3 из 3:

В понимании списка:

  1. Замените все zeros на filt_zeros
  2. Удалите первое условие

Дайте мне знать, как это работает с вашим полномасштабным набором данных.

Комментарии:

1. Большое вам спасибо! К сожалению, это не сильно сократило время. В итоге я немного изменил характер своей модели, достаточно, чтобы мои результаты оставались правильными, но мой код намного быстрее.

Ответ №2:

Итак, в конце концов, мое решение состояло в том, чтобы изменить мой алгоритм поиска. reloc_findSpot() больше не создает список всех возможных позиций, а затем выбирает одну. Теперь он возвращает первый элемент, соответствующий моим условиям в zeros наборе.

Это сократило время выполнения с 15 секунд до 0,4 секунды для выполнения 1000 циклов (придется проверять эффективность для гораздо большего числа циклов, но это уже значительное улучшение). Это было достигнуто с помощью строки relocSpot = next(ele for ele in zeros if ele[0]==coords[0] if 1 not in warehouse[:ele[0],ele[1],ele[2]] if (warehouse[-(ASdepth-1-ele[0]):,ele[1],ele[2]] == warehouse[-(ASdepth-1-coords[0]):,coords[1],coords[2]]).all())

Кажется, на мои результаты это не повлияло (я думаю, поскольку наборы не упорядочены, первый элемент, соответствующий условиям, в любом случае всегда случайный). Спасибо всем за вашу помощь!