标签: data-structures

我知道性能永远不会是黑白的,通常一个实现在X情况下更快,在Y情况下更慢等等,但一般来说 - B树比AVL或RedBlack-Trees快吗？它们比AVL树(甚至可能是RedBlack-trees？)要复杂得多,但它们更快(它们的复杂性是否得到回报)？

编辑:我还想补充一点,如果它们比等效的AVL/RedBlack树更快(就节点/内容而言) - 为什么它们更快？

用于实现Python内置列表数据类型的典型底层数据结构是什么？

我之前关于此的帖子说:

对于LinkedList

• 得到的是O(n)
• 加是O(1)
• 删除是O(n)
• Iterator.remove是O(1)

对于ArrayList

• 得到的是O(1)
• add是O(1)摊销,但O(n)最坏情况,因为必须调整和复制数组
• 删除是O(n)

因此,通过观察这一点,我得出结论,如果我只是在我的集合中为5000000个元素执行顺序插入,那么LinkedList将会超出ArrayList.

如果我只是通过迭代来获取集合中的元素,即不在中间抓取元素,仍然LinkedList会超出`ArrayList.

现在要验证我的上述两个陈述,我在下面写了示例程序...但我很惊讶我的上述陈述被证明是错误的.

ArrayListLinkedlist在两个案件中都超过了.花费的时间少于LinkedList添加以及从Collection中获取它们所花费的时间.有什么我做错了,或有关初步陈述LinkedList和ArrayList尺寸为500万的收藏品不成立？

我提到了尺寸,因为如果我将元素数量减少到50000,那么LinkedList表现更好,初始语句也成立.

long nano1 = System.nanoTime();

List<Integer> arr = new ArrayList();
for(int i = 0; i < 5000000; ++i) {
    arr.add(i);
}
System.out.println( (System.nanoTime() - nano1) );

for(int j : arr) {
    ;
}
System.out.println( (System.nanoTime() - nano1) );

long nano2 = System.nanoTime();

List<Integer> arrL = new …

我在很多地方都看过这个:

"在一个数据结构上运行100个函数比在10个数据结构上运行10个函数更好." -Alan Perlis

但我从未见过它解释了为什么这应该是真的.您是否应该尝试从第一个派生其他9个数据结构以避免重复数据？我觉得我错过了一些背景.

在NSSet/ NSMutableSet基于集合中对象的属性对对象进行排序的最有效方法是什么？现在,我这样做的方法是迭代每个对象,将它们添加到a中NSMutableArray,然后对该数组进行排序NSSortDescriptor.

存储字典所有单词的最佳数据结构是什么？我能想到的最好的就是使用a HashMap,它将映射到a HashTable.基本上,根据第一个字符,我们将得到关联HashTable,然后使用它,我们可以添加从该字符开始的单词.然后我们将根据字符串选择一个好的哈希函数.

有更好的方法吗？

我已经阅读了有关Fibonacci堆的维基百科文章,并阅读了CLRS对数据结构的描述,但它们对于这种数据结构的工作原理几乎没有直觉.为什么Fibonacci堆的设计方式如何呢？他们是如何工作的？

谢谢!

我有一个std :: vector m_vPaths; 我会迭代这个向量并调用:: DeleteFile(strPath).如果我成功删除了该文件,我将从矢量中删除它.我的问题是,我可以使用两个向量吗？是否有不同的数据结构可能更适合我需要做的事情？

示例:使用迭代器几乎可以实现我想要的,但问题是一旦使用迭代器擦除,所有迭代器都将变为无效.

 std::vector<std::string> iter = m_vPaths.begin();
    for( ; iter != m_vPaths.end(); iter++) {
        std::string strPath = *iter;
        if(::DeleteFile(strPath.c_str())) {
            m_vPaths.erase(iter);   
                //Now my interators are invalid because I used erase,
                //but I want to continue deleteing the files remaining in my vector.    
        }
    }

我可以使用两个向量,我将不再有问题,但是有没有更好,更有效的方法来做我想做的事情？

顺便说一句,如果不清楚,m_vPaths就是这样声明的(在我的课上):

std::vector<std::string> m_vPaths;

我正在查看PHP手册,我没有看到大多数语言都有的数据结构部分,例如列表和集合.我只是盲目或PHP没有这样的内置？

哈希映射和字典ADT之间有什么区别.什么时候比较喜欢一个.对于我的编程作业,我的导师要求使用其中一个,但我认为两者之间没有任何区别.该计划应该与一个巨大的没有.字符串.有什么建议？