另类四则运算之大整数加减法：


十进制的数值运算在计算机里都将转换成二进制的数值运算，而二进制的运算就是cpu中最根本的逻辑运算，最后再转化成十进制输出。这次介绍的方法是保留十进制的运算方式（小学生的列竖式计算），仅仅将每位数字转换成二进制。这种算法既在速度上有所提升，又能克服单个数据存储大小的限制。因此可以用来进行大整数的加减法（大整数通常指16位或32位以上整型数）。至于竖式计算的原理就不说了哦，不然有损大家的智商！
 

核心：模拟竖式计算，将大整数的每一位分开来存储与计算。
 
C语言完整程序：


//大整数加法：

#include

#include

char a[100],b[100];

int c[100],d[100];

int main()

{

        
int m,n,i,j;

        
scanf("%s %s",a,b);

        
m=strlen(a);

        
n=strlen(b);

        
for(i=0;i<=m-1;i++)

        
c[i]=a[m-1-i]-'0';

        
for(i=0;i<=n-1;i++)

        
d[i]=b[n-1-i]-'0';

        
for(i=0;i<=99;i++)

        
{

                  
c[i]+=d[i];

                  
if(c[i]>=10)

                  
{

                           
c[i]-=10;

                           
c[i+1]+=1;

                  
}

        
}

        
for(i=99;i>=0;i--)

        
{

                  
if(c[i]!=0)

                  
{j=i;break;}

   
}

   
for(i=j;i>=0;i--)

   
printf("%d",c[i]);

}






//大整数减法：

#include

#include

char a[100],b[100];

int c[100],d[100];

int main()

{

        
int m,n,i,j;

        
scanf("%s %s",a,b);

        
m=strlen(a);

        
n=strlen(b);

        
for(i=0;i<=m-1;i++)

        
c[i]=a[m-1-i]-'0';

        
for(i=0;i<=n-1;i++)

        
d[i]=b[n-1-i]-'0';

        
for(i=0;i<=99;i++)

        
{

                  
c[i]-=d[i];

                  
if(c[i]<0)

                  
{

                           
c[i]+=10;

                           
c[i+1]-=1;

                  
}

        
}

        
for(i=99;i>=0;i--)

        
{

                  
if(c[i]!=0)

                  
{j=i;break;}

   
}

   
for(i=j;i>=0;i--)

   
printf("%d",c[i]);

}
							
		

#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
#define MAX 100
 
 
int main()
{
	string std1, std2;
	cin>>std1>>std2;
	int length1 = std1.length();
	int length2 = std2.length();
	int a[MAX] = {0};
	int b[MAX] = {0};
	int result[2 * MAX] = {0};
	int i = 0, j = 0;
	//将字符串转移到数组中，以方便计算 ，注意是倒叙存储
	//即字符串123存为321，为的是将低位放在前面方便计算
	for(i = length1 - 1, j = 0; i >= 0; i--, j++){
		a[j] = std1[i] - '0';
	}
	for(i = length2 - 1, j = 0; i >= 0; i--, j++){
		b[j] = std2[i] - '0';
	}
	//将结果储存在 resullt中，result[i + j] = a[i] * b[j]
	for(i = 0; i < length1; i++){
		for(j = 0; j < length2; j++){
		result[i + j] += a[i] * b[j];
		}
	}
	 
	//从低位到高位进行进位
	for(i = 0; i < (length1+length2); i++)
	{
		if(result[i] > 9){
			result[i+1] += result[i]/10;
			result[i] %= 10;
		}
	}
	//将前导0全部剔掉，比如我们结果是236，在result中
	//是这样存储的63200……我们需要定位到第一个不为零的数，它的位置也就是i ，两数相乘，位数最多是两数位数之和
	 
	for(i = length1 + length2; i >= 0 ; i--){
		if(result[i] == 0) continue;
		else break;
	}
	//接着i继续输出，就是我们的结果
	for(; i >=0; i--)	cout<<result[i];
	return 0;
}

A*算法求解迷宫寻路问题
实验内容
设置相关数据
设置两种地图
设置两种启发式函数
性能分析
分析不同起点终点
分析不同启发式函数
分析不同地图
总结
附录代码


A*算法求解迷宫寻路问题资源链接如右：A*算法求解迷宫寻路问题

