用Strassen算法(分治)计算矩阵乘法及python实现(一)

前言:

设A和B都是n*n的矩阵,那么我们可以很容易通过一个简单的分治算法得到乘积C=A·B,以下是其伪代码,它将接收n*n矩阵A,B,并返回它们的乘积C:

SQUARE-MATRIX-MULLTIPLY(A,B)
n=A.rows
let C be a new n*n matrix
for i=1 to n
     for j=1 to n
         c[i][j]=0
         for k=1 to n
               c[i][j]=c[i][j]+a[i][k]*b[k][j]

return C

显然三重循环中每一重都要执行n布,因此其时间复杂度为O(n^3),而Strassen算法的时间复杂度为O(n^log7),显然Strassen算法更优。

Strassen算法的核心思想是通过常数次的额外的矩阵加法来减少递归的次数,如果你对递归有所了解,那么你应该明白这种代价确实能够减少渐进运行时间。下面来介绍一下Strassen算法的步骤

Strassen算法的步骤

为简单起见,当使用分治算法计算矩阵积C=A*B时,假定三个矩阵均为n*n矩阵,其中n为2的幂。我们做出这个假设是因为在每个分解步骤中,n*n矩阵都被划分为4个n/2*n/2的子矩阵,如果假定n是2的幂,则只要n>=2即可保证子矩阵规模n/2为整数。

Strassen算法一共4个步骤:

  1. 将输入矩阵A、B和输出矩阵C分解为n/2*n/2的子矩阵。采用下标计算方法,此步骤花费O(1)时间。
  2. 创建10个n/2*n/2的矩阵S1, S2, … , S10,每个矩阵保存步骤1中创建的两个子矩阵的和或差。花费时间为O(n^2)。
  3. 用步骤1中创建的子矩阵和步骤2中创建的10个矩阵,递归地计算7个矩阵积P1, P2, …, P7。每个矩阵Pi都是n/2*n/2的。
  4. 通过Pi矩阵的不同组合进行加减计算,计算出结果矩阵C的子矩阵C11, C12, C21, C22。花费时间O(n^2)。

以上即为Strassen算法的简略步骤,至于具体步骤,敬请期待 用Strassen算法(分治)计算矩阵乘法及python实现(二)。

 

关于谷歌adsense申请的记录

最近终于申请成功了Adsense,特发此贴发表一下自己的感慨。

其实,这个服务器最初我并没有想来做网站,这只是我的一个魔法上网的小鸡(还是免费从gcp那里薅来的,详细可以看看这里:官方网站 ),顺便做离线下载服务器(这个以后可能有教程,敬请期待)。

不过实在是感觉太浪费了(吐槽一下:gcp的小鸡太贵了,流量还要收费),于是想着就随便做了一个网站。前前后后大概花了一周时间吧,终于做的能看了。下面来说说我是怎么申请到Adsense的吧。

其实我申请的过程并不算波折,看了不少其他网站的申请记录分享,甚至有申请23次之多的。而我一共也不过申请了2次,真的幸运。

第一次:

其实第一次申请时我自己都不觉得能通过,那时候整个网站的文章不过区区5篇,还都是水文,就急吼吼地提交了申请。

结果嘛,自然没有通过了,仅仅3天后就收到了拒绝的邮件:

不过这里吐槽一下,谷歌真的很严格的,以下是他们内容合作规范,就是禁止的一些内容:

成人内容
老少皆宜内容中的成人主题
危险或诋毁内容
与消遣性药物和毒品相关的内容
与酒精饮料相关的内容
与烟草相关的内容
与赌博和游戏相关的内容
与医疗保健相关的内容
与黑客和破解相关的内容
为用户操作提供报酬的网页
与虚假陈述相关的内容
惊悚内容
与武器相关的内容
助长欺诈行为的内容
非法内容

这就有很讨厌的一点了,谷歌不会告诉你网站到底哪里出问题了,只会让你去参阅内容政策或访问帮助中心。

第二次:

其实我在谷歌给我发邮件之后,几乎立刻就重新提交了申请(大概是受到了那位申请了23次的大佬的感召),不过其实我也没有报什么期望。

这次申请提交后就一直没有消息,天天去adsense上看,但都是灰色的

等了至少半个月了吧,一直都没有一点动静。突然前两天收到了邮件

以上就是我申请AdSense的全过程了,接下来只用照着谷歌给的教程投放广告就行了。

其实投放广告也不是为了赚钱,只是闲来无事做了一个,希望各位能够多点一点广告,能赚一点是最好的了。如果实在讨厌的话,就把广告屏蔽了吧(adblock plus应该没有人不知道吧)。

如果您支持本网站,请点一点广告。(如果发现有不良信息的广告,请通过telegram或邮箱提交给我)

本站已加入CDN加速

一直觉得网站打开的很慢,早就想申请一个CDN加速,无奈国内的CDN服务商都需要备案。作为一个新建站的小站长,自然没有备案号了。这件事也就不了了之。

