ordenamiento - busqueda binaria java wikipedia

Búsqueda binaria en un archivo ordenado(¿mapeado en memoria?) En Java

Question

Estoy luchando para portar un programa Perl a Java y aprendiendo Java sobre la marcha. Un componente central del programa original es un módulo Perl que realiza búsquedas de prefijos de cadena en un archivo de texto clasificado de +500 GB usando búsqueda binaria (esencialmente, "busca" a un desplazamiento de bytes en el medio del archivo, retrocede a la línea nueva más cercana, compara prefijo de línea con la cadena de búsqueda, "buscar" a la mitad / duplicar el desplazamiento de bytes, repetir hasta que se encuentre ...)

He experimentado con varias soluciones de base de datos, pero descubrí que nada supera esta velocidad de búsqueda con conjuntos de datos de este tamaño. ¿Conoces alguna biblioteca Java existente que implemente tal funcionalidad? Si eso falla, ¿podría señalarme algún código de ejemplo idiomático que haga lecturas de acceso aleatorio en archivos de texto?

Alternativamente, no estoy familiarizado con las nuevas bibliotecas de E / S de Java (?) Pero sería una opción mapear en memoria el archivo de texto de 500 GB (estoy en una máquina de 64 bits con memoria de sobra) y hacer binario buscar en la matriz de bytes mapeada en memoria? Estaría muy interesado en escuchar cualquier experiencia que tenga que compartir sobre este y otros problemas similares.

Answer 1

Este es un simple ejemplo de lo que quiere lograr. Probablemente primero indexaría el archivo, manteniendo un registro de la posición del archivo para cada cadena. Supongo que las cadenas están separadas por líneas nuevas (o retornos de carro):

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

El último paso es convertir a una matriz para una ligera mejora de velocidad al hacer muchas búsquedas. Probablemente también convertiría el Long[] a un long[] , pero no lo mostré anteriormente. Finalmente el código para leer la cadena desde una posición indexada dada:

    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 2

No tengo conocimiento de ninguna biblioteca que tenga esa funcionalidad. Sin embargo, un código correcto para una búsqueda binaria externa en Java debería ser similar a esto:

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

Tenga en cuenta: inventé este código ad-hoc: los casos de esquina no se probaron lo suficientemente bien, el código asume que ninguna línea es más grande que 64K, etc.

También creo que la construcción de un índice de los desplazamientos donde comienzan las líneas podría ser una buena idea. Para un archivo de 500 GB, ese índice debe almacenarse en un archivo de índice. Debería obtener un factor constante no tan pequeño con ese índice porque no hay necesidad de buscar la siguiente línea en cada paso.

Sé que esa no era la cuestión, pero construir una estructura de datos de árbol de prefijos como (Patrica) Tries (en disco / SSD) podría ser una buena idea para realizar la búsqueda de prefijos.

Answer 3

Publico un gist https://gist.github.com/mikee805/c6c2e6a35032a3ab74f643a1d0f8249c

ese es un ejemplo bastante completo basado en lo que encontré en el desbordamiento de pila y algunos blogs con suerte alguien más puede usarlo

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

Answer 4

Si está tratando con un archivo de 500 GB, es posible que desee utilizar un método de búsqueda más rápido que la búsqueda binaria, es decir, un tipo de raíz que es esencialmente una variante de hashing. El mejor método para hacer esto depende de las distribuciones de datos y los tipos de búsqueda, pero si busca prefijos de cadenas, debe haber una buena forma de hacerlo.

Publiqué un ejemplo de una solución de clasificación de radix para enteros, pero puede usar la misma idea, básicamente, para reducir el tiempo de clasificación al dividir los datos en grupos, luego usar la búsqueda O (1) para recuperar el grupo de datos que es relevante .

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 5

Si realmente desea probar el mapeo de memoria del archivo, encontré un tutorial sobre cómo usar el mapeo de memoria en Java nio.

Answer 6

Tengo el mismo problema. Estoy tratando de encontrar todas las líneas que comienzan con algún prefijo en un archivo ordenado.

Aquí hay un método que cociné, que en gran parte es un puerto de código Python que se encuentra aquí: http://www.logarithmic.net/pfh/blog/01186620415

Lo he probado pero no completamente todavía. Sin embargo, no utiliza la asignación de memoria.

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 7

Tuve un problema similar, así que creé (Scala) la biblioteca de las soluciones provistas en este hilo:

https://github.com/avast/BigMap

Contiene utilidad para ordenar archivos grandes y búsquedas binarias en este archivo ordenado ...

Answer 8

Soy un gran admirador de MappedByteBuffers de Java para situaciones como esta. Está ardiendo rápido. Debajo hay un fragmento que preparé para ti que mapea un búfer en el archivo, busca en el centro y luego busca hacia atrás un carácter de nueva línea. Esto debería ser suficiente para ponerte en marcha?

Tengo un código similar (buscar, leer, repetir hasta que MappedByteBuffer hecho) en mi propia aplicación, java.io transmisiones MappedByteBuffer contra MappedByteBuffer en un entorno de producción y MappedByteBuffer los resultados en mi blog ( publicaciones Geekomatic etiquetadas como ''java.nio'' ) con datos sin procesar, Gráficos y todo.

Dos segundo resumen? Mi implementación basada en MappedByteBuffer fue un 275% más rápida. YMMV.

Para trabajar con archivos de más de ~ 2 GB, que es un problema debido a la .position(int pos) y .position(int pos) , he creado un algoritmo de paginación respaldado por una matriz de MappedByteBuffer s. Tendrá que trabajar en un sistema de 64 bits para que funcione con archivos de más de 2-4 GB porque los MBB usan el sistema de memoria virtual del sistema operativo para hacer su magia.

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