Rust入坑记 1:极有可能取代C++的21世纪语言

Rust 一致依赖以为Rust跟那个Ruby差不多,近期看了一下感觉Rust实际上应该是和C++匹敌的语言。而Rust作为21世纪最有可能与C++进行匹敌的对手也就是golang了。作为一个golang从入门到中级的中级段位手,我决定义无反顾的踏入Rust这个大坑,不是因为别的,只是因为Rust具有深度学习库!!!!

Rust安装

闲话不多说,既然决定采坑,那么请把Rust的环境高熟悉一下。这里是官方的书 the book of rust, 一句话安装:

curl https://sh.rustup.rs -sSf | sh

如果出现:

Rust is installed now. Great!

那么,牛逼的rust就安装好了!如果是windows,从这里 下载exe文件安装好。接下来是升级和卸载:

rustup update
rustup self uninstall
# get rust version
rustc --version

Hello Rust!

接着就是实现我们牛逼的hello world程序了。新建一个工程my_project, 然后新建一个main.rs文件,写入:

fn main() {
println!("Hello, Rust!");
}

然后编译:

rustc main.rs
./main

C++建造自用深度学习库二:从放弃到再次捡起来

这是对前面自己建造深度学习库的继续版本

上回说道,我想自己建造深度学习库,用纯C++实现,并且只用C++接口,但是由于基础设施并不是非常完善,几乎要放弃了。但是好在在我即将放弃的时候,我发现还是有可能搭建出来的。今天的主题就是在seth中实现反响传播。

反向传播公式推导

现在很多人搞深度学习,人工智能,但是我感觉能够推导反向传播公式的没有几个人。其中也包括我,既然明知不足,那就去把这个坑填一下。接下来我会用手工的方式来推倒一下反向传播公式。

在这里不得不称赞一下牛逼的typora markdown编辑器,要不是它,我想我无法继续创作。好闲话不多说,让我们直接开始今天的推到,前方一大波公式预警。

所有的一切起源于下面四个公式,我称之为神经网络反向传播四大公示:

$$\delta^L=\Delta_aC\odot\sigma’(z^L)$$ (BP-1)

$$\delta^l = (W^{l+1}\delta^{l+1})\odot\sigma’(z^l)$$ (BP-2)

$$\frac{\partial C}{\partial b^l} = \delta ^l$$ (BP-3)

$$\frac{\partial C}{\partial W^l} = W^{l-1} \delta ^ l$$ (BP-4)

OK, 上述四个公式便是牛逼的反向传播四大公式了,有了它就可以进行反向传播。但是在这里我就不一一推导了。比较简单,其中第一个公式是计算最后一层的梯度。那么这个最后一层的梯度就可以一层一层向前传播,使用公式2.

编程实现反向传播

既然公式已经出来了,那么就编程实现它吧。在这里有个问题,那就是这个梯度的维度到底是多少啊???我们在进行前向传播的时候,最终的误差应该是

C++ 经典算法集锦 二

C++经典算法实现系列2

上回我们说道,牛逼的C++可以实现很多牛逼的算法。我们继续之前的记录。

Algorithm 4. 二分查找

我们将实现一个二分查找的算法。
首先必须明白,二分法查找数毕竟满足:这堆数是保存在数组中,而且这堆数必须是有序排列,也就是需要要求有一定的顺序。之所以要求实在数组中,是因为,如果存在链表中,链表的存储不是连片的,
而数组是连片的,这样数组就可以非常轻而易举的通过下标index每个元素。其实我感觉C++里面好像都是用的数组吧。直接上代码吧:

int binary_search(int a[], int low, int high, int target) {
// binary search, search x in a
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (a[mid] > target) {
return binary_search(a, low, mid - 1, target);
}
if (a[mid] < target) {
return binary_search(a, mid + 1, high, target);
}
return mid;
}

这是比较简单的二分查找的递归实现。但是请注意,二分法其实是有要求的,那就是,查找的数组必须是升序。我感觉这样查找就没有啥意思了,要是有一个牛逼的查找算法可以在一个混乱的数组中定位一个元素那就比较牛逼了。
二分查找的局限性就发生在它的前置条件上,需要数组是有序的,然而大部分数组都是无序的,如果将数组构建成为有序数组,那么又有第二个问题,必须是数组,而数组在构建有序过程中其实是非常低效的,因为数组是连片存储,在移动和 插入过程中会有很大的开销。因此让我们接下来来实现一个二叉查找树算法。据说该算法既可以构建有序的集合又可以高效率的搜寻目标。

Algorithm 5. 寻找最大的K个元素