实验内容
在一个n×m的迷宫里，入口坐标和出口坐标分别为(startx,starty)和(endx,eny)，每一个坐标点有两种可能：0或1，其中0表示该位置允许通过，1表示该位置不允许通过。以寻路问题为例实现A*算法的求解程序，设计两种不同的估价函数。
设置相关数据
设置两种地图
根据题意，用矩阵设置两个地图。

地图1：设置5行5列的迷宫，代码如下：
a = np.mat([[0, 0, 0, 0, 0], 
            [1, 0, 1, 0, 1], 
            [0, 0, 1, 1, 1], 
            [0, 1, 0, 0, 0], 
            [0, 0, 0, 1, 0]])

地图2：设置20行20列的迷宫，代码如下
a = np.mat([[0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1], 
            [0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1], 
            [0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1],
            [0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1],
            [1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1],
            [0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1],
            [0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1],
            [1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1],
            [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1],
            [0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0],
            [0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1],
            [0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1],
            [0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1],
            [1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
            [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
            [0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
            [0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0],
            [0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0]])


设置两种启发式函数
定义估价函数

$f(n)=g(n)+h(n)$

式中，$g(n)$为起点到$n$状态的最短路径代价的估计值，$h(n)$是$n$状态到目的状态的最短路径代价的估计值。

令$g(n)$为起点到$n$状态的曼哈顿距离，代码如下：
def gs(i, j):
    return abs(i - startx) + abs(j - starty)

定义两种启发式函数。

启发式函数$h_1 (n)$：$h_1 (n)=10×(|n_x-endx|+|n_y-endy|)$，代码如下：
def h1(i, j):
    return 10*(abs(i - endx) + abs(j - endy))

启发式函数$h_2 (n)$：$h_2 (n)=(n_x-endx)^2+(n_y-endy)^2$，代码如下：
def h2(i, j):
    return pow(i - endx, 2) + pow(j - endy, 2)

性能分析
分析不同起点终点
采用地图2，具体如下图1，启发式函数$h_1$进行分析，分别设置起点为（0，0）和（9，5），终点为（20，20）、（18，20）。


（0，0）→(20,20)的路径如图2，（9，5）→(18,20)的路径如图3。





两次寻路过程的性能分析如下表1。




路径
（0，0）→(20，20)
（9，5）→(18，20)




扩展节点数
107
80


生成节点数
79
59


运行时间
0.001601705298526
0.000871252588694


由上述图表可知路径延长后运行时间会相对变长，扩展节点及生成节点也会相应增多，且两次寻找的路程有重合的部分，所以寻找到的路径为较优路径。
分析不同启发式函数
采用地图2，启发式函数$h_1，h_2$进行分析，设置起点为（0，0），终点为（20，20），两次寻路过程的路径，扩展节点数、生成节点数和运行时间分别如下图4，图5。




由图表可知，两种启发式函数所用时间相近，但$h_2$相比$h_1$所扩展的节点数和生成的节点数会减少，仔细分析可以发现启发式函数$h_2$陷入的凹路径会少一些，更接近最优路径，但在远离目标点的路径行进时还是会陷进凹路径。
分析不同地图
上述过程一直采用地图2进行实验，为验证程序的普适性，现采用地图1进行实验。经过分析，选择上述较优的启发式函数$h_2$进行分析。寻路问题初始节点为（0，0），目标节点为（5，5），寻路路径如图5。



应用启发式函数$h_2$对地图2的寻路路径彩绘图如下（因显示问题，第一行略去）。


汇总上述性能报告如下表2。




地图
启发式函数
扩展节点数
生成节点数
运行时间




地图1
$h_2$
14
13
0.0001113599


地图2
$h_1$
107
79
0.0008827725


地图2
$h_2$
103
71
0.0007970126


总结
A*算法在地图寻路问题中具有很好的优势，相比宽度优先搜索，效率更高，所耗时间更少，相比深度优先搜索，可以解决其不能找到最优解的不足，具有较高的应用价值。该算法的重点及难点就是启发式函数的选择，通过上述实验，可以发现启发式函数$h_2$相比$h_1$效果更好，但仍存在一些问题，需要继续找寻更优的启发式函数。
附录代码
主程序代码如下，其中用到的方法和地图在上述代码中已定义，故不再给出。设置不同的起点与终点需相应的更改startx,starty和endx,endy的值。
b = a
startx, starty = 1, 1
i = startx - 1
j = starty - 1
endx, endy = 20, 20
Open, Close = [[i + 1, j + 1]], [[i + 1, j + 1]]
Opens = [[i + 1, j + 1]]
road = 100
start = time.clock()
while(Open != []):  
    if(Open[-1] != [endx, endy]):
        Open = []
        minf = 10000
        if(i + 1 < len(a) and a[i + 1, j] == 0):
            f = gs((i + 1), j) + h2((i + 1), j)
            if([i + 2, j + 1] not in Close):
                Open.append([i + 2, j + 1])
            if(f < minf):
                minf = f
                i1 = i + 1
                j1 = j
        if(i - 1 >= 0 and a[i - 1, j] == 0):
            f = gs((i - 1), j) + h2((i - 1), j)
            if([i, j + 1] not in Close):
                Open.append([i, j + 1])
            if(f < minf):
                minf = f
                i1 = i - 1
                j1 = j
        if(j + 1 < len(a) and a[i, j + 1] == 0):
            f = gs(i, (j + 1)) + h2(i, (j + 1))
            if([i + 1, j + 2] not in Close):
                Open.append([i + 1, j + 2])
            if(f < minf):
                minf = f
                i1 = i
                j1 = j + 1
        if(j - 1 >= 0 and a[i, j - 1] == 0):
            f = gs(i, (j - 1)) + h2(i, (j - 1))
            if([i + 1, j] not in Close):
                Open.append([i + 1, j])
            if(f < minf):
                minf = f
                i1 = i
                j1 = j - 1
        b[i, j] = road
        road = road + 1
        i = i1
        j = j1
        Close.append([i + 1, j + 1])
        Opens.extend(Open)
    else:
        end = time.clock()
        b[endx - 1, endy - 1] = road + 1
        print("最短路径寻找成功，路径为：")
        for l in range(len(b)):
            for m in range(b[0].size):
                #0表示format中第一个元素，>表示右对齐输出，3表示占三个字符
                print("{0: >4}".format(b[l, m]), end = '')
            print('')
        print("扩展节点数为：", len(Opens))
        print("生成节点数为：", len(Close))
        print('用时为:', end - start)

        print('Close表为:', Close)
        print("点的移动轨迹为：")
        for k in range(len(Close)):
            if(k < len(Close) - 1):
                print(Close[k], "-->", end = '')
            else:
                print(Close[k])

        break
if(Open == []):
    print("最短路径寻找失败，失败位置为：", Close[-1], "路径为：", Close)

列存储不同于传统的关系型数据库，其数据在表中是按行存储的，列方式所带来的重要好处之一就是，由于查询中的选择规则是通过列来定义的，因此整个数据库是自动索引化的。按列存储每个字段的数据聚集存储，在查询只需要少数几个字段的时候，能大大减少读取的数据量，一个字段的数据聚集存储，那就更容易为这种聚集存储设计更好的压缩/解压算法。
传统的行存储和列存储的区别
 
1、数据是按行存储的 
2、没有索引的查询使用大量I/O 
3、建立索引和物化视图需要花费大量时间和资源 
4、面对查询的需求，数据库必须被大量膨胀才能满足性能需求
 
1、数据按列存储–每一列单独存放 
2、数据即是索引 
3、只访问查询涉及的列–大量降低系统IO 
4、每一列由一个线索来处理–查询的并发处理 
5、数据类型一致，数据特征相似–高效压缩

列式数据库
什么是列式数据库？可能大家也才到了，既然有列式数据库，那么肯定就有行式的喽！确实是这样的。也许大多数人并不了解数据库储存模型（storage model）和数据库的数据模型（data model），不过对上层是使用者也没多大关系。不过我们现在讲的列式和行式就是指数据库的storage model，而他们支持同样的data schema，即对data model感知不到storage model的实现区别。 
一个数据库的data model约定可以进行上层数据操作，而storage model决定这些操作的性能。比如，No Sql数据库使用的是data model是key-value，而储存模型有map结构实现，也可以由tree结构实现。而对于sql数据库，其数据模型是一张二维表，而至于怎么存储这张二维表，很容易就可以想到可以按行存储和按列储存。按行存储就是我们现在常见操作型数据库，而是最大众的数据库，比如MySql、Oracle、……等等你所知道大部分数据库。而按列储存的数据库现在也是很有名，比如Hive、Vertica、Druid、Infobright等。
为什么要行式数据库又要列式数据库？
先让让我们想象关于二维表我们有哪些操作？—— select、update、delete和insert。这些操作都会需要找到相应的位置，所以这些操作的基础都是search。 
而基本的算法都是即从时间考虑也是从空间考虑的。我们开始具体举个例子。
在数据库储存作为实际的一堆储存在磁盘上的文件，在设计不得不考虑磁盘的特性。一般的磁盘特性，其实所有的储存都有一个特性就是对于locality良好的存取性能是随机存取的好几倍。我们现在把一块想像成一组固定大小的块，如图： disk logic model 而文件的内容实际会被分开按照磁盘逻辑块来储存，数据库主要任务就是怎么组织这些逻辑块来取得更好的读取性能和便捷性。 
在不考虑索引的情况下，所有的磁盘读取都是顺序读取，这意味了要查找一个东西，都需要扫描全表或者部分表。很直观的道理，读取的性能就是取决于扫描的范围。范围越大，速度当然越慢。 
我们先假设我们有一堆如下的数据：
RowId
EmpId
Lastname
Firstname
Salary
001
10
Smith
Joe
40000
002
12
Jones
Mary
50000
003
11
Johnson
Cathy
44000
004
22
Jones
Bob
55000
行式储存模型
好现在我们开始让磁盘里塞，假设我们的磁盘块只能容下5个字段（抽象的，假设我们的这些字段的大小都一样），因为我们是按找行优先的，所以结果就如下： 
于是当我们要找Jones的所有信息的工资时候，我们会依次从第一块磁盘块直到扫描到最后（为什么要扫到最后，因为是在找全部叫Jones的信息，所以不扫都最后都不能确定是否会遗漏）。一共需要扫4块，然后取出其第二块和第四块信息，找出其工资的信息。
其实基于行式储存，对于where语句处理都需要处理全表。对于磁盘的不停seek，速度就可想而知。当然一般数据库为了应对这种全数据扫描，找到了建立索引的方法。而索引就是对某个或者某些字段的组合的信息，即取出数据的部分信息，以减少每次扫描从全表到部分信息的扫描的过渡。
这种查询方式很适合于一次取出一个行数据，而对于日常应用系统来说这种方式是非常合适的，因为我们设计应用的时候都是针对一个事务，而我们会把一个事务所有属性存储成一行，使用的时候也是有很大的概率涉及到整行的信息，很利于做缓存。还比如我们经常使用的那些经典sql 语句：
select * from user where id = 1001;
select id, user_name, email, address, gender, ... from user where id = 1001;
1
2
！！还敢不敢列出些更多的字段！！
列式储存模型
而列储存就是下图这种按列优先储存。为了方便我们每块只储存了一个一列，没有存满。 

这下我们再考虑上面的查找所有Jones的工资，这下我们只扫描第三个磁盘块，找出Jones都再那些行，然后根据查出来的行号，直接去第五块磁盘（这块对应的式salary列）找出第二、四行的数据，然后输出。一共2次seek。大大小于row－oriented的4次。
这种查询方式的前提就是你就需要这列数据就行了，其前提假设就是查询基本不会使用这个行的其他列数据。显然这种假设对于日常操作系统的围绕着一个主题进行的活动是不合适旳。但是却在分析型数据大显身手。
列式的另一大优势是压缩。因为列的天然凝聚性（比如上面的两个Jones就可以压缩成一个）大大强与行，所以列式储存可以有很高的压缩比，这个进一步使使用的磁盘的数量减少，因为使用的磁盘块少，进一步减少了需要扫描的次数。这方面很利于加快查找速度，但是因为解压缩也是耗时耗内存的过程，所以压缩的控制也是需要一个定平衡点。
优劣总结
从上面的例子可以明显看出列式数据库在分析需求（获取特点——每次查询几个维度，通常是）时候，不仅搜索时间效率占优势，其空间效率也是很明显的。特别是针对动辄按T计算的数据量来说，在分布式环境中能进行压缩处理能节省宝贵的内部带宽，从而提高整个计算任务性能。