无聊想动脑筋的进来

righttang

其实这也是我昨天碰到的一个问题。。

手头有几十万条记录，为了便于叙述，这个记录就当作是“Family Name”吧，长度也就是英语单词。数据样本是随机的，并不能预先排序或者索引.(数据是XML格式，并没有放在数据库里，纯粹JAVA处理这些数据)

我现在的需求就是，统计出，最常用的15个姓氏，并且给出具体数字。比如说，姓Smith的，有2000个人，姓Wong的，有20个人。

于是，我也就随便写了个算法，遍历一遍，然后读一个判断一个，要是有了就加1，要是没有的话，就新增

全部读完，最后排序一下。

结果呢，就是150%CPU占用率（双核），30多秒的运行时间。。。

这个服务使用率非常高，大概一天会被点击上万下，每次的样本都不一样，样本小的，速度还行，1，2秒可以处理几千个记录。但是碰上大样本，直接服务器报警。所以呢我就想改进一下。

1.用模糊算法，由于这个要求并不是100%精确的数据，几十万个记录里，取一部分，能大概表示一下，赵钱孙里大概有多少。不过我也只是耳闻，没有实际用过。谁要了解的指点一下
2.改进算法，我也想了半天，到底用什么样的算法好呢？

贴一下数据XML样本
贴一下XML的样本，需要统计的，就是XML里面的的value，以逗号分隔。当前算法，已经在遍历的时候，就做了分类了，还是慢。。。。

<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:15 编辑 ]

rogerk

那每次的样本是怎么选出来的？

北风

sql? or plain text file?
一般来说加family name index应该能解决你的问题
再看一下exec plan

不过，看你的描述不像sql

肥而不腻

这个跟搜索引擎的搜索常用词排行有点像嘛。

righttang

每次样本，是根据用户不同的输入来选的，比如说，用户输，澳大利亚炮兵连，然后出现2000个士兵的名字。。
接着，用户又输入，维州居民，出现500W个维州居民。。

我接到这些数据的时候，已经是XML形式了，用JAVA把XML提出来，放在向量里面，然后咋办呢。。。

和SQL数据库没关系咯。。。。纯粹是算法

rogerk

就是你拿到的就是一堆ｘｍｌ的数据？

那parse xml的时候，难道不能把它分类放么？你反正也需要parse的时间的。

另外，这种活，最好都是服务端做好。你不能让他们把这个数统计好也加在ｘｍｌ里么？数据库就是用来干这个的。

[ 本帖最后由 rogerk 于 2010-12-9 15:43 编辑 ]

righttang

原帖由 rogerk 于 2010-12-9 15:42 发表
就是你拿到的就是一堆ｘｍｌ的数据？

那parse xml的时候，难道不能把它分类放么？你反正也需要parse的时间的。

另外，这种活，最好都是服务端做好。你不能让他们把这个数统计好也加在ｘｍｌ里么？数据库就是用来干这个的。 ...

XML parsing是用的一个现成的产品。要改动他，让他分类放，估计有点困难。
而且，xml parsing似乎速度挺快。。。倒是我自己写的函数，运行了30多秒

不过谢谢你的建议，我反编译一下XML引擎，看看有没有可以着手的地方

righttang

原帖由 rogerk 于 2010-12-9 15:42 发表
就是你拿到的就是一堆ｘｍｌ的数据？

那parse xml的时候，难道不能把它分类放么？你反正也需要parse的时间的。

另外，这种活，最好都是服务端做好。你不能让他们把这个数统计好也加在ｘｍｌ里么？数据库就是用来干这个的。 ...

但是每次样本都不一样，又如何让服务端统计呢？

PS，我这里属于后台，是 Application Service的

coolioo

这种情况必须要做Index，没有Index只能遍历，非常Expensive

huazhb

你把xml装到数据库里, 然后一个group by 很快的

rogerk

另外你要优化算法，把那些字串比较去掉。一般你可以把字串作一个hash, 然后比较hash的值就行了。

这样也许能稍微快点。

rogerk

原帖由 righttang 于 2010-12-9 15:49 发表


但是每次样本都不一样，又如何让服务端统计呢？

PS，我这里属于后台，是 Application Service的

如果你这个已经是app server了，那就应该在database里做。。还真的靠app一个个数阿。。除非你的数据不是从database里来的，比如时文本文件里来的。

北风

这样啊，就是要在BL完成排序
数据量不大还好，太大是会慢的，而且你的这个application server会很累
你可以在你处理xml的时候加index

原帖由 righttang 于 9/12/2010 14:36 发表
每次样本，是根据用户不同的输入来选的，比如说，用户输，澳大利亚炮兵连，然后出现2000个士兵的名字。。
接着，用户又输入，维州居民，出现500W个维州居民。。

我接到这些数据的时候，已经是XML形式了，用JAVA把XML提出来，放在向量里面， ...

北风

没有index，算法基本都是在scan而不是seek

bc

无论何种方式，把数据读一遍或者说解析一遍是免不了的，所以说，慢一定是慢在你自己统计的算法，而且我猜一定是慢在对你所使用的向量的定位上。这个向量（对不起，我不知道这个在JAVA中是个什么东西）我猜是一种数组。它必须有序才能快速定位。由于遍历完，又要对它们的出现次数进行排序，所以它们的次数的存放也必须有利于排序，这样才能提高效率，缩短时间。

