2009-04-10 23 views
29

J'ai du mal à porter un programme Perl vers Java et à apprendre Java au fur et à mesure. Un composant central du programme d'origine est un Perl module qui fait des recherches de préfixe de chaîne dans un fichier texte trié +500 Go en utilisant la recherche binaire (essentiellement, "chercher" à un décalage d'octet au milieu du fichier, revenir en arrière au newline le plus proche, comparer préfixe de ligne avec la chaîne de recherche, "chercher" à moitié/double ce décalage d'octet, répéter jusqu'à trouvé ...)Recherche binaire dans un fichier trié (mappé en mémoire?) En Java

J'ai expérimenté plusieurs solutions de base de données, mais j'ai constaté que rien ne le bat en vitesse de recherche avec des ensembles de données de cette taille. Connaissez-vous une bibliothèque Java existante qui implémente une telle fonctionnalité? A défaut, pourriez-vous me montrer un exemple de code idiomatique qui fait des lectures aléatoires dans des fichiers texte? Sinon, je ne suis pas familier avec les nouvelles bibliothèques d'E/S Java (?) Mais serait-ce une option pour mapper le fichier texte de 500 Go (je suis sur une machine 64 bits avec de la mémoire à ma disposition)) et faire une recherche binaire sur le tableau d'octets mappé en mémoire? Je serais très intéressé d'entendre toutes les expériences que vous avez à partager à propos de ce problème et d'autres similaires.

Répondre

29

Je suis un grand fan de de Java MappedByteBuffers pour des situations comme celle-ci. Il flambe vite. Ci-dessous, un extrait que je mets ensemble pour mapper un tampon sur le fichier, cherche vers le milieu, puis effectue une recherche en arrière vers un caractère de retour à la ligne. Cela devrait être suffisant pour vous y aller?

J'ai un code similaire (chercher, lire, répéter jusqu'à ce que fait) dans ma propre application, benchmarkée java.io flux contre MappedByteBuffer dans un environnement de production et a publié les résultats sur mon blog (Geekomatic posts tagged 'java.nio') avec des données brutes, graphiques et tous.

Deux secondes de résumé? Ma mise en œuvre basée sur MappedByteBuffer était environ 275% plus rapide. YMMV.

Pour travailler pour les fichiers de plus de ~ 2 Go, ce qui est un problème à cause de la distribution et .position(int pos), j'ai conçu un algorithme de pagination soutenu par un tableau de MappedByteBuffer s. Vous aurez besoin de travailler sur un système 64 bits pour que cela fonctionne avec des fichiers de plus de 2 à 4 Go parce que les MBB utilisent le système de mémoire virtuelle du système d'exploitation pour travailler leur magie.

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); 
    } 
} 
+2

Je ne peux pas croire que les tampons NIO utilisent un int comme offset excluant la possibilité pour l'utiliser avec plus de 2 Go. C'est presque stupide sur les machines d'aujourd'hui. Dans ce contexte, aussi rapide soit-il, cela exclut l'approche dans le contexte donné ici. – dmeister

+3

Notez que la fonction FileChannel.map() prend beaucoup de temps, mais ByteBuffer lui-même ne prend que des ints. Vous pouvez utiliser des fichiers d'une taille supérieure à 2 Go, mais une vue mappée particulière ne peut pas dépasser 2 Go. (pour l'enregistrement le système d'exploitation Win32 a la même limitation) –

+0

Bon point, Jason S. –

1

Ceci est un exemple simple de ce que vous voulez réaliser. J'aurais probablement d'abord indexer le fichier, en gardant une trace de la position du fichier pour chaque chaîne. Je présume que les chaînes sont séparées par des sauts de ligne (ou retour chariot):

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

La dernière étape consiste à convertir en un tableau pour une légère amélioration de la vitesse lorsque vous faites beaucoup de recherches. Je voudrais probablement convertir le Long[] en un long[] aussi, mais je n'ai pas montré cela ci-dessus. Enfin, le code pour lire la chaîne à partir d'une position indexée donnée:

