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.
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
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) –
Bon point, Jason S. –