不过最后还是忍不住了,就申请了一个CDN加速。我选择的是cloudflare,一家老牌CDN服务商。虽然是国外的,加速效果不如国内的理想,不过对我而言也是一个不错的选择了。

下面让我说说我是怎么申请的:

1.cloudflare简介

CloudFlare成立于2009年,是国外著名的免费CDN网站加速服务公司,CloudFlare 还提供实时安全保护服务和网络优化等,采用的是免费+增值模式,可以免费使用,也有收费服务。

CloudFlare的CDN节点主要分布于荷兰、美国、香港、法国、日本等国家和地区,使用CloudFlare在亚太地区的CDN节点可以大大加速你在美国或者欧洲的主机访问速度。

2.注册cloudflare

官方网站:dash.cloudflare.com

1.填写你的邮箱和密码,创建你的账号。

2.首次登录后就会进入引导界面,填写你要加速的站点,点击下方按钮即可

3.添加完网站后,cloudflare会提示要自动搜索你域名的解析记录,点击next确认,之后就会要求你选择服务方案,我们选择免费的即可,选好了确定进入下一步。

4.然后就进入到配置界面,你也可以手动添加或修改,支持A记录和CNAME记录,如像下边这样添加,可以添加上你所有的一级或二级域名,点击Add Record添加,点击Continue下一步。

5.根据自己的域名供应商的修改DNS教程修改自己的域名的DNS,我的域名是在万网购买的,去阿里云修改DNS即可。

6.修改好后就等待DNS修改生效就行了,生效时间各不相同,我的站点用了大概2个小时。

 

3.后话

以上就是我申请CDN加速的过程,真的很简单。其他的新站长朋友们如果还没有使用过CDN加速,可以来试一试。

常用的字符串处理函数

  • 1.字符串的输入和输出

  • scanf(格式控制字符串,输入参数表);

例:scanf(“%s”,s);(该函数遇回车和空格输入结束)

  • printf(格式控制字符串,输出参数表);

例:printf(“%s”,s);

  • gets(s)(输入的字符允许带空格)

 

  • puts(s)(输出时遇’\0’自动将其转化为’\n’)

2.字符串的复制,连接和比较及字符串的长度

  • 字符串复制函数char*strcpy(char*s1,char*s2)

参数s1必须是字符型数组基地址,参数s2可以是字符数组名或字符串常量

char s1[80],s2[80],a[80]=”hello”;

strcpy(str1,a); //把a中的字符串复制给str1

strcpy(str2,”world”);//把字符串常量“world”复制给str2

 

  • 字符串连接函数strcat(s1,s2)

char str1[80]=”hello”,str2[80],a[80]=”world”;

strcat(str1,a);//连接str1和a,结果为hello world

strcpy(str2,str1);//将str1中的字符串赋给str2

strcat(str2,”!”);//结果为hello world!

 

  • 字符串比较函数strcmp(s1,s2)

strcmp(“sea”,”sea”)的值为0,”sea’与”sea”相等

strcmp(“compute”,”compare”)的值(‘u’-‘a’)是个正数

strcmp(“happy”,”z”)的值(‘h’-‘z’)是个负数

strcmp(“sea”,”seat”)的值(‘\0-‘t’)是个负数

 

  • 字符串长度strlen(s1)例

strlen(“happy”)的值是5

p.s.

在应用标准库中的任何函数之前,必须提供函数原型。#include<string.h>

 

—–部分内容参考《c语言程序设计》(第三版)

 

 

 

 

本站已支持AMP

AMP——移动页面加速,是由谷歌公司启动的一个加快移动页面加载速度的项目。

AMP是一个开源项目,这项技术可以让移动端访问页面时加载更快。就目的而言,与百度启动的MIP计划非常相似,并且谷歌与百度两家公司也确实在移动页面加速技术上达成了共识与合作。

以后访问网站应该会快一点吧。

本站已支持https

刚刚脑子一抽,突然想起来了https这回事,就想给自己的网站添加上https。

无奈找到了一堆收费的SSL,一看售价都几千靠上,吓得我浑身一震。还好后来找到了一家免费的,成功获得SSL证书。这下又重新认识到了自己是有多蠢,一堆教程都看不懂(这tm是啥?)。还好我安装了bt面板,用上面的一键SSL安装好了。

虽然没能装13成功,不过还算凑合吧。

最后说一句,bt面板真好用。(希望bt能把广告费结一下。)

美滋滋

欸嘿嘿,今天弄了一整天,终于建好了自己的第一个博客。

说点啥好呢?

这几天连续换了四台小鸡,才有了今天的网站。Linux真的好难啊,为了给centos7安装python3把yum命令删了,找了一堆教程都下不回来(被自己蠢哭)。无奈又开了一台新的Ubuntu小鸡。

emmmm,就这样吧。

今天心情很好(假装没有作业)。