这个问题应该被归结为top k问题,而不是排序问题。这个问题有很多种解法,其中最简单的当然是先排序,然后再选取k个最大的数,还有一种解法是,使用快速排序的思想,具体如下:

1. 随机选择一个元素X,将数组S分为两部分,一部分全部大于X,一部分全部小于X,其实这就是快速排序的第一步;
2. 如果第一部分元素个数大于K,在继续在该部分查找K,重复1,直到元素个数等于K
3. 如果第二部分元素小于K,则在第二部分继续分开,查找剩下的K-T个元素;

这个算法简单易行,但是请注意,这个top K是无序的,时间复杂度为O(nlogK),这里我实现一个牛逼的基于模板的实现,事实上用模板更简单易懂一些:

#include <iostream>
#include <vector>
using namespace std;
// find top k implement by STL
vector<int>::iterator find_k(vector<int>::iterator begin, vector<int>::iterator end, int k) {
vector<int>::difference_type n = k;
if (end - begin <= k) {
return end;
}
auto left = begin;
auto right = end - 1;
srand(time(NULL));
int index = (int) rand() % n;
iter_swap(begin, begin + index);
while (left < right) {
// traverse right than left
while (*right <= *left && left < right) {right--;}
if (left < right) {iter_swap(left, right);}
while (*left > *right && left < right) { left++; }
if (left < right) {iter_swap(left, right);}
}
n = left - begin;
if (n + 1 >= k ) {
// if left element more than k, find from left
// TODO: why left + 1?
return find_k(begin, left + 1, k);
} else {
// if left element less than k, find the rest k- n
return find_k(left + 1, end, k - n - 1);
}
}
int main()
{
vector<int> a = {3, 56, 7, 89, 34, 12, 56, 39};
auto it_r = find_k(a.begin(), a.end(), 5);
for (auto it = a.begin(); it < it_r; it++) {
cout << *it << " ";
}
cout << endl;
return 0;
}

当然,这个问题还有一个清晰的解法,我把它叫做最小堆方法,它的思想是:

1. 首先随机选择K个数,然后从原数组中依次拿出一个数,和这里的每一个数进行比较,如果都小于,则pass该数,如果比某个元素大,就替换掉它,直到所有元素比完为止;

大家可以看到,这个算法非常简单,只需要一步,而且时间复杂度是:O(n*K),不仅如此,这个算法的空间复杂度也很低,只需要把K个元素装入内存即可,其他元素只需要读取。这个算法我就不写出实际实现额。相反还有一个有意思的算法,也就是二分法来实现它。
二分法之前业实现过。二分法的思路是:

1. 首先我们要知道整个数组的最大值和最小值以及数组长度,然后先从中值开始,如果mid~max个数大于K,则在mid~max继续寻找,mid变成min
2. 如果mid~max个数小于K则在min~mid继续寻找,mid变成max,不断的缩短区间,知道max-min=1;

二分法实现的思想也很简单,但是实际上,在实际问题运用中不好用。首先我觉得你必须要知道最大值最小值有时候并不太现实。这个算法复杂度也是O(n*K).

C++建造自用深度学习库一:Eigen3从入门到花式写卷积

金天,写于北京中关村,想自己建造一套人工智能框架,遂从这里开始一个系列,C++实现

Eigen3 导入和安装

首先必须说明,eigen3好像我目前还没有找到比较好的安装方式,也许从apt可以直接安装,但是没有测试。下面这段代码是将eigen3安装到/usr/local/include 下面,因为eigen里面都是头文件实现的,因此直接cp到include下面即可,也是非常的方便。

cd ~/Downloads
wget http://bitbucket.org/eigen/eigen/get/3.3.4.tar.bz2
sudo tar -xvjf ~/Downloads/3.3.4.tar.bz2 -C /usr/local/include
sudo mkdir /usr/local/include/eigen3
sudo mv /usr/local/include/eigen-eigen-*/Eigen /usr/local/include/eigen3

然后在cmake里面或者说直接在c++源文件里面都可以直接include,如果使用cmake编译的话应该这样:

find_package( PkgConfig )
pkg_check_modules( EIGEN3 REQUIRED eigen3 )
include_directories( ${EIGEN3_INCLUDE_DIRS} )

这样就可以自动自动find eigen这个package了。

Eigen3 - 让我们实现一个一层的神经网络吧

既然是自己动手实现神经网络框架,那实现一个一层的神经网络应该是必须要完成的事情。实现神经网络其实也不难。经典公式:

y = W*x + b

