匹配：KMP 算法

前端性能：用 web workers 或者分块异步运算

=========

以上纯粹从面试题角度

如果是实际的问题，那么要考虑：

1.这些数据是不是有非英文字符，如果是，那么就最好用正则或者其他底层提供的方法而不是自己实现

2.数据是否有重复，重复的数据是否可以相互替代，如果是，那可以在控件加载先做一些删减

3.数据能不能做索引，如果可以，那么优先做索引

4.实际在做的时候这种大量的数据最好还是放在后端去做，前端 Ajax 加载

10W 条数据的滚动，且不说会不会造成浏览器的性能问题，就这个事情本身来说，没有意义，谁会去滚动着在 10W 条数据里找要的那一条？一般情况下，会根据输入，选择最接近的一二十条列出来供选择，输入的内容越多就越精确，这就是“自动完成”。你要解决的问题就是如何选择要列出来的这一二十条数组。

个人觉得，可以按“快速查找”或者“二分查找”算法进行 prefix 匹配，自己实现这个算法还是有点难度。

用正则表达式是可行的，正则表达式不一定会匹配全文，比如 /^abc/ 匹配的就是开始的3个字母，只要这三个字母匹配上了，就算匹配成功，不会再去比较剩下的内容（也不知道跟谁比较了）

正则表达式实现应该比较简单，先试试再说，如果性能达不到，再想其它办法。

这是携程的笔试题吗

我的思路：

1. 可以用<datalist>来实现，这样可以解决匹配prefix的问题和下拉的问题

2. 关于数据量过大，当用户在未输入情况下进行下拉操作的时候，可以展示部分数据，然后拉到底部的时候动态追加option里面的内容

3. 因为十万条比较多，所以我的想法是用ajax动态获取数据，但一次不要获取完