品味生活

在实现koren论文的算法的时候我遇到了很多问题：

（1）针对大规模数据的时候（100M的打分数据），以前那种粗放型的使用cpu和内存的方法完全行不通，因为数据量大，算法和数据结构不考虑周到则时间和空间消耗都难以忍受。

（2）数据的初始化和参数的设置对结果有很大的影响，为了复现koren的结果，我第一个svd的程序大概花了2周时间才搞定，中间走了很多弯路，光调参数就花了4天。

（3）其他一些困难，此处省略1000字-_-……

为了减少推荐系统领域的朋友入门的难度，我将一些推荐算法的细节展现出来，通过代码的形式呈现给大家，给大家一个好的参照，使大家能尽快上手，减小入门的门槛，希望能为推荐系统领域的发展尽一些绵薄之力！希望有更多的人研究这个有趣且有用的领域！

代码说明：

(1)所有的代码都是用c++实现（c++效率高，对于像netflix dataset这么大规模的数据，脚本语言处理起来太慢）

(2)代码使用GPL V3协议发布，大家在使用的时候请保留版权信息。

(3)代码中肯定有很多不完善和错漏的地方，如果发现，请给我发邮件，也希望大家和我一起完善这个project。

一些有用的链接

(1) 新人第一步：快速使用本project的入门指南

(2) 获取本project中用到的netflix的测试集和训练集数据的方法：netflix数据预处理方法

(3) 在代码实现过程中遇到的问题

(4) knn算法执行的一些结果

(5) svd算法执行的一些结果

希望有更多的人加入这个project，将更多的算法代码贡献出来，比如目前尚缺RBM model，temporal model

想加入开发的或者交流的朋友可以从这里很方便的联系我:我的联系方式 或者直接给我发mail，honglianglv at gmai的邮箱

Project的地址： http://code.google.com/p/recsyscode/

ps: 这也是我的第一个开源项目，用了这么多的开源软件，今天算是迈出了回馈开源界的第一步，以后如果有好的东西我也会分享给大家

版权声明：本文某些内容来源于互联网，经过自己整理、编辑和总结成文，谢谢csdn，谢谢 google

vector和built-in数组类似，它拥有一段连续的内存空间，并且起始地址不变，因此
它能非常好的支持随即存取，即[]操作符，但由于它的内存空间是连续的，所以在中间
进行插入和删除会造成内存块的拷贝，另外，当该数组后的内存空间不够时，需要重新
申请一块足够大的内存并进行内存的拷贝。这些都大大影响了vector的效率。

list就是数据结构中的双向链表(根据sgi   stl源代码)，因此它的内存空间可以是不连续
的，通过指针来进行数据的访问，这个特点使得它的随即存取变的非常没有效率，因此它
没有提供[]操作符的重载。但由于链表的特点，它可以以很好的效率支持任意地方的删除
和插入。

deque是一个double-ended   queue，它的具体实现不太清楚，但知道它具有以下两个特点：
它支持[]操作符，也就是支持随即存取，并且和vector的效率相差无几，它支持在两端的
操作：push_back,push_front,pop_back,pop_front等，并且在两端操作上与list的效率
也差不多。

Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性map内部的实现自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能。

set是集合，set中不会包含重复的元素，这是和vector的第一个区别，第二个区别是set内部用平衡二叉树实现，便于元素查找，而vector是使用连续内存存储，便于随机存取。
因此在实际使用时，如何选择这几个容器中哪一个，应根据你的需要而定，一般应遵循下面
的原则：
1、如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
2、如果你需要大量的插入和删除，而不关心随即存取，则应使用list
3、如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque。

4、如果你要存储一个数据字典，并要求方便地根据key找value，那么map是较好的选择

5、如果你要查找一个元素是否在某集合内存中，则使用set存储这个集合比较好

参考文献：
1、http://topic.csdn.net/t/20011226/08/442147.html

2、http://41620935.blog.163.com/blog/static/498206420082185032531/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
int atoi(char *str);
int main(int argc, char* argv[])
{
 printf("%d",atoi("   +902d0asdf"));
}
 
int atoi(char *str)
{
 int i = 0;
 int sign = 1;
 for (;isspace(str[i]);i++) //跳过空字符
 ;
 sign = (str[i] == '-')?-1:1;
 if ('+' == str[i] || '-' == str[i])
 {
 ++i;
 }
 int result = 0;
 for(int n=0;isdigit(str[i]);n++)
 {
 result = 10*n + (str[i] - '0');
 i++;
 }
 return result;
}

6.计算fibanacci数列，给出递归和非递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <stdio.h>
#define N 8
int genFibnacci(int num);
int genFibnacciNoRecursion(int num);
int main()
{
 printf("%d\n",genFibnacci(10));
 printf("%d\n",genFibnacciNoRecursion(500));
}
 
int genFibnacci(int num)
{
 if(num == 0)return 0;
 else if(num == 1)return 1;
 else return genFibnacci(num-1) + genFibnacci(num-2);
}
 
int genFibnacciNoRecursion(int num)
{
 if(num == 0)return 0;
 else if(num == 1)return 1;
 
 int f0 = 0;
 int f1 = 1;
 int result;
 for(int i = 2;i<num+1;++i)
 {
 result = f0 + f1;
 f0 = f1;
 f1 = result;
 }
 return result;
}

