在Python中，存储集合数据的最佳方法是什么？

Question

我有一个数据列表，格式如下：

`[(id__1_, 描述, id_type), (id__2_, 描述, id_type), ... , (id__n_, 描述, id_type))]`

这些数据是从属于同一组的文件中加载的。在每个组中，可能会有多个相同的id，每个id来自不同的文件。我不关心重复项，所以我想将所有内容存储到Set类型中。但是有一个问题。

有时，对于相同的id，描述可能会略有不同，如下所示：

`IPI00110753`

- Tubulin alpha-1A chain - Tubulin alpha-1 chain - Alpha-tubulin 1 - Alpha-tubulin isotype M-alpha-1

（请注意，此示例取自uniprot蛋白质数据库。）

我不在意描述的变化。因为我使用的蛋白质数据库可能没有某个标识符的列表，所以我不能将它们丢弃。如果发生这种情况，我将希望能够向生物学家显示可读的人类描述，以便他们大致了解正在查看的蛋白质。

我目前正在使用字典类型来解决这个问题。然而，我并不喜欢这个解决方案，因为它使用了很多内存（我有很多这些ID）。这只是它们的中间列表。这些ID在放入数据库之前还要经过一些额外的处理，因此我希望保持我的数据结构更小。

我有两个问题。首先，如果我使用Set类型（而不是字典类型），是否可以获得更小的内存占用？或者我应该使用排序列表，在每次插入列表时检查ID是否存在？还是有第三种解决方案我没有想到的？其次，如果Set类型是更好的答案，如何将其键入为仅查看元组的第一个元素而不是整个元组？

感谢您阅读我的问题，
Tim

更新

基于我收到的一些评论，让我稍微澄清一下。我在数据结构方面做的大部分工作是将其插入其中。我只读取它两次，一次用来注释附加信息，另一次用来插入数据库。然而，在插入到数据库之前可能会有额外的注释。不幸的是，我现在不知道是否会发生这种情况。

现在，我正在研究将此数据存储在不基于哈希表（即字典）的结构中。我希望新结构在插入时相当快速，但由于我只真正地读取它两次，因此可以进行线性读取。我试图摆脱哈希表以节省空间。是否有更好的结构或哈希表是最好的选择？

* 这些信息是我通过查询uniprot获得的Swiss-Prot蛋白质标识符列表。

- tim.tadh

---

你在那个数据上90%的时间都是做查找还是插入？ - Florian Bösch

Answer 1

集合没有键，元素就是键。

如果你认为你需要键，那你就需要一个映射。这几乎是定义。

即使使用二分查找，顺序列表查找可能会很慢。映射使用哈希，速度很快。

你是在谈论这样的字典吗？

{ 'id1': [ ('description1a', 'type1'), ('description1b','type1') ], 
  'id2': [ ('description2', 'type2') ],
...
}

这看起来非常简洁。ID仅表示一次。

也许你有类似这样的东西？

{ 'id1': ( ('description1a', 'description1b' ), 'type1' ),
  'id2': ( ('description2',), 'type2' ),
...
}

除非您使用struct模块，否则我不确定您是否可以找到更紧凑的内容。

- S.Lott

---

你提供的字典示例与我现有的非常接近，但是我正在寻找一种不涉及哈希表以减少内存消耗的解决方案。但如果其他结构都不能显著节省空间，我仍会继续使用字典。 - tim.tadh

有其他的方法可以安排你的数据，但这取决于你对数据的处理方式、你的需求和限制。 - Florian Bösch

我的例子只是瞎猜的。你的描述对你拥有的东西和实际问题都很模糊。你是内存不足了吗？还是这是过早的优化？ - S.Lott

这不是过早优化。使用 alpha 版本的人已经达到了我初始设计的固有限制。这只是我没有考虑周全的许多设计决策中的一个方面。 - tim.tadh

集合使用哈希表背后的相同逻辑进行实现，因此您在那里不会得到任何价值。 - Claudiu

Answer 2

我猜测你试图通过减少内存使用来解决的问题是进程地址空间限制。此外，你还在寻找一种数据结构，可以让你快速插入和合理顺序读取。

除字符串（str）外使用更少的结构

你所问的问题是如何在一个进程中组织你的数据以使用更少的内存。这个问题的一个标准答案是（只要你仍然需要关联查找），尽可能少地使用Python字符串（str，而不是unicode）以外的其他结构。Python哈希（字典）相当有效地存储了对你的字符串的引用（它不是B树实现）。

然而，我认为你不会在这个方法上有太大的进展，因为你面对的是可能最终超过进程地址空间和机器物理内存的巨大数据集。

替代方案

我提出了一个不涉及将你的数据结构更改为更难插入或解释的东西的不同解决方案。

