Gracias a las personas que probaron el Desafío 7. Con suerte, incluso si no tuvo la oportunidad, ha estado siguiendo las discusiones. ¿Cómo podemos resolver este desafío? Conceptualmente, el enfoque más simple encontraría duplicados de un solo carácter, luego duplicados de dos caracteres, tres caracteres, etc., aumentando en un carácter hasta que no hubiera duplicados. La verificación ingenua de todas las cadenas posibles para una longitud determinada consume cada vez más tiempo con la longitud de la subcadena. Para el genoma de Covid-19 con una longitud de aproximadamente 30 000 caracteres, aunque tenemos la garantía de tener duplicados de subcadenas de siete caracteres con solo 4 7 = 16,384 combinaciones únicas, solo ocurren 6889 (42%). Y el número de duplicados disminuye a medida que la cantidad de posibles duplicados aumenta rápidamente a medida que las subcadenas crecen. Se debe encontrar un método eficiente para identificar duplicados para que este enfoque funcione. Volveremos a esto después de examinar otras formas de abordar este problema.
Centrémonos en encontrar el duplicado más largo sin tener que preocuparnos por encontrar todos los duplicados. Un enfoque simple sería comenzar la subcadena en el primer carácter con un duplicado de siete caracteres, ya que debe existir uno. Luego, hágalo crecer un carácter a la vez hasta que no haya ningún duplicado. Muévase al siguiente carácter y una subcadena duplicada más larga. Continúe con esto hasta que esté lo suficientemente cerca del final de la cadena de búsqueda como para que no sea posible un duplicado. En el genoma de Covid-19, una subcadena de ocho caracteres ATTAAGG se puede construir a partir del primer carácter. Pasando al segundo carácter, una cadena de 11 caracteres TTAAAGGTTTA mirando fijamente a la posición 2 tiene un duplicado en la posición 20063. No hay duplicados de 11 caracteres o más a partir de la posición 3, por lo que pasamos a la posición 4. Etcétera. El siguiente código necesita alrededor de 5 segundos para encontrar la cadena duplicada más larga, dos cadenas superpuestas de 32 caracteres de A s. Tenga en cuenta que en el código a continuación, cuando existe un duplicado para una subcadena de igual longitud que la subcadena más larga ya encontrada, Mientras itera al menos una vez más antes de terminar. En estas situaciones SiguienteLen debe ser decrementada en 1.
findLongestDupe = Function({inString,charSet},{parts,nextLen,nextPos=1,longestDupes={""}},
parts = Items(inString,"");
nextLen = Floor(Log(Length(inString))/Log(N Items(charSet)));
While(nextPos <= Length(inString)-nextLen+1,
nextWord = Concat Items(parts[nextPos::(nextPos+nextLen-1)],"");
While(Contains(inString,nextWord,nextPos+1),
nextLen++;
nextWord = Concat Items(parts[nextPos::(nextPos+nextLen-1)],"");
);
nextPos++;
If(Length(nextWord)>Length(longestDupes[1]),
nextLen--; //nextLen will be one more than longest length when Pat Match fails
nextWord = Concat Items(parts[nextPos::(nextPos+nextLen-1)],"");
If(Length(nextWord)==Length(longestDupes[1])+1,
Insert Into(longestDupes,nextWord),
longestDupes = Eval List({nextWord})
);
);
nextChar++;
);
longestDupes;
);
Al igual que con @Craige_Hales ' publicado en la entrada de blog anterior, intenté implementar el enfoque anterior utilizando la coincidencia de patrones. Sorprendentemente, los resultados tardaron entre cinco y seis veces más. No estoy seguro exactamente por qué, pero mi corazonada es que (como se ilustró la última vez) Contiene es mucho más rápido cuando el duplicado de la subcadena ocurre con menos frecuencia.
Podríamos hacer que las cosas fueran más rápidas aprovechando el buscador de duplicados integrado de JMP, el Resumen plataforma de mesa. Una ventaja de este enfoque es que podemos comenzar con cualquier longitud de subcadena. ¿Cómo debe construir las subcadenas? Se pueden encontrar dos soluciones en la publicación del blog del mes pasado. El primero atomiza e itera sobre la cadena de entrada.
parts = Items(inString,"");
nInds = Length(inString) - subStringLen + 1;
stringList = {};
For(i=1,i<=nInds,i++,
Insert Into(stringList,Concat Items(parts[i::(i + subStringLen - 1)],""))
);
dónde enCadena es la cadena de entrada y subStringLen es la longitud de las subcadenas que se están construyendo. Se puede implementar un enfoque no iterativo usando expresiones:
parts = Items(inString,"");
nInds = Length(inString) - subStringLen + 1;
stringList = {};
i=1;
stringList[1::nInds] = Expr(Concat Items(parts[i::(i++ + subStringLen - 1)],""));
stringList = Eval List(stringList);
o coincidencia de patrones
stringList = {};
Pat Match(inString, Pat Len(subStringLen) >> nextWord+Pat Test(Insert Into(stringList,nextWord);0));
Para probar la velocidad de cada enfoque, construí subcadenas de tamaño 4, 9, 15 y 21 en una cadena de entrada de 1 000 000 de caracteres compuesta por cuatro caracteres generados aleatoriamente. Se corrieron diez iteraciones en cada longitud. Los resultados a continuación muestran la superioridad de la coincidencia de patrones. Los resultados completos se pueden encontrar en Subcadenas de compilación de prueba.JMP .
Algoritmo
|
Tiempos de construcción de longitud de cadena (seg)
|
4
|
9
|
15
|
21
|
Expresiones
|
6.91
|
7.35
|
8.19
|
9.01
|
Bucle
|
2.56
|
2.98
|
3.62
|
4.26
|
La coincidencia de patrones
|
1.09
|
1.12
|
1.10
|
1.11
|
Se realizó un ANOVA que mostró una diferencia estadística (p << 0,001) para el algoritmo, la longitud de la cadena y la interacción algoritmo x longitud de la cadena. Las pruebas post hoc con HSD de Tukey indicaron que no había diferencia estadística entre los niveles de longitud de cadena para el algoritmo de coincidencia de patrones. Para ver cómo funcionaba este método con un conjunto de caracteres más grande, se ejecutó una prueba con una cadena de 1 000 000 de caracteres construida a partir de 26 caracteres seleccionados al azar. Se ejecutaron veinte repeticiones en las mismas longitudes de subcadena que las anteriores más subcadenas de 2 y 40 caracteres. Si bien hubo diferencias estadísticas, las diferencias prácticas fueron pequeñas.
subcadena
Longitud
|
Tiempo (seg)
|
2
|
1.11
|
4
|
1.08
|
9
|
1.09
|
15
|
1.11
|
24
|
1.13
|
40
|
1.53
|
Juntar la construcción de subcadenas y la búsqueda de duplicados podría parecerse al código siguiente. Conocer las filas asociadas con los duplicados nos permite identificar su ubicación en la cadena. Esto funcionará a nuestro favor un poco más tarde. Hacer que las mesas sean Privadas acelera ligeramente las operaciones.
stringList = {};
Pat Match(inString, Pat Len(subStringLen) >> nextWord+Pat Test(Insert Into(stringList,nextWord);0));
tmpTbl = New Table("tmp",New Column("tmp",Character,Values(stringList)),Private);
sumTbl = tmpTbl << Summary(Group(:tmp),Private);
dupeLocs = sumTbl << Get Rows Where(:N Rows > 1);
dupes = Column(sumTbl,1)[dupeLocs];
Close(tmpTbl,No Save);
La siguiente tabla proporciona el tiempo de ejecución promedio para una sola iteración basada en 10 ejecuciones con el Covid-19 y 1 000 000 de cadenas de caracteres. Dados los resultados, es fácil ver que el uso exclusivo de este enfoque y sin la optimización del tamaño de la subcadena será problemático a medida que las cadenas y las subcadenas crezcan.
subcadena
Longitud
|
COVID-19
|
1M
|
2
|
0.0517
|
1.68
|
4
|
0.0504
|
4.25
|
9
|
0.1837
|
8.29
|
15
|
0.2226
|
8.63
|
21
|
0.2209
|
8.85
|
40
|
0.2957
|
12.30
|
Incluso con la optimización inicial del tamaño de la subcadena, no podemos predecir cuánta estructura tendrán los datos de entrada. Un mejor enfoque sería emplear una estrategia híbrida. Usar Resumen para identificar duplicados de un tamaño dado, luego, usando solo estos duplicados, encuentre los duplicados más largos que se pueden construir a partir de ellos. Esto funcionará, ya que una subcadena de los duplicados más largos debe aparecer en el conjunto de duplicados creados a partir de una subcadena más corta. Hay varios enfoques posibles. Elijo un enfoque análogo, pero diferente del método final que se discutirá. Para ser honesto, vi el método final antes de idear este enfoque y, sin duda, me influyó mucho. El desafío del enfoque que elegí fue crear una estructura de datos para realizar un seguimiento de las posiciones originales de las subcadenas. El código es sorprendentemente corto, alrededor de 50 líneas con espacios generosos. Se tarda aproximadamente 0,32 segundos en encontrar todos los duplicados en los datos de Covid-19 y 13 segundos para la cadena de 1 000 000 de caracteres. El código se puede encontrar en findLangestDupe (Resumen).JSL .
Resumen se utiliza para encontrar los duplicados en cada iteración. Si bien esto es lento para tablas grandes, solo necesitamos crear tablas tan grandes como la cantidad de duplicados del paso anterior. Comenzando con una longitud de subcadena de un carácter más allá de la longitud mínima para garantizar los duplicados, es probable que el número total de duplicados disminuya, si no inmediatamente, muy rápidamente. Si la cantidad de filas en las pocas iteraciones no es demasiado grande, este método se puede usar sin más optimización, como comenzar con subcadenas más largas. Una ventaja de estos métodos es que se puede utilizar una optimización adicional en estas situaciones. La indexación utilizada para realizar un seguimiento de las posiciones iniciales de las cadenas funciona de una manera que podría emplearse con una matriz asociativa, que es lo que se utiliza en el método final que se analiza. Comience por encontrar las ubicaciones de las cadenas duplicadas de longitud inicial y guárdelas en una matriz temporal. Cree cadenas un carácter más largas a partir de estas ubicaciones y asegúrese de eliminar cualquier cadena que exceda los límites de la cadena de entrada. Encuentre las ubicaciones de las cadenas duplicadas en esta lista. Podemos vincular estos nuevos índices a la ubicación original usándolos como índices de la matriz previamente guardada, manteniendo solo aquellos elementos que tienen índices. Reemplace la matriz anterior con esta. Continúe hasta que no queden duplicados, momento en el cual la matriz anterior contiene las ubicaciones de los duplicados más largos.
Como se mencionó anteriormente, el método final es similar en sabor al anterior. La idea de este enfoque es gracias a @brady_brady . Hay algunas diferencias importantes. Primero, construye todas las subcadenas desde un carácter hacia arriba. Si bien esto suena ineficiente, al usar matrices asociativas e indexar los caracteres de cadena individuales mediante matrices, se elimina la búsqueda directa de la cadena y se evitan combinaciones de caracteres que no existen. En general, supera al método anterior cuando el conjunto de caracteres y la cadena de entrada aumentan. Se realizaron diez ejecuciones para varios tamaños de cadena de entrada (50K - 2,5M) y conjuntos de caracteres (4 a 72) para comparar los dos enfoques. Los tiempos medios de ejecución se muestran a continuación para el método de resumen (1) y el método de matriz asociativa (2). Los resultados completos se pueden encontrar en Comparar métodos más rápidos.JMP.
|
50K
|
100K
|
500K
|
1M
|
2,5 millones
|
Tamaño del conjunto de caracteres
|
1
|
2
|
1
|
2
|
1
|
2
|
1
|
2
|
1
|
2
|
4
|
0.5087
|
0.5814
|
0.9081
|
1.2664
|
5.421
|
6.813
|
13.412
|
13.778
|
32.23
|
35.67
|
10
|
0.2724
|
0.4117
|
0.6251
|
0.9207
|
2.850
|
4.509
|
6.998
|
9.503
|
13.61
|
24.70
|
26
|
0.3098
|
0.3748
|
0.6786
|
0.7441
|
3.625
|
3.981
|
7.363
|
8.537
|
21.68
|
19.58
|
52
|
0.4247
|
0.3265
|
1.0617
|
0.7682
|
4.246
|
4.046
|
9.522
|
7.395
|
30.67
|
18.08
|
72
|
0.3186
|
0.3309
|
0.7308
|
0.7079
|
3.533
|
4.236
|
7.192
|
8.917
|
20.14
|
18.97
|
Al igual que con el método Resumen, este enfoque comienza convirtiendo la cadena de entrada en caracteres individuales. Sin embargo, en lugar de trabajar con los caracteres directamente, se utilizan sus posiciones numéricas tal como aparecen en el juego de caracteres. Esto permite que se produzca la creación de subcadenas mediante operaciones matriciales, que tienden a ser más rápidas que las operaciones de cadenas. Específicamente, la primera iteración toma una representación matricial de cada posición del juego de caracteres como una clave (por ejemplo, [3] para G) a una matriz asociada y usa el vector de sus ubicaciones en la cadena de entrada como su valor. Cada iteración subsiguiente comienza con la creación de una nueva matriz asociativa al encontrar los valores de cadena de entrada en 1 más los valores de vector para cada clave en la matriz anterior, teniendo cuidado de no ir más allá del último elemento de la cadena de entrada. El valor correspondiente al primer elemento del vector incrementado se utiliza para buscar duplicados en el resto de los valores del vector incrementado. Si existen, las posiciones con las que están asociadas se utilizan para el valor en el nuevo elemento de matriz. La clave para este elemento se crea concatenando el valor del conjunto de caracteres del elemento duplicado con la clave original, lo que facilita la recreación de la cadena de caracteres. El valor de búsqueda y sus duplicados, si existen, se eliminan del vector y la búsqueda continúa hasta que no quedan valores. Este proceso de construcción se produce para cada elemento de la matriz anterior. Una vez completada, la nueva matriz asociada reemplaza a la anterior y comienza la siguiente iteración. Esto continúa hasta que no haya nuevas claves para reemplazar la matriz anterior. La matriz anterior contiene los duplicados más largos.
El código de Brady se puede encontrar en findDupe más largo (AA).JSL . He realizado un pequeño ajuste para permitir el uso de diferentes conjuntos de caracteres.
Para la próxima vez pasaremos de cadenas a listas. Como se mencionó en el blog anterior, evitar la iteración ha sido el tema de dos publicaciones recientes de la comunidad que involucran convertir elementos numéricos en caracteres y indexación de listas . Dos retos para la próxima. Se basan en preguntas que surgieron en las publicaciones vinculadas. En ambos casos. Está convirtiendo valores numéricos en cadenas de caracteres.
- Escribe una función que cubra una lista de norte listas (cada una con metro i números). no asumas metro i es el mismo para todas las listas.
- Escribe una función que pueda transponer la lista del elemento 1. He aquí un pequeño ejemplo:
inputList = {{12, 11, 16, 1, 15, ., 23, 8, 16, 17}, {1, 10, ., 4, 25, ., 19, 21, ., 3}, {11, 21,
22, 7, 3, ., 24, 10, 21, 20}, {., ., ., ., ., ., ., ., ., .}, {11, ., 3, ., 9, ., 23,
., 3, 16}};
outputList = {{12, 1, 11, ., 11}, {11, 10, 21, ., .}, {16, ., 22, ., 3}, {1, 4, 7, ., .}, {15, 25,
3, ., 9}, {., ., ., ., .}, {23, 19, 24, ., 23}, {8, 21, 10, ., .}, {16, ., 21, ., 3},
{17, 3, 20, ., 16}}
¡Buena suerte!
Esta es una manera de abordar el desafío. Decidí "No asumas mi es el mismo para todas las listas", lo que significaba que es posible que las listas cruzadas deban rellenarse con valores faltantes. Repetir({.},10) produce {.,.,.,.,.,.,.,.,.,.}. Insert() agrega los elementos de la lista, no la lista (ver Cómo insertar una lista en otra lista .)
inputList = {
{12, 11, 16, 1, 15, ., 23, 8, 16, 17},
{1, 10, ., 4, 25, ., 19, 21, ., 3},
{11, 21, 22, 7, 3, ., 24, 10, 21, 20},
{1}, // odd across-list
{., ., ., ., ., ., ., ., ., .},
{11, ., 3, ., 9, ., 23, ., 3, 16}};
// find rows and max cols of input:
nrows = N Items( inputList );
ncols = 0;
For( irow = 1, irow <= nrows, irow += 1,
ncols = Max( ncols, N Items( inputList[irow] ) )
);
// if the across-lists are not all the same size, add missing values
For( irow = 1, irow <= nrows, irow += 1,
If( ncols > N Items( inputList[irow] ),
Insert Into( inputList[irow], Repeat( {.}, ncols - N Items( inputList[irow] ), . ) )
)
);
// make a table of numbers from the lists
dt = New Table( "temp", invisible, Add Rows( nrows ), <<ADD multiple="" columns=""></ADD>Este JSL crea una tabla de datos que faltan con suficientes filas y columnas numéricas para contener los valores numéricos en la lista. El subíndice de la tabla de datos no está satisfecho con las filas de longitud desigual y no está satisfecho con la conversión de números a caracteres durante la asignación. La conversión se realiza casi al final enviando el mensaje SetDataType a una lista de columnas (evitando un bucle JSL explícito). La lista transpuesta de números se captura justo antes de eso.
El subíndice de la tabla de datos quiere obtener y configurar a través de una matriz numérica cuando las columnas son todas numéricas, pero felizmente se configurará a partir de una lista de listas de números. Dado que get devolverá una matriz, pero el requisito del problema es devolver una lista transpuesta de números, AsList() hace el trabajo de convertir la matriz (de la tabla de datos) nuevamente en una lista.
