Вот пример (псевдокод, не тестировался) того, как вы можете построить частичный индекс записей в вашем двоичном файле, который позволит вам эффективно получать доступ к поддиапазонам, не загружая весь файл в память и максимизируя последовательное чтение:
import bisect
recordSize = 16 # size in bytes of one record in the file
chunkSize = 1024 # groups of 1K records (in number of records)
chunkIndex = [] # indexing value of first record of chunk (for each chunk)
with open("testFile", "rb") as binaryFile:
# build the partial index (chunkIndex) - only done once
binaryFile.seek(0, 2)
fileSize = binaryFile.tell()
for position in range(0, fileSize, chunkSize * recordSize):
binaryFile.seek(position)
record = binaryFile.read(recordSize)
# use your own record/binary format conversion here
chunkValue = int.from_bytes(record[:4],byteorder="little", signed=False)
chunkIndex.append(chunkValue)
# to access a range of records with values between A an B:
firstChunk = bisect_left(chunkIndex,A) # chunk that will contain start value
position = firstChunk * chunksize * recordSize
binaryFile.seek(position)
while not binaryFile.eof:
records = binaryFile.read(recordSize*chunkSize) # sequential read.
for i in range(0,len(records),recordSize):
record = records[i:i+recordSize)
# use your own record/binary format conversion here
value = int.from_bytes(record[:4],byteorder="little", signed=False)
if value < A : continue
if value > B : break
# Process record here ...
if value > B : break
Вам нужно будет поиграть со значением chunkSize, чтобы найти подходящее место, которое уравновешивает время загрузки / использование памяти и время доступа к данным. Поскольку ваши диапазоны не всегда попадают на границы чанков, в худшем случае вы можете в конечном итоге прочитать записи, которые вам не нужны, и вам придется пропускать их. В среднем вы будете читать ненужные записи chunkSize / 2. Вот где разница в производительности между последовательным и произвольным доступом может окупиться.
На сетевом диске задержки влияют на произвольный доступ, а последовательный доступ является функцией полосы пропускания. Другими словами, для большего количества запросов требуется больше двусторонней передачи на сервер (задержка), а для чтения больших кусков требуется больше пакетов (пропускная способность).
Если вы используете жесткий диск (или сетевой диск), последовательное чтение нескольких соседних записи будут иметь тенденцию быть намного быстрее (по крайней мере, в 20 раз), чем произвольный доступ, и вы должны получить некоторые преимущества от этой частичной индексации.
Однако, если ваш файл находится на внутреннем SSD, тогда стандартный двоичный поиск непосредственно в файле ( без индексации памяти) будет работать быстрее.
При наличии 1 миллиарда записей для поиска позиции первой записи потребуется 30 операций поиска / чтения (2 ^ 30> 1B). Это означает, что, если вы сохраните 16M записей в индексе чанков, каждый чанк будет соответствовать 64 записям. Имея 16 миллионов ключей в памяти, вы сохраните 24 из 30 операций поиска / чтения, которые потребуются для прямого двоичного поиска. Это будет стоить 32 (в среднем) ненужных последовательных чтений.
Вы также можете реализовать гибрид двух подходов, чтобы минимизировать доступ к диску (т. Е. Использовать частичный индекс для определения диапазона фрагментов, а затем двоичный поиск, чтобы точно определить точное положение первой записи в начальном фрагменте). ). Для этого потребуется всего 6 операций поиска / чтения, чтобы точно определить первую запись в диапазоне 64 записей, указанном частичным индексом в памяти.
В обоих подходах, как только вы нашли первую запись, остальная часть диапазона будет считываться последовательно оттуда, пока вы не достигнете конца диапазона или конца файла. Если вы ожидаете, что читаете одни и те же записи более одного раза, возможно, будет возможна дальнейшая оптимизация путем сохранения кэша диапазонов записей, которые вы читали ранее, и использования его для получения данных без возврата на диск (например, путем пропуска запись читает, что у вас в кеше при последовательном чтении)