Двоичный поиск в отсортированном (память-отображенном?) Файле в Java

Question

Я изо всех сил пытаюсь перенести программу Perl на Java и изучать Java, когда я иду. Центральным компонентом исходной программы является Perl module, который выполняет строковые префиксные поиски в отсортированном текстовом файле +500 ГБ, используя двоичный поиск (по существу, «искать» смещение байта в середине файла, откат до ближайшей новой строки, сравнивать префикс строки с поисковой строкой, «искать» на половину/удвоить это смещение байта, повторить до тех пор, пока не будет найден ...)

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

В качестве альтернативы, я не знаком с новыми (?) Java-I/O-библиотеками, но это будет вариант для карты памяти с текстовым файлом 500 ГБ (я на 64-битной машине с памятью, чтобы сэкономить) и выполнить двоичный поиск в массиве байтов с отображением памяти? Мне было бы очень интересно услышать любой опыт, который вы должны поделиться об этом и аналогичных проблемах.

Answer 1

Я большой поклонник Java-MappedByteBuffers для подобных ситуаций. Он быстро вспыхивает. Ниже приведен фрагмент, который я собрал для вас, который отображает буфер в файл, ищет середину и затем выполняет поиск назад к символу новой строки. Этого должно быть достаточно, чтобы вы собрались?

У меня есть подобный код (искать, читать, повторять до готовности) в моем собственном приложении, протестированные java.io потоков против MappedByteBuffer в производственной среде и опубликовал результаты на моем блоге (Geekomatic posts tagged 'java.nio') с исходными данными, графиками и все.

Вторая секунда? Реализация на моем MappedByteBuffer была примерно на 275% быстрее. YMMV.

Чтобы работать с файлами размером более ~ 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); 
    } 
} 

Answer 2

Это простой пример того, чего вы хотите достичь. Я бы, наверное, сначала проиндексировал файл, отслеживая позицию файла для каждой строки. Я предполагаю, что строки разделяются символами новой строки (или возврат каретки):

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. 

Answer 3

Если вы действительно хотите попробовать память отображение файла, я нашел в Java NiO в tutorial on how to use memory mapping.

Answer 4

Я не знаю ни одной библиотеки, имеющей эту функциональность.Тем не менее, правильный код для внешнего двоичного поиска в 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"); 
} 
} 

Пожалуйста, обратите внимание: я сделал этот код одноранговый: случаи Угловой не тестируются почти достаточно хорошо, код предполагает, что ни одна линия больше, чем 64K и т. д.

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

Я знаю, что это не вопрос, но создание префикса древовидной структуры данных, например (Patrica) Tries (на диске/SSD), может быть хорошей идеей для поиска префикса.

Answer 5

У меня такая же проблема. Я пытаюсь найти все строки, которые начинаются с некоторого префикса в отсортированном файле.

Вот метод, который я состряпал, который в значительной степени является порт кода 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; 
} 

Answer 6

Если вы имеете дело с файлом 500GB, то вы можете использовать более быстрый метод поиска, чем бинарный поиск, а именно - десятичные сортировки, который по существу представляет собой вариант хэширования. Лучший способ для этого действительно зависит от ваших распределений данных и типов поиска, но если вы ищете строковые префиксы, должен быть хороший способ сделать это.

Я разместил пример решения для сортировки счисления для целых чисел, но вы можете использовать ту же идею - в основном сократить время сортировки, разделив данные на ведра, а затем используя поиск 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 

Answer 7

У меня была аналогичная проблема, поэтому я создал (Scala) библиотеки из решений, представленных в этой теме:

https://github.com/avast/BigMap

Он содержит утилиту для сортировки огромный файл и бинарный поиск в этом отсортированного файла. ..

Answer 8

я отправляю Сущность https://gist.github.com/mikee805/c6c2e6a35032a3ab74f643a1d0f8249c

, что довольно полный пример, основанные на том, что я нашел на стек о verflow и некоторые блоги, надеюсь, кто-то еще сможет его использовать

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; 
    } 
}