Самый быстрый способ построения перекрестных таблиц двух массивных логических векторов в R

Для двух логических векторов, x и y , длины > 1E8, каков самый быстрый способ вычисления кросс-таблиц 2x2?

Я подозреваю, что ответ - написать его на C / C ++, но мне интересно, есть ли в R что-то, что уже достаточно умно в отношении этой проблемы, поскольку это не редкость.

Пример кода для 300 миллионов записей (не стесняйтесь принимать N = 1E8, если 3E8 слишком велик; я выбрал общий размер чуть меньше 2,5 ГБ (2,4 ГБ). Я нацелился на плотность 0,02, чтобы сделать его более интересным (можно использовать разреженный вектор, если это помогает, но преобразование типов может занять время.)

set.seed(0)
N = 3E8
p = 0.02
x = sample(c(TRUE, FALSE), N, prob = c(p, 1-p), replace = TRUE)
y = sample(c(TRUE, FALSE), N, prob = c(p, 1-p), replace = TRUE)

Некоторые очевидные методы:

1. table
2. bigtabulate
3. Простые логические операции (например, sum (x & y) )
4. Векторное умножение (boo)
5. data.table
6. Некоторые из вышеперечисленных, с параллельным из многоядерного пакета (или нового parallel package)

Я попробовал первые три варианта (см. Мой ответ), но чувствую, что должно быть что-то лучше и быстрее.

Я считаю, что table работает очень медленно. bigtabulate кажется излишним для пары логических векторов.И, наконец, выполнение обычных логических операций похоже на кладж, и он смотрит на каждый вектор слишком много раз (3X? 7X?), Не говоря уже о том, что он заполняет много дополнительной памяти во время обработки, что является большой тратой времени.

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

Не стесняйтесь изменять N и p , если это продемонстрирует что-нибудь интересное поведение функций табуляции. :)

Обновление 1. Мой первый ответ дает тайминги для трех наивных методов, что является основанием полагать, что таблица работает медленно. Тем не менее, главное понять, что «логический» метод крайне неэффективен. Посмотрите, что он делает:

• 4 операции с логическими векторами
• 4 преобразования типов (логические в целые числа или FP - для суммы )
• 4 суммирования векторов
• 8 присваиваний (1 для логическая операция, 1 для суммирования)

Не только это, но это даже не компилируется и не распараллеливается. Тем не менее, он по-прежнему выигрывает у таблицы . Обратите внимание, что bigtabulate с дополнительным преобразованием типа ( 1 * cbind ... ) по-прежнему превосходит таблицу .

Обновление 2. Чтобы никто не указал, что логические векторы в R поддерживают NA , и что это будет ключом к системе для этих перекрестных таблиц (что верно в большинстве случаев), я должен указать из того, что мои векторы берутся из is.na () или is.finite () .:) Я отлаживал NA и другие не конечные значения - они были для меня головной болью в последнее время . Если вы не знаете, все ли ваши записи являются NA , вы можете протестировать с помощью any (is.na (yourVector)) - это будет разумно, прежде чем принимать некоторые идей, возникающих в этом вопросе и ответе.

Обновление 3. Брэндон Бертельсен задал очень разумный вопрос в комментариях: зачем использовать столько данных, когда подвыборка (в конце концов, первоначальный набор является выборкой ;-)) может быть адекватной для целей создания перекрестная таблица? Чтобы не заходить слишком далеко в статистику, но данные получены из случаев, когда наблюдения ИСТИНА очень редки для обеих переменных. Один из них является результатом аномалии данных, другой - возможной ошибкой в ​​коде (возможной ошибкой, потому что мы видим только результат вычислений - подумайте о переменной x как о «мусоре на входе» и y как «Мусор Out». В результате возникает вопрос, являются ли проблемы в выводе, вызванные кодом, исключительно теми случаями, когда данные являются аномальными, или есть другие случаи, когда хорошие данные портятся? (Это вот почему я задал вопрос об остановке при обнаружении NaN , NA или Inf .)

Это также объясняет почему мой пример имеет низкую вероятность для ИСТИННЫХ значений; это действительно происходит гораздо меньше, чем в 0,1% случаев.

Предлагает ли это другой путь решения? Да: он предполагает, что мы можем использовать два индекса (т.е.местоположения ИСТИНА в каждом наборе) и подсчитывают пересечения наборов. Я избегал пересечений множеств, потому что некоторое время назад я был сожжен Matlab (да, это R, но терпи меня), который сначала сортирует элементы множества, прежде чем он сделает пересечение. (Я смутно припоминаю, что сложность была еще более неприятной: вроде O (n ^ 2) вместо O (n log n) .)