0

我正在使用 bisect 模块来搜索 sha256 哈希并将其插入到列表中。

我有大约 8,000,000 个要搜索和添加的项目，它们存储在 sqlite 数据库中，我想将它们读入列表中，以便更快地搜索它们。

我遇到的问题是使用 bisect 将项目插入列表以找到正确的插入点非常慢。完成所有 8,000,000 个项目大约需要 700 秒。

在 sqlite 数据库中按升序创建索引只需要大约 90 秒，然后将这些按顺序插入到列表中大约需要 60 秒。

问题是当我这样做时，对某些项目的平分搜索失败，但如果我按顺序搜索项目以查找哈希，它实际上就在那里。

所以看起来数据库提供的顺序与使用 bisect 获取索引位置时提供的顺序不太一样。

任何想法为什么会这样？在依赖 bisect 之前能够对列表进行预排序会非常有用。

更新....根据评论，我应该解释一下我有一个行为类似于列表的自定义类，它将散列打包在一个字节数组中以节省内存。这是我的课

class Hashlist():

def __init__(self, hashLen):
    self.__hashLen = hashLen
    self.__hashlist = bytearray()
    self.__num_items = 0

def __getitem__(self, index):
    if index >= len(self) or index < 0: 
        print index
        raise IndexError("hash index out of range")
        return 
    return str(self.__hashlist[index*self.__hashLen:(index+1)*self.__hashLen])

def __setitem__(self, index, data):
    if index > len(self) or index < 0: 
        raise IndexError("hash index out of range")
        return 
    if index == len(self):
        self.__hashlist.extend(data)
    else:
        self.__hashlist[index*self.__hashLen:(index+1)*self.__hashLen] = data

def insert(self, index, data):
    oldlen = len(self.__hashlist)/self.__hashLen
    if index > oldlen  or index < 0:
        raise IndexError("trying to insert past next element")
        return
    if index == oldlen:
        self.__hashlist.extend(data)
    else:
        # move the data
        if self.__hashLen == 1:
            self.__hashlist.append(chr(0))
            orig_data = str(self.__hashlist[(index):(len(self.__hashlist)-1)])
            self.__hashlist[(index + 1)*self.__hashLen:(len(self.__hashlist))*self.__hashLen] = orig_data
            #replace existing data
            self.__hashlist[index*self.__hashLen:(index+1)*self.__hashLen] = data
        else:
            orig_data = str(self.__hashlist[(index*self.__hashLen):(len(self.__hashlist) -1)*self.__hashLen])
            self.__hashlist[(index + 1)*self.__hashLen:(len(self.__hashlist))*self.__hashLen] = orig_data
            #replace existing data
            self.__hashlist[index*self.__hashLen:(index+1)*self.__hashLen] = data

谢谢

院长

4

1 回答 1

0

如果它们存储在 SQL 数据库中，则索引不能保证以“排序”顺序返回结果 - 您必须明确使用“排序依据”。

另外，如果您要进行那么多插入，那么我不会使用二分法，而是排序/合并。

# Add new to old and sort the whole lot...
old_hash_list.extend(new_hash_list)
old_hash_list.sort()

# Assuming new is already sorted than create new list of merged
import heapq
old_and_new = list(heapq.merge(old_hash_list, sorted(new_hash_list)))
于 2014-01-18T12:09:33.050 回答