首页 文章

如何删除Python中巨大的对象列表的重复项

提问于
浏览 次
1

我有很多重复的对象列表（我说的是数千个列表，每个列表包含数千个对象，占用大约1000万个单独的对象（已经没有重复） .

我需要浏览它们并删除每个列表中的所有重复项（不需要在列表之间进行比较，只在每个列表中进行比较） .

当然，我可以浏览列表并与已经发布很多次的任何重复数据删除算法进行比较，但我猜这将永远带我 .

我以为我可以使用精心设计的 __hash__ 方法创建一个对象并使用 list(set(obj)) 删除它们但是首先：我不知道这是否可行，第二：我仍然需要循环列表以将元素转换为新对象 .

我知道Python不是我想要实现的最佳解决方案，但在这种情况下，它必须在Python中完成 . 我想知道以最佳性能实现这一目标的最佳方法是什么 .

Edit ：澄清：我有大约2k个对象列表，每个对象里面有大约5k个对象（粗略估计） . 重复的对象是副本，而不是对同一内存位置的引用 . 列表（dicts）基本上是转换后的JSON数组

Edit 2 ：我很抱歉不清楚，我会改写 .

这是一个django数据迁移，虽然我的问题只适用于数据“格式化”而不适用于框架本身或数据库插入 . 我将一大堆数据作为JSON插入表中供以后分析 . 现在我需要将其标准化并正确保存 . 我创建了新表并需要迁移数据 .

所以当我从db检索数据时，我有大约2000个JSON数组 . 应用 json.loads(arr) （通过文档）我得到2000个对象列表（dicts） . 每个dict只有字符串，数字和布尔值作为每个键的值，没有嵌套的对象/数组，所以像这样：

[
  {
    a: 'aa',
    b: 2,
    c: False,
    date: <date_as_long> // ex: 1471688210
  },
  {
    a: 'bb',
    b: 4,
    c: True,
    date: <date_as_long> // ex: 1471688210
  }
]

我需要的是遍历每个列表并删除重复项 . 如果除了日期之外的所有字段都匹配（这不是原始问题，因为我没有预测到），那么某些内容被认为是重复的 . 如果它们在不同的列表中匹配，则不会将它们视为重复 .

在对内容进行更好的分析后，我发现我有近200万个人记录（如前所述，不是1000万个） . 我面临的性能问题是因为每个dict需要进行某种数据格式化（例如转换日期）和'wrap'它在数据库插入的模型对象中： ModelName(a='aaa', b=2, c=True, date=1471688210) .

数据库本身的插入由 bulk_create 完成 .

NOTE ：对于原始问题缺乏澄清，我感到很遗憾 . 我越了解这一点，就越了解必须完成的工作以及如何处理数据 .

我接受了@tuergeist的答案，因为它指出了我所需要的东西，即使我的细节也不好 .

鉴于dicts不能被散列，因此我无法将它们添加到set（）中，我的解决方案是为重复数据创建一个 set() 元组，并使用它验证重复项 . 如果重复列表中的位置，这会阻止额外的迭代 .

所以它是这样的：

data = [lots of lists of dicts]
formatted_data = []
duplicates = set()

for my_list in data:
  for element in my_list:
    a = element['a']
    b = convert_whatever(element['b'])
    c = element['c']

    d = (a, b, c) # Notice how only the elements that count for checking if it's a duplicate are here (not the date)

    if d not in duplicates:
      duplicates.add(d)
      normalized_data = {
        a: a,
        b: b,
        c: c,
        date: element['date']
      }
      formatted_data.append(MyModel(**normalized_data)

  duplicates.clear()

在此之后，为了更好的内存管理，我使用了生成器：

data = [lots of lists of dicts]
formatted_data = []
duplicates = set()

def format_element(el):
  a = el['a']
  b = convert_whatever(el['b'])
  c = el['c']

  d = (a, b, c)

  if d not in duplicates:
    duplicates.add(d)
    normalized_data = {
      'a': a,
      'b': b,
      'c': c,
      'date': el['date']
    }
    formatted_data.append(MyModel(**normalized_data))

def iter_list(l):
  [format_element(x) for x in l]
  duplicates.clear()

[iter_list(my_list) for my_list in data]

这里的工作代码：http://codepad.org/frHJQaLu

NOTE ：我完成的代码与此代码略有不同（并且在功能样式中） . 这只是我如何解决问题的一个例子 .

Edit 3 ：对于数据库插入，我使用了bulk_create . 最后花了1分钟正确格式化所有内容（150万个唯一条目，225k重复项）和2分钟将所有内容插入数据库 .

谢谢你们！

python python-3.x

3 回答

  • 1

    （可洗物品）的快速而非订单保留解决方案是

    def unify(seq):
    # Not order preserving
    return list(set(seq))

    Complete Edit

    我假设你在 list 里面有 dicts . 你有很多名单 . 从单个列表中删除重复项的解决方案是：

    def remove_dupes(mylist):
    newlist = [mylist[0]]
    for e in mylist:
        if e not in newlist:
            newlist.append(e)
    return newlist

    此处的列表包含以下序列 . （但所有随机）

    {"firstName":"John", "lastName":"Doe"}, 
{"firstName":"Anna", "lastName":"Smith"}, 
{"firstName":"Peter","lastName":"Jones"}

    运行这个，我的MacBook（2.4GHz，i5）花费了8s用于2000 dicts

    完整代码：http://pastebin.com/NSKuuxUe

    回复于
  • 1

    我建议有一个排序列表（如果可能的话），这样你就可以更精确地想要比较项目（就像我的意思是一个词典） . 哈希（或非）列表可以实现该功能 .

    如果您能够管理列表中的“添加和删除”，那就更好了！每次添加/删除时对新项目进行排序 . （IMO很好，如果你有哈希列表，忘了如果你有链表） .

    复杂性当然取决于你的结构（fifo / filo列表，链表，哈希...）

    回复于
  • 0

    以下是排序列表的解决方案：

    class Solution:
def removeDuplicates(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if (len(nums) == 0):
        return 0;
    j = 0
    for i in range(len(nums)):
        if (nums[i] != nums[j]):
            j = j+1
            nums[j] = nums[i];

    return j + 1
    回复于

相关问题