我有以下形式的数据列表：

[[(id \ __ 1_，description，id \ _type)，(id \ __ 2_，description，id \ _type)，...，(id \ __ n_，description，id \ _type))

数据是从属于同一组的文件中加载的。在每个组中，可能有多个具有相同ID的ID，每个ID来自不同的文件。我不在乎重复项，因此我认为存储所有这些内容的一种好方法是将其放入Set类型。但是有一个问题。

有时，对于相同的ID，说明可能会略有不同，如下所示：

IPI00110753

• 微管蛋白α-1A链
• 微管蛋白α-1链
• α-微管蛋白1
• α-微管蛋白同型M-alpha-1

(请注意，此示例摘自uniprot蛋白质数据库。)

我不在乎描述是否有所不同。我不能扔掉它们，因为我使用的蛋白质数据库有可能不会包含特定标识符的列表。如果发生这种情况，我将希望能够向生物学家显示人类可读的描述，以便他们大致了解他们正在寻找的蛋白质。

我目前正在通过使用字典类型解决此问题。但是，我不太喜欢这种解决方案，因为它占用大量内存(我有很多这些ID)。这只是它们的中间清单。在将ID放入数据库之前，还需要进行一些其他处理，因此我希望使数据结构更小。

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

感谢我们阅读我的问题，
提姆

更新

根据我收到的一些评论，让我澄清一下。我对数据结构所做的大部分工作都是插入其中。我只读过两次，一次是用添加信息注释它，*一次是插入数据库。但是，在插入数据库之前，可能还会进行其他注释。不幸的是，我不知道现在是否会发生这种情况。

现在，我正在考虑将这些数据存储在不基于哈希表(即字典)的结构中。我希望新结构在插入时相当快，但是读取它可以是线性的，因为我实际上只做过两次。我试图离开哈希表以节省空间。是否有更好的结构或者哈希表是否达到了它的最佳水平？

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

解决方案

集合没有键。元素是关键。

如果我们认为需要按键，则可以进行映射。根据定义，或者多或者少。

即使使用二进制搜索，顺序列表查找也可能很慢。映射使用哈希并且速度很快。

我们是在说这样的字典吗？

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

这肯定显得微不足道。 ID仅代表一次。

也许我们有这样的事情？

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

我不确定是否可以找到更紧凑的东西，除非我们诉诸于使用struct模块。

如何使用{{id：(description，id_type)}`字典呢？如果(id，id_type)是键，则使用" {{id，id_type)：description}"字典。

Python中的集合是使用哈希表实现的。在早期版本中，它们实际上是使用集合实现的，但是这改变了AFAIK。使用集保存的唯一内容就是每个条目的指针大小(指向值的指针)。

要仅将元组的一部分用于哈希码，我们必须对元组进行子类化并重写hashcode方法：

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方法。

我会去问康斯坦丁的建议，从元组中取出ID，看看有什么帮助。

我假设我们尝试通过减少使用的内存来解决的问题是进程的地址空间限制。另外，我们搜索的数据结构允许我们快速插入并进行合理的顺序读出。

使用较少的结构，除了字符串(str)

我们要问的问题是如何在一个进程中结构化数据以使用更少的内存。一个规范的答案是(只要我们仍然需要关联查询)，请使用尽可能少的其他结构，然后使用python字符串(str，而不是unicode)。 python哈希(字典)相当有效地存储了对字符串的引用(它不是b树实现)。

但是，我认为使用这种方法不会走得太远，因为我们面对的是庞大的数据集，这些数据集最终可能会刚好超过我们正在使用的机器的进程地址空间和物理内存。

替代解决方案

我将提出一种不同的解决方案，该解决方案不涉及将数据结构更改为更难插入或者解释的内容。

• 将信息分解为多个过程，每个过程都保存有便利的数据结构。
• 与套接字实现进程间通信，以便进程可以完全驻留在其他计算机上。
• 尝试对数据进行划分，例如以最大程度地减少进程间的通信(与CPU周期相比，I / O速度慢)。

我概述的方法的优点是

• 我们必须在机器上完全使用两个或者两个以上的内核来提高性能
• 我们不受一个进程的地址空间或者一台计算机的物理内存的限制

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

• 琳达
• 加工

它仍然很模糊，但是听起来我们有[[id，description，type)...]的一些列表

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.

这通过排序和合并来组装两个列表的并集。没有映射，没有哈希。

如果要进行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

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