алгоритм — файл индекса сортировки C ++ на месте (с heapsort)

Привет. Я пытаюсь отсортировать индексный файл на месте. Файл состоит из блоков данных 14B и обычно слишком велик для загрузки в оперативную память. Первые 8B — это байты, которые я хочу отсортировать после. Я реализовал алгоритм Heapsort, который пока кроме производительности работает отлично!

Мне интересно, можно ли улучшить мою реализацию и как я мог бы ускорить этот процесс, используя немного оперативной памяти. Я думал о возможном частичном хранении кучи в оперативной памяти, но я не уверен, как это будет работать.

Мой код до сих пор:

sortidx.h

#ifndef SORTIDX_H
#define SORTIDX_H

// Includes
#include <atomic>
#include <fstream>
#include <iostream>
#include <limits>
#include <string>
#include <thread>

// Constants
constexpr size_t hashSize = 8;
constexpr size_t offsetSize = 6;
constexpr size_t writeSize = hashSize + offsetSize;

// Typedefs & Structs
typedef std::lock_guard<std::mutex> scoped_lock;

struct IndexEntry {
unsigned char hash[hashSize]; // First 64 bits of the hash
unsigned char position[offsetSize]; // Position of word in dictionary (48-bit little endian integer)
} __attribute__( (__packed__) );

// Functions
bool operator>( const IndexEntry &rhs, const IndexEntry &lhs );

constexpr size_t getParent( size_t i ) {
return (i - 1) / 2;
}

constexpr size_t getLeft( size_t i ) {
return i * 2 + 1;
}

constexpr size_t getRight( size_t i ) {
return i * 2 + 2;
}

void sortIDX( std::string idxFile );

void heapifyIDX( size_t heapifyLimit );
void sortIDXHeap( size_t numDataSets );

void readData( IndexEntry* entry, size_t pos );
void writeData( IndexEntry* entry, size_t pos );
bool isInHeap( size_t pos );
void orderHeap( IndexEntry &top, size_t posTop );

#endif

sortidx.cpp

#include "sortidx.h"
using namespace std;

streampos fileSize;
size_t numDataSets;
size_t limit;
atomic<size_t> pos;
fstream* file;

bool operator>( const IndexEntry &rhs, const IndexEntry &lhs ) {
for ( size_t i = 0; i < hashSize; i++ ) {
if ( rhs.hash[i] > lhs.hash[i] )
return true;
else if ( rhs.hash[i] < lhs.hash[i] )
return false;
}

return false;
}

void sortIDX( string idxFile ) {
file = new fstream( idxFile, ios::in | ios::out | ios::binary | ios::ate );
fileSize = file->tellg();
numDataSets = fileSize / writeSize;
limit = numDataSets - 1;
const size_t localLimit = limit;
const size_t heapifyLimit = getParent( limit );
thread* sorterThread;

sorterThread = new thread( heapifyIDX, heapifyLimit );

while ( pos <= heapifyLimit ) {
// Some progressbar stuff (uses pos)
}

sorterThread->join();
delete sorterThread;

pos = 0;
sorterThread = new thread( sortIDXHeap, localLimit );

while ( pos < localLimit ) {
// Some progressbar stuff (uses pos)
}

sorterThread->join();
delete sorterThread;

file->close();
delete file;
}

void heapifyIDX( size_t heapifyLimit ) {
IndexEntry top;
size_t posTop;

for ( pos = 0; pos <= heapifyLimit; pos++ ) {
posTop = heapifyLimit - pos;

readData( &top, posTop );

orderHeap( top, posTop );
}
}

void sortIDXHeap( size_t numDataSets ) {
IndexEntry last;
IndexEntry top;
size_t posLast;
size_t posTop;

for ( pos = 0; pos < numDataSets; pos++ ) {
posLast = numDataSets - pos;
posTop = 0;
limit = posLast - 1;

readData( &last, posTop );
readData( &top, posLast );
writeData( &last, posLast );

orderHeap( top, posTop );
}
}

void readData( IndexEntry* entry, size_t pos ) {
file->seekg( pos * writeSize );
file->read( (char*)entry, writeSize );
}

void writeData( IndexEntry* entry, size_t pos ) {
file->seekp( pos * writeSize );
file->write( (char*)entry, writeSize );
}

bool isInHeap( size_t pos ) {
return pos <= limit;
}

void orderHeap( IndexEntry &top, size_t posTop ) {
static IndexEntry left;
static IndexEntry right;
static size_t posLeft;
static size_t posRight;
static bool swapped;

do {
posLeft = getLeft( posTop );
posRight = getRight( posTop );

if ( isInHeap( posLeft ) ) {
readData( &left, posLeft );

if ( isInHeap( posRight ) ) {
readData( &right, posRight );

if ( right > left ) {
if ( right > top ) {
writeData( &right, posTop );
posTop = posRight;

swapped = true;
} else {
swapped = false;
}
} else {
if ( left > top ) {
writeData( &left, posTop );
posTop = posLeft;

swapped = true;
} else {
swapped = false;
}
}
} else {
if ( left > top ) {
writeData( &left, posTop );
posTop = posLeft;

swapped = true;
} else {
swapped = false;
}
}
} else {
swapped = false;
}
} while ( swapped );

writeData( &top, posTop );
}

Я надеюсь, что вы можете немного помочь мне с проблемой, на которой я застрял довольно давно.
Я реализую простую таблицу поиска для быстрого поиска файла. Моя текущая проблема — индексный файл. В настоящее время я перебираю файл данных и создаю свои записи индекса с 8 байтами данных, которые я собираюсь искать, за которыми следуют 6 байтов данных, указывающих расположение этого набора данных в исходном файле. Таким образом, мой индексный файл состоит из 14-байтовых блоков данных. Теперь я хочу отсортировать этот файл, чтобы я мог легко найти свои данные, выполнив бинарный поиск в индексном файле. Это та часть, где я до сих пор борюсь.

Мне нужно отсортировать эти 14-байтовые записи на месте по первым 8 байтам. Простая сортировка по первым 8 байтам не должна быть слишком большой проблемой. Я довольно озадачен тем, как я могу отсортировать сам файл.
Я пытался реализовать класс «итератор» для файла, чтобы передать его std::sort который должен делать работу довольно хорошо. Но так как я не уверен, какие интерфейсы я должен предоставить, чтобы это работало, и я также не могу прочитать текущий прогресс, я провел некоторое исследование и мне напомнили об алгоритме Heapsort, который звучит очень хорошо, так как он имеет O(n*log(n)), на месте, и я могу оценить прогресс довольно хорошо.

Все идет нормально. Я все еще немного озадачен фактической реализацией этого, так как я не уверен, что было бы лучшим способом поменять несколько байтов данных в файле. Также мне интересно услышать, есть ли у вас альтернативные предложения о том, как отсортировать этот файл, так как размер файлов индекса составляет несколько ГБ, а производительность очень важна!