Python: набор фильтров/список кортежей на основе свойства мощности
Я ищу способ фильтровать набор (или список) кортежей по количеству раз. элемент появляется в одной из других позиций кортежа.
Моя текущая цель немного сложна, поэтому я разделил проблему на три небольших шага.
1. Начнем с самого простого случая: только одно значение, которое применяется только к первому элементу кортежа.
Например:
my_filter([(1,2),(1,3),(2,4),(3,1),(3,4),(3,5),(5,2),(5,4)], 2)
Должно вернуться:
[(1,2),(1,3),(5,2),(5,4)]
Потому что это единственные кортежи, для которых первый элемент кортежа появляется во всем списке только дважды.
Наивный способ сделать это: для каждого первого элемента кортежа в списке подсчитать, сколько раз этот элемент появляется в качестве первого элемента во всех кортежах, и, если счетчик соответствует выбранному числу, добавить все кортежи, имеющие этот элемент в первой позиции. .
Но мне кажется, что это настолько неоптимально, и мне приходится перебирать список для каждого возможного значения, что я наверняка упускаю лучший способ сделать это.
2. Сделайте это взаимным
В идеале хотелось бы иметь возможность применить ту же обработку на основе второго элемента кортежа, но с другим параметром мощности.
Например:
my_filter([(1,2),(1,3),(2,4),(3,1),(3,4),(3,5),(5,2),(5,4)], 2, 1)
Здесь мы хотим сохранить только кортежи, в которых первый элемент появляется ровно два раза, а второй элемент появляется только один раз (пересечение двух условий). Это должно вернуться:
[(1,3)]
3. Обобщение на несколько значений
my_filter([(1,2),(1,3),(2,4),(3,1),(3,4),(3,5),(5,2),(5,4)], 2, [1,3])
В этом случае мы разрешаем фильтру мощности принимать несколько возможных значений. В этом примере мы хотим сохранить кортежи, для которых первый элемент появляется ровно два раза (в первой позиции), а второй элемент появляется один или три раза (во второй позиции). Это должно вернуться:
[(1,3),(5,4)]
Еще раз: у меня нет проблем с написанием простого решения, которое просто перебирало бы все разрешенные значения и объединяло наборы результатов, но я ищу что-то поумнее.
Я чувствую, что в библиотеке itertools могут быть некоторые полезные функции, но мне она не очень нравится. Любой совет ? Спасибо.
Ответы 2
Вот решение с линейным временем (O(n)) для частей 2 и 3 (1 можно реализовать с некоторыми изменениями):
Сначала мы преобразуем второй и третий аргументы в набор, равный O(n).
Затем мы вычисляем частоту каждого элемента в позициях 0 и 1, снова O(n).
Затем мы перебираем список и проверяем, соответствует ли он нашим критериям. Поиск в Counter и наборах - это O(1), так что эта вещь снова эффективна, в целом O(n).
from collections import Counter
def my_filter(list: list[tuple[int, int]], first: list[int], second: list[int]):
first_set = set(first)
second_set = set(second)
first_counter = Counter(a for (a, _) in list)
second_counter = Counter(b for (_, b) in list)
return [
(a, b)
for (a, b) in list
if first_counter[a] in first_set and second_counter[b] in second_set
]
print(
my_filter(
[(1, 2), (1, 3), (2, 4), (3, 1), (3, 4), (3, 5), (5, 2), (5, 4)], [2], [1]
)
)
print(
my_filter(
[(1, 2), (1, 3), (2, 4), (3, 1), (3, 4), (3, 5), (5, 2), (5, 4)], [2], [1, 3]
)
)
Выход:
[(1, 3)]
[(1, 3), (5, 4)]
Это можно сделать значительно быстрее, если не использовать Counter и выполнить итерацию по списку только один раз для создания first_counter и Second_counter.
Поскольку Counter itertools написан на C и высоко оптимизирован, я сомневаюсь, что ванильный Python сможет превзойти его использование, хотя нам нужно дважды перебрать список с помощью Counter
@ibi0tuxЯ добавил еще один ответ в качестве доказательства своего утверждения.
Улучшение производительности по сравнению с отличным предложением @Dogbert.
from collections import Counter
from timeit import timeit
# code from the accepted answer
def my_filter1(list: list[tuple[int, int]], first: list[int], second: list[int]):
first_set = set(first)
second_set = set(second)
first_counter = Counter(a for (a, _) in list)
second_counter = Counter(b for (_, b) in list)
return [
(a, b)
for (a, b) in list
if first_counter[a] in first_set and second_counter[b] in second_set
]
# code that avoids use of Counter
def my_filter2(list: list[tuple[int, int]], first: list[int], second: list[int]):
first_set = set(first)
second_set = set(second)
first_counter = {}
second_counter = {}
for a, b in list:
first_counter[a] = first_counter.get(a, 0) + 1
second_counter[b] = second_counter.get(b, 0) + 1
return [
(a, b)
for (a, b) in list
if first_counter[a] in first_set and second_counter[b] in second_set
]
X = [(1, 3), (2, 4), (3, 1), (3, 4), (3, 5), (5, 2), (5, 4),(1,2)]
Y = [2]
Z = [1]
assert my_filter1(X, Y, Z) == my_filter2(X, Y, Z)
for func in my_filter1, my_filter2:
print(func.__name__, timeit(lambda: func(X,Y,Z)))
Выход:
my_filter1 2.4996074590017088
my_filter2 1.1667742919817101
Платформа:
Apple M2
macOS Sonoma 14.6
Python 3.12.4
Отличное улучшение производительности, спасибо!
Отлично спасибо ! Он работает нормально.
Counterэто то, чего мне не хватало. Очевидно, что первый случай легко разрешим, поскольку это частный случай.