4

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

[(id\__1_, description, id\_type), (id\__2_, description, id\_type), ... , (id\__n_, description, id\_type))

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

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

IPI00110753

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

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

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

我目前正在通过使用字典类型来解决这个问题。但是我不太喜欢这个解决方案，因为它使用了大量内存（我有很多这些 ID）。这只是它们的中间列表。在将 ID 放入数据库之前，还需要进行一些额外的处理，所以我想保持我的数据结构更小。

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

感谢您阅读我的问题，
蒂姆

更新

根据我收到的一些评论，让我稍微澄清一下。我对数据结构所做的大部分工作都是插入其中。我只读了两次，一次是用附加信息注释它，一次是要插入到数据库中。然而，在我插入数据库之前，可能会有额外的注释。不幸的是，我不知道此时是否会发生这种情况。

现在我正在研究将这些数据存储在不基于哈希表（即字典）的结构中。我希望新结构在插入时相当快，但读取它可以是线性的，因为我实际上只做了两次。我试图远离哈希表以节省空间。是否有更好的结构或者哈希表是否尽可能好？

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

4

6 回答 6

2

Sets don't have keys. The element is the key.

If you think you want keys, you have a mapping. More-or-less by definition.

Sequential list lookup can be slow, even using a binary search. Mappings use hashes and are fast.

Are you talking about a dictionary like this?

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

This sure seems minimal. ID's are only represented once.

Perhaps you have something like this?

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

I'm not sure you can find anything more compact unless you resort to using the struct module.

于 2008-09-24T16:59:10.230 回答
1

如果您正在通过删除重复项进行 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

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

于 2008-09-24T19:40:55.160 回答
1

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

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

您提出的问题是如何在一个进程中构建数据以使用更少的内存。对此的一个规范答案是（只要您仍然需要关联查找），尽可能少地使用其他结构，然后使用 python 字符串（str，而不是 unicode）。python 哈希（字典）相当有效地存储对字符串的引用（它不是 b-tree 实现）。

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

替代解决方案

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

  • 将您的信息拆分为多个进程，每个进程都包含任何适合的数据结构。
  • 使用套接字实现进程间通信，以便进程可能完全驻留在其他机器上。
  • 尝试划分您的数据，以尽量减少进程间通信（与 cpu 周期相比，i/o 速度非常慢）。

我概述的方法的优点是

  • 您可以在一台机器上完全使用两个或更多内核来提高性能
  • 你不受一个进程的地址空间的限制，甚至不受一台机器的物理内存的限制

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

于 2008-09-24T17:32:59.523 回答
0

用{id: (description, id_type)}字典怎么样？或{(id, id_type): description}字典，如果 (id,id_type) 是键。

于 2008-09-24T17:04:11.963 回答
0

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

要仅将元组的一部分用于哈希码，您必须继承元组并覆盖哈希码方法：

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 ，看看有多大帮助。

于 2008-09-24T17:30:36.270 回答
0

它仍然很模糊，但听起来你有几个 [(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.

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

于 2008-09-24T17:36:20.233 回答