Mathematica的MemberQ

Question

我有点不知道如何在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}]

预期产出是:

{False, True, False, True, False}

我的名单a,并b都大了,所以数学是线性搜索,通过做kazillion b.我希望它使用哈希表进行更快的查找.但似乎没有这样的结构.我能找到的最接近的是SparseArray,但是

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

是False.

我确信在一行代码或更少的代码中,这在Mathematica中一定是可能的,我只是看不到树木或其他东西.

救援的任何英雄？同时,我打算用C#做这件事.

Answer 1

以下问题与您的问题相同,并在Mathematica中包含答案:

/sf/ask/136824551/

这是答案(我可以随意窃取,因为它实际上是我的):

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

我们的想法是创建一个哈希表f,它可以在恒定时间内回答给定元素是否是列表b的成员.第一个f的默认值为False(如果我们在它不在b之前没有看到它).然后进行单次通过列表b,将b中的每个i的f [i]设置为True.这就是所有的设置.现在,对列表a的哈希函数f的单次传递给出了答案.总时间为O(n + m) - 每个列表通过一次.

Answer 2

另一个想法是使用规则和Dispatch.当blist的长度很大时似乎更快:

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;
]

在我的笔记本电脑上,规则(0.06s)<fct(0.09s)<稀疏(0.9s)<membQ(40s).

编辑/比较fct和规则时间

@Karsten请随时回滚到原来的答案

用Prime生成的表[...]

使用RandomInteger生成的表[...]