int i; // Initialize this appropriately for your algorithm. 
    file.seek(indexArray[i]); 
    String line = file.readLine(); 
      // At this point, line contains the string #i. 
+0

Est-ce que vous allez avoir assez de mémoire pour garder la liste d'index en mémoire? –

+0

Cela dépend du nombre d'entrées. On pourrait toujours écrire l'index et utiliser un LongBuffer, éventuellement mmap'd. –

+0

C'est une bonne idée, mais le fichier texte fait plus de 500 Go, ce qui gouverne à peu près cette approche. Quoi qu'il en soit, même si vous sautez au milieu d'une ligne avec seek, l'appel ultérieur d'un readLine() vous amène à la nouvelle ligne la plus proche, ajoutant peu ou pas de surcharge. – sds

2

Je ne connais aucune bibliothèque qui possède cette fonctionnalité.Cependant, un code correct pour une recherche binaire externe en Java doit être similaire à ceci:

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

S'il vous plaît noter: J'ai fait cette ad hoc code: cas d'angle ne sont pas testés presque assez bon, le code suppose que Je ne pense pas non plus que la construction d'un index des offsets où les lignes commencent pourrait être une bonne idée. Pour un fichier de 500 Go, cet index doit être stocké dans un fichier d'index. Vous devriez obtenir un facteur constant pas si petit avec cet index car il n'est pas nécessaire de rechercher la ligne suivante dans chaque étape.

Je sais que ce n'était pas la question, mais la construction d'une structure de données arborescente de préfixe comme (Patrica) Tries (sur disque/SSD) pourrait être une bonne idée de faire la recherche de préfixe.

+0

Merci, je me pencherai sur Patricia Tries (je ne vois pas encore à quoi ressemblerait une Trie sur le disque au lieu de la mémoire) – sds

+0

Comme pour trouver le début d'une ligne, le module perl original vide juste les lignes partielles avec readLine() après chaque recherche. Quand vous y pensez, cela n'interfère pas avec la recherche binaire elle-même. Le fichier texte a ~ 29x10^9 lignes, de sorte que l'index des décalages d'octets peut lui-même devenir lourd. – sds

3

J'ai le même problème. J'essaie de trouver toutes les lignes qui commencent par un préfixe dans un fichier trié.

Voici une méthode que je cuisinais jusqu'à ce qui est en grande partie un port de code Python trouvé ici: http://www.logarithmic.net/pfh/blog/01186620415

Je l'ai testé, mais pas à fond tout de suite. Il n'utilise pas de mappage de mémoire, cependant.

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

Si vous avez affaire à un fichier 500Go, alors vous voudrez peut-être utiliser une méthode de recherche plus rapide que la recherche binaire - à savoir une sorte radix qui est essentiellement une variante de hachage. La meilleure méthode pour cela dépend vraiment de vos distributions de données et des types de recherche, mais si vous cherchez des préfixes de chaînes, il devrait y avoir un bon moyen de le faire. J'ai posté un exemple d'une solution de tri de base pour les entiers, mais vous pouvez utiliser la même idée - essentiellement pour réduire le temps de tri en divisant les données en compartiments, puis en utilisant O (1) pour récupérer le seau de données pertinentes.

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 
0

J'ai eu le même problème, donc je créé (Scala) bibliothèque de solutions fournies dans ce fil:

https://github.com/avast/BigMap

Il contient l'utilitaire pour le fichier énorme tri et recherche binaire dans ce fichier trié. ..

0

je poste un point essentiel https://gist.github.com/mikee805/c6c2e6a35032a3ab74f643a1d0f8249c

qui est par exemple assez complet basé sur ce que j'ai trouvé sur pile o verflow et quelques blogs espérons que quelqu'un d'autre peut l'utiliser

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