Dado un conjunto de 50k cadenas, necesito encontrar todos los pares (s, t), de modo que s, t y s + t estén todos contenidos en este conjunto.

Lo que he intentado

, hay una restricción adicional: s.length() >= 4 && t.length() >= 4. Esto hace posible agrupar las cadenas por prefijos de longitud 4 y, por separado, sufijos. Luego, para cada cadena composed de longitud de al menos 8, busco el conjunto de candidatos para s utilizando los primeros cuatro caracteres de composed y el conjunto de candidatos para t utilizando sus últimos cuatro caracteres. Esto funciona, pero necesita mirar 30 millones de pares de candidatos (s, t) para encontrar los resultados de 7k.

Este número sorprendentemente alto de candidatos proviene del hecho de que la cadena son palabras (en su mayoría alemanas) de un vocabulario limitado y la palabra comienza y termina a menudo igual. Todavía es mucho mejor que probar todos los pares de 2.5G, pero mucho peor de lo que esperaba.

Lo que necesito

Como la restricción adicional puede caerse y el conjunto crecerá, estoy buscando un mejor algoritmo.

La pregunta "faltante"

Hubo quejas de que no hice una pregunta. Entonces, el signo de interrogación faltante está al final de la siguiente oración. ¿Cómo se puede hacer esto de manera más eficiente, idealmente sin usar la restricción?

4
maaartinus 10 sep. 2018 a las 07:42

3 respuestas

Una posible solución podría ser esta. Comienzas con la primera cadena como prefijo y la segunda cadena como sufijo. Atraviesas cada cuerda. Si la cadena comienza con la primera cadena, verifica si termina en la segunda cadena. Y sigue hasta el final. Para ahorrar algo de tiempo antes de verificar si las letras son las mismas, puede hacer una verificación de longitud. Es más o menos lo que hizo, pero con esta verificación de longitud adicional, puede recortar algunas. Esa es mi opinión al menos.

0
The Mods Hunter 10 sep. 2018 a las 04:56

No estoy seguro de si esto es mejor que su solución, pero creo que vale la pena intentarlo.

Cree dos Intentos, uno con los candidatos en orden normal y el otro con las palabras invertidas.

Camina hacia adelante Trie desde la profundidad 4 hacia adentro y usa el resto de la hoja para determinar el sufijo (o algo así) y búscalo hacia atrás Trie.

He publicado una implementación Trie en el pasado aquí https://stackoverflow.com/a/9320920/823393.

0
OldCurmudgeon 10 sep. 2018 a las 06:02

Puede mejorar la respuesta de Erik evitando la mayor parte de la creación de sub - String usando CharBuffer vistas y alterando su posición y límite:

Set<CharBuffer> strings = Stream.of(
    "a", "abc", "abcdef", "def", "sun", "sunshine", "shine",
    "bear", "hug", "bearhug", "cur", "curlique", "curl",
    "down", "downstream", "stream"
 )
.filter(s -> s.length() >= 4) // < 4 is irrelevant
.map(CharBuffer::wrap)
.collect(Collectors.toSet());

strings
    .stream()
    .filter(s -> s.length() >= 8)
    .map(CharBuffer::wrap)
    .flatMap(cb -> IntStream.rangeClosed(4, cb.length() - 4)
        .filter(i -> strings.contains(cb.clear().position(i))&&strings.contains(cb.flip()))
        .mapToObj(i -> cb.clear()+" = "+cb.limit(i)+" + "+cb.clear().position(i))
    )
    .forEach(System.out::println);

Este es el mismo algoritmo, por lo tanto, no cambia la complejidad del tiempo, a menos que incorpore los costos de copia de datos de caracteres ocultos, lo que sería otro factor (multiplicado por la longitud promedio de la cadena).

Por supuesto, las diferencias se vuelven significativas solo si utiliza una operación de terminal diferente a la impresión de las coincidencias, ya que la impresión es una operación silenciosa y costosa. Del mismo modo, cuando la fuente es una secuencia sobre un archivo grande, la E / S dominará la operación. A menos que vaya en una dirección completamente diferente, como utilizar el mapeo de memoria y refactorizar esta operación para operar en ByteBuffer s.

1
Holger 10 sep. 2018 a las 10:19