Binäre Suche in einer sortierten (Memory-Mapped?) Datei in Java

Question

Ich habe Probleme, ein Perl-Programm nach Java zu portieren und Java zu lernen, so wie ich es mache. Eine zentrale Komponente des ursprünglichen Programms ist eine , die String-Präfix-Lookups in einer +500 GB sortierten Textdatei unter Verwendung der binären Suche (im Wesentlichen "suchen" zu einem Byte Offset in der Mitte der Datei, zurück zum nächsten Newline, vergleichen) Zeile Präfix mit der Suchzeichenkette, "suchen", um den Byteversatz zu halbieren/zu verdoppeln, wiederholen, bis gefunden ...)

Ich habe mit mehreren Datenbanklösungen experimentiert, aber gefunden, dass nichts dieses in bloßer Nachschlagegeschwindigkeit mit Datensätzen schlägt diese Größe. Kennen Sie eine vorhandene Java-Bibliothek, die diese Funktionalität implementiert? Könnten Sie mich auf einen idiomatischen Beispielcode hinweisen, der zufällige Lesezugriffe in Textdateien vornimmt?

Alternativ kenne ich die neuen (?) Java I/O-Bibliotheken nicht, aber wäre es eine Option, die 500-GB-Textdatei zu speichern (ich bin auf einer 64-Bit-Maschine mit Speicher)) und binäre Suche auf dem Speicher-gemappten Byte-Array durchführen? Ich würde mich sehr freuen, irgendwelche Erfahrungen zu hören, die Sie über diese und ähnliche Probleme teilen müssen.

Answer 1

Ich bin ein große Fan von Java MappedByteBuffers für Situationen wie diese. Es ist blitzschnell. Unten ist ein Ausschnitt, den ich für Sie zusammengestellt habe, der der Datei einen Puffer zuordnet, nach der Mitte sucht und dann rückwärts nach einem Zeilenumbruch sucht. Dies sollte genug sein, um Sie in Gang zu bringen?

Ich habe einen ähnlichen Code (suchen, lesen, bis getan wiederholen) in meiner eigenen Anwendung, gebenchmarkt java.io Ströme gegen MappedByteBuffer in einer Produktionsumgebung und veröffentlicht die Ergebnisse auf meinem Blog (Geekomatic posts tagged 'java.nio') mit Rohdaten, Grafiken und alle.

Zwei zweite Zusammenfassung? Meine MappedByteBuffer-basierte Implementierung war etwa 275% schneller. YMMV.

Um für Dateien größer als ~ 2GB zu arbeiten, was ein Problem wegen der Besetzung und .position(int pos) ist, habe ich Paging-Algorithmus erstellt von einem Array von MappedByteBuffer s unterstützt. Sie müssen an einem 64-Bit-System arbeiten, um mit Dateien arbeiten zu können, die größer als 2-4 GB sind, da MBBs das virtuelle Speichersystem des Betriebssystems verwenden, um ihre Magie zu entfalten.

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

Dies ist ein einfaches Beispiel für das, was Sie erreichen möchten. Ich würde wahrscheinlich zuerst die Datei indexieren und die Dateiposition für jede Zeichenfolge verfolgen. Ich gehe davon aus den Saiten durch Zeilenumbrüche voneinander getrennt sind (oder Zeilenumbrüche):

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

Der letzte Schritt ist eine leichte Verbesserung der Geschwindigkeit auf ein Array zu konvertieren, wenn viele Lookups zu tun. Ich würde wahrscheinlich auch die Long[] in eine long[] konvertieren, aber das habe ich oben nicht gezeigt. Schließlich wird der Code die Zeichenfolge aus einer bestimmten indizierten Position zu lesen:

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

Wenn Sie wirklich Speicherzuordnung, die Datei versuchen wollen, fand ich eine tutorial on how to use memory mapping in Java nio.

Answer 4

Mir ist keine Bibliothek bekannt, die diese Funktionalität hat.Allerdings sollte ein korrekter Code für eine externe binäre Suche in Java ähnlich der folgenden sein:

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

Bitte beachten Sie: Ich machte diesen Code Ad-hoc-up: Corner Fälle sind nicht annähernd gut genug getestet, der Code geht davon aus, dass keine einzelne Zeile ist größer als 64K, usw.

Ich denke auch, dass die Erstellung eines Index der Offsets, wo Zeilen starten, eine gute Idee sein könnte. Für eine 500-GB-Datei sollte dieser Index in einer Indexdatei gespeichert werden. Sie sollten einen nicht so kleinen konstanten Faktor mit diesem Index erhalten, da es nicht notwendig ist, in jedem Schritt nach der nächsten Zeile zu suchen.

Ich weiß, das war nicht die Frage, aber eine Präfix Baum Datenstruktur wie (Patrica) Tries (auf Festplatte/SSD) zu bauen, könnte eine gute Idee sein, die Präfix-Suche zu tun.

Answer 5

Ich habe das gleiche Problem. Ich versuche alle Zeilen zu finden, die mit einem Präfix in einer sortierten Datei beginnen. Hier

ist eine Methode, die ich gekocht, die weitgehend eine Portierung von Python-Code hier ist: http://www.logarithmic.net/pfh/blog/01186620415

ich es getestet haben, aber nicht gründlich nur noch. Es wird jedoch keine Speicherzuordnung verwendet.

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

Wenn Sie mit einer 500 GB-Datei zu tun hat, dann mögen Sie vielleicht eine schnellere Lookup-Methode als binäre Suche verwenden - nämlich eine Radixsort, die im Wesentlichen eine Variante des Hashing ist. Die beste Methode, um dies zu tun, hängt wirklich von Ihren Datenverteilungen und Lookup-Typen ab, aber wenn Sie nach String-Präfixen suchen, sollte dies ein guter Weg sein.

Ich habe ein Beispiel für eine Radix Sortierung Lösung für Integer, aber Sie können die gleiche Idee - im Grunde, um die Sortierzeit durch Teilen der Daten in Eimer, dann mit O (1) Suche, um den Eimer von Daten, die relevant sind.

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

ich ähnliches Problem hatte, so habe ich (Scala) Bibliothek von Lösungen in diesem Thread zur Verfügung gestellt:

https://github.com/avast/BigMap

Es enthält Dienstprogramm in dieser sortierten Datei große Datei und binäre Suche Sortierung. ..

Answer 8

poste ich einen Kern https://gist.github.com/mikee805/c6c2e6a35032a3ab74f643a1d0f8249c

, die eher vollständiges Beispiel basiert auf, was ich gefunden auf Stapel o verflow und einige Blogs hoffentlich kann jemand anderes es verwenden

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