wolfram-mathematica - valor - sustituir variables mathematica
Una implementación rápida en Mathematica para Position2D (4)
Estoy buscando una implementación rápida para lo siguiente, lo llamaré Position2D por falta de un término mejor:
Position2D[ matrix, sub_matrix ]
que encuentra las ubicaciones de sub_matrix dentro de la matrix y devuelve la fila / columna superior izquierda y derecha de una coincidencia.
Por ejemplo, esto:
Position2D[{
{0, 1, 2, 3},
{1, 2, 3, 4},
{2, 3, 4, 5},
{3, 4, 5, 6}
}, {
{2, 3},
{3, 4}
}]
debe devolver esto:
{
{{1, 3}, {2, 4}},
{{2, 2}, {3, 3}},
{{3, 1}, {4, 2}}
}
Debería ser lo suficientemente rápido para trabajar rápidamente en matrices de 3000x2000 con 100x100 . Para simplificar, es suficiente considerar solo matrices de enteros.
Algoritmo
El siguiente código se basa en una función de posición personalizada eficiente para encontrar posiciones de secuencias enteras (posiblemente superpuestas) en una lista de enteros grande. La idea principal es que primero podemos tratar de encontrar eficientemente las posiciones donde la primera fila de la submatriz se encuentra en la matriz grande aplanada, y luego filtrarlas, extraer las submatrices completas y compararlas con la submatriz de interesar. Esto será eficiente para la mayoría de los casos, excepto los muy patológicos (aquellos, para los cuales este procedimiento generaría un gran número de posibles candidatos a la posición, mientras que el verdadero número de entradas de la submatriz sería mucho menor. Pero tales casos parecen bastante poco probables en general, y luego, se pueden hacer mejoras adicionales a este esquema simple).
Para matrices grandes, la solución propuesta será aproximadamente 15-25 veces más rápida que la solución de @Szabolcs cuando se use una versión compilada de la función de posiciones de secuencia, y 3-5 veces más rápida para la implementación de las posiciones de secuencia en el nivel superior. . La aceleración real depende de los tamaños de matriz, es más para matrices más grandes. El código y los puntos de referencia están a continuación.
Código
Una función generalmente eficiente para encontrar posiciones de una sub-lista (secuencia)
Estas funciones de ayuda se deben a Norbert Pozar y se toman de this hilo de Mathgroup. Se utilizan para encontrar de manera eficiente las posiciones de inicio de una secuencia de enteros en una lista más grande (consulte la publicación mencionada para obtener más detalles).
Clear[seqPos];
fdz[v_] := Rest@DeleteDuplicates@Prepend[v, 0];
seqPos[list_List, seq_List] :=
Fold[
fdz[#1 (1 - Unitize[list[[#1]] - #2])] + 1 &,
fdz[Range[Length[list] - Length[seq] + 1] *
(1 - Unitize[list[[;; -Length[seq]]] - seq[[1]]])] + 1,
Rest@seq
] - Length[seq];
Ejemplo de uso:
In[71]:= seqPos[{1,2,3,2,3,2,3,4},{2,3,2}]
Out[71]= {2,4}
Una función de búsqueda de posición más rápida para enteros
Por muy rápidos que puedan ser los seqPos , sigue siendo el principal cuello de botella en mi solución. Aquí hay una versión compilada a C de esto, que le da otra mejora de rendimiento 5x a mi código:
seqposC =
Compile[{{list, _Integer, 1}, {seq, _Integer, 1}},
Module[{i = 1, j = 1, res = Table[0, {Length[list]}], ctr = 0},
For[i = 1, i <= Length[list], i++,
If[list[[i]] == seq[[1]],
While[j < Length[seq] && i + j <= Length[list] &&
list[[i + j]] == seq[[j + 1]],
j++
];
If[j == Length[seq], res[[++ctr]] = i];
j = 1;
]
];
Take[res, ctr]
], CompilationTarget -> "C", RuntimeOptions -> "Speed"]
Ejemplo de uso:
In[72]:= seqposC[{1, 2, 3, 2, 3, 2, 3, 4}, {2, 3, 2}]
Out[72]= {2, 4}
Los puntos de referencia a continuación se han rehecho con esta función (también el código para la función principal está ligeramente modificado)
Función principal
Esta es la función principal. Encuentra las posiciones de la primera fila en una matriz, y luego las filtra, extrae las submatrices en estas posiciones y las compara con la submatriz de interés completa:
Clear[Position2D];
Position2D[m_, what_,seqposF_:Automatic] :=
Module[{posFlat, pos2D,sp = If[seqposF === Automatic,seqposC,seqposF]},
With[{dm = Dimensions[m], dwr = Reverse@Dimensions[what]},
posFlat = sp[Flatten@m, First@what];
pos2D =
Pick[Transpose[#], Total[Clip[Reverse@dm - # - dwr + 2, {0, 1}]],2] &@
{Mod[posFlat, #, 1], IntegerPart[posFlat/#] + 1} &@Last[dm];
Transpose[{#, Transpose[Transpose[#] + dwr - 1]}] &@
Select[pos2D,
m[[Last@# ;; Last@# + Last@dwr - 1,
First@# ;; First@# + First@dwr - 1]] == what &
]
]
];
Para las listas de enteros, se puede utilizar la función de búsqueda de posición de subsecuencias más rápida compilada seqposC (esto es un valor predeterminado). Para listas genéricas, uno puede proporcionar, por ejemplo, seqPos , como un tercer argumento.
Cómo funciona
Usaremos un ejemplo simple para analizar el código y explicar su funcionamiento interno. Esto define nuestra matriz de prueba y sub-matriz:
m = {{0, 1, 2, 3}, {1, 2, 3, 4}, {2, 3, 4, 5}};
what = {{2, 3}, {3, 4}};
Esto calcula las dimensiones de lo anterior (es más conveniente trabajar con dimensiones invertidas para una sub-matriz):
In[78]:=
dm=Dimensions[m]
dwr=Reverse@Dimensions[what]
Out[78]= {3,4}
Out[79]= {2,2}
Esto encuentra una lista de las posiciones iniciales de la primera fila ( {2,3} aquí) en la matriz principal Aplanada. Estas posiciones son al mismo tiempo posiciones candidatas "planas" de la esquina superior izquierda de la sub-matriz:
In[77]:= posFlat = seqPos[Flatten@m, First@what]
Out[77]= {3, 6, 9}
Esto reconstruirá las posiciones 2D "candidatas" de la esquina superior izquierda de una submatriz en una matriz completa, utilizando las dimensiones de la matriz principal:
In[83]:= posInterm = Transpose@{Mod[posFlat,#,1],IntegerPart[posFlat/#]+1}&@Last[dm]
Out[83]= {{3,1},{2,2},{1,3}}
Luego podemos intentar usar Select para filtrarlos, extraer la matriz parcial completa y comparar con what , pero nos encontraremos con un problema aquí:
In[84]:=
Select[posInterm,
m[[Last@#;;Last@#+Last@dwr-1,First@#;;First@#+First@dwr-1]]==what&]
During evaluation of In[84]:= Part::take: Cannot take positions 3 through 4
in {{0,1,2,3},{1,2,3,4},{2,3,4,5}}. >>
Out[84]= {{3,1},{2,2}}
Aparte del mensaje de error, el resultado es correcto. El mensaje de error en sí se debe al hecho de que para la última posición ( {1,3} ) en la lista, la esquina inferior derecha de la sub-matriz estará fuera de la matriz principal. Por supuesto, podríamos usar Quiet para simplemente ignorar los mensajes de error, pero ese es un mal estilo. Entonces, primero filtraremos esos casos, y esto es lo que la línea Pick[Transpose[#], Total[Clip[Reverse@dm - # - dwr + 2, {0, 1}]], 2] &@ is para. Específicamente, considere
In[90]:=
Reverse@dm - # - dwr + 2 &@{Mod[posFlat, #, 1],IntegerPart[posFlat/#] + 1} &@Last[dm]
Out[90]= {{1,2,3},{2,1,0}}
Las coordenadas de las esquinas superiores izquierda deben permanecer dentro de una diferencia de dimensiones de matriz y una submatriz. Las sublistas anteriores se hicieron de coordenadas x e y esquinas superior izquierda. Agregué 2 para que todos los resultados válidos sean estrictamente positivos. Tenemos que seleccionar solo coordenadas en esas posiciones en Transpose@{Mod[posFlat, #, 1], IntegerPart[posFlat/#] + 1} &@Last[dm] (que es posInterm ), en la que ambas sublistas anteriores tienen números estrictamente positivos. Utilicé Total[Clip[...,{0,1}]] para modificarlo en la selección solo en las posiciones en las que esta segunda lista tiene 2 (el Clip convierte todos los enteros positivos en 1 y los números de las sumas Total en 2 sublistas). La única forma de obtener 2 es cuando los números en ambas sublistas son positivos).
Entonces tenemos:
In[92]:=
pos2D=Pick[Transpose[#],Total[Clip[Reverse@dm-#-dwr+2,{0,1}]],2]&@
{Mod[posFlat,#,1],IntegerPart[posFlat/#]+1}&@Last[dm]
Out[92]= {{3,1},{2,2}}
Después de que la lista de posiciones 2D se haya filtrado, de modo que no haya posiciones estructuralmente no válidas, podemos utilizar Select para extraer las submatrices completas y compararlas con la submatriz de interés:
In[93]:=
finalPos =
Select[pos2D,m[[Last@#;;Last@#+Last@dwr-1,First@#;;First@#+First@dwr-1]]==what&]
Out[93]= {{3,1},{2,2}}
En este caso, ambas posiciones son genuinas. Lo último que hay que hacer es reconstruir las posiciones de las esquinas inferior derecha de la submatriz y agregarlas a las posiciones de la esquina superior izquierda. Esto se hace por esta línea:
In[94]:= Transpose[{#,Transpose[Transpose[#]+dwr-1]}]&@finalPos
Out[94]= {{{3,1},{4,2}},{{2,2},{3,3}}}
Podría haber usado Map , pero para una gran lista de posiciones, el código anterior sería más eficiente.
Ejemplo y puntos de referencia
El ejemplo original:
In[216]:= Position2D[{{0,1,2,3},{1,2,3,4},{2,3,4,5},{3,4,5,6}},{{2,3},{3,4}}]
Out[216]= {{{3,1},{4,2}},{{2,2},{3,3}},{{1,3},{2,4}}}
Tenga en cuenta que mis convenciones de índice están invertidas con la solución de @Szabolcs.
Puntos de referencia para grandes matrices y submatrices
Aquí hay una prueba de potencia:
nmat = 1000;
(* generate a large random matrix and a sub-matrix *)
largeTestMat = RandomInteger[100, {2000, 3000}];
what = RandomInteger[10, {100, 100}];
(* generate upper left random positions where to insert the submatrix *)
rposx = RandomInteger[{1,Last@Dimensions[largeTestMat] - Last@Dimensions[what] + 1}, nmat];
rposy = RandomInteger[{1,First@Dimensions[largeTestMat] - First@Dimensions[what] + 1},nmat];
(* insert the submatrix nmat times *)
With[{dwr = Reverse@Dimensions[what]},
Do[largeTestMat[[Last@p ;; Last@p + Last@dwr - 1,
First@p ;; First@p + First@dwr - 1]] = what,
{p,Transpose[{rposx, rposy}]}]]
Ahora, probamos:
In[358]:= (ps1 = position2D[largeTestMat,what])//Short//Timing
Out[358]= {1.39,{{{1,2461},{100,2560}},<<151>>,{{1900,42},{1999,141}}}}
In[359]:= (ps2 = Position2D[largeTestMat,what])//Short//Timing
Out[359]= {0.062,{{{2461,1},{2560,100}},<<151>>,{{42,1900},{141,1999}}}}
(el número real de submatrices es más pequeño que el número que intentamos generar, ya que muchos de ellos se superponen y "destruyen" los que se insertaron anteriormente; esto es así porque el tamaño de la submatriz es una fracción considerable del tamaño de la matriz en nuestro punto de referencia).
Para comparar, debemos invertir los índices xy en una de las soluciones (nivel 3) y ordenar ambas listas, ya que las posiciones pueden haberse obtenido en un orden diferente:
In[360]:= Sort@ps1===Sort[Reverse[ps2,{3}]]
Out[360]= True
No excluyo la posibilidad de que sean posibles otras optimizaciones.
Esta es mi implementación:
position2D[m_, k_] :=
Module[{di, dj, extractSubmatrix, pos},
{di, dj} = Dimensions[k] - 1;
extractSubmatrix[{i_, j_}] := m[[i ;; i + di, j ;; j + dj]];
pos = Position[ListCorrelate[k, m], ListCorrelate[k, k][[1, 1]]];
pos = Select[pos, extractSubmatrix[#] == k &];
{#, # + {di, dj}} & /@ pos
]
Utiliza ListCorrelate para obtener una lista de posibles posiciones, luego filtra aquellas que realmente coinciden. Probablemente sea más rápido en matrices reales empaquetadas.
Que tal algo como
Position2D[bigMat_?MatrixQ, smallMat_?MatrixQ] :=
Module[{pos, sdim = Dimensions[smallMat] - 1},
pos = Position[bigMat, smallMat[[1, 1]]];
Quiet[Select[pos, (MatchQ[
bigMat[[Sequence@@Thread[Span[#, # + sdim]]]], smallMat] &)],
Part::take]]
que devolverá las posiciones superiores a la izquierda de las submatrices. Ejemplo:
Position2D[{{0, 1, 2, 3}, {1, 2, 3, 4}, {2, 3, 4, 5}, {3, 5, 5, 6}},
{{2, 3}, {3, _}}]
(* Returns: {{1, 3}, {2, 2}, {3, 1}} *)
Y para buscar una matriz de 1000x1000, toma aproximadamente 2 segundos en mi máquina anterior
SeedRandom[1]
big = RandomInteger[{0, 10}, {1000, 1000}];
Position2D[big, {{1, 1, _}, {1, 1, 1}}] // Timing
(* {1.88012, {{155, 91}, {295, 709}, {685, 661},
{818, 568}, {924, 45}, {981, 613}}} *)
Según la sugerencia de Leonid, aquí está mi solución. Sé que no es muy eficiente (es aproximadamente 600 veces más lento que el de Leonid cuando lo programé) pero es muy breve, recordable y una buena ilustración de una función que se usa raramente, PartitionMap . Es del paquete de Desarrollador, por lo que necesita una llamada de Needs["Developer`"] primero.
Dado que, Position2D se puede definir como:
Position2D[m_, k_] := Position[PartitionMap[k == # &, m, Dimensions[k], {1, 1}], True]
Esto solo da las coordenadas superiores izquierda. Siento que las coordenadas de la parte inferior derecha son realmente redundantes, ya que las dimensiones de la submatriz son conocidas, pero si surge la necesidad, se pueden agregar esas a la salida al anteponer {#, Dimensions[k] + # - {1, 1}} & /@ a la definición anterior.