r - 什么算法用于设置交集？

Question

R 在内部使用什么算法来设置交集，即intersect(x,y)？帮助文件中似乎没有任何信息。据我所知，它不是基于排序然后合并x和y，作为预排序x并且y不会加速它。

标签： r

Answer 1

的代码intersect(x, y)是

function (x, y) 
{
    y <- as.vector(y)
    unique(y[match(as.vector(x), y, 0L)])
}

unique是一个通用函数，unique.default调用内部 C 函数do_duplicated，然后调用any_duplicated或any_duplicated3. match调用内部 C 函数do_match，该函数又调用match5. 各自的 C 函数、any_duplicated、any_duplicated3和match5使用哈希表，请参见https://svn.r-project.org/R/trunk/src/main/unique.c。

因此，intersect使用哈希表来计算集合交集，尽管哈希表会被构造两次，一次是 for match，一次是 for unique。