Ruby数组交集性能问题

Question

我需要对数百万个元素（数据库ID）的n个数组进行交集操作。这段代码可以完美运行，但处理非常慢（对于非常大的数组）。我该如何改进它？

[[1,2,3,4],[2,4,6,8],[4,5,8]].inject([]){|c,v| c = v if c.size==0; c = c&v if c.size>0; c }

- Nicolae Rotaru

Answer 1

[1,2,3,4] & [2,4,6,8] & [4,5,8] #=> [4]

交集方法使用哈希表，因此速度应该很快。

- megas

Answer 2

Ruby提供了一个交集操作符。

我可以建议您尝试这个：

> [[1,2,3,4],[2,4,6,8],[4,5,8]].reduce{ |accum, arr| accum & arr }
=> [4] 

编辑：

这段文字可以更加简洁，但可能会影响可读性。

[[1,2,3,4],[2,4,6,8],[4,5,8]].reduce(:&)

- Kyle

---

是的。[[1,2,3,4],[2,4,6,8],[4,5,8]].reduce{ |accum, arr| accum | arr } - Kyle

你可以不使用&，只需使用reduce(:&)。 - megas

这不是reduce，而是因为交集方法。 - megas

没错。如果你将reduce替换为inject，它们的功能是相同的，因为它们是彼此的别名。 - Kyle

这个操作符的时间复杂度是多少？有任何链接可以帮助吗？ - Parikshit Singh