Gracias a las personas que probaron el Desafío 7. Con suerte, incluso si no tuviste la oportunidad, has estado siguiendo las discusiones. ¿Cómo podemos resolver este desafío? Conceptualmente, el enfoque más simple sería encontrar duplicados de un solo carácter, luego duplicados de dos caracteres, tres caracteres, etc., aumentando en un carácter hasta que no hubiera duplicados. Verificar ingenuamente 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 se garantiza que tendremos 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. Para que este enfoque funcione, se debe encontrar un método eficaz para identificar duplicados. 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, hazlo crecer un carácter a la vez hasta que no quede ningún duplicado. Pase al siguiente carácter y a 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 realizar un duplicado. En el genoma del Covid-19, una subcadena de ocho caracteres ATTAAAGG Se puede construir a partir del primer carácter. Pasando al segundo carácter, una cadena de 11 caracteres TTAAAGTTTA mirando a la posición 2 tiene un duplicado en la posición 20063. No hay duplicados de 11 caracteres o más que comiencen en la posición 3, por lo que pasamos a la posición 4. Etcétera. El siguiente código necesita unos 5 segundos para encontrar la cadena duplicada más larga, dos cadenas superpuestas de 32 caracteres. A s. Tenga en cuenta que en el código siguiente, 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 disminuirse 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 anterior del blog, 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 de 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 vayan más rápido 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 deberías 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 en cadena es la cadena de entrada y subcadenaLen es la longitud de las subcadenas que se están construyendo. Se puede implementar un enfoque no iterativo utilizando 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 de longitud compuesta por cuatro caracteres generados aleatoriamente. Se ejecutaron 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 cuerda (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 muestra 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 utilizando el HSD de Tukey indicaron que no había diferencias estadísticas entre los niveles de longitud de las cadenas para el algoritmo de coincidencia de patrones. Para ver cómo funciona 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 subcadenas 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 (segundos)
|
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 nos beneficiará un poco más tarde. Hacer que las tablas 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 única iteración basada en 10 ejecuciones utilizando Covid-19 y 1.000.000 de cadenas de caracteres. Dados los resultados, es fácil ver que usar este enfoque exclusivamente y sin optimización del tamaño de las subcadenas 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 o poca 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 determinado, luego, utilizando solo estos duplicados, encuentre los duplicados más largos que se puedan 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, al 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 de las subcadenas originales. El código es sorprendentemente corto, alrededor de 50 líneas con espacios generosos. Se necesitan aproximadamente 0,32 segundos para 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 findLongestDupe (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 duplicados, es probable que el número total de duplicados disminuya, si no inmediatamente, sí muy rápidamente. Si el número de filas en las pocas iteraciones no es demasiado grande, este método se puede utilizar sin optimización adicional, 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 la misma manera que podría emplearse con una matriz asociativa, que es lo que se utiliza en el método final que analizaremos. Comience por encontrar las ubicaciones de las cadenas duplicadas de longitud inicial y guárdelas en una matriz temporal. Cree cadenas de 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 que 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 en adelante. Si bien esto suena ineficiente, al usar matrices asociativas e indexar los caracteres de cadena individuales usando 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 crecen. Se realizaron diez ejecuciones para varios tamaños de cadenas de entrada (50K – 2,5M) y conjuntos de caracteres (4 a 72) para comparar los dos enfoques. Los tiempos de ejecución medios se muestran a continuación para el método Resumen (1) y el método 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 conjunto 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 conjunto de caracteres como clave (por ejemplo, [3] para G) a una matriz asociada y utiliza el vector de sus ubicaciones en la cadena de entrada como su valor. Cada iteración posterior comienza construyendo una nueva matriz asociativa buscando los valores de la cadena de entrada en 1 más los valores vectoriales 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 a las que están asociadas se utilizan para el valor del nuevo elemento de matriz. La clave para este elemento se construye 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 ocurre 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 encontrarLongestDupe (AA).JSL . He realizado un pequeño ajuste para permitir el uso de diferentes conjuntos de caracteres.
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 vez. 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 convierta 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!
He aquí una forma de afrontar el desafío. Decidí "No asumas mi es el mismo para todas las listas" significaba que las listas entre listas podrían necesitar ser rellenadas 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 faltantes con suficientes filas y columnas numéricas para contener los valores numéricos en la lista. La subíndice de la tabla de datos no está contenta con las filas de longitud desigual y no está contenta con la conversión de números a caracteres durante la asignación. La conversión se realiza cerca del 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 todas las columnas son 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.
