删除列表中一半重复项的有效方法

Question

如果我有一个列表说l = [1, 8, 8, 8, 1, 3, 3, 8]并且保证每个元素出现偶数次，我如何制作一个包含l现在出现n/2次数的所有元素的列表。所以既然1发生了2，它现在应该发生一次。由于8出现4次数，它现在应该出现两次。既然3发生了两次，就应该发生一次。

所以新列表将类似于 k=[1,8,8,3]

执行此操作的最快方法是什么？我list.count()为每个元素都做了，但速度很慢。

Answer 1

如果顺序不重要，一种方法是仅在排序后获取奇数或偶数索引。这些列表将相同，因此您只需要其中之一。

l = [1,8,8,8,1,3,3,8]
l.sort()

# Get all odd indexes
odd = l[1::2]

# Get all even indexes
even = l[::2]

print(odd)
print(odd == even)

结果：

[1, 3, 8, 8]
True

Answer 2

使用计数器来跟踪每个元素的计数

from collections import Counter
l = [1,8,8,8,1,3,3,8]
res = []
count = Counter(l) # its like dict(1: 2, 8: 4, 3: 2)
for key, val in count.items():
    res.extend(val//2 * [key])
print(res)
# output
[1, 8, 8, 3]

Answer 3

由于您保证列表的每个元素出现 2 的倍数，因此在构建输出列表时构建计数器会更快，而不是先构建计数器（或排序）然后再使用它。

l = [1,8,8,8,1,3,3,8]
count={}
res=[]
for i in l:
  if i in count: count[i]+=1
  else: count[i]=1
  if count[i]%2: res.append(i)

print(res)

输出

[1,8,8,3]

编辑比较每种方法的时间/费用

使用该timeit模块表明，这种方法比首先使用计数器快 2.7 倍。

IE

def one():
  l = [1,8,8,8,1,3,3,8]
  count={}
  res=[]
  for i in l:
    if i in count: count[i]+=1
    else: count[i]=1
    if count[i]%2: res.append(i)

  #print(res)


def two():
  from collections import Counter
  l = [1,8,8,8,1,3,3,8]
  res = []
  count = Counter(l) # its like dict(1: 2, 8: 4, 3: 2)
  for key, val in count.items():
    res.extend(val//2 * [key])

o=timeit.Timer(one)

t=timeit.Timer(two)

print(o.timeit(100000))

print(t.timeit(100000))

print(o.timeit(100000))

print(t.timeit(100000))

输出（秒）

0.28666
0.80822
0.28678
0.80113

如果顺序不重要，那么 Wimanicesir 的方法将是首选，加速提高 4 倍，结果为 0.07037（比使用计数器方法快约 11 倍）。

更新 我怀疑Counter在two(unordered)中使用该方法可能会带来显着的膨胀或导入速度变慢，所以我测试了“先计数，稍后编译结果”方法，同时使用来自one（有序）的简单方法进行计数

count={}
for i in l:
  if i in count: count[i]+=1
  else: count[i]=1

这比Counter. 更换Counter在two测试的定义导致了0.31，而不是0.80的时间。然而，在计数期间编译（有序）结果仍然稍微快一些two。对于无序结果，使用 Wimanicesir 的方法要快得多。

Answer 4

这是集合的一个经典用例，我很惊讶没有其他人尝试过它是如何与Counter和dict实现叠加的。

我实现了一个解决方案，使用set如下：

def set_impl(l):
  bag = set()
  res = []
  for i in l:
    if i in bag:
      res.append(i)
      bag.remove(i)
    else:
      bag.add(i)

此实现比使用快 28%，比使用Counter字典快 51%。

Wimanicesir 给出的排序和切片实现是最快的，比使用set. 但请注意，因为它在删除重复项之前对项目进行排序，所以与其他三个不同，不会保留外观顺序。

以下是所有建议的实现，以及用于评估比较性能的时间。
https://repl.it/@franzalex/StackOverflow-py#removeDuplicateHalf.py

import random
import statistics as stats
from collections import Counter as counter
from timeit import Timer

def slice_impl(l):
  l.sort()
  res = l[::2]

def dict_impl(l):
  count={}
  res=[]
  for i in l:
    if i in count:
      count[i] += 1
    else:
      count[i] = 1
    if count[i] % 2:
      res.append(i)

def counter_impl(l):
  count = counter(l)
  res = []
  for key, val in count.items():
    res.extend(val//2 * [key])

def set_impl(l):
  bag = set()
  res = []
  for i in l:
    if i in bag:
      res.append(i)
      bag.remove(i)
    else:
      bag.add(i)

def timed_run():
  for name, func in {"Sort and Slice": slice_impl, 
                     "Dictionary": dict_impl, 
                     "Counter": counter_impl, 
                     "Set": set_impl}.items():
    seq = list(range(50))*2
    results = []
    print(f"{name} Implementation Results")
    for i in range(50):
      if len(results) % 10: random.shuffle(seq) # shuffle after 10 runs
      results.append(Timer(lambda: func(seq)).timeit(10**4))
      # print(f"Run {i+1:02}: {results[i]:.6f}")
    print("")
    print(f"Median:  {stats.median(results):.6f}")
    print(f"Mean:    {stats.mean(results):.6f}")
    print(f"Std Dev: {stats.stdev(results):.6f}")
    print("\n\n")

timed_run()

示例运行结果

排序和切片实现结果

中位数：0.009686
平均值：0.009721
标准偏差：0.000529


字典实现结果

中位数：0.230081
平均值：0.227631
标准偏差：0.014584


反执行结果

中位数：0.192730
平均值：0.194577
标准偏差：0.008015


设置实施结果

中位数：0.149604
平均值：0.151227
标准偏差：0.006838

Answer 5

与其使用计数器来跟踪列表中每个可能元素的整数，不如尝试使用字典将元素映射到布尔值。第一次看到它们时映射为 true，然后每次翻转位，如果为 true，则跳过该元素。