标签: data-structures

假设我想用字符串作为键来映射数据.我应该选择哪个容器,map或者unordered_map？unordered_map占用更多内存所以让我们假设内存不是问题,关注的是速度.

unordered_map通常应该给出O(1)的平均复杂度与O(n)的最坏情况.在什么情况下它会到达O(n)？什么时候map获得更多的时间效率unordered_map？当n很小时会发生吗？

假设我将STL unordered_map与默认的haser Vs一起使用.地图.字符串是关键.

如果我要迭代元素而不是每次访问单个元素,我应该更喜欢map吗？

我遇到了这个问题: 实现一个队列,其中push_rear(),pop_front()和get_min()都是常量时间操作.

我最初想过使用一个最小堆数据结构,它对于get_min()具有O(1)复杂度.但是push_rear()和pop_front()将是O(log(n)).

有谁知道实现这样一个有O(1)push(),pop()和min()的队列的最佳方法是什么？

我搜索了这个,并想指出这个算法极客线程.但似乎没有一个解决方案遵循所有3种方法的恒定时间规则:push(),pop()和min().

感谢所有的建议.

给定数据结构规范,例如具有已知复杂性边界的纯函数映射,必须在若干实现之间进行选择.有一些关于如何选择正确的民间传说,例如红黑树被认为通常更快,但AVL树在工作负载上具有更好的性能和许多查找.

1. 是否有关于这种知识的系统性介绍(发表的论文)(与集合/地图相关)？理想情况下,我希望看到对实际软件进行统计分析.例如,它可能得出结论,有N种典型的地图用法,并列出每种地图的输入概率分布.

2. 是否有系统基准测试地图并设置不同输入分布的性能？

3. 是否存在使用自适应算法根据实际使用情况更改表示的实现？

所以我最近一直在讨论C#,所有的Generic Collections让我有些困惑.假设我想表示一个数据结构,其中树的头是一个键值对,然后在它下面有一个可选的键值对列表(但没有比这些更多的级别).这适合吗？

public class TokenTree
{
    public TokenTree()
    {
        /* I must admit to not fully understanding this,
         * I got it from msdn. As far as I can tell, IDictionary is an
         * interface, and Dictionary is the default implementation of
         * that interface, right?
         */
        SubPairs = new Dictionary<string, string>();
    }

    public string Key;
    public string Value;
    public IDictionary<string, string> SubPairs;
}

传递数据只是一个简单的分流.

我的场景如下:我有一个数据表(少数字段,少于一百行),我在我的程序中广泛使用.我还需要这些数据是持久的,因此我将其保存为CSV并在启动时加载它.我选择不使用数据库,因为每个选项(甚至是SQLite)对我的简单要求来说都是过度的(同样 - 我希望能够以简单的方式离线编辑值,没有什么比记事本简单).

假设我的数据看起来如下(在文件中,它的逗号分隔没有标题,这只是一个例子):

 Row  | Name     | Year   | Priority
------------------------------------
 1    | Cat      | 1998   | 1
 2    | Fish     | 1998   | 2
 3    | Dog      | 1999   | 1 
 4    | Aardvark | 2000   | 1
 5    | Wallaby  | 2000   | 1
 6    | Zebra    | 2001   | 3

笔记:

1. 行可以是写入文件的"实际"值,也可以是表示行号的自动生成的值.无论哪种方式,它都存在于内存中.
2. 名字是独一无二的.

我对数据做的事情:

1. 根据ID(迭代)或名称(直接访问)查找一行.
2. 根据多个字段以不同的顺序显示表格:我需要按优先级排序,然后按年份,年份,然后优先级等.
3. 我需要根据参数集计算实例,例如1997年到2002年之间有多少行,或者1998年有多少行,优先级> 2等.

我知道SQL的"哭"......

我想弄清楚什么是数据结构的最佳选择.以下是我看到的几个选择:

行列表列表:

a = []
a.append( [1, "Cat", 1998, 1] )
a.append( [2, "Fish", 1998, 2] ) …

哪种编程语言,你会推荐学习有关数据结构和算法吗？

考虑以下因素:

• 个人经验
• 语言功能(指针,面向对象等)
• 适合学习DS&A概念

我问,因为有些书是编程语言无关的(从数学角度编写,并使用伪代码).如果我从其中一个中学习,我想选择一种编程语言来编写和运行算法.

然后,还有其他书籍介绍了DS&A概念和用特定编程语言编写的示例 - 我也想编写这些算法 - 因此,在某种程度上,语言也会选择这本书.

无论哪种方式,我必须选择一种语言,我宁愿坚持一个.撇开个人语言偏好,哪一个最适合此目的？

何时使用哈希映射或树图？

我知道当我需要对它们进行排序时,我可以使用TreeMap迭代元素.但就是这样吗？当我只想查阅地图或某些最佳特定用途时,没有优化？

我对以下树的术语感到困惑,我一直在研究树,我无法区分这些树:

a)完整的二叉树

b)严格的二叉树

c)完整的二叉树

请帮我区分这些树.在数据结构中何时何地使用这些树？

我最近读到在C中使用灵活的阵列成员是糟糕的软件工程实践.但是,该声明没有任何论据支持.这是公认的事实吗？

(灵活的数组成员是C99中引入的C特性,其中可以将最后一个元素声明为未指定大小的数组.例如:)

struct header {
    size_t len;
    unsigned char data[];
};

存储100万个电话号码的最有效方式是什么？

显然这是Google的面试问题,请提出您的想法.