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
ありがとう
ディーン