sfa*_*tor 8 java optimization perl search
我必须认识到一大堆URL(几百万行)属于特定类别.我有另一个列表,其中包含子字符串,如果URL中存在属于该类别.说,类别A.
要检查的子字符串列表包含大约10k个这样的子字符串.我所做的只是在子字符串文件中一行一行地查找匹配项,如果发现该URL属于A类,我在测试中发现这相当耗时.
我不是计算机科学专业的学生,因此对优化算法知之甚少.但有没有办法让这更快？只是简单的想法.编程语言不是一个大问题,但Java或Perl更可取.
要匹配的子字符串列表不会有太大变化.但是我会收到不同的URL列表,所以每次我都要运行它.瓶颈似乎是URL,因为它们可以变得很长.
是的,我在java中为你提出的问题实现了Aho-Corasick算法算法,并且在幼稚实现(你正在做的事情)上显示出大约x180的持续改进.有几种在线实现,但我会调整它们以获得更好的性能.请注意,解决方案的复杂性受到单词长度(在您的情况下为URL)的限制,而不是子字符串的数量.此外,它只需要平均一次通过匹配.
PS - 我们曾经在求职面试中向人们提出这个问题,因此有很多方法可以解决这个问题.我提供的那个是我们在生产代码中使用的那个(现在)胜过所有其他解决方案.
编辑:之前写过错误的算法名称,修复...