Сколько уникальных ключей есть у моих data.table?

Question

С учетом data.table, как найти количество уникальных ключей, которые оно содержит?

library(data.table) 
z <- data.table(id=c(1,2,1,3),key="id") 
length(unique(z$id)) 
==> 3 

Проблема заключается в том, что unique является в целом квадратным, но, так как ключи в data.table сортируют, это должно быть возможно найти количество уникальных ключей в data.table в линейной времени.

Answer 1

Может быть, это:

sum(Negate(duplicated)(z$id)) 

г $ ID остается отсортированный, поэтому дублируется может работать быстрее на нем:

bigVec <- sample(1:100000, 30000000, replace=TRUE) 
system.time(sum(Negate(duplicated)(bigVec))) 
    user system elapsed 
    8.161 0.475 8.690 

bigVec <- sort(bigVec) 
system.time(sum(Negate(duplicated)(bigVec))) 
    user system elapsed 
    0.00 2.09 2.10 

Но я только что проверил и длина (уникальный()) работает быстрее на отсортирован векторы также ...

Так что, возможно, существует какая-то проверка, если вектор сортируется (это можно сделать в линейном времени). Для меня это не выглядит квадратичным:

system.time(length(unique(bigVec))) 
    user system elapsed 
    0.000 0.583 0.664 

bigVec <- sort(sample(1:100000, 20000000, replace=TRUE)) 
system.time(length(unique(bigVec))) 
    user system elapsed 
    0.000 1.290 1.242 

bigVec <- sort(sample(1:100000, 30000000, replace=TRUE)) 
system.time(length(unique(bigVec))) 
    user system elapsed 
    0.000 1.655 1.715 

Answer 2

Я буду раскрывать свой комментарий в качестве ответа.

base::unique (unique.default) на векторах использует хеш-таблицы и достаточно эффективен, со средней сложностью O (1) - это, скорее всего, общий случай. Наихудшей сложностью является O (n). Но шансы на то, что это происходит при каждом вставке/поиске, должны быть крайне редкими - это должно быть ужасная хеш-функция, если это произойдет.

В вашем вопросе у вас есть только один ключевой столбец, поэтому уникальность базы должна быть достаточно эффективной. Однако в более чем одном столбце unique.data.frame очень неэффективен - поскольку он коэрцирует все столбцы символам, затем вставляет их вместе, а затем называет unique.default.

Вы можете использовать:

nrow(unique(z)) 

unique метод data.table в, по умолчанию, содержит ключевые столбцы его by аргумента. И поскольку мы знаем, что данные уже отсортированы, вместо упорядочения мы используем data.table:::uniqlist, чтобы получить индексы, соответствующие уникальным строкам, намного эффективнее в O(n). Поэтому он эффективен для любого количества ключевых столбцов.

Однако мы могли бы добавить эту информацию в качестве атрибута при установке ключа, так как это довольно просто.