7、将字符串变成int型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
int atoi(char *str);
int main(int argc, char* argv[])
{
 printf("%d",atoi("   +902d0asdf"));
}
 
int atoi(char *str)
{
 int i = 0;
 int sign = 1;
 for (;isspace(str[i]);i++) //跳过空字符
 ;
 sign = (str[i] == '-')?-1:1;
 if ('+' == str[i] || '-' == str[i])
 {
 ++i;
 }
 int result = 0;
 for(int n=0;isdigit(str[i]);n++)
 {
 result = 10*n + (str[i] - '0');
 i++;
 }
 return result;
}

8、CPU在上电后，进入操作系统的main()之前必须做什么工作？

（1）bios自检，检查硬件等

（2）读取MBR，转到MBR执行MBR代码，检查活动分区

（3）把活动分区的引导扇区的引导代码装入内存

（4）运行引导代码

（5）引导代码装入该分区的操作系统

（6）进入main（）

原文链接：http://blog.csdn.net/msccao/archive/2007/10/27/1848445.aspx

一。 new/delete 与 malloc/free 的区别

1。new自动计算需要分配的空间，而malloc需要手工计算字节数
2。new是类型安全的，而malloc不是，比如：
int* p = new float[2]; // 编译时指出错误
int* p = malloc(2*sizeof(float)); // 编译时无法指出错误

—— 以上两点只是改进，但以下两点malloc就无能为力了

new operator 由两步构成，分别是 operator new 和 construct
3。 operator new对应于malloc，但operator new可以重载，可以自定义内存分配策略，甚至不做内存分配，甚至分配到非内存设备上。而malloc无能为力
4。 new将调用constructor，而malloc不能；delete将调用destructor，而free不能。

通常 new 时干两件事，a. 为对应变量（或数组）分配内存。b. 调用相关构造函数。而 malloc() 只是为对应变量（或数组）分配内 存。而且当失败时表现不一样，malloc 失败返回 NULL，而 new 失败抛出异常，用返回值判断 malloc 是否成功绝对正确，而用返回的 值判断是否是 NULL 来判断对应 new 是否成功不是总是可靠（标准未规定）。

对应于 new 干的 delete 时也是干两件事 a. 调用对应对象的析构方法，b. 释放对应变量占用内存，free 只是释放对应的内存。

在 C++ 中可以重载 new 和 delete 操作符号（全局的或类自己的），而 malloc、free 无法重载。

new ,delete是c++对malloc，free的扩展。基本可以这样理解：
new 相当于：
T *ptr = (T) malloc( sizeof(T) ); //申请没有初始化的内存
ptr->T::T(); //调用构造函数初始化这块内存

delete 相当于：
ptr->T::~T(); //调用析构函数
free(ptr);//释放这块内存

二。指针和引用的区别

1.从现象上看：指针在运行时可以改变其所指向的值，而引用一旦和某个对象绑定后就不再改变
2.从内存分配上看：程序为指针变量分配内存区域，而引用不分配内存区域
3. 从编译上看：程序在编译时分别将指针和引用添加到符号表上，符号表上记录的是变量名及变量所对应地址。指针变量在符号表上对应的地址值为指针变量的地址 值，而引用在符号表上对应的地址值为引用对象的地址值。符号表生成后就不会再改，因此指针可以改变指向的对象（指针变量中的值可以改），而引用对象不能 改。

今天和室友以及师弟们讨论Builder模式的时候，提到了一种思想，就是利用覆盖父类中的某些函数，来解决生成不同对象的问题。

回来的路上对这个是否能在构造函数中实现动态绑定拿不定主意，回来后写了如下代码测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <IOSTREAM>
 
class Base {
public:
 Base();
 virtual void compose();
protected:
 virtual void A();
 virtual void B();
 virtual void C();
 
};
Base::Base()
{
 A();
 B();
 C();
}
 
void Base::compose(){
 A();
 B();
 C();
}
 
void Base::A()
{
 std::cout<<"in Base A"<<std::endl;
}
 
void Base::B()
{
 std::cout<<"in Base B"<<std::endl;
}
 
void Base::C()
{
 std::cout<<"in Base C"<<std::endl;
}
 
class Derived : public Base{
public:
 void B();
};
 
void Derived::B()
{
 std::cout<<"in Derived B"<<std::endl;
}
 
int main(int argc, char* argv[])
{
 //Derived *obj = new Derived();
 Base *obj = new Derived();
 obj->compose();
 delete obj;
 return 0;
}

输出结果如下：

in Base A
 in Base B
 in Base C
 in Base A
 in Derived B
 in Base C
 Press any key to continue

从输出结果可以看出在构造函数中无法实现动态绑定，但是在非构造函数中完全没有问题。
注：
如果在linux/unix中运行上述代码，需要将
“#include <IOSTREAM>” 改成 “#include <iostream>” (windows 不区分大小写）

linux/unix中编译方法：

gcc -lstdc++ -o build  build.cpp 或者 g++ -o build  build.cpp

运行方法：

./build

（加上-lstdc++在linux系统会自动在/usr/lib/下面中找stdc++.a stdc++.so.* ）