程序的健壮性是否该有一个度？

[kongque2016]

我想用项目里的具体例子来开始这次讨论。我自己的一个小项目。。。可以当成一个具有代码提示功能的编辑器。现在我要实现两个功能：
1, 按键序列的映射。例如 vim 风格的:
map ^X x
map ^X^A ggvGx
（这两个映射随便写的，没什么特殊意义。）
2，属性名称的智能补全, 像输入"string.l"时，提示:
string.length,
string.lastIndexOf

要实现这两个功能，在编程上需要一个数据结构，来搜集用户绑定按键序列（例如"^X", "^X^A"),或是对象的属性名称（例如"length", "lastIndexOf")。
有两个选择（哈希表被排除了，因为这里需要对字符串排序）：
1,普通数组。 排序存储+二分查找。
2,AVL 树。

现在我的问题是，应该选哪一个？这两者的区别仅在于插入 /删除元素时，后者是稳定的，前者在 100 以内通常快，但会随着容量增加而线性变慢。

如果按照“量体裁衣”的原则，数组似乎是更好的选择，毕竟很少有用户绑定超过 100 个快捷键，也很少有一个对象的属性 /方法超过 100 个，即使超过，在 1000 范围内，速度都还是可接受的。

但问题是，如果有某个用户绑定超过 1000 个快捷键，或者某个用户的对象的属性超过 1000 个，甚至是一万，十万，然后他感觉到程序变迟钝了。那这是谁的错？我们怪用户的行为稀奇古怪，用户也可能觉得我们的程序不够“健壮”。毕竟，我们只需要简单的把数组换成 AVL 树，所有的问题都会消失。而且代价不算大，仅仅是代码稍微复杂了一些。
但如此一来，我们是不是过度的关注程序了健壮性呢？

希望听听各位在这方面的宝贵意见，也想听听大家若遇到帖子里的情形，会怎么选择。如果各位你能分享你在编程生涯中遇到的类似的设计抉择，那就更好了。

[casparchen]

属性名称千千万，所以这个肯定得选合适的数据结构吧。
这个问题不该是 Trie 或者后缀数组之类的来解决吗

[zwgmlr3]

看用户的规模以及影响的严重性

[PP]

量级。参考个人级和企业级，同时规定不同需求对应的硬件环境。

[niubee1]

速速 go die 比较好, 比如 erlang

[wenzhoou]

首先，你是一个做刀的。你需要知道你的用户拿着你的刀去做什么，砍柴有砍柴的刀，闯江湖有闯江湖的刀。

恩。上面基本是废话。

针对这个具体的例子。做一个系统参数，默认用数组。用户可以指定为树。

当然也可以做成动态的，自己调优。

如果你还觉得，我一定只能做一个。那就去做用户调查吧。

[whileFalse]

遇到问题再改倒是不迟。就这个问题本身我同意一楼。

[iConnect]

面条代码 vs 提前优化时万恶之源，事物的两面性

[kongque2016]

@casparchen @whileFalse
具体到 C++/python 语言里一个具体的类，方法+属性名都是有限的吧。

[kongque2016]

@iConnect
你好，我想你误解我的意思了。我没有讨论“性能”这个话题，小规模下，线性数组应该比 AVL 还要快，但我不关心这些，我倾向于数组也不是因为这个。就目前为止，我应该会选择数组继续推进项目，但这个问题最终要回来面对。

[kongque2016]

@whileFalse 对，这种问题能得到用户的反馈最佳。发帖是想听听大家的经验，感觉大家在工作中应该遇到过类似的情形。我阅读过 zsh 和早期 vi 的源码，在这个问题上，前者用 hash 表（它的排序方式我没细看），vi 用的就是简单的链表。可见不同程序员对“健壮”的理解也是不一样的。

[MiffyLiye]

依赖接口，不依赖内部实现
后续把实现换成 Hybrid Dictionary 就行了

[doubleflower]

只为正常使用情况设计就行，现实中的软件也一般都是这么设计的，用户做出超常规行为会受到性能的代价也很合理。比如编辑器处理超大文件的情况，除非处理超大文件当成一个功能，否则不会这种情况考虑。

[kongque2016]

@doubleflower
嗯，要高效的编辑大文件，通常要牺牲掉处理常规文件的一部分性能，而且代码量和复杂度会增加不少，就因为弊端明显，反而容易做取舍。我这里用 AVL 树的话，额外引入的代码量和复杂度是有限的，毕竟 AVL 树在项目的别处有用到，函数已经链接进来了，有种“不用白不用”的感觉。而用的好处是明显的：不用考虑用户习惯什么的，一了百了。

[akira]

这个是 性能优化的 问题。

如果 99%的用户永远都用不到 100 个以上的按键序列，那这个功能就是多余的。

[samaxu]

我大学老师说的一句话很有道理
给多少钱，就写值多少钱的代码

[98jiang]

那你限制一下，不让他设置这么多

[loveour]

如果是面向大众的，还是尽量优化下吧，但是也要权衡，我觉得先采用简单办法，但是预留接口以后优化比较好。
优化也得注意方式，有个大概是在某种情况下反向优化的例子，某个看图软件，似乎在打开文件夹内一张图片的时候会预先缓存文件夹内其他图片的信息，估计是为了优化切换图片什么的速度，但是，我有一些超过 1W 张图片的文件夹，打开其中一个图片软件就会卡死，我觉得这个就是反向优化了。说实话，打开图片慢一点，切换慢一点，我觉得也能忍。

[kongque2016]

@98jiang 我也这样想过，这种策略有点儿苹果公司的风格（非贬义）。。其实还可以在用户绑定的快捷键过度时，发出警告。我想这样比让他什么都不知道强。

[kongque2016]

@loveour 是面向程序员的。我同意你说的“尽量优化”和“权衡”，如果只需要付出很少的代价，就能让一个功能“无后顾之忧”，何乐而不为呢。这里的权衡，应该就是比较 AVL 在小数量时，相对数组的 overhead。也包括对代码的可读性影响了多少。

[choice4]

这种东西可以转吗？ 参考 jdk1.8 后的 hashmap 在链表元素超过 8 后将链表转为了红黑树 是不是可以借鉴这种思想 当用户添加快捷键数量到达一定值时对该用户的数据结构进行一下转换？

[kongque2016]

@choice4
谢谢，感觉这是最佳的方式。
linux 内核 2.4 源码里也有一处，是链表长出 32 后，重构成红黑树。
BTW，真是巧，我这两天正在琢磨这个思路。