我们需要其实就是这个W的矩阵,我们给一对数据x和y,计算W*x + b和真实y的差值,然后再根据一个公式,使用误差来更新W,也就是我们的损失函数?(窝草,看来还挺麻烦,这里的怎么进行反向传播的?)。不管怎么说,让我们先用eigen来写一个层吧。

从开始到放弃

由于写到一半发现这个牛逼的Eigen库根本不支持多维的矩阵,于是乎只能作罢,看来在c++里面构建一个类似于numpy一样的多维矩阵库还是一件非常麻烦的事情啊,如果同志们有好的建议可以向我提一下。

C++ 算法精研系列一

C++算法精细研究系列

经典问题一

这个问题其实很经典,简而言之,就是一个数组中,有正有负,求取一个和最大的连续子数组。

这几天在看算法,都得过一遍,但是要领会算法里面的思想,所有代码都用c++实现。首先咋一看这个问题,我们先不管最优算法是如何实现的,直接一顿暴力计算怎么样?
思考一下,暴力计算其实很简单,比如我们有数组:

int a[10] = {-1, -2, 2, 9, 2, -4, 2, -1, -9, -3};

那首先我们要遍历一下数组a,在每一个子循环里面,从i->a.size,遍历,i->a.size中的每个j,求取i->j的子序列和。三个遍历应该就可以把所有情况便利玩。
直接上代码了:

void findMaxContinueSeq(int* result, int a[], int size){
// result, returns the bounds and max sum, size is the a list size
int maxSum = 0;
int sum=0;
int maxStartIndex = 0;
int maxEndIndex = 0;
for (int i = 0; i < size; ++i) {
for (int j = i; j < size; ++j) {
for (int k = i; k < j; ++k) {
sum += a[k];
}
if (sum > maxSum) maxSum = sum, maxStartIndex = i, maxEndIndex = j-1;
sum = 0;
}
}
cout << "max sum: " << maxSum << endl;
cout << "max start index: "<< maxStartIndex << endl;
cout << "max end index: "<< maxEndIndex << endl;
}

我们设置两个标志位,一个是最大序列的起始一个是终止,起始出现的位置就在当和比暂存器大的时候,把这时候的i记录下来,终止就是j。
这个算法起始也很简单的。但是时间复杂度是o(n^3),因为要遍历三个循环。

接下来我们看一个只需要一次循环就可以解决的算法。
这个最优算法,起始道理也是很简单,我就是遍历一次,首先假设一个b=0,每次加一个数,我都用b+a[i],然后我都判断一下,加完之后是大于0还是小于0,
如果小于0,那很显然,就抛弃b,把b重置为a[i]从新开始一个序列,加入不小于零,在判断一下b和暂存的最大值大小,如果大,就把暂存最大值更新,小就不管了。
这个算法其实用到了呀一个双重保险的思想,即首先添加一个数如果变成了负的,我就终端这个序列,重头开始,如果没有,再判断一下加了之后是变大了还是变小了,如果变大了就更新,没有就保存之前的值,实际上如果没有变大了说明加了一个负数,但是还没有小于零,没有小于零说明还有希望加到一个更大的正数,因此,不到b小于零都不要中断这个序列,一直加下去,实在是小于0了在重置b,开始下一个序列。
仔细想一下,这个算法其实,就是基于一个非常简单的假设:序列有正有负,最大和的序列一定大于零,既然如此那我就一直加,如果大于就更新不大于继续加,知道小于零就更新序列。
代码如下:

void findMaxContinueSeqOptimal(int* result, int a[], int size){
//算法思想很简单,首先最大值一定大于0,那么每次加一下下一个元素,我就
//判断一下,上一个和,如果小于零则直接把b重置,否则加上下一个元素
int sum=0;
int b=0;
int maxStartIndex = 0;
int maxEndIndex = 0;
for (int i = 0; i < size; ++i) {
if (b<0){
b = a[i];
maxStartIndex = i;
} else{
b += a[i];
}
if (b>sum){
sum = b;
maxEndIndex = i;
}
}
cout << "optimal max sum: " << sum << endl;
cout << "max start index: "<< maxStartIndex << endl;
cout << "max end index: "<< maxEndIndex << endl;
}

最后我们调用代码来测试一下:

int main() {
int a[10] = {-1, -2, 2, 9, 2, -4, 2, -1, -9, -3};
int b;
findMaxContinueSeq(a, a, 10);
findMaxContinueSeqOptimal(a, a, 10);
return 0;
}

两个函数返回的结果是一致的。


Powered by 萝莉萝莉 and Sia

Copyright © 2017 - 2018 Jin Tian All Rights Reserved.

访客数 : | 访问量 :