Улучшить быстродействие кода python

Question

Функция transform_input выполняет следующие действия:

• Параметр combination представляет собой список кортежей (размер этого списка обычно равен 6), содержащий 1 или 2 значения.
• Затем удаляется вся избыточность внутри combination. То, что я называю избыточностью, - это удаление дубликатов и удаление кортежей, которые содержат те же значения, которые поменялись местами. Примеры избыточных кортежей: (2,3) and (3,2), (7,) and (7,), (1,2) and (1,2).
• Полученный кортеж должен быть в порядке возрастания. Пример: (2,4), а не (4,2).
• Порядок результирующего списка не важен.
• Все значения кортежей являются натуральными числами.

Код, который я придумал, показан ниже (с работающим примером):

def transform_input(combination):
  combination = [list(elem) for elem in combination]
  for t in combination:
      t.sort()
  combination = [tuple(elem) for elem in combination]
  combination = list(set(combination))
  return combination

my_input = [
[(3,8), (8,3), (7,)],
[(8,8), (8,8)],
[(3,), (7,), (6,), (3,), (7,)],
[(2,3), (3,2)],
[(2,), (2,)]
]

for comb in my_input:
  print(transform_input(comb))

Вывод:

[(3, 8), (7,)]
[(8, 8)]
[(6,), (7,), (3,)]
[(2, 3)]
[(2,)]

Есть ли каким образом я могу улучшить быстродействие transform_input?

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

Answer 1

Здесь два других возможных подхода; во-первых, это небольшая вариация ответа, отправленного Błotosmętek с использованием {} вместо set (в списках с очень небольшим количеством элементов оно должно быть быстрее, посмотрите здесь и здесь ).

def transform_input3(combination):
    return list({tuple(sorted(elem)) for elem in combination})

Другой подход основан на функции map (т. е. с использованием итераторов).

def transform_input4(combination):
    return list(set(map(tuple, map(sorted, combination))))

Если внутренние кортежи не может содержать более 2 элементов, вы можете реализовать что-то подобное, чтобы избежать сортировки каждого из них и преобразования из list в tuple:

def transform_input6(combination):
    return [t for t in {x[::-1] if x[0] > x[-1] else x for x in combination}]

Я добавил некоторые элементы в ваш my_input (и тот, который использовался alireza yazdandoost ) и сравнивал все подходы, выполняя каждую функцию 100 раз для каждого элемента; это новый my_input:

my_input = [
    [(3, 8), (8, 3), (7,)],
    [(3, 8), (8, 3), (7,), (3, 8), (8, 3), (7,)],
    [(8, 8), (8, 8)],
    [(3,), (7,), (6,)],
    [(3,), (7,), (6,), (3,), (7,), (3,)],
    [(2, 3), (3, 2), (2, 3), (3, 2), (2, 3), (3, 2), (2, 3), (3, 2), (2, 3), (3, 2), (2, 3), (3, 2)],
    [(2,), (2,)],
    [(2,), (2,), (2,), (2,), (2,), (2,)],
    [(3, 8), (8, 3), (7,), (2, 3), (3, 2), (2, 3)],
    [(3, 8), (8, 3), (7,), (3, 4), (8, 8), (8, 8), (3,), (7,), (6,), (3,), (7,), (2, 3), (3, 2), (2,), (2,)],
]

Это результаты теста (my_transform - ваш исходный код, my_transform2 - ответ Błotosmętek, а my_transform5 - ответ alireza yazdandoost), так как среднее и стандартное отклонение времени выполнения (в се c):

[(3, 8), (8, 3), (7,)]
transform_input: 2.524e-06 (9.738e-07)
transform_input2: 2.067e-06 (2.728e-07)
transform_input3: 1.750e-06 (1.570e-07)
transform_input4: 1.804e-06 (1.984e-07)
transform_input5: 1.116e-06 (2.566e-07)
transform_input6: 1.051e-06 (1.874e-07)

[(3, 8), (8, 3), (7,), (3, 8), (8, 3), (7,)]
transform_input: 3.743e-06 (2.239e-07)
transform_input2: 3.308e-06 (2.461e-07)
transform_input3: 2.893e-06 (1.354e-07)
transform_input4: 2.848e-06 (9.448e-07)
transform_input5: 1.710e-06 (2.458e-07)
transform_input6: 1.477e-06 (1.823e-07)

[(8, 8), (8, 8)]
transform_input: 1.894e-06 (2.101e-07)
transform_input2: 1.641e-06 (1.979e-07)
transform_input3: 1.370e-06 (1.294e-07)
transform_input4: 1.593e-06 (1.063e-06)
transform_input5: 9.250e-07 (2.063e-07)
transform_input6: 8.319e-07 (1.358e-07)

[(3,), (7,), (6,)]
transform_input: 2.415e-06 (1.107e-06)
transform_input2: 1.944e-06 (2.173e-07)
transform_input3: 1.635e-06 (1.073e-07)
transform_input4: 1.710e-06 (1.585e-07)
transform_input5: 1.079e-06 (1.747e-07)
transform_input6: 1.061e-06 (9.636e-07)