• 将您的信息分成多个进程，每个进程都持有适合它的数据结构。
• 使用套接字实现进程间通信，以便进程可以完全驻留在其他机器上。
• 尝试划分数据以最小化进程间通信（与 CPU 周期相比，I/O 速度极慢）。

我所概述的方法的优点是

• 您可以充分利用机器上两个或更多核心的性能
• 您不受一个进程的地址空间或甚至一个机器的物理内存的限制

有许多分布式处理的软件包和方法，其中一些是

• linda
• processing

- Florian Bösch

---

感谢您发布并分享了这些并行化库的链接。我一直在考虑将我的应用程序多进程化，但是一直不想去解决那些困难的问题。也许等我完成工具链后，会使用其中一个库来实现。 - tim.tadh

Answer 3

如果您正在进行带有去重的n路合并，则以下内容可能是您要寻找的。

此生成器将合并任意数量的源。每个源必须是一个序列。 关键字必须在位置0上。它逐个生成合并的序列项。

def merge( *sources ):
    keyPos= 0
    for s in sources:
        s.sort()
    while any( [len(s)>0 for s in sources] ):
        topEnum= enumerate([ s[0][keyPos] if len(s) > 0 else None for s in sources ])
        top= [ t for t in topEnum if t[1] is not None ]
        top.sort( key=lambda a:a[1] )
        src, key = top[0]
        #print src, key
        yield sources[ src ].pop(0)

这个生成器可以从序列中移除重复元素。

def unique( sequence ):
    keyPos= 0
    seqIter= iter(sequence)
    curr= seqIter.next()
    for next in seqIter:
        if next[keyPos] == curr[keyPos]:
            # might want to create a sub-list of matches
            continue
        yield curr
        curr= next
    yield curr

这是一个使用这些函数的脚本，用于生成一个结果序列，该序列是所有源的并集，并删除了重复项。

for u in unique( merge( source1, source2, source3, ... ) ):
    print u

每个序列中的完整数据集必须存在于内存中一次，因为我们在内存中进行排序。然而，结果序列实际上并不存在于内存中。事实上，它通过消耗其他序列来工作。

- S.Lott

---

在查看了你的代码之后，我得出结论：你的代码处理整个数据集的时间大约是nalg(a)，其中n是所有来源中元素的总数，a是来源的数量。嘿，这仍然是线性时间，非常不错。我还没有决定要做什么，但干得好。 - tim.tadh

你可以通过外部排序来加快速度。这样就真的是线性的了。使用subprocess.Popen('sort source', stdout=PIPE)并从sort读取stdout。 - S.Lott

Answer 4

使用 {id:（描述，id_类型）} 字典如何？如果以（id，id_类型）作为键，则使用 {(id，id_类型)：描述} 字典。

- Constantin

Answer 5

Python中的集合是使用哈希表实现的。在早期版本中，它们实际上是使用集合实现的，但据我所知，这已经改变了。如果使用集合，您可以节省每个条目（即指向值的指针）的指针大小。

要仅使用元组的一部分进行哈希码，您需要子类化元组并覆盖哈希码方法：

class ProteinTuple(tuple):
     def __new__(cls, m1, m2, m3):
         return tuple.__new__(cls, (m1, m2, m3))

     def __hash__(self):
         return hash(self[0])

请记住，在这种情况下，您需要为额外的函数调用__hash__付费，否则它将成为一个C方法。

我会采纳Constantin的建议，从元组中删除id并查看它能帮助多少。

- Torsten Marek

Answer 6

虽然还不是很清楚，但听起来你有一些由[(id、描述、类型)...]组成的列表。

在一个列表中，id是唯一的，并且在多个列表之间保持一致。

你想要创建一个UNION：一个单一的列表，其中每个id只出现一次，可能有多个描述。

由于某种原因，你认为映射可能太大了。你有任何证据吗？不要在没有实际测量的情况下过度优化。

如果我猜得正确，这可能是来自多个来源的标准“合并”操作。

source1.sort()
source2.sort()
result= []
while len(source1) > 0 or len(source2) > 0:
    if len(source1) == 0:
        result.append( source2.pop(0) )
    elif len(source2) == 0:
        result.append( source1.pop(0) )
    elif source1[0][0] < source2[0][0]:
        result.append( source1.pop(0) )
    elif source2[0][0] < source1[0][0]:
        result.append( source2.pop(0) )
    else:
        # keys are equal
        result.append( source1.pop(0) )
        # check for source2, to see if the description is different.

通过排序和合并，这将两个列表组装成一个联合。没有映射，也没有哈希。

- S.Lott

---

这是一个有趣的解决方案，但我需要扩展它以便能够使用n个来源（n可能达到15或20），并允许在其中一个来源中出现两次相同的id。源可以由人类组装，因此我需要考虑这种可能性。简而言之，我需要进行一些时间分析。 - tim.tadh