有效地根据索引列表从列表中删除元素

问题描述

我有两个非常大的整数列表:list1和list2.

I have two very large lists of ints: list1 and list2.

在list1中，我有list2的索引(有些无效)，我需要从list2中删除这些索引中的元素.

In list1 I have indexes of list2 (some are invalid), I need to remove the elements in these indexes from list2.

这是我的代码:

for index in list1:
    if index >= 0 and index < len(list2):  # verify index is valid
        list2.pop(index)

这是可行的，但是我想有一个比这更快的解决方案.是否有可能?也许使用numpy?

This is working, but I'm would like to have a faster solution than this. Is it possible? Maybe using numpy?

推荐答案

我假设您有效地使用 来表示时间复杂度.让我们将n和m命名为list1和list2的大小.

I'm supposing you use efficiently referring to time complexity. Let's name n and m as the sizes of list1 and list2.

您的解决方案似乎是最好的选择，但未提供Python .pop()以O(m)运行因此需要O(n * m).

Your solution seems to be the best option but it's not given Python .pop() operates in O(m) so it takes O(n*m).

在没有更多信息的情况下，列表理解解决方案通常不是一个好主意，因为您应该测试索引是否在list1内，即O(n).所以解决方法:

With no more information, list comprehension solutions are a bad idea in general as you should test if index is inside list1 which is O(n). So the solution:

filtered = [item for index, item in enumerate(list2) if index not in list1]

也执行O(n * m).

performs in O(n*m) too.

但是如果list1是一个集合，则可以将in操作设为O(1).如果您这样做，则该集合的构造为O(n):

But you could make that in operation to be O(1) if list1 were a set. The construction of this set is O(n) if you do:

ignore_indices = { index for index in list1 if 0 < index < len(list2) }

现在，您可以构建另一个过滤列表，而忽略此集合中的位置:

Now you can construct another filtered list ignoring positions in this set:

filtered = [item for index, item in enumerate(list2) if index not in ignore_indices]

此运算为O(m)，因此最终的复杂度为O(n + m).

And this run O(m) so the final complexity is in O(n+m).

顺便说一句，我认为您的验证检查是0 <= index < len(list2)，但是我不确定您是否故意排除了0.

By the way, I think your validation check is 0 <= index < len(list2) but I'm not sure if you're excluding 0 intentionally or not.

这篇关于有效地根据索引列表从列表中删除元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！