MemberQ en Mathematica

estoy un poco en una pérdida de cómo hacer lo siguiente de manera eficiente en Mathematica:MemberQ en Mathematica

a = { 1, 2, 3, 4, 5 }; (* list of integers *) 
b = { 2, 4, 6, 8 };  (* another list of integers *) 
filter = Table[MemberQ[b, element], {element,a}]

salida esperada es:

{False, True, False, True, False}

Mis listas a y b son grandes, por lo que Mathematica está haciendo un kazillion búsquedas lineales a través de b. Quiero que haga búsquedas más rápidas con una tabla hash. Pero parece que no hay tal estructura. Lo más cerca que pude encontrar es una SparseArray, pero

sa = SparseArray[{1 -> True, 2 -> True}]; 
MemberQ[sa, 1]

es False.

Estoy seguro de que esto debe ser posible en Mathematica en una línea de código o menos, simplemente no puedo verlo por los árboles, o algo así.

¿Algún héroe al rescate? Mientras tanto, voy a hacer esto con C#.

Fuente

2010-09-12 Gleno

Otra idea sería usar las reglas y Dispatch. Parece que es más rápido cuando la longitud de la blist es grande:

alist = Prime /@ Range[20000]; 
blist = alist + 2; 

membQ = [email protected][MemberQ[blist,#]&/@alist;] 

sparse = [email protected][ 
    s = SparseArray[blist -> ConstantArray[True, [email protected]], Max[alist, blist], False]; 
    s[[#]] & /@ alist; 
] 

rules = [email protected][ 
    bRules = Dispatch[Append[Rule[#, True] & /@ blist, _ -> False]]; 
    (# /. bRules) & /@ alist; 
] 

fct = [email protected][ 
    f[_] = False; 
    (f[#] = True) & /@ blist; 
    f /@ alist; 
]

En mi portátil, reglas (0.06s) < FCT (0,09 s) < escasa (0,9 segundos) < membQ (40).

Editar/Comparación de FCT y reglas tiempos

@Karsten no dude en revertir a su respuesta original

Cuadros producidos con el primer [...]

alt text

Tablas generadas con RandomInteger [...]

alt text

Fuente

2010-09-13 06:02:11

Gracias por hacer la comparación de tiempos. Creo que mereces una Respuesta Aceptada por eso incluso si no tuviste la respuesta más rápida. Pero sobre eso, el .06 vs .09 no es convincente. ¿Quieres probarlo con un orden de magnitud mayor para asegurarte de que aguanta? – dreeves

Cuál es mejor, parece depender de alist y blist, también. Con alist y blist establecidos en RandomInteger [** 100000 **, 800000], la solución Dispatch es con 5.2s mejor que la solución funcional (5.4), mientras que en RandomInteger [** 10000 **, 800000] la solución funcional es más rápida (5.3s contra 5.7s). La solución dispersa emite mensajes de error, que no examiné. –

Le volví a adjudicar la respuesta aceptada, porque dreeves la solicitó. Gracias por las comparaciones de tiempo, me siento un poco inquieto desperdiciando el tiempo de la gente así. :) – Gleno

El filter construido por búsqueda lineal se puede simplificar a:

MemberQ[b, #]& /@ a

De todos modos, se puede construir una matriz dispersa de b por:

s = SparseArray[b -> ConstantArray[True, [email protected]], Max[a, b], False];

a continuación para los índices i en la matriz dispersa, s[[i]] devolverá True y, para los que estén fuera, s[[i]] devolverá False. Por lo que la lista puede ser construido con

s[[#]]& /@ a

Podemos comparar los resultados:

In[130]:= alist = Prime /@ Range[2000]; 
      blist = alist + 2; 

In[165]:= Timing[MemberQ[blist, #]& /@ alist;] 

Out[165]= {0.91024,Null} 

In[168]:= Timing[ 
      s = SparseArray[blist -> ConstantArray[True, [email protected]], 
          Max[alist, blist], False]; 
      s[[#]]& /@ alist;] 

Out[168]= {0.017772,Null}

Fuente

2010-09-12 19:26:11 kennytm

En cuanto a su primera frase, probablemente el autor de la pregunta sólo significaba MemberQ [b, elemento] en lugar de MemberQ [elemento, b]. No quiere decir que tu versión no es mejor. – dreeves

@dreeves: en realidad estoy hablando de la parte 'Table [..., {element, a}]'. Los argumentos de MemberQ son algo menor. – kennytm

Pero no hay nada de malo en la parte Table [..., {element, a}] (excepto tal vez que no es tan eficiente/elegante como su versión basada en mapas). Para eliminar cualquier ambigüedad acerca de esto, creo que voy a seguir adelante y corregir el error tipográfico en la pregunta para que pueda ejecutar el ejemplo del asker. [Hecho; también se agregó la producción esperada.] – dreeves

La siguiente pregunta es equivalente a la suya y contiene una respuesta en Mathematica:

https://stackoverflow.com/questions/1954636/given-list-subset-of-list-return-bitmask

Aquí está la respuesta (que me siento libre de robar, ya que es en realidad la mía):

bitmask[a_, b_] := Module[{f}, 
    f[_] = False; 
    (f[#] = True)& /@ b; 
    f /@ a]

La idea es crear una tabla hash, f, que pueda responder en tiempo constante si un elemento determinado es miembro de la lista b. Primero f tiene un valor predeterminado de False (si no lo hemos visto antes no está en b). Luego se realiza una única pasada a través de la lista b, estableciendo f [i] en True para cada i en b. Eso es todo lo establecido. Ahora, una sola pasada de la función hash f sobre la lista a nos da la respuesta. El tiempo total es O (n + m): una pasada por cada lista.

Fuente

2010-09-12 20:29:43 dreeves

Gracias a un millón, funciona como un encanto. ¿Dónde aprendes los matices sutiles de la coincidencia de patrones de todos modos? Por ejemplo, cómo sabes que es aproximadamente O (1) vez, etc. Lo único que realmente no me gusta de la matemática es que, aunque se supone que es matemática, casi nunca enumera las complejidades. – Gleno

@Gleno Creo que su comentario es una muy buena semilla para otra pregunta :) –

@dreeves ¡Muy elegante! +1 –

Respuesta

Cuestiones relacionadas