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

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()对每个元素都做了，但速度很慢。

score 105 · Accepted Answer

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

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

score 28 · Accepted Answer

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

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]

score 21 · Accepted Answer

由于您保证列表的每个元素都是 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))

输出（秒）

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

更新我怀疑使用（无序）中的Counter方法two可能会导致导入显着膨胀或减慢，所以我测试了“先计数，后编译结果”方法，同时使用来自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 的方法要快得多。

score 20 · Accepted Answer

This is a classic use case of sets and I'm quite surprised that no one else tried it out to see how it stacks against the Counter and dict implementations.

I implemented a solution using set instead as follows:

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)

This implementation is about 28% faster than using Counter and 51% faster than using a dictionary.

The sort and slice implementation given by Wimanicesir is the fastest, giving results 17 times faster than when using set. Note though, that because it sorts the items before removing duplicates, the order of appearance is not preserved unlike the other three.

Here are all the suggested implementations with timing for evaluation of comparative performance.
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()

Sample run result

Sort and Slice Implementation Results

Median:  0.009686
Mean:    0.009721
Std Dev: 0.000529


Dictionary Implementation Results

Median:  0.230081
Mean:    0.227631
Std Dev: 0.014584


Counter Implementation Results

Median:  0.192730
Mean:    0.194577
Std Dev: 0.008015


Set Implementation Results

Median:  0.149604
Mean:    0.151227
Std Dev: 0.006838

score 7 · Accepted Answer

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

score 3 · Accepted Answer

如果您不关心保留相对顺序，您可以先使用获取每个元素的计数collections.Counter，然后创建一个新列表，其中每个元素重复一半的次数。

>>> from collections import Counter
>>> from itertools import chain
>>> list(chain.from_iterable([key]*(count//2) for key, count in Counter(l).items()))
[1, 8, 8, 3]

score 3 · Accepted Answer

您保留所有访问次数不均的项目的列表。然后遍历所有列表项。

在其他语言中可能会使用一些 map() 或 filter() 方法，但这里有一些简单的代码，因为我不太了解 python！:)

l = [1,8,8,8,1,3,3,8]
seen = []
result = []
for num in l:
  if num in seen:
    seen.remove(num)
    #result.append(num) #print every even appearance
  else:
    seen.append(num)
    result.append(num) #print every odd appearance

if len(seen)==0:
  print(result)
else:
  print("Error: uneven elements found:", seen)

最后，visited-array 应该为空，因此您可以在返回结果数组之前将其用作完整性检查。

编辑：这是一个带有过滤器的版本，它返回奇怪的外观

l = [1,8,8,8,1,3,3,8]
seen = []
result = list(filter(lambda x: seen.append(x) is None if x not in seen else not seen.remove(x) is None, l))

if len(seen)==0:
  print(result)
else:
  print("Error: uneven elements found:", seen)

这一个返回均匀的外观：

l = [1,8,8,8,1,3,3,8]
seen = []
result = list(filter(lambda x: seen.remove(x) is None if x in seen else not seen.append(x) is None, l))

if len(seen)==0:
  print(result)
else:
  print("Error: uneven elements found:", seen)

score 1 · Accepted Answer

我喜欢使用 trie 集，因为您需要检测重复项以删除它们，或者使用大哈希集（很多桶）。trie 不会不平衡，您不需要知道最终集合的大小。另一种方法是非常并行的排序——蛮力。

score 0 · Accepted Answer

我知道这已经得到解答，并且有一些相当冗长的解决方案。它特别提到了Python。但是，我认为 Powershell 解决方案可能对某些人来说很有趣（而且很简单！）：

版本 1（分组项目 - 效率较低）

$OriginalArray = @("1","8","8","8","1","3","3","8") 
$NewArray = New-ObjectSystem.Collections.ArrayList
$ArrayGroup = $OriginalArray | Group-Object | Select-Object Count,Name

ForEach ($EachNumber in $ArrayGroup) {
    $HalfTheCount = (1..([Math]::Round($EachNumber.Count / 2)))
    ForEach ($Item in $HalfTheCount) {$NewArray.Add($EachNumber.Name) | Out-Null}   
    } 
$NewArray

版本 2（从排序数组中挑选所有其他项目 - 更高效）

$OriginalArray = @("1","8","8","8","1","3","3","8") 

$NewArray = New-Object System.Collections.ArrayList

$OddOrEven = "Even"
ForEach ($SortedItem in ($OriginalArray | Sort-Object)) {
    If ($OddOrEven -eq "Even") {$NewArray.Add($SortedItem);$EvenNumber = $True}
    If ($OddOrEven -eq "Odd") {$EvenNumber = $False}
    If ($EvenNumber -eq $True) {$OddOrEven = "Odd"} Else {$OddOrEven = "Even"} 
}
$NewArray

score -1 · Accepted Answer

如果顺序很重要，以下代码可以使用 O(N)：

import collections
c = collections.Counter(l)
c2 = collections.Counter()
i, n = 0, len(l)
res=[]
for x in l:
    if i == n//2:break
    if c2[x] < c[x] // 2:
        res.append(x)
        c2[x] += 1
        i += 1

score -1 · Accepted Answer

import itertools

st=time.time()
lst = [1,8,8,8,1,3,3,8]
list(itertools.chain.from_iterable(itertools.repeat(x, int(lst.count(x)/2)) for x in list(set(lst)) if lst.count(x)%2==0))

这给出了排序列表

score -2 · Accepted Answer

也许这个。

    newList = []
    for number in l:
        if(newList.count(number) < l.count(number)/2):
            newList.append(number)

print(newList)

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

12 回答 12

Related

Reference