无聊想动脑筋的进来

rogerk

这个里面最费的操作肯定是字串比较，你想办法优化以下这个部分吧。

GPS

读取。
比如按块读入就比一个记录一个的读快。

huazhb

首先, 如果你要识别字段中的逗号, 你一定要用custom function, 不能直接在sql中用, 这样要快很多很多...然后你应该在把数据装到数据库的时候, 就要把这些预处理做好. 这样在查询的时候才能体现出数据库的速度.

righttang

贴一下XML的样本，需要统计的，就是XML里面的的value，以逗号分隔。当前算法，已经在遍历的时候，就做了分类了，分类不是用的hash，是用的List。我是说JAVA里的

<group value="ENDORSED,Interactive,Digilearn,Focus groups,Furnishings,Furniture,Houses,Learning Federation,Locations,Pinyin,Positioning,Prepositional phrases,Prepositions,Questions,Rooms,Scootle,TL,Chinese languages">
<count>1</count>
</group>
<group value="ENDORSED,Interactive,Digilearn,German language,Illustration,Learning Federation,Scootle,Simple sentences,Sound effects,TLF,Adjectives">
<count>1</count>
</group>

[ 本帖最后由 righttang 于 2010-12-9 17:17 编辑 ]

GPS

如果源数据不在数据库里，我不认为用数据库是最快的。用数据库加索引，最少就是个o(nlogn)的排序。
数据库也是用算法实现。如果还要重复用这些数据，那倒是可以，不过，LZ的意思似乎不是这样， 而是每次都不同。

o2h2o

Lucene 是一个很不错的全文收索引擎
java的
text file based 的
他会先index

收索效果 酷似 google
这个 应该是 最牛逼的 开源的 search engine 了

[ 本帖最后由 o2h2o 于 2010-12-9 17:18 编辑 ]

GPS

还有就是如果是multi-core的话，可以考虑多线程阿。

righttang

原帖由 o2h2o 于 2010-12-9 17:16 发表
Lucene 是一个很不错的全文收索引擎
java的
text file based 的
他会先index

收索效果 酷似 google
这个 应该是 最牛逼的 开源的 search engine 了

我们用的是Oracle Text Search，应该客户不会轻易去修改全文搜索引擎。这个东西我也是听说过，的确是不错

o2h2o

原帖由 righttang 于 2010-12-9 17:20 发表


我们用的是Oracle Text Search，应该客户不会轻易去修改全文搜索引擎。这个东西我也是听说过，的确是不错

o 原来已经有了
我还以为啥都没

righttang

原帖由 GPS 于 2010-12-9 17:19 发表
还有就是如果是multi-core的话，可以考虑多线程阿。

JAVA的多线程可以指定用哪个core的吗？这个应该是JVM自己管的吧。

另外对于这种一天上万次点击的服务，从设计上来说，多线程应该是按request来分的比较好哦？ 如果一个单独的request，再分出多个线程来一起计算，感觉有点没必要呢。

righttang

晕，5点半了，下班了下班了，谢谢各位，今天没分了。回家再和各位讨论哈。

stevenbian

保存上次前30位的结果，然后下次就只比较前30位。应该差别不大吧

GPS

有多个core的时候，JVM才会有可能真正的并行吧。
如果服务器端本身就有多个应答的线程，比如thread-pool之类的，每个里面有已经固定分开多个分组的线程。收到数据后，直接放到第一层线程，它们再分开放到第二层。
如果这些都是永久反复使用的线程，那就不存在开销了。
呵呵，我不知道在web server里怎样做，也不知道到底有多块。

GPS

原帖由 stevenbian 于 2010-12-9 17:27 发表
保存上次前30位的结果，然后下次就只比较前30位。应该差别不大吧

这个是个好思路。如果真是比family name，应该可以利用经验结果。比如，收到数据后，如果需要20名，就只排经验数据的前100名，但同时讲所有数据传到另一个后台程序做全排，并修改经验数据。不过这要求每次的数据要足够大，否则偏差挺大。

梦呓人

如果有.net这样的话，几行code就可以了


      DataSet dsSouece = new DataSet();
     dsSouece.ReadXml(new StringReader(yourxml));                                 // xml 读进一个 dataset

     DataView dv = dsSouece.Tables[0].DefaultView;
     DataTable dtGroup = dv.ToTable(true, new string[] {"lastname"});             // get all unique surname
     dtGroup.Columns.Add("Count", typeof(int));
   
     foreach(DataRow dr in dtGroup.Rows)
         dr["Count"] = dsSouece.Tables[0].Compute("Count(lastname)", "lastname='" + dr["lastname"] + "'");   // datatable的compute() 很给力

