Как проходить список и одновременно удалять элементы, в том числе впереди курсора?

Question

[PavelMos]

Есть список или другой перебираемый объект. Нужно обойти его таким способом - я беру первый элемент, например, X , затем ищу в остальной части списка элементы, подходящие по определённому критерию на основе этого X. Например, все делящиеся X на 2 без остатка.

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

Далее в уже изменённом первоначальном списке я беру следующий элемент, например Y, проверяю оставшиеся в оригинальном списке элементы по критерию Y. тоже удаляю их или переношу в отдельный объект и т.д.

То есть, убирать нужные (подходящие по критерию) элементы имелось ввиду для того, чтобы не тратить время на их проверку при следующих проходах, когда будут проверять все элементы по второму критерию (рассчитанному на основе второго по счёту элемента), по третьему и тд. Чтобы если за первый проход из 100 элементов отфильровалось 20 (убрал их в другой объект), то за второй проход нужно проверить уже 80, за третий 60 и т.д.

Есть ли какой-то общий алгоритм, метод для этого, для перебора списка с одновременным его изменением ( и так, чтобы итератор не запутался, поскольку пишут, что итерируемый объект изменять не рекомендуется) ? Можно наверное использовать что-то вроде ведения параллельных списков и тд., но возможно есть более простой способ

Желательно для Питона, но можно на другом языке или в общем виде.

Comments

[Ланской Кирилл]

Не очень понятно, у тебя есть X и ты, например, хочешь проверить, кто делится на X без остатка?

Answer 1

[Wataru]

Для такой вот работы идеально подходят связные списки. Там можно менять объект не портя никакие итераторы. Проблема только в том, что связные списки в питоне не реализованы на уровне языка. Поищите реализацию, наверняка есть удобный модуль со списками.

Еще можноиспользовать обычный list, только вы итерируйтесь циклом while и используйте индексы:

i = 0
while i < len(arr):
  x = arr[i]
  j = i+1
  while j < len(arr):
    if ShouldDelete(arr[j], arr[i]):
      del a[j]

Это будет в n раз медленнее, к сожалению. Можно наверно слайсами сделать быстрее:

arr[i+1:] = y for y in arr[i+1:] if not ShouldDelete(x, arr[i])

Я не питонист и возможно ошибку допустил. И мне этот код не кажктся очень понятным, но возможно это истиный путь для питона.

А так, в общем случае, идет двойная итерация с пометками элементов на удаление.

Какого-то названия этот прием не имеет, ибо это костыль для конкретных реализаций контейнеров.

Answer 2

[Vindicar]

Сделай цикл while и наращивай индекс текущего элемента сам, в отдельной переменной. Если элемент не нужен - удаляешь его, если нужен - увеличиваешь индекс.
Альтернативно, ты можешь просто проходить список с конца, тогда "съезжать" будут только те элементы, которые ты и так уже обработал. Будет простой цикл с шагом -1.

Answer 3

[Everything_is_bad]

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

Не изменение текущего списка и добавление отфильтрованных данных в новых список и есть более простой способ

Comments

[PavelMos]

Убирать нужные (подходящие по критерию) элементы имелось ввиду для того, чтобы не тратить время на их проверку при следующих проходах, когда будут проверять все элементы по второму критерию (рассчитанному на основе второго по счёту элемента), по третьему и тд.

[Everything_is_bad]

PavelMos, так в новый список добавляй всех, кроме тех что не прошли проверку, на следующем проходе уже по новому списку иди

[PavelMos]

Я хотел на лету, без ведения второго списка. В общем, сделал цикл не через range, а через while. Хотя применительно для питоне не экспериментировал, будет ли в for i in range нормально работать, если в цикле вручную менять i