Бинарный поиск в отсортированном (отображенном в память?) файле в Java
https://stackoverflow.com/questions/736556
-
09-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я изо всех сил пытаюсь портировать программу Perl на Java и изучаю Java по ходу дела.Центральным компонентом оригинальной программы является Perl-модуль Это выполняет поиск префикса строки в текстовом файле сортировки +500 ГБ с использованием двоичного поиска (по сути, «ищите» с байтовым смещением в середине файла, возвращайте к ближайшему новому линию, сравните префикс строки со строкой поиска «Ищите» наполовину/удвоить это смещение байта, повторить, пока не найден ...)
Я экспериментировал с несколькими решениями для баз данных, но обнаружил, что ничто не сравнится с этим по скорости поиска в наборах данных такого размера.Знаете ли вы какую-либо существующую библиотеку Java, реализующую такую функциональность?Если это не удастся, не могли бы вы указать мне на какой-нибудь идиоматический пример кода, который выполняет произвольное чтение текстовых файлов?
В качестве альтернативы я не знаком с новыми (?) библиотеками ввода-вывода Java, но будет ли возможность сопоставить с памятью текстовый файл размером 500 ГБ (я на 64-битной машине с свободной памятью) и выполнить двоичный файл поиск в массиве байтов, отображенном в памяти?Мне было бы очень интересно услышать ваш опыт по поводу этой и подобных проблем.
Решение
Я большой фанат Java MappedByteBuffers для подобных ситуаций.Он пылает быстро.Ниже приведен фрагмент, который я собрал для вас, который сопоставляет буфер с файлом, ищет середину, а затем выполняет поиск назад до символа новой строки.Этого должно быть достаточно, чтобы начать работу?
У меня есть аналогичный код (ищите, читайте, повторяйте, пока не закончите) в моем собственном приложении, проверенном на практике.java.io потоки против MappedByteBuffer в производственной среде и разместил результаты в своем блоге (Сообщения Geekomatic с тегами «java.nio» ) с необработанными данными, графиками и всем остальным.
Двухсекундное резюме? Мой MappedByteBufferРеализация на основе технологии была примерно на 275 % быстрее. ЮММВ.
Для работы с файлами размером более ~2 ГБ, что является проблемой из-за приведения и .position(int pos), я разработал алгоритм пейджинга, опирающийся на массив MappedByteBufferс.Вам нужно будет работать в 64-битной системе, чтобы это работало с файлами размером более 2–4 ГБ, поскольку MBB использует систему виртуальной памяти ОС для творения чудес.
public class StusMagicLargeFileReader {
private static final long PAGE_SIZE = Integer.MAX_VALUE;
private List<MappedByteBuffer> buffers = new ArrayList<MappedByteBuffer>();
private final byte raw[] = new byte[1];
public static void main(String[] args) throws IOException {
File file = new File("/Users/stu/test.txt");
FileChannel fc = (new FileInputStream(file)).getChannel();
StusMagicLargeFileReader buffer = new StusMagicLargeFileReader(fc);
long position = file.length() / 2;
String candidate = buffer.getString(position--);
while (position >=0 && !candidate.equals('\n'))
candidate = buffer.getString(position--);
//have newline position or start of file...do other stuff
}
StusMagicLargeFileReader(FileChannel channel) throws IOException {
long start = 0, length = 0;
for (long index = 0; start + length < channel.size(); index++) {
if ((channel.size() / PAGE_SIZE) == index)
length = (channel.size() - index * PAGE_SIZE) ;
else
length = PAGE_SIZE;
start = index * PAGE_SIZE;
buffers.add(index, channel.map(READ_ONLY, start, length));
}
}
public String getString(long bytePosition) {
int page = (int) (bytePosition / PAGE_SIZE);
int index = (int) (bytePosition % PAGE_SIZE);
raw[0] = buffers.get(page).get(index);
return new String(raw);
}
}
Другие советы
У меня та же проблема.Я пытаюсь найти в отсортированном файле все строки, начинающиеся с какого-либо префикса.
Вот метод, который я придумал, который по сути представляет собой порт кода Python, найденный здесь: http://www.logarithmic.net/pfh/blog/01186620415
Я протестировал это, но еще не полностью.Однако он не использует отображение памяти.
public static List<String> binarySearch(String filename, String string) {
List<String> result = new ArrayList<String>();
try {
File file = new File(filename);
RandomAccessFile raf = new RandomAccessFile(file, "r");
long low = 0;
long high = file.length();
long p = -1;
while (low < high) {
long mid = (low + high) / 2;
p = mid;
while (p >= 0) {
raf.seek(p);
char c = (char) raf.readByte();
//System.out.println(p + "\t" + c);
if (c == '\n')
break;
p--;
}
if (p < 0)
raf.seek(0);
String line = raf.readLine();
//System.out.println("-- " + mid + " " + line);
if (line.compareTo(string) < 0)
low = mid + 1;
else
high = mid;
}
p = low;
while (p >= 0) {
raf.seek(p);
if (((char) raf.readByte()) == '\n')
break;
p--;
}
if (p < 0)
raf.seek(0);
while (true) {
String line = raf.readLine();
if (line == null || !line.startsWith(string))
break;
result.add(line);
}
raf.close();
} catch (IOException e) {
System.out.println("IOException:");
e.printStackTrace();
}
return result;
}
Я не знаю ни одной библиотеки, которая имела бы такую функциональность.Однако правильный код для внешнего двоичного поиска в Java должен выглядеть примерно так:
class ExternalBinarySearch {
final RandomAccessFile file;
final Comparator<String> test; // tests the element given as search parameter with the line. Insert a PrefixComparator here
public ExternalBinarySearch(File f, Comparator<String> test) throws FileNotFoundException {
this.file = new RandomAccessFile(f, "r");
this.test = test;
}
public String search(String element) throws IOException {
long l = file.length();
return search(element, -1, l-1);
}
/**
* Searches the given element in the range [low,high]. The low value of -1 is a special case to denote the beginning of a file.
* In contrast to every other line, a line at the beginning of a file doesn't need a \n directly before the line
*/
private String search(String element, long low, long high) throws IOException {
if(high - low < 1024) {
// search directly
long p = low;
while(p < high) {
String line = nextLine(p);
int r = test.compare(line,element);
if(r > 0) {
return null;
} else if (r < 0) {
p += line.length();
} else {
return line;
}
}
return null;
} else {
long m = low + ((high - low) / 2);
String line = nextLine(m);
int r = test.compare(line, element);
if(r > 0) {
return search(element, low, m);
} else if (r < 0) {
return search(element, m, high);
} else {
return line;
}
}
}
private String nextLine(long low) throws IOException {
if(low == -1) { // Beginning of file
file.seek(0);
} else {
file.seek(low);
}
int bufferLength = 65 * 1024;
byte[] buffer = new byte[bufferLength];
int r = file.read(buffer);
int lineBeginIndex = -1;
// search beginning of line
if(low == -1) { //beginning of file
lineBeginIndex = 0;
} else {
//normal mode
for(int i = 0; i < 1024; i++) {
if(buffer[i] == '\n') {
lineBeginIndex = i + 1;
break;
}
}
}
if(lineBeginIndex == -1) {
// no line begins within next 1024 bytes
return null;
}
int start = lineBeginIndex;
for(int i = start; i < r; i++) {
if(buffer[i] == '\n') {
// Found end of line
return new String(buffer, lineBeginIndex, i - lineBeginIndex + 1);
return line.toString();
}
}
throw new IllegalArgumentException("Line to long");
}
}
Пожалуйста, обрати внимание:Я составил этот код специально:Угловые случаи не проверены достаточно хорошо, код предполагает, что ни одна строка не превышает 64 КБ и т. д.
Я также думаю, что создание индекса смещений, где начинаются линии, может быть хорошей идеей.Для файла размером 500 ГБ этот индекс должен храниться в индексном файле.С этим индексом вы должны получить не такой уж маленький постоянный коэффициент, потому что тогда нет необходимости искать следующую строку на каждом шаге.
Я знаю, что это был не вопрос, но создание структуры данных префиксного дерева, такой как (Patrica) Tries (на диске/SSD), могло бы быть хорошей идеей для поиска префиксов.
Это простой пример того, чего вы хотите достичь.Я бы, вероятно, сначала проиндексировал файл, отслеживая позицию файла для каждой строки.Я предполагаю, что строки разделены символами новой строки (или возвратами каретки):
RandomAccessFile file = new RandomAccessFile("filename.txt", "r");
List<Long> indexList = new ArrayList();
long pos = 0;
while (file.readLine() != null)
{
Long linePos = new Long(pos);
indexList.add(linePos);
pos = file.getFilePointer();
}
int indexSize = indexList.size();
Long[] indexArray = new Long[indexSize];
indexList.toArray(indexArray);
Последний шаг — преобразовать в массив для небольшого повышения скорости при выполнении большого количества поисков.Я бы, наверное, перевел Long[] к long[] тоже, но выше я этого не показывал.Наконец, код для чтения строки из заданной индексированной позиции:
int i; // Initialize this appropriately for your algorithm.
file.seek(indexArray[i]);
String line = file.readLine();
// At this point, line contains the string #i.
Если вы имеете дело с файлом размером 500 ГБ, возможно, вам захочется использовать более быстрый метод поиска, чем двоичный поиск, а именно, поразрядную сортировку, которая по сути является вариантом хеширования.Лучший способ сделать это действительно зависит от вашего распределения данных и типов поиска, но если вы ищете строковые префиксы, должен быть хороший способ сделать это.
Я опубликовал пример решения поразрядной сортировки целых чисел, но вы можете использовать ту же идею — по сути, чтобы сократить время сортировки, разделив данные на сегменты, а затем используя поиск O (1) для получения сегмента соответствующих данных. .
Option Strict On
Option Explicit On
Module Module1
Private Const MAX_SIZE As Integer = 100000
Private m_input(MAX_SIZE) As Integer
Private m_table(MAX_SIZE) As List(Of Integer)
Private m_randomGen As New Random()
Private m_operations As Integer = 0
Private Sub generateData()
' fill with random numbers between 0 and MAX_SIZE - 1
For i = 0 To MAX_SIZE - 1
m_input(i) = m_randomGen.Next(0, MAX_SIZE - 1)
Next
End Sub
Private Sub sortData()
For i As Integer = 0 To MAX_SIZE - 1
Dim x = m_input(i)
If m_table(x) Is Nothing Then
m_table(x) = New List(Of Integer)
End If
m_table(x).Add(x)
' clearly this is simply going to be MAX_SIZE -1
m_operations = m_operations + 1
Next
End Sub
Private Sub printData(ByVal start As Integer, ByVal finish As Integer)
If start < 0 Or start > MAX_SIZE - 1 Then
Throw New Exception("printData - start out of range")
End If
If finish < 0 Or finish > MAX_SIZE - 1 Then
Throw New Exception("printData - finish out of range")
End If
For i As Integer = start To finish
If m_table(i) IsNot Nothing Then
For Each x In m_table(i)
Console.WriteLine(x)
Next
End If
Next
End Sub
' run the entire sort, but just print out the first 100 for verification purposes
Private Sub test()
m_operations = 0
generateData()
Console.WriteLine("Time started = " & Now.ToString())
sortData()
Console.WriteLine("Time finished = " & Now.ToString & " Number of operations = " & m_operations.ToString())
' print out a random 100 segment from the sorted array
Dim start As Integer = m_randomGen.Next(0, MAX_SIZE - 101)
printData(start, start + 100)
End Sub
Sub Main()
test()
Console.ReadLine()
End Sub
End Module
я публикую суть https://gist.github.com/mikee805/c6c2e6a35032a3ab74f643a1d0f8249c
это довольно полный пример, основанный на том, что я нашел при переполнении стека, и в некоторых блогах, надеюсь, кто-то еще сможет его использовать
import static java.nio.file.Files.isWritable;
import static java.nio.file.StandardOpenOption.READ;
import static org.apache.commons.io.FileUtils.forceMkdir;
import static org.apache.commons.io.IOUtils.closeQuietly;
import static org.apache.commons.lang3.StringUtils.isBlank;
import static org.apache.commons.lang3.StringUtils.trimToNull;
import java.io.File;
import java.io.IOException;
import java.nio.Buffer;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.file.Path;
public class FileUtils {
private FileUtils() {
}
private static boolean found(final String candidate, final String prefix) {
return isBlank(candidate) || candidate.startsWith(prefix);
}
private static boolean before(final String candidate, final String prefix) {
return prefix.compareTo(candidate.substring(0, prefix.length())) < 0;
}
public static MappedByteBuffer getMappedByteBuffer(final Path path) {
FileChannel fileChannel = null;
try {
fileChannel = FileChannel.open(path, READ);
return fileChannel.map(FileChannel.MapMode.READ_ONLY, 0, fileChannel.size()).load();
}
catch (Exception e) {
throw new RuntimeException(e);
}
finally {
closeQuietly(fileChannel);
}
}
public static String binarySearch(final String prefix, final MappedByteBuffer buffer) {
if (buffer == null) {
return null;
}
try {
long low = 0;
long high = buffer.limit();
while (low < high) {
int mid = (int) ((low + high) / 2);
final String candidate = getLine(mid, buffer);
if (found(candidate, prefix)) {
return trimToNull(candidate);
}
else if (before(candidate, prefix)) {
high = mid;
}
else {
low = mid + 1;
}
}
}
catch (Exception e) {
throw new RuntimeException(e);
}
return null;
}
private static String getLine(int position, final MappedByteBuffer buffer) {
// search backwards to the find the proceeding new line
// then search forwards again until the next new line
// return the string in between
final StringBuilder stringBuilder = new StringBuilder();
// walk it back
char candidate = (char)buffer.get(position);
while (position > 0 && candidate != '\n') {
candidate = (char)buffer.get(--position);
}
// we either are at the beginning of the file or a new line
if (position == 0) {
// we are at the beginning at the first char
candidate = (char)buffer.get(position);
stringBuilder.append(candidate);
}
// there is/are char(s) after new line / first char
if (isInBuffer(buffer, position)) {
//first char after new line
candidate = (char)buffer.get(++position);
stringBuilder.append(candidate);
//walk it forward
while (isInBuffer(buffer, position) && candidate != ('\n')) {
candidate = (char)buffer.get(++position);
stringBuilder.append(candidate);
}
}
return stringBuilder.toString();
}
private static boolean isInBuffer(final Buffer buffer, int position) {
return position + 1 < buffer.limit();
}
public static File getOrCreateDirectory(final String dirName) {
final File directory = new File(dirName);
try {
forceMkdir(directory);
isWritable(directory.toPath());
}
catch (IOException e) {
throw new RuntimeException(e);
}
return directory;
}
}
У меня была похожая проблема, поэтому я создал библиотеку (Scala) из решений, представленных в этой теме:
https://github.com/avast/BigMap
Он содержит утилиту для сортировки огромных файлов и бинарного поиска в этом отсортированном файле...
Если вы действительно хотите попробовать отобразить файл в памяти, я нашел учебник о том, как использовать сопоставление памяти в Java нио.
