相关疑难解决方法(0)

我不知道这是否是询问算法的地方.但是,让我们看看我是否得到任何答案...... :)

如果有什么不清楚我很乐意澄清事情.

我刚刚在python中实现了一个Trie.然而,有一点似乎比它应该更复杂(作为一个喜欢简单的人).也许有人遇到过类似的问题？

我的目标是通过在其根中存储子trie的最大公共前缀来最小化节点数.例如,如果我们有stackoverflow,stackbase和stackbased这两个词,那么树看起来像这样:

              [s]tack
[o]verflow ______/ \_______ [b]ase
                                  \___ [d]

注意,人们仍然可以想到边缘具有一个字符(子节点的第一个).

查找 -query很容易实现. 插入并不难,但比我想要的更复杂.. :(

我的想法是一个接一个地插入密钥(从一个空的trie开始),首先搜索要插入的密钥k(Find(k)),然后在本地重新排列/拆分节点查找程序停止.结果是4种情况:(设k是我们要插入的键,k'是节点的关键,搜索结束)

1. k与k'相同
2. k是k'的"正确"前缀
3. k'是k的"正确"前缀
4. k和k'共享一些共同的前缀,但没有一种情况发生(1),(2)或(3).

似乎每个案例都是独特的,因此意味着对Trie的不同修改.但是:真的那么复杂吗？我错过了什么吗？有更好的方法吗？

谢谢 :)

我正在编写一个Web爬虫,其最终目标是创建爬虫所采用的路径的映射.虽然我不清楚其他的,以及绝大多数更好的爬行器下拉页面,但我的时钟大约每分钟2,000页.

爬虫使用递归回溯算法,我将其限制为15深度.此外,为了防止我的爬虫无休止地重新访问页面,它将它访问过的每个页面的URL存储在列表中,并检查该列表是否为下一个候选网址.

for href in tempUrl:
    ...
    if href not in urls:
         collect(href,parent,depth+1)

这种方法在下载约300,000页时似乎成了一个问题.此时,爬虫平均每分钟计时500页.

所以我的问题是,在提高效率的同时实现相同功能的另一种方法是什么.

我认为减小每个条目的大小可能会有所帮助,所以我不是追加整个url,而是将前两个和最后一个附加到每个url的字符作为字符串.然而,这并没有帮助.

有没有办法用套装或其他东西做到这一点？

谢谢您的帮助

编辑:作为旁注,我的程序还没有多线程.在我开始学习线程之前,我想我应该解决这个瓶颈.

我被要求在一个10GB大的大文件中找到字符串"And"的出现次数,并且有1GB RAM.我该如何有效地做到这一点.我回答说我们需要以每个100MB的内存块读取文件,然后在每个内存块中找到"And"的总出现次数并保持字符串"And"的累积计数.面试官对我的回答不满意,他告诉我grep命令如何在unix中运行.编写类似于python中的代码,但我不知道答案.我将很感激回答这个问题.