有效删除元组列表中的部分重复项

Question

我有一个元组列表，该列表的长度可以在 ~8 - 1000 之间变化，具体取决于元组的长度。列表中的每个元组都是唯一的。元组的长度为 N，其中每个条目都是通用单词。示例元组的长度可以是 N(Word 1, Word 2, Word 3, ..., Word N)对于列表中的任何元组，所述元组中的元素 j 将是''或Word j一个非常简单的字母示例是l = [('A', 'B', '', ''), ('A', 'B', 'C', ''),       ('', '', '', 'D'), ('A', '', '', 'D'),       ('', 'B', '', '')]每个元组的每个位置要么具有相同的值，要么为空。''我想删除所有在同一位置的另一个元组中具有所有非值的元组。例如，其中(A,B,'','')包含所有非''值(A,B,C,'')，因此应将其删除。filtered_l = [(A,B,C,''),(A,'','',D)]元组的长度始终相同（不一定是 4）。元组的长度在 2-10 之间。最快的方法是什么？

Answer 1

让我们将每个元组概念化为一个二进制数组，其中 1 是“包含某些内容”，2 是“包含一个空字符串”。由于每个位置的项目都是相同的，因此我们不需要关心每个位置有什么，只关心有什么。

l = [('A','B','',''),('A','B','C',''),('','','','D'),('A','','','D'),('','B','','')]

l_bin = [sum(2**i if k else 0 for i,k in enumerate(tup)) for tup in l]

# [3, 7, 8, 9, 2]

# [0b0011, 0b0111, 0b1000, 0b1001, 0b0010]

# that it's backwards doesn't really matter, since it's consistent

现在，我们可以遍历该列表并构建一个没有“重复项”的新数据结构。由于我们将元组编码为二进制，因此我们可以通过执行按位运算来确定重复的、被另一个“包围”的元组 - 给定aand b， if a | b == a，thena必须包含b。

codes = {}

for tup, b in zip(l, l_bin):

    # check if any existing code contains the potential new one

    # in this case, skip adding the new one

    if any(a | b == a for a in codes):

        continue

    # check if the new code contains a potential existing one or more

    # in which case, replace the existing code(s) with the new code

    for a in list(codes):

        if b | a == b:

            codes.pop(a)

    # and finally, add this code to our datastructure

    codes[b] = tup

现在我们可以撤回我们的“过滤”元组列表：

output = list(codes.values())

# [('A', 'B', 'C', ''), ('A', '', '', 'D')]

请注意，(A, B, C, '')包含(A, B, '', '')和('', B, '', '')，并且(A, '', '', D')包含('', '', '', D)，所以这应该是正确的。

从 python 3.8 开始，dict保留插入顺序，因此输出应该与元组最初出现在列表中的顺序相同。

这个解决方案不会非常有效，因为代码的数量可能会堆积起来，但它应该在 O(n) 和 O(n^2) 之间，具体取决于最后剩下的唯一代码的数量（并且因为每个元组的长度明显小于 的长度l，它应该更接近 O(n) 而不是 O(n^2)。

Answer 2

特别是对于该限制，明显的解决方案是将每个元组转换为位掩码，将它们累积在计数器数组中，执行子集和转换，然后过滤数组l。

详细代码说明见评论。

时间复杂度显然是n + m * 2^m，其中n是元组的数量，m是每个元组的长度。对于n == 1000和m == 10，这显然比 更快n^2。

l = [('A','B','',''),('A','B','C',''),('','','','D'),('A','','','D'),('','B','','')]

# assumes that l is not empty. (to access l[0])

# The case where l is empty is trivial to handle.

def tuple_to_mask(tuple_):

    # convert the information whether each value in (tuple_) is empty to a bit mask

    # (1 is empty, 0 is not empty)

    return sum((value == '') << index for index, value in enumerate(tuple_))

count = [0] * (1 << len(l[0]))

for tuple_ in l:

    # tuple_ is a tuple.

    count[tuple_to_mask(tuple_)] += 1

# now count[mask] is the number of tuples in l with that mask

# transform the count array.

for dimension in range(len(l[0])):

    for mask in range(len(count)):

        if mask >> dimension & 1:

            count[mask] += count[mask - (1 << dimension)]

# now count[mask] is the number of tuples in l with a mask (mask_) such that (mask) contains (mask_)

# (i.e. all the bits that are set in mask_ are also set in mask)

filtered_l = [tuple_ for tuple_ in l if count[tuple_to_mask(tuple_)] == 1]

print(filtered_l)

Answer 3

我不确定这是否是最有效的或Python式的方法，但这将是直接的方法（同样，也许其他人会提供更复杂的列表理解方法）：

看看这个：

l = [('A','B','',''),('A','B','C',''),('','','','D'),('A','','','D'),('','B','','')]

def item_in_list(item, l):

    for item2comp in l:

        if item!=item2comp:

            found = True

            for part,rhs_part in zip(item, item2comp):

                if part!='' and part!=rhs_part:

                    found = False

                    break

            if found:

                return True

    return False

            

                

            

new_arr = []

for item in l:

    if not item_in_list(item, l):

        new_arr.append(item)

print(new_arr)

输出：

[('A', 'B', 'C', ''), ('A', '', '', 'D')]

我认为时间复杂度是 - O((N**2)*M)

N - 列表中的元素数量

M - 每个元素中的零件数

Answer 4

这些字符串始终位于同一位置，因此我将它们替换为布尔值，以便更轻松地比较它们。首先，我进行排序，然后仅保留与所有其他元素相比，前一个元素在任何地方都为 true 或与后一个元素相同的元素。然后，当比较完成后，我会将其从列表中删除。

f = sorted(map(lambda x: list(map(bool, x)), l), key=sum, reverse=True)

to_keep = []

while len(f) > 1:

    if all(map(lambda x, y: True if x == y or x else False, f[0], f[1])):

        to_keep.append(len(l) - len(f) + 1)

    f = f[1:]

print([l[i] for i in to_keep])

[('A', 'B', 'C', ''), ('A', '', '', 'D')]

速度为 43.7 µs，也是投票最高答案的两倍。

Answer 5

L = [('A', 'B','',''),('A','B','C',''),('','','','D'),('A','','','D'),('','B','','')]

keys = collections.defaultdict(lambda: collections.defaultdict(set))

# maintain a record of tuple-indices that contain each character in each position

for i,t in enumerate(L):

    for c,e in enumerate(t):

        if not e: continue

        keys[e][c].add(i)

delme = set()

for i,t in enumerate(L):

    collocs = set.intersection(*[keys[e][c] for c,e in enumerate(t) if e])

    if len(collocs)>1:  # if all characters appear in this position in >1 index

        # ignore the collocation with the most non-empty characters

        # mark the rest for deletion

        C = max(collocs, key=lambda i: sum(bool(e) for bool in L[i]))

        for c in collocs:

            if c!=C: delme.add(c)

filtered = [t for i,t in enumerate(L) if i not in delme]