时间戳

首页 > 解决方案 > 从列表中删除重复项（算法速度）

python - 从列表中删除重复项（算法速度）

问题描述

我目前正在阅读如何像计算机科学家一样思考并完成那里的练习。列表算法部分中有一个函数（remove_adjacent_dups），我认为我可以改进。

原始功能：

def remove_adjacent_dups(xs):
    """ Return a new list in which all adjacent
        duplicates from xs have been removed.
    """
    result = []
    most_recent_elem = None
    for e in xs:
        if e != most_recent_elem:
            result.append(e)
            most_recent_elem = e

    return result

我的功能：

def remove_duplicates(xs):
    """Removes duplicate elements from given list ”xs” """
    result = []
    for e in xs:
        if e not in xs:
            result.append(e)
    return result

remove_adjacent_dups仅适用于排序列表，因此涉及额外的操作。remove_duplicates不关心序列是否已排序，无论如何它都会删除所有重复项。但问题是，如果我将我的函数应用到书中的练习中，它会慢得多：

删除重复项：

全书共27336字。只有 2569 个是唯一的。

这花了 0.2556 秒。

remove_adjacent_dups：

全书共27336字。只有 2569 个是唯一的。

这花了 0.0132 秒。（本次包括分拣操作）

任何人都知道为什么remove_adjacent_dups更有效，即使它涉及额外的排序操作并且它还有一个额外的变量most_recent_elem？

标签： pythonalgorithmperformanceduplicates

解决方案

一个额外的变量不会像你想象的那么慢。

其实关键就在这里：

if e not in results:

如果结果是True，这将非常耗时，因为整个列表被迭代一次。也就是说，只有 10 个元素的列表和 100,000 个元素的巨大列表，运行时间e not in lst变化很大。

使用remove_adjacent_duplicates时，您只查看最后一项，因此此比较需要固定的时间，并且不会因列表长度而异。

推荐阅读