Sqlite升序似乎不适用于对分

Question

我正在使用二分模块搜索并将sha256哈希插入列表。

我有大约8,000,000项要搜索和添加，它们存储在sqlite数据库中，我想把它们读入列表，这样我就可以更快地搜索它们。

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

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

问题是当我这样做的时候，对一些项目的二分搜索失败了，但是如果我依次搜索项目的哈希值，它实际上就在那里。

因此，似乎数据库提供的顺序与使用对分获取索引位置时提供的顺序并不完全相同。

知道为什么会这样吗？能够在依赖二分法之前对列表进行预先排序将非常有用。

更新...基于一个注释，我应该解释我有一个行为像列表的自定义类，它将哈希打包在字节数组中以节省内存。这是我的班级

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

谢谢

院长

Answer 1

如果它们存储在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)))