MemberQ in Mathematica

Question

Io sono un po 'in perdita come effettuare le seguenti operazioni in modo efficiente in 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}] 

risultato atteso è:

{False, True, False, True, False} 

mie liste a e b sono grandi, così Mathematica sta facendo ricerche kazillion lineari attraverso b. Voglio che faccia ricerche più veloci con una tabella hash. Ma sembra che non ci sia una tale struttura. Il più vicino che ho trovato è uno SparseArray, ma

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

è False.

Sono sicuro che questo deve essere possibile in Mathematica in una riga di codice o meno, non riesco a vederlo per gli alberi, o qualcosa del genere.

Qualsiasi eroe in soccorso? Nel frattempo, lo farò con C#.

Answer 1

Un'altra idea sarebbe utilizzare le regole e Dispatch. Sembra essere più veloce quando la lunghezza del blist è grande:

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

membQ = First@Timing[MemberQ[blist,#]&/@alist;] 

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

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

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

Sul mio computer portatile, le regole (0.06s) < FCT (0.09s) < sparse (0.9s) < membQ (anni '40).

Modifica/Confronto FCT e regole tempi

@Karsten non esitate a rollback alla tua risposta originale

tabelle generate con il primo [...]

Tabelle generate con RandomInteger [...]

Answer 2

Il filter costruito da ricerca lineare può essere semplificata:

MemberQ[b, #]& /@ a 

Comunque, si potrebbe costruire un array sparso da b da:

s = SparseArray[b -> ConstantArray[True, Length@b], Max[a, b], False]; 

poi per indici i nella matrice sparsa, s[[i]] restituirà True e per quelli esterni, s[[i]] restituirà False. Così la lista può essere costruito con

s[[#]]& /@ a 

Possiamo paragonare i risultati:

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, Length@blist], 
          Max[alist, blist], False]; 
      s[[#]]& /@ alist;] 

Out[168]= {0.017772,Null} 

Answer 3

La domanda è equivalente al tuo e contiene una risposta in Mathematica:

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

Ecco la risposta (che riterrò libera di rubare poiché è in realtà la mia):

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

L'idea è di creare una tabella hash, f, che possa rispondere in tempo costante se un dato elemento è un membro della lista b. Prima viene assegnato un valore predefinito di False (se non lo abbiamo visto prima non è in b). Quindi viene eseguito un singolo passaggio nell'elenco b, impostando f [i] su True per ogni i in b. Questo è tutto il set up. Ora una singola passata della funzione hash f sulla lista a ci dà la risposta. Il tempo totale è O (n + m) - un passaggio per ciascuna lista.