algorithm - 设定操作的数据结构

原文 标签 algorithm data-structures language-agnostic

什么样的数据结构能在时间和空间上有效地支持以下集合操作?
联盟
差异
伊斯曼堡
添加
删除
我可以想出三种不同的操作方法,假设我们有两个集合,它们的大小都是N:
位数组:

1. O(N)  2.O(N)  3.O(1)  4.O(1)  5.O(1)

哈希表:
1. O(N)  2.O(N)  3.O(1)  4.O(1)  5.O(1)

有序树:
1. O(NlogN)  2.O(NlogN)  3.O(logN)  4.O(logN)  5.O(logN)

位数组和哈希表很快,但它们占用的内存太多,有序树很慢,但占用的内存更少。
请注意:集合可以包含除整数以外的其他类型,如浮点数或字符串
还有哪些数据结构既快速又通用,而且节省空间?

最佳答案

一种选择是使用bloom过滤器来增加有序树,以加快ismemberof类型测试。
我认为,整体行为将类似于:

1. O(N log(N) )  2. O( ? )  3.O(1)  4.O(log(N))  5.O( log(N) )

但是,确切的细节将取决于过滤器的大小、集合的大小和域的大小。
另一个选择可能是Judy Arrays。我听说过它们的优点,但没有个人经验。
另一种选择是forrest approach(而不是纯二叉树)。

相关文章:

algorithm - 神经网络进行威胁分析

algorithm - 证明存在10次交换的O(n)算法

c++ - 如果相同数据的两个副本位于不同的数据结构中,是不好的做法吗?

algorithm - 子串搜索

algorithm - 为Rabin-Karp字符串搜索算法找到一个好的哈希函数

algorithm - 重新排列列表中的元素,以便连续的元素彼此成功?

c++ - 我的最大二进制堆中的C++轮询操作非常缓慢

language-agnostic - 深度复制操作是否以递归方式复制它不拥有的子变量?

language-agnostic - 在计算阶乘之前,可以知道它多大吗?

linux - 在Linux中是否可以将两个连接从相同的客户端端口连接到不同的服务器端口?