回复： 回复： 算法求助

[尖头鳗]

redis是一个内存数据结构服务器， 支持list set map hashtable 等数据结构，可以大致满足你的要求。接口丰富c、python啥都有。

------------------ 原始邮件 ------------------

发件人: "余露"<cool...@gmail.com>;

发送时间: 2012年6月12日(星期二) 中午1:55

收件人: "yuntable"<yunt...@googlegroups.com>;

主题: Re: 回复： 算法求助

redis是？

我是用C写的，木有什么比较好用的神器

2012/6/12 尖头鳗 <lhua...@qq.com>

有24w商品，那每个商品的购买用户列表必然很稀疏。

 

用redis把你的原始数据存进来就ok了。

------------------ 原始邮件 ------------------

发件人: "周龙亭"<njdra...@gmail.com>;

发送时间: 2012年6月12日(星期二) 中午1:47

收件人: "yuntable"<yunt...@googlegroups.com>;

主题: Re: 算法求助

100W的数据，全部放在内存里就行。

建两个Hash表，

1. uid --> product_id

2. product_id  --> set of uid

在 2012年6月12日 下午1:42，余露 <cool...@gmail.com>写道：

我的错，忘记说明下我的问题了。

是这样的，我在实现一个推荐算法----协同过滤（CF）

数据是二元的，第一列是用户ID，第二列是用户购买过的商品ID，整个数据表明了用户和他所购买过的商品信息

我先要计算每个用户的邻居，也就是跟他购买过相同商品的人，然后通过这些邻居预测目标用户对没有购买过的商品的打分。

我的数据集中数据记录有100多万条，10000个用户，24万多商品，数据集并非数据库，可以通过普通的编辑器就能打开的文件。每条记录格式：

123  456

123 45678

123 23679

......

计算主要消耗在寻找相似用户，预测商品打分上了

我目前没有太好的数据组织方式

我的方式：

1，分别为用户和商品库建立一个链表，每个用户节点包涵了三个链表：购买过的商品，自己的邻居，推荐列表

2，通过查找不同用户和目标用户之间是否购买过相同的商品计算他们的相似度

3，找完自己的邻居后，就开始对商品库中的商品进行预测打分

用户和商品库都是通过简单的单链表进行组织，经常进行循环查找，费时的很。

吴工有啥比较好的方法吗，有好的处理工具推荐一下也好。苦思中....

余露

2012/6/12 吴朱华 <ike...@gmail.com>

很多的计算？ 主要是那些计算？

如果不知道如何使用这些数据，那么就很难选择合适的算法了

在 2012年6月12日 上午10:05，余露 <cool...@gmail.com>写道：

大家好：

   大概有100多万条的数据，要经过很多的计算，让他们推荐几个算法，有名字就行呀，当然各位要是不吝啬笔墨的话，那就更谢谢啦。

真心没头绪，光自己想到的也就是用下二叉树，或者链表的形式组织数据了，没有数据库，只有数据文件

单条数据记录格式：

123 345

134 56789

........

余露

--
Cheers！
人云科技 PeopleYun.com
只有掌握和控制最核心的云计算技术，才能在这场巨大的浪潮中处于主导！！！

[余露]

太好了，谢谢了尖头鳗。

几万行的代码量，下去研究下。

2012/6/12 尖头鳗 <lhua...@qq.com>

[吴朱华]

你先试试，如果有问题再沟通，这里的大牛很多^_^

[余露]

   酱油很久了，平时看你们的问题，基本不会。

在学校也没啥机会接触云计算的东西，再次感谢各位的回帖，呵呵。

2012/6/12 吴朱华 <ike...@gmail.com>

[余露]

大家好，继续上次的话题，这次有一个23万多个节点的链表每个节点都有一个Value，就先代号Item吧，想按照这个Value进行排序，苦思了很久（排序方面的知识有限，没有什么经验），没有找到较高效的排序方式。

我的处理方式：

      新申请一块大小想通的空闲链表（freelist）和一个已用链表的头节点( usedlist 包涵有链表长度信息 )，然后没从item上取一个节点，用于初始化usedlist。在每次插入节点到usedlist的时候，都会将新进入的节点与其他节点的Value进行比较，然后找到合适的插入位置，这样能够保证链表是按照Value值降序排列的。

      但是在面对23万多个节点的时候，消耗时间还是很长的，最长达到了900多秒，算法方面的菜鸟，这次是初次遇见这种情况，所以上来想请教下大大们，不知道有什么比较好的速度较快的排序工具，最好能在100秒以内搞定，那就太爽啦。

余露

2012/6/12 余露 <cool...@gmail.com>

[余露]

不好意思哈，忘记说了，自己是用C语言写的

2012/6/20 余露 <cool...@gmail.com>

[潘志铭]

链表的插入排序肯定是最慢的时间复杂度大于n。换一个数据结构和排序。

可以考虑用堆排序

[吴朱华]

可以试试qsort，理论上23万个key/item的排序应该一秒之内，zhiming思路也可以

发自Ike's Galaxy Note

[余露]

嗯是的，使用快排速度很快，自己写了一个，因为自己的数据中有很多是相同的，会照成堆栈溢出，在排序之前就对数据进行了处理。谢谢各位啦！~

2012/6/25 吴朱华 <ike...@gmail.com>

[Colin Shi]

链表插入排序的时间复杂度是n^2吧？

不知道radix sort适合他的情况不？

[吴朱华]

堆栈溢出？ 这种事情我从来没碰到过，你可以直接试试libc自带的qsort

[余露]

是的，在不同的数据集下测试了下，同样的数据个数，当数据集中的数据有序的数据个数达到一定量（我的情况是达到了8万个相同的数据，比如我的数据集中有8万个 value为0的数据）的时候就会堆栈溢出，我是采用递归的方式做的，可能会因为递归层次太深造成堆栈溢出。当数据集的有序个数很少的时候，就能很顺利的执行，这样递归次数就会比较少了。至于qsort也会有同样的情况发生。

2012/6/26 吴朱华 <ike...@gmail.com>

[Marco]

python的实现中， 如果递归次数太多， 虚拟机会抛出 maximum recursion depth exceeded

2012/6/27 余露 <cool...@gmail.com>

--
LinuX
Violin
Canon EOS

[余露]

是的，Python会报递归次数太多的错，不过在C语言中木有这样的错误扑捉呀。如果采用系统自动分配堆栈的话，有最大堆栈值吗？

2012/6/27 Marco <chopi...@gmail.com>

[吴朱华]

应该只有Kernel才会有 递归次数 的限制，具体的出错信息是什么，libc的qsort试过没有？

[余露]

程序运行的时候没有出错信息，我是用Codeblocks调试的，运行的时候是直接程序奔溃了。

2012/6/27 吴朱华 <ike...@gmail.com>

[余露]

libc的qsort也试过了，同样会奔溃那。

2012/6/27 余露 <cool...@gmail.com>

[Marco]

那你需要自己count ++啊

内存总是有限的， 很多单片机还没有堆栈结构呢

2012/6/27 余露 <cool...@gmail.com>