乱码

把xml可以直接放在db中，用xquery作，这种效率一定比自己写高，但它对db空间的占用几乎是灾难性的，相对那种传统意义上的针对table的query也基本上不是一个级别的。

建议前段放一个自己写的parser，拿到xml之后，往db table上map 存一下，这个过程费不了多少事，但你以后用这些数据，能得到传统意义上db的强力支持，你自己根本不用考虑底层算法，db engine帮你搞定了。

小皇爷

我公司里拿到第三方的XML后，是直接插入数据库的。拿出来用的时候就很方便。

另外加一点，通常会设计一个cron job，每隔一段时间运行一次，把XML插入到DB。

[ 本帖最后由 小皇爷 于 2010-12-9 22:14 编辑 ]

kr2000

如果用户搜索的内容差不多
可以把比较慢的计算结果存在cache里

xji

减少搜索空间吧。一个词由字母组成，如果原始的方法，每个字母都要比较，比如一个词是ABCDE，如果前缀ABC就已经不在top 15的前缀里，那么后面的DE就不用考虑。也就是说，可以从前缀开始比较，然后前缀不在top 15的直接砍掉。具体还可以考虑前缀重复的可能性大还是后缀，如果是人名，那么像Susan，Smith，Sam，Stephen，前缀重复的可能性比后缀大，那么比后缀可能更好，但你的情况可能不是人名，所以另外考虑。

其实database里的string index也无非是prefix/suffix tree或者是好点的hash。

mangrove

最快的方法是，每次更新数据源的时候，就先统计好来。等要用的时候只是一个结果查询而已。

如果没有办法做到，就定期去查询数据源，然后做好统计，等用户查询的时候给出上次统计的结果就可以了。

righttang

原帖由 GPS 于 2010-12-9 17:37 发表

这个是个好思路。如果真是比family name，应该可以利用经验结果。比如，收到数据后，如果需要20名，就只排经验数据的前100名，但同时讲所有数据传到另一个后台程序做全排，并修改经验数据。不过这要求每次的数据要足够大，否则偏 ...

恩，最终我选的解决办法，是只处理头2000个数据，然后得到的结果，基本上和全局的结果差不多。
但是处理2000个，比处理20W个数据块了不知道多少，基本上能在1秒内解决，CPU占用也不是很高。

这算一个最简单的解决办法把。至于把XML放进数据库，这个应该也是一个好办法。
不过我这里的XML，本来就是从数据库里出来的，而且我们这个系统目前的瓶颈也是数据库，所以我也就不麻烦数据库了。。。。

再次谢谢各位热心的参与讨论～

乱码

原帖由 righttang 于 2010-12-23 12:27 发表


恩，最终我选的解决办法，是只处理头2000个数据，然后得到的结果，基本上和全局的结果差不多。
但是处理2000个，比处理20W个数据块了不知道多少，基本上能在1秒内解决，CPU占用也不是很高。

这算一个最简单的解决办法把。至于把 ...

如果你的xml本来就是db中存的东西，而且是xml形式的，你可以用xquery做view，不难，然后用传统的sql去query这个view，从programming的角度就容易很多，但底层的东西还是xquery，但对developer来说是感觉不到的，跟query一般的table一样。

porcorosso

can try PHP with inbuilt lib Xmlparser IF you can run this app as cli, since there is no presentation required... for cli php can run by itself without any app server. i have been doing similar thing in my previous job, 500k+ rows csv single file

but first thing first, how big is the xml file? the physical IO will take a bit of time already if the hdd is bad LOL

good luck

starchu

如果要处理海量数据可以考虑使用map reduce, 处理这种问题比较好。当然这是针对海量数据的。。。这里还算不上

jackiezhang2008

不应该用头2000个记录，应该从全部样本里面随机选择2000个记录，前提是你读取全部记录不需要太长时间的话。

另外，你这个问题在时间复杂度上很好分析的：
如果你要必须在运行时进行排序，那你最快也一定是O(NlogN)
如果你每次只是要找到比如说前15个出现次数最多的记录，那么实际上是有O(N)的算法存在的，这个就是order statistics，具体的你google一下。

原帖由 righttang 于 2010-12-23 12:27 发表


恩，最终我选的解决办法，是只处理头2000个数据，然后得到的结果，基本上和全局的结果差不多。
但是处理2000个，比处理20W个数据块了不知道多少，基本上能在1秒内解决，CPU占用也不是很高。

这算一个最简单的解决办法把。至于把 ...