Самый быстрый алгоритм поиска в двоичных файлах?
Я ищу самый быстрый и лучший алгоритм для поиска некоторых значений в очень огромном двоичном файле (например, AFP-файл размером 2 ГБ), который означает, что загрузка всех данных в память должна быть немыслимой. Я работаю с C#, и я не знаю, будет ли какой-нибудь другой язык программирования (C/C++..) действительно намного быстрее, иначе я продолжу с C#. Спасибо за любые идеи.
4 ответа
Бойер-Мур предлагает хороший компромисс между производительностью и сложностью (а в связанных статьях есть ссылки на другие методы.
Реализация в C (исходный код в ссылке) будет значительно быстрее, чем в C#, хотя на практике вы, вероятно, обнаружите, что дисковый ввод-вывод является самым большим препятствием.
Прокомментировав, я решил предоставить возможное решение.
Будьте осторожны: это решение не самое лучшее и не элегантное.
Используйте это как отправную точку:
string SEARCH = @"X'D3A8AF";
int BUFFER = 1024;
int tot = 0;
using (FileStream fs = new FileStream(filename, FileMode.Open))
{
using (StreamReader sr = new StreamReader(fs))
{
char[] buffer = new char[BUFFER];
int pos = 0;
while (fs.Position < fs.Length)
{
sr.ReadBlock(buffer, 0, BUFFER);
string s = new string(buffer);
int i = 0;
do
{
i = s.IndexOf(SEARCH, i);
if (i >= 0) { tot++; i++; }
}
while (i >= 0);
pos += BUFFER;
if (!s.EndsWith(SEARCH)) pos -= SEARCH.Length;
fs.Position = pos;
}
sr.Close();
}
fs.Close();
}
BUFFER может быть изменено (увеличено), как вам угодно.
Вы должны загрузить весь файл для поиска объекта. Если возможно, разделите файлы на основе уникальных идентификаторов, если у вас есть. Например, разделить файл на каждые 100 записей (1-100, 101-200, 201-300 и т. Д.) На основе уникальных идентификаторов или некоторых других параметров. Это своего рода индексация вашего двоичного файла.