MemberQ в Mathematica

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 большие, поэтому Mathematica выполняет казиллионный линейный поиск по b. Я хочу, чтобы он быстрее выполнял поиск с помощью хеш-таблицы. Но, похоже, такой структуры не существует. Самый близкий, который я мог найти, это SparseArray, но

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

- это False.

Я уверен, что в Mathematica это должно быть возможно в одной строке кода или меньше, я просто не вижу это для деревьев или чего-то еще.

Любой герой на помощь? Тем временем я собираюсь сделать это с C #.

Answer 1

Следующий вопрос эквивалентен вашему и содержит ответ в Mathematica:

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

Вот этот ответ (который я смогу украсть, поскольку он на самом деле мой):

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

Идея состоит в том, чтобы создать хеш-таблицу f, которая в постоянное время может ответить, является ли данный элемент членом списка b. Сначала для f задано значение по умолчанию False (если мы не видели его раньше, его нет в b). Затем делается один проход по списку b, устанавливая f [i] в ​​True для каждого i в b. Это все готово. Теперь один проход хеш-функции f по списку a дает нам ответ. Общее время O (n + m) - один проход через каждый список.

Answer 2

Другая идея - использовать правила и Dispatch.Кажется, быстрее, когда длина блиста велика:

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,06 с)

Редактирование / Сравнение сроков fct и rules

@ Карстен, пожалуйста, не стесняйтесь откатиться к исходному ответу

Таблицы, созданные с помощью Prime [...]

Таблицы, созданные с помощью RandomInteger [...]

Answer 3

filter, построенный с помощью линейного поиска, может быть упрощен до:

MemberQ[b, #]& /@ a

В любом случае, вы можете построить разреженный массив из b:1008 * в разреженном массиве s[[i]] вернет True, а для тех, кто снаружи, s[[i]] вернет False.Таким образом, список может быть построен с помощью

s[[#]]& /@ a

Мы можем сравнить результаты:

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}