算法导论 笔记2 4.2-矩阵乘法Strassen算法

    4.2.1 使用Strassen计算

    [1 3][6 8]
    [7 5][4 2]
    

    先手工算一下答案记下来

    [18 14]
    [62 66]
    

    完全参考书的步骤来做一下这个题目

    1. 分解矩阵 略
    2. 创建并计算10个矩阵

         S1 = B12 - B22 = [6]
         S2 = A11 + A12 = [4]
         S3 = A21 + A22 = [12]
         S4 = B21 - B11 = [-2]
         S5 = A11 + A22 = [6]
         S6 = B11 + B22 = [8]
         S7 = A12 - A22 = [-2]
         S8 = B21 + B22 = [6]
         S9 = A11 - A21 = [-6]
         S10 = B11 + B12 = [14]
      
    3. 计算7次矩阵乘法

       P1 = A11 * S1 = [6]
       P2 = S2 * B22 = [8]
       P3 = S3 * B11 = [72]
       P4 = A22 * S4 = [-10]
       P5 = S5 * S6 = [48]
       P6 = S7 * S8 = [-12]
       P7 = S9 * S10 = [-84]
      
    4. 计算 C11 C12 C21 C22

       C11 = P5 + P4 - P2 + P6 = [18]
       C12 = P1 + P2 = [14]
       C21 = P3 + P4 = [62]
       C22 = P5 + P1 - P3 - P7 = [66]
      

    没有纸笔, 靠我的脑子想不出来, 我先跳到第五章吧.

    Read More...

    算法导论 读书笔记1

    先占个坑, 督促自己一下.

    2018-11-04T19:55:28+0800

    4.1.1

    返回数组里面的最大值, 例子参见下面的 4.1.2

    4.1.2

    def find_maximum_subarray(A):
        maximum_subarry_sum = None
        rst = (None, None)
        for i in range(len(A)):
            sum_of_array_i_to_j = 0
            for j in range(i, len(A)):
                sum_of_array_i_to_j += A[j]
                if sum_of_array_i_to_j > maximum_subarry_sum:
                    maximum_subarry_sum = sum_of_array_i_to_j
                    rst = (i, j)
    
        return rst
    
    
    if __name__ == '__main__':
        A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
        i, j = find_maximum_subarray(A)
        print(A[i: j+1])
    
        import random
        A = []
        for i in range(30):
            A.append(random.randint(-100, -1))
    
        print(A)
        i, j = find_maximum_subarray(A)
        print(A[i: j+1])
    

    4.1.3

    代码如下, 在我电脑测试时, 临界点为45. 当数组长度小于45时, 采用暴力算法, 显然不会改变性能交叉点. 但比如说, 当数组长度小于10时采用暴力算法, 可以改变性能交叉点.

    # -*- coding: utf-8 -*-
    
    
    def find_maximum_subarray_1(A, low, high):
        """
        暴力运算
        """
        maximum_subarry_sum = None
        rst = (None, None)
        for i in range(low, high+1):
            sum_of_array_i_to_j = 0
            for j in range(i, high+1):
                sum_of_array_i_to_j += A[j]
                if sum_of_array_i_to_j > maximum_subarry_sum:
                    maximum_subarry_sum = sum_of_array_i_to_j
                    rst = (i, j)
    
        return rst[0], rst[1], maximum_subarry_sum
    
    
    def find_maximum_subarray(A, low, high):
        """
        分治
        """
        if high - low <= 10:
            return find_maximum_subarray_1(A, low, high)
    
        mid = (low+high)/2
    
        left_low, left_high, left_sum = find_maximum_subarray(A, low, mid)
        right_low, right_high, right_sum = find_maximum_subarray(A, mid+1, high)
    
        left_sum_part, array_sum = None, 0
        for i in range(mid, low-1, -1):
            array_sum += A[i]
            if array_sum > left_sum_part:
                left_sum_part = array_sum
                max_left = i
    
        right_sum_part, array_sum = None, 0
        for i in range(mid+1, high+1):
            array_sum += A[i]
            if array_sum > right_sum_part:
                right_sum_part = array_sum
                max_right = i
    
        if left_sum_part+right_sum_part > max(left_sum, right_sum):
            return max_left, max_right, left_sum_part+right_sum_part
    
        if left_sum > right_sum:
            return left_low, left_high, left_sum
    
        return right_low, right_high, right_sum
    
    
    def main():
        import time
        import random
        import sys
        A_length = int(sys.argv[1])
        A_count = int(sys.argv[2]) if sys.argv[2:] else 1000
    
        all_A = []
        for i in range(A_count):
            all_A.append([random.randint(-100, 100) for _ in range(A_length)])
    
        start_time = time.time()
        for i in range(A_count):
            find_maximum_subarray_1(all_A[i], 0, A_length-1)
        end_time = time.time()
        print(u'暴力 %.2f' % (end_time - start_time))
    
        start_time = time.time()
        for i in range(A_count):
            find_maximum_subarray(all_A[i], 0, A_length-1)
        end_time = time.time()
        print(u'分治 %.2f' % (end_time - start_time))
    
    
    if __name__ == '__main__':
        main()
    

    4.1.4

    如果最终的结果maximum_subarry_sum是小于0的, 那么就返回一个空数组

    4.1.5

    个人感觉, 完全按题干中的”如下思想”来写, 时间复杂度并不是O(n), 而是O(n*2). 因为第一层需要遍历1..n, 当遍历到j的时候, 第二层最坏情况下, 需要遍历i..j.

    动态规划的话,还需要一个额外的数组, 叫它 maximum_subarry_endswith_j, 记录的是A[:j]里面以A[j]结尾的最大子数组. 能避免第二层的O(n)的复杂度. 代码如下:

    def find_maximum_subarray_2(A, low, high):
        """
        动态规划
        """
    
        maximum_subarry = (-1, -1, None)
        maximum_subarry_endswith_j = []
    
        maximum_subarry = (low, low, A[low])
        maximum_subarry_endswith_j.append((low, A[low]))
    
        for j in range(low+1, high+1):
            _start, _max_sum = maximum_subarry_endswith_j[-1]
            if _max_sum < 0:
                maximum_subarry_endswith_j.append((j, A[j]))
            else:
                maximum_subarry_endswith_j.append((_start, _max_sum + A[j]))
    
            if maximum_subarry_endswith_j[-1][1] > maximum_subarry[-1]:
                maximum_subarry = (maximum_subarry_endswith_j[-1][0], j, maximum_subarry_endswith_j[-1][1])
    
        return maximum_subarry
    

    数组长度100, 跑1000个100长度的随机的数组, 时间如下:

    % python c.py 100 1000
    暴力 0.71
    分治 0.23
    动态规划 0.06
    
    
    % python c.py 200 1000
    暴力 2.57
    分治 0.48
    动态规划 0.11
    
    % python c.py 400 1000
    暴力 10.25
    分治 1.08
    动态规划 0.23
    
    Read More...

    nginx配置中的if条件与querystring配置例子

    set $search 0;
    if ($request_uri ~ "_search"){
        set $search 1;
    }
    if ($request_uri ~ "_count"){
        set $search 1;
    }
    
    if ($arg_ignore_unavailable = true) {
        set $search "${search}1";
    }
    if ($search = 1) {
        set $args $args&ignore_unavailable=true;
    }
    
    
    if ($arg_preference = "") {
        set $args $args&preference=$upstream_http_django_user;
    }
    
    Read More...

    部署superset+clickhouse

    我选择使用docker方式安装部署, 虽然中间碰到两个坑, 但对于之后的二次部署或者多次部署,应该还是简单一些.

    Read More...

    mmap中shared方式锁定的内存能否释放

    很多文章都提到 cache中的 shared memory的cache不能被释放, 比如https://linux.cn/article-7310-1.html, 那自然就有一个问题: 如果系统内存用完了, 程序继续通过share memory mmap读取数据, 会发生什么情况?

    是老的cache被释放, 还是读取失败?

    做了一下测试, 还是会释放的, 只不过不能通过 echo 3 > /proc/sys/vm/drop_caches 这种方式释放而已.

    找一个4G内存的机器做下测试.

    写了一段代码, mmap读取一个3G文件的每一页, 这样就会让文件常驻cache了. echo 3 > /proc/sys/vm/drop_caches 之后可以看到cahce没有少, vmtouch也可以看到未释放.

    然后 cat another-3G-file > /dev/null,通过 vmtouch可以看到老文件已经有page不在cache中了. 而another-3G-file几乎全部在cache.

    Read More...

    golang里面array/slice的内存分配测试1

    1. 当cap还够用的时候, append不会申请新内存
    2. cap不够的时候, 会申请一块新内存. buf = append(buf, …), 新得到的buf会是一块新内存,指针是变掉的, 新的cap是之前的两倍(但一定是8的偶数倍, 比如2->8, 10->32)
    3. newbuf = buf[2:5] 生成slice的时候, newbuf指向buf[2], 他们共用同一块内存, 直到上面2中描述的新内存申请后, 他们会指向不同内存. 不管是buf还是newbuf扩容
    4. make([]byte, 10)[0:] , len, cap都是10, append会分配新内存.
    5. make([]byte, 10)[0:0] , len是0, cap是10, append 10 以内不会分配新内存
    Read More...

    函数中传递指针引起的一个BUG

    我是觉得编程里面最烧脑的就是传值和传引用的甄别, 一不小心就会出错.

    我是写一个kafka lib https://github.com/childe/healer, producer的类写好了, 然后在此基础上写一个可执行文件, 从stdin输入数据, 然后写入kafka.

    简单说一下producer逻辑, 输入1000条之后做为一批数据一起写kafka, 或者是200ms定时器到了就写, 哪怕没有1000条.

    但是在测试过程中, 无意间发现, 最终写到kafka的数据是错乱的, 后面写的数据会把前面的数据覆盖掉. 比如先输入 1111111111, 再输入 2222222222, 最后写到kafka的就是两条 2222222222

    这就让人很尴尬了…

    Read More...

    ES中使用mmap存储的索引会锁定内存不释放?

    在可用内存不充足的情况下, ES中索引配置如果使用mmapfs, 会导致内存不足, Load飙升.

    虽然从发现这个问题到最后确认原因,花了很长时间, 这里长话短说.

    Read More...

    git rebase移动commit到另外分支

    起因

    有两个分支, 一个master, 一个topic.

    master上面有commit: A C D
    topic上面有commit: A B C D

    本来是要在master上面提交2个新的commit: X Y , 但提交之后才发现是在topic上面提交的. 现在想把 X Y 两个commit移动到mater上面.

    git rebase --onto 可以实现这个功能, 模拟一下.

    模拟脚本

    用下面这个脚本模拟一下当前的情况

    git init
    date > 1
    git add 1
    git commit -m'1'
    git checkout -b dev
    date > 2
    git add 2
    git commit -m'2'
    git checkout master
    date > 3
    git add 3
    git commit -m'3'
    git checkout dev
    git merge master -m'merge from master into dev'
    date > 4
    git add 4
    git commit -m'4'
    date > 5
    git add 5
    git commit -m'5'
    

    脚本执行之后的commit情况

    * 2d2e87a - (HEAD -> dev) 5 (2 seconds ago) <childe>
    * afef668 - 4 (2 seconds ago) <childe>
    *   472e819 - merge from master into dev (2 seconds ago) <childe>
    |\
    | * ac945fe - (master) 3 (2 seconds ago) <childe>
    * | 1afa191 - 2 (2 seconds ago) <childe>
    |/
    * 18f563a - 1 (2 seconds ago) <childe>
    

    移动commit

    [/private/tmp/1521020400 on dev]
    % git checkout -b newbranch
    Switched to a new branch 'newbranch'
    [/private/tmp/1521020400 on newbranch]
    % git rebase --onto master 472e819 newbranch
    First, rewinding head to replay your work on top of it...
    Applying: 4
    Applying: 5
    [/private/tmp/1521020400 on newbranch]
    % git checkout master
    Switched to branch 'master'
    [/private/tmp/1521020400 on master]
    % git merge newbranch
    Updating ac945fe..33c077f
    Fast-forward
     4 | 1 +
     5 | 1 +
     2 files changed, 2 insertions(+)
     create mode 100644 4
     create mode 100644 5
    [/private/tmp/1521020400 on dev]
    % git rebase --onto 472e819  dev
    

    具体文档参见 https://git-scm.com/docs/git-rebase/2.21.0

    Read More...

    vmtouch

    vmtouch可以方便的控制和诊断文件在系统Cache中的情况

    官方文档在https://hoytech.com/vmtouch/

    Read More...