这是一个创建于 1814 天前的主题，其中的信息可能已经有所发展或是发生改变。
今天面试被问到一道题目，回来想了半天也没思路，求拍醒
问题： 假设你平时用 IDE 进行编码，IDE 会在启动的时候做一些索引。然后你整个项目搜索“String”会迅速定位到多个包含 String 关键字的代码。 请问由你来做这个功能，怎么才能让搜索执行效率高？
第 1 条附言 · 2019-11-28 18:19:03 +08:00
搜索部分应该是像 4 楼所说的，分索引和没索引两种类型。
有没有做中文搜索匹配的能告诉我一下火星文该怎么匹配啊？
有没有做中文搜索匹配的能告诉我一下火星文该怎么匹配啊？
 |
1
lhx2008 2019-11-28 17:41:08 +08:00 via Android
索引之后肯定是 O(logn) 以下了，所以是问怎么建立索引？
|
 |
2
vjnjc OP @lhx2008 嗯应该是问怎么建索引。
我一个粗糙的考虑是用 dictionary，比如“String” -> [“file1”, "file2", "file3"...], “Str” -> [“file1”, "file2", "file3"...], “S” -> [“file1”, "file2", "file3"...],这样的话查起来方便，但是空间效率利用太低了吧。。。 |
 |
4
optional 2019-11-28 17:47:34 +08:00  1
无索引搜索可能问的是 BM 算法， 有索引问的应该是分词之后倒排索引。
|
|
5
lhx2008 2019-11-28 17:47:53 +08:00 via Android
@vjnjc 你这个示例，用一个前缀树做 key 的结构就行啊，而且 s 这种单词有没有搜索的价值。至于怎么解析代码就很复杂了。
|
 |
6
jenschen 2019-11-28 17:48:54 +08:00 via iPhone
b+树吧
|
|
7
lhx2008 2019-11-28 17:49:12 +08:00 via Android
同意楼上，可能考的是只是字符串搜索
|
|
9
vjnjc OP @lhx2008 多谢。
这应该是个开放性题目，看我知识广度，感觉回答出 4#说的 2 种之一就好了，然而我都没看到过 0 0，说实话前缀树在做算法的时候自己还用过，忘得一干二净了 |
 |
10
Vegetable 2019-11-28 18:02:12 +08:00
这场景怪怪的,ide 真的会做这个事情吗?
|
 |
11
66450146 2019-11-28 18:50:53 +08:00
这个最合适的还是参考 Language Server Protocol ( https://microsoft.github.io/language-server-protocol/overview)
从这里倒推具体 language server 的实现，其实就是一个 tokeniser，生成 AST ( https://en.wikipedia.org/wiki/Abstract_syntax_tree) 分析就行了，大部分都是这么做的 字符串匹配不是不行，但是效果要差很多，对于关键字很多的语言更麻烦 |
Select Language