用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加速,可以来试一试。

美区Apple ID注册方法

1.为什么要注册美区id

1.美区是app数量最多的区,很多中国区没有或者下架了的app美区都有!
比如小火箭,这也是我注册美区id的主要原因。

2.有些app仅限美区id限免!(推荐一个telegram频道:t.me/limitfree,经常发布限免软件。)

2.如何注册美区id

前两年的时候,注册一个美区apple id非常容易,不用付款选项,分分钟就注册好了。不过现在苹果审核越来越严格,以前的方法已经行不通了。建议各位尽早注册一个。

以下为具体步骤:

到这里,注册美区apple id算是搞定了!后面就剩去iPhone\IPad激活账号下载app了!

3.后续

美国区有不少好应用是需要购买的,这时候只需要进入app store修改付款信息即可。一定不要选择credit card,一定不要选择credit card,一定不要选择credit card!credit card使用非常麻烦,而且只有美国信用卡可以用,国内的VISA/Mastercard都不行的。

推荐直接购买itunes礼品卡,可以选10~100刀,官网地址:www.apple.com/shop/gift-cards

或者你也可以使用美国区的PayPal,我们下次再说。

一个EDU邮箱能做什么?

前一段时间,我去学校的网络管理中心申请了一个edu邮箱,并且薅了不少羊毛。今天就来分享一下我的战果。

1.GitHub学生包

 

这简直就是一份大礼,具体有:

可用工具

  • ATOM:

来自21世纪的可定制文本编辑器
详细优惠信息: 由GitHub开源,人人可以免费使用。

  • 一键安装云端应用程序

详细优惠信息: 一年Business 3 方案(通常49美元/月)

  • crowdflower

众包及数据富集平台
详细优惠信息: 可以使用Crowdflower平台(通常2500美元/月)

  • DigitalOcean

简单的云主机,为开发者而设
详细优惠信息: $50平台账户代金券

  • DNSimple

简单的DNS管理工具,集简单的一键式服务与健壮的API于一身
详细优惠信息:两年的Bronze hosted DNS方案(通常3美元/月)

  • GitHub

强大的协作开发,代码审查以及代码管理工具
详细优惠信息: 在校期间,可免费使用具有五个私人仓库的微型账户(通常7美元/月)

  • HACKHANDS

7*24小时在线编程帮助
详细优惠信息:$25平台账户代金券

  • Orchestrate

完整的数据库产品组合,包括查找,时间序列事件,地理位置和图查询
详细信息:在校期间免费使用开发者账户 (通常49美元/月)

  • Screenhero

团队桌面共享协作工具
详细优惠信息: 在校期间可以使用个人账户(通常9.99美元/月)

  • SendGrid

触发类邮件工具
详细优惠信息: 在校期间Student plan每月免费email数为15k (通常为每天200免费email)

  • Stripe

移动及在线支付,为开发者而设
详细优惠信息: 在处理收入时免去首个1000美元的交易税

  • Travis CI

为开源和私人项目提供持续集成服务
详细优惠信息: 在校期间可免费使用Private builds (通常69美元/月)

  • Unreal Engine

一套完整的游戏开发工具,可以用于开发PC,主机,移动平台,网页及虚拟现实游戏。
详细优惠信息: 在校期间可以免费使用虚幻引擎 (通常19美元/月)

  • namecheap

使用Namecheap提供的.ME域名
详细信息: .me域名一年免费使用(通常8.99美元/月)
使用Namecheap提供的PositiveSSL

  • 详细优惠信息:

为期一年的SSL证书(通常9美元/月)

申请链接:

https://education.github.com/

p.s.没有edu邮箱也可以用学生证试试,一般一天就过了。DO家的50刀挺有用的,还有无限的GitHub私人仓库,赚爆。

2.申请扩容Onedrive5TB

Office 365教育版是微软专门针对学生和教师推出版本,包括在线Word, Excel, PowerPoint, OneNote, Outlook, Access及Publisher服务,1TB的OneDrive存储空间,可以注册5台PC/Mac电脑进行使用。

不过大部分学校并没有购买,因此只有教育A1版的。这个里面的office365全是在线版的,不过有5TB的OneDrive挺不错的,值得一试。

官方网站:

https://portal.office.com/signup?sku=Education

3.JetBrains Toolbox 专业开发工具学生免费授权计划

支持的验证方法有:

  • 邮件认证: 如果你的学校对学生有提供类似@.edu或者是@.edu.cn 的邮箱,那么你可以通过这种方式去认证。
  • ISIC/ITIC 认证: 这个没试过,不知道要怎么弄 —__—
  • 文档认证:我是申请这个的,这个需要你的学生证 ===>
    这里填你的学校就行了!

JetBrains家的ide真乃神器,尤其是IntelliJ IDEA。墙裂推荐!

p.s.一次申请有效期只有一年,到期重新申请即可。他们家的申请还是挺容易通过的,可以一直续到毕业。计算机专业的一定不容错过。>v<

总结:

其实还有很多优惠可以领取,不过今日时间有限,就先到这里吧。我想这篇文章应该会持续更新,找到更多优惠,敬请期待吧。(假装明天不用上课)

本站已支持AMP

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

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

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

本站已支持https

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

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

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

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