[(3,), (7,), (6,), (3,), (7,), (3,)]
transform_input: 3.653e-06 (1.049e-06)
transform_input2: 3.152e-06 (2.191e-07)
transform_input3: 2.749e-06 (1.331e-07)
transform_input4: 2.576e-06 (1.495e-07)
transform_input5: 1.674e-06 (2.078e-07)
transform_input6: 1.285e-06 (1.356e-07)

[(2, 3), (3, 2), (2, 3), (3, 2), (2, 3), (3, 2), (2, 3), (3, 2), (2, 3), (3, 2), (2, 3), (3, 2)]
transform_input: 6.527e-06 (2.066e-07)
transform_input2: 5.980e-06 (2.107e-07)
transform_input3: 5.370e-06 (1.381e-07)
transform_input4: 5.504e-06 (4.534e-06)
transform_input5: 2.974e-06 (1.017e-06)
transform_input6: 2.422e-06 (1.929e-07)

[(2,), (2,)]
transform_input: 1.830e-06 (1.616e-07)
transform_input2: 1.565e-06 (2.068e-07)
transform_input3: 1.317e-06 (1.332e-07)
transform_input4: 1.541e-06 (1.074e-06)
transform_input5: 9.414e-07 (1.911e-07)
transform_input6: 8.253e-07 (1.391e-07)

[(2,), (2,), (2,), (2,), (2,), (2,)]
transform_input: 3.798e-06 (1.423e-06)
transform_input2: 3.165e-06 (2.080e-07)
transform_input3: 2.767e-06 (1.471e-07)
transform_input4: 2.602e-06 (1.492e-07)
transform_input5: 1.718e-06 (2.056e-07)
transform_input6: 1.255e-06 (1.435e-07)

[(3, 8), (8, 3), (7,), (2, 3), (3, 2), (2, 3)]
transform_input: 3.762e-06 (2.038e-07)
transform_input2: 3.323e-06 (2.212e-07)
transform_input3: 2.923e-06 (1.341e-07)
transform_input4: 2.763e-06 (1.599e-07)
transform_input5: 1.663e-06 (2.349e-07)
transform_input6: 1.468e-06 (1.796e-07)

[(3, 8), (8, 3), (7,), (3, 4), (8, 8), (8, 8), (3,), (7,), (6,), (3,), (7,), (2, 3), (3, 2), (2,), (2,)]
transform_input: 7.692e-06 (3.647e-07)
transform_input2: 7.048e-06 (2.708e-07)
transform_input3: 6.550e-06 (1.439e-06)
transform_input4: 6.143e-06 (2.281e-06)
transform_input5: 3.450e-06 (2.875e-07)
transform_input6: 2.544e-06 (2.064e-07)

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

Answer 2

Как вы знаете, кортежи можно хэшировать, поэтому вы можете использовать их в качестве dict ключей.

Как вы, возможно, знаете, вставка и поиск в хеш-таблицах выполняется в порядке O (1).

Таким образом, использование хеш-таблицы (dict в python) может помочь улучшить ваш код.

Я написал transform_input2 на основе приведенных выше фактов.

Я знаю Он не очень хорошо читается, но повышает производительность.

* Я немного изменил ваш код, чтобы иметь возможность лучше рассчитывать затраченное время в каждом решении.

import time

def transform_input3(combination):
    print("start")
    start = time.time()
    res = list(set([tuple(sorted(elem)) for elem in combination]))
    end = time.time()
    print(end - start)
    return res


def transform_input2(combination):
    print("start")
    start = time.time()
    hashtable = {}
    for t in combination:
        rev = t[::-1]
        if rev in hashtable:
            if t[0]<rev[0]:
                hashtable[(t[0],t[1])] = None
            else:
                continue
        else:
            hashtable[t] = None
    res = list(hashtable.keys())    
    end = time.time()
    print(end - start)
    return res

def transform_input(combination):
    print("start")
    start = time.time()
    combination = [list(elem) for elem in combination]
    for t in combination:
        t.sort()
    combination = [tuple(elem) for elem in combination]
    combination = list(set(combination))
    end = time.time()
    print(end - start)
    return combination

my_input = [
(3,8), (8,3), (7,), (3,4),
(8,8), (8,8),
(3,), (7,), (6,), (3,), (7,),
(2,3), (3,2),
(2,), (2,)
]
print(transform_input(my_input))
print(transform_input2(my_input))
print(transform_input3(my_input))

вот результат за одно исполнение:

start
3.600120544433594e-05
[(2,), (3,), (3, 8), (8, 8), (2, 3), (6,), (7,), (3, 4)]
start
1.0967254638671875e-05
[(3, 8), (7,), (3, 4), (8, 8), (3,), (6,), (2, 3), (2,)]
start
1.9788742065429688e-05
[(2,), (3,), (3, 8), (8, 8), (2, 3), (6,), (7,), (3, 4)]

Answer 3

Это может быть немного более эффективно (не уверен, проверьте):

def transform_input(combination):
  return list(set([tuple(sorted(elem)) for elem in combination]))