righttang

原帖由 rogerk 于 2010-12-9 15:59 发表


如果你这个已经是app server了，那就应该在database里做。。还真的靠app一个个数阿。。除非你的数据不是从database里来的，比如时文本文件里来的。

其实我也想过在数据库里面做，不过我写的sqlquery更expensive
原因就在于，数据在存储的时候，同一列里面有逗号。而在计算的时候，逗号分隔的，要算两个。

比如说
Column A      Column B
John,Marry    Smith
John          Smith,Allen
Terry         Mark

当我对Column A统计的时候，得得出John有2个，Marry有1个的结论
如果用Sql 语句去“切”逗号，那真是噩梦啊。。。2分钟处理2000多个数据

我把以前的SQL拿出来看一看，要切的Column是docmeta表里的xUN_TAG，切成singleTAG，然后排序，实现是能实现。。。不过慢就一个字。。。感觉这样写sql，索引完全起不了作用。。。
select singleTAG, count(singleTAG)
from (select did, regexp_substr(str, '[^,]+', 1, level) singleTAG, level lv, lag(level, 1, 0) over (partition by did order by level) lg
from (select did, ','|| xUN_TAG str from docmeta where xUN_TAG is not null) connect by regexp_substr(str, '[^,]+', 1, level) is not null)
where lv != lg
group by singleTAG;

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

典

How about try XSL --- XPath 2.0 -- xquery)
you can use
sort
groupt by
count
distinct

大饼

抛开算法。
读取这个xml文件花了多少时间？

righttang

原帖由 大饼 于 2010-12-9 16:40 发表
抛开算法。
读取这个xml文件花了多少时间？

很快，这个XML，是DB直接返回的，在内存里，基本上没有延迟。

我如果遍历一边，不判断，就一个个读，大概2-3秒的样子。如果读了之后，再判断，然后统计，就要30-40秒

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

rogerk

原帖由 righttang 于 2010-12-9 16:13 发表


其实我也想过在数据库里面做，不过我写的sqlquery更expensive
原因就在于，数据在存储的时候，同一列里面有逗号。而在计算的时候，逗号分隔的，要算两个。

比如说
Column A      Column B
John,Marry    Smith
John         ...

靠，这都是什么倒霉数据阿。。这也能统计？

大饼

原帖由 righttang 于 2010-12-9 16:42 发表


很快，这个XML，是DB直接返回的，在内存里，基本上没有延迟。

记得当年数据结构课程设计。用586统计几十万个电话号码，也只要10秒不到

righttang

原帖由 rogerk 于 2010-12-9 16:43 发表


靠，这都是什么倒霉数据阿。。这也能统计？

呵呵，这个可是我们的selling point。当初为了考虑到 full text search，处于种种权衡，把Multi-value的attribute，以逗号分隔的形式，放在一列里面。
那样对于这一列，全文搜索引擎能够很好的进行全文索引。当然，这个是题外话。

这样做的结果就是，统计起来不方便了。。。

大饼

原帖由 righttang 于 2010-12-9 16:42 发表


很快，这个XML，是DB直接返回的，在内存里，基本上没有延迟。

我如果遍历一边，不判断，就一个个读，大概2-3秒的样子。如果读了之后，再判断，然后统计，就要30-40秒 ...

那就是算法的事情了。lz具体是怎么做的？

righttang

原帖由 大饼 于 2010-12-9 16:45 发表

记得当年数据结构课程设计。用586统计几十万个电话号码，也只要10秒不到

恩，不过数字比文字好弄点，唯一的又比不唯一的更好弄一点。。。

righttang

原帖由 大饼 于 2010-12-9 16:48 发表

那就是算法的事情了。lz具体是怎么做的？

新建一个数组，储存名称和统计数字
一个一个读，每读一个，先判断是否已经有了，如果有了的话，就对统计数字加一
如果没有，就在新的数组里多加一个记录。

算是最笨的办法了

general_tang

Hashtable行吗？key is the name, value is the count

righttang

原帖由 general_tang 于 2010-12-9 16:56 发表
Hashtable行吗？key is the name, value is the count

Hashtable完成后，可以按照count来排序吗？我记得好像不行的吧？还是我hashtable学得不好？

大饼

原帖由 righttang 于 2010-12-9 16:51 发表


新建一个数组，储存名称和统计数字
一个一个读，每读一个，先判断是否已经有了，如果有了的话，就对统计数字加一
如果没有，就在新的数组里多加一个记录。

算是最笨的办法了 ...

最笨的办法应该是先排序，然后一个一个读，并在新数组里添加纪录。最后再排序。说不定还比你的方法快。

GPS

同意楼上，hashtable是个简单好方法。否则就类似排序了。

general_tang

because i havn't use java for a long time, I can't remember there is any sort methods implemented for java  collections. if it has, transfer the values in hashtable to arraylist and sort it. In c#, it is doable.

take a look at http://mrtextminer.wordpress.com ... e-sorted-by-values/

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