吾爱破解 - LCG - LSG |安卓破解|病毒分析|破解软件|www.52pojie.cn

 找回密码
 注册[Register]

QQ登录

只需一步,快速开始

查看: 678|回复: 4

[原创源码] 【python】Strassen算法源码分享-《算法导论》学习

[复制链接]
发表于 2018-5-17 00:11 | 显示全部楼层
本板块禁止发布 “电子书资料” ,此类主题请发布至『电子书屋』
本板块禁止发布讨论和求助帖,此类主题请发布至『编程语言讨论求助区』
本板块禁止发布 “视频教程” ,此类主题请发布至『动画精品转载区』
本帖最后由 象相合 于 2018-5-17 15:53 编辑

        

        大家好久不见,最近在摸《算法导论》,简单的算法感觉别人都写过就不想发,写到Strassen算法的时候,发现GitHub上python版本没有正宗的写法,只有捞的写法,于是就分享一下代码=w=
        
        Strassen算法是做[2^n]*[2^n]矩阵相乘的算法,局限性很大,但比较具有挑战性,因为需要使用【分治策略】且对矩阵和下标比较熟悉, 不然总会有这样或那样的错误,而且是矩阵调试很混乱,楼主比较菜写了个前置算法 递归的matlab版本(square_matrix_multiply_recursive) 再转成python, 最后补成Strassen算法才弄好,有闲时间的同学们可以玩一玩w

贴代码:

[Python] 纯文本查看 复制代码
import numpy as np
import math


def strassen_algorithm(A, B, L1, L2):
    n = int(L1[1]) - int(L1[0]) + 1
    d = math.floor(n / 2 - 1)  # the half length of matrix width/height minus one
    # if the matrix's length is 1, then set whose value
    C = np.zeros((n, n))
    if n <= 0:
        return
    if n == 1:
        C[n - 1, n - 1] = A[L1[3], L1[0]] * B[L2[3], L2[0]]
    else:
        a11 = [L1[0], L1[0] + d, L1[2], L1[2] + d]
        a12 = [int((L1[0] + L1[1] + 1) / 2), L1[1], L1[2], L1[2] + d]
        a21 = [L1[0], L1[0] + d, int((L1[2] + L1[3] + 1) / 2), L1[3]]
        a22 = [int((L1[0] + L1[1] + 1) / 2), L1[1], int((L1[3] + L1[2] + 1) / 2), L1[3]]
        b11 = [L2[0], L2[0] + d, L2[2], L2[2] + d]
        b21 = [L2[0], L2[0] + d, int((L2[2] + L2[3] + 1) / 2), L2[3]]
        b12 = [int((L2[0] + L2[1] + 1) / 2), L2[1], L2[2], L2[2] + d]
        b22 = [int((L2[0] + L2[1] + 1) / 2), L2[1], int((L2[2] + L2[3] + 1) / 2), L2[3]]

        P1 = strassen_algorithm(A, B, a11, b12) - strassen_algorithm(A, B, a11, b22)
        P2 = strassen_algorithm(A, B, a11, b22) + strassen_algorithm(A, B, a12, b22)
        P3 = strassen_algorithm(A, B, a21, b11) + strassen_algorithm(A, B, a22, b11)
        P4 = strassen_algorithm(A, B, a22, b21) - strassen_algorithm(A, B, a22, b11)
        P5 = strassen_algorithm(A, B, a11, b11) + strassen_algorithm(A, B, a11, b22) + \
             strassen_algorithm(A, B, a22, b11) + strassen_algorithm(A, B, a22, b22)
        P6 = strassen_algorithm(A, B, a12, b21) + strassen_algorithm(A, B, a12, b22) - \
             strassen_algorithm(A, B, a22, b21) - strassen_algorithm(A, B, a22, b22)
        P7 = strassen_algorithm(A, B, a11, b11) + strassen_algorithm(A, B, a11, b12) - \
             strassen_algorithm(A, B, a21, b11) - strassen_algorithm(A, B, a21, b12)

        C[0:d + 1, 0:d + 1] = P5 + P4 - P2 + P6
        C[0:d + 1, int(n / 2):int(n / 2 + d + 1)] = P1 + P2
        C[int(n / 2):int(n / 2 + d + 1), 0:d + 1] = P3 + P4
        C[int(n / 2):int(n / 2 + d + 1), int(n / 2):int(n / 2 + d + 1)] = P5 + P1 - P3 - P7
    return C


n = 8
A = np.random.randint(0, 100, size=[n, n])
B = np.random.randint(0, 100, size=[n, n])

L1 = [0, n - 1, 0, n - 1]
L2 = [0, n - 1, 0, n - 1]
ret = strassen_algorithm(A, B, L1, L2)
# ret2 = np.dot(A, B)
# print(ret2)


print(ret)



         为啥这种是正宗的写法呢?因为在15-22行中,a11,a12,...,b21,b22 这些变量存放的是矩阵的下标。我看了大佬python的写法,也就随便直接实例数组了。这种实例数组的写法比用下标的更慢,甚至比矩阵乘法的标准写法三次循环O(n^3)更慢。


     代码分享地址:https://github.com/EleComb/IntroductionToAlgorithms/tree/master/chapter_4_DivideStrategy


     里面也有之前的matlab写的和转成python的前置算法,欢迎各位互相学习指正=w=

免费评分

参与人数 1吾爱币 +1 热心值 +1 收起 理由
lertty + 1 + 1 感谢发布原创作品,吾爱破解论坛因你更精彩!

查看全部评分

发帖求助前要善用论坛搜索功能,那里可能会有你要找的答案;

如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子分类或者标题加上【已解决】

如何回报帮助你解决问题的坛友,一个好办法就是给对方加【热心】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

发表于 2018-5-17 08:44 | 显示全部楼层
学习了,深受启发,楼主发帖辛苦了,谢谢。

发帖求助前要善用论坛搜索功能,那里可能会有你要找的答案;

如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子分类或者标题加上【已解决】

如何回报帮助你解决问题的坛友,一个好办法就是给对方加【热心】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

发表于 2018-5-17 08:56 | 显示全部楼层

发帖求助前要善用论坛搜索功能,那里可能会有你要找的答案;

如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子分类或者标题加上【已解决】

如何回报帮助你解决问题的坛友,一个好办法就是给对方加【热心】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

发表于 2018-5-17 09:22 | 显示全部楼层

发帖求助前要善用论坛搜索功能,那里可能会有你要找的答案;

如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子分类或者标题加上【已解决】

如何回报帮助你解决问题的坛友,一个好办法就是给对方加【热心】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

发表于 2018-5-17 13:51 | 显示全部楼层
请规范发帖!
【公告】发帖代码插入教程
https://www.52pojie.cn/thread-713042-1-1.html

发帖求助前要善用论坛搜索功能,那里可能会有你要找的答案;

如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子分类或者标题加上【已解决】

如何回报帮助你解决问题的坛友,一个好办法就是给对方加【热心】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

 楼主| 发表于 2018-5-17 15:54 | 显示全部楼层
wushaominkk 发表于 2018-5-17 13:51
请规范发帖!
【公告】发帖代码插入教程
https://www.52pojie.cn/thread-713042-1-1.html

已修改,感谢提醒

发帖求助前要善用论坛搜索功能,那里可能会有你要找的答案;

如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子分类或者标题加上【已解决】

如何回报帮助你解决问题的坛友,一个好办法就是给对方加【热心】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

您需要登录后才可以回帖 登录 | 注册[Register]

本版积分规则


免责声明:
吾爱破解所发布的一切破解补丁、注册机和注册信息及软件的解密分析文章仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容。如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。如有侵权请邮件与我们联系处理。

Mail To:Service@52PoJie.Cn

快速回复 收藏帖子 返回列表 搜索

RSS订阅|手机版|小黑屋|联系我们|吾爱破解 - LCG - LSG ( 京ICP备16042023号 | 京公网安备 11010502030087号 )

GMT+8, 2018-8-17 07:25

Powered by Discuz!

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表