虚拟一个 Mysql 给 Django 用

    我想通过 Model 生成建表的 Sql, 但是一定要有一个可用的 Mysql 才行, 觉得很麻烦. 于是找到了这个项目.

    https://pypi.org/project/django-fake-database-backends/

    安装:

    pip install django-fake-database-backends

    配置:

    DATABASES = {
        'default': {
            'ENGINE': 'django_fake_database_backends.backends.mysql',
        }
    }
    
    Read More...

    django 连 Mysql 报2059错误

    参考https://blog.csdn.net/xiaoyaosheng19/article/details/82643729

    原因: 最新的mysql8.0对用户密码的加密方式为caching_sha2_password, django暂时还不支持这种新增的加密方式。只需要将用户加密方式改为老的加密方式即可。

    use mysql;
    alter user 'root'@'localhost' identified with mysql_native_password by 'yourpassword';
    flush privileges;
    
    Read More...

    8皇后问题

    问题是8皇后问题有多少种解法(只需要一个总数, 不需要每一个具体的解决方案)

    据说是目前效率最高的代码, 使用位运算操作.

    #include<stdio.h>
    
    int succ, ans;
    
    void sol(int cp, int lp, int rp) {
        if (cp == succ) {
            ++ans;
            return;
        }
        int p = succ & (~(cp | lp | rp));
        while (p) {
            int bit = p & (-p);
            sol(cp | bit, (lp | bit) << 1, (rp | bit) >> 1);
            p &= (p - 1);
        }
    }
    
    int totalNQueens(int n){
        ans = 0;
        succ = (1 << n) - 1;
        sol(0, 0 ,0);
        return ans;
    }
    
    int main(){
        int ans;
        ans = totalNQueens(4);
        printf("%d\n", ans);
    }
    

    自己看了很久没看明白, 网上搜索了一下资料后才理解, 其实挺简单的. 不记得资料 URL 了, 也不去再找了, 默默致谢一下.

    一步步来, 先不管上面的代码, 不管是不是使用位来操作, 先按一个简单的思路写下伪代码.

    sol(depth, pos) { // depth 是当前要处理第几行, pos 是前面已经安放好的位置, 也就是上面 depth-1 行的数据
    
    	 // 如果 N 排数据都已经安置好了, ans 加1
    	if depth == N+1 {
    		ans++
    	}
    
    	p = 根据 pos 计算当前行可以放的所有位置
    
    	while ( p 中还有位置可以尝试 ) {
    		next = 取当前行的下一个位置
    		sol(depth+1, pos.update(next))
    		update(p)
    	}
    }
    
    

    我们如果想使用 BIT 记录数据(包括已经安放的位置, 以及当前行可以尝试的位置等等), 以及使用位运算加速, 需要考虑几个问题:

    1. 如何表示已经安放的位置
    2. 如何根据问题 1 计算出当前行可以安放的位置

    直接看一下上面的代码是如何解决这些问题的.

    它并没有直接使用一个变量记录”已经安放的位置”, 而是使用了三个变量间接实现的, 理解了这三个变量就理解这个代码了.

    cp 用来记录”只考虑直上直下的冲突, 前面所有行安放的棋子会导致 depth 这一行哪些位置不能放”, 就是说, 第一行放左数第一个位置, 那么第二行就不能再放左数第一个位置了. 拿”八”皇后举例说明, 第一行棋子放在左数第三个位子, 那在计算第二行的位置时, cp = 0b00100000 . 继续在第二行的左数第一个位置放棋子, 计算第三行的位置时, cp = 0b00100000 0b10000000 = 0b10100000 . 很自然的, cp 的初始值应该是 0b00000000
    lp 用来记录”右上-左下这条对角线上的冲突, 前面所有行安放的棋子会导致 depth 这一行哪些位置不能放”, 就是说, 第一行放左数第二个位置, 那么第二行就不能再放左数第一个位置了. 拿”八”皇后举例说明, 第一行棋子放在左数第三个位子, 那在计算第二行的位置时, lp = 0b00100000 0b01000000 = 0b01100000 .

    rp 和 lp 类似, 只是记录 “左上-右下” 这条对角线.

    搞清楚这三个变量, 再回头看一下问题1和2 . 问题1并不是一定要解决的, 因为”记录已经安放的位置”也只是为了解决问题2, 我们使用这三个变量有两个好处, 一是可以快速算出问题2, 二是可以使用位运算快速更新三个变量本身

    然后, depth 这个变量并不是必需的, 可以使用 cp 取得一样的效果. cp 里面有多少个1, 就代表处理了几行了.

    Read More...

    下面这段代码是模拟一个工作任务: goroutine里面做任务, 主进程里面等任务完成才退出, 避免一个任务因进行中退出. 实际代码肯定会复杂, 这两种线程可能散落在多个文件中.

    package main
    
    import "sync"
    
    var wg sync.WaitGroup
    
    func work() {
    	for {
    		wg.Add(1)
    		// ... work here
    		// time.Sleep(time.Second)
    		wg.Done()
    	}
    }
    
    func main() {
    	go work()
    	defer wg.Wait()
    }
    

    乍一看好像也没问题, 但有小概率 Panic: WaitGroup is reused before previous Wait has returned.

    直接google查了好几个文章都没解释为什么, 最后还是看官方文档找到解释. 官方文档好啊, 一定要花时间撸一遍才好.

    If a WaitGroup is reused to wait for several independent sets of events, new Add calls must happen after all previous Wait calls have returned.
    

    上面代码中的 Wait 并不是原子操作, 可能 Wait 还没有结束的时候, 又再次调用到了 Add 方法, 这时候就会 Panic.

    Read More...

    defer里面的值何时evaluate

    第一个问题

    我在写这个的时候只是想记录一下像标题中说的, defer里面的值何时evaluate, 就像下面这一个例子.

    例子来自于 https://groups.google.com/forum/#!topic/golang-nuts/c7YUK65Xqgs%5B1-25%5D

    package main
    import (
        "fmt"
    )
    func main() {
        for i := 0; i < 10; i++ {
            defer func() {
                fmt.Printf("func(): %v\n", i)
            }()
            defer printi(i)
            defer fmt.Printf("i: %v\t", i)
        }
    }
    func printi(i int) {
        fmt.Printf("printi(): %v\t", i)
    }
    

    结果是这样的

    OUTPUT
    ======
    i: 9	printi(): 9	func(): 10

    i: 8	printi(): 8	func(): 10

    i: 7	printi(): 7	func(): 10

    i: 6	printi(): 6	func(): 10

    i: 5	printi(): 5	func(): 10

    i: 4	printi(): 4	func(): 10
    
i: 3	printi(): 3	func(): 10
    
i: 2	printi(): 2	func(): 10

    i: 1	printi(): 1	func(): 10

    i: 0	printi(): 0	func(): 10
    

    有趣的是, 匿名函数里面的输出和Print(也就是非匿名函数)里面的输出是不一样的. 这里可以用一个原因来解决(有种大统一理论的感觉不… )

    二楼的 emepyc 说的很清楚, 我也不画蛇添足了, 直接复制过来

    The key point is that the arguments to the deferred functions are 
    evaluated and copied in the invocation of the defer. So: 
    
     >          defer  func()  { 
     >              fmt.Printf("func():  %v\n",  i) 
     >          }() 
    
    No arguments to func(), so i is not copied and the final value of i is 
    used when the deferred function is executed. 
    
     >          defer  printi(i) 
     >          defer  fmt.Printf("i:  %v\t",  i) 
    
    In both cases, i is the argument of the deferred function, so its value 
    is copied and used when the deferred function is evaluated. 
    

    第二个问题

    第二个问题, 在我看完之后, 并看了相关的链接资料, 发现是第一个问题的超集.

    先来看一下原问题, https://stackoverflow.com/questions/51360229/the-deferred-calls-arguments-are-evaluated-immediately

    这个回答里面也给出了 golang 官方资料关于 defer 的链接, 我之前在 google 搜索 golang defer 在第一页居然没有出现这个官方链接 .. https://golang.org/ref/spec#Defer_statements . 官方资料里面言简意赅的解释了 defer 的执行规则, 但是… 如果不能精确理解其中一些术语的话, 会看的很不明白, 比如我..

    由三句话组成, 分别对应三个执行规则.

    1. Each time a “defer” statement executes, the function value and parameters to the call are evaluated as usual and saved anew but the actual function is not invoked.
    2. Instead, deferred functions are invoked immediately before the surrounding function returns, in the reverse order they were deferred. That is, if the surrounding function returns through an explicit return statement, deferred functions are executed after any result parameters are set by that return statement but before the function returns to its caller.
    3. If a deferred function value evaluates to nil, execution panics when the function is invoked, not when the “defer” statement is executed.

    写 Blog 真的还挺累(麻烦)的, 具体的意思我就不再解释了. https://stackoverflow.com/questions/51360229/the-deferred-calls-arguments-are-evaluated-immediately这里对第一点, 第二点, 都有很好的解释了.

    Read More...

    搭建Kafka集群时, 对ZooKeeper认证与权限控制

    废话写在最前

    1. 公司需要部署一套kafka, 放在公网服务, 所以就查查资料, 尝试部署一套有SSL加密传输的, 而且有认证和权限控制机制的Kafka集群.

    2. 我之前对ZK的认证机制不了解, 也几乎不在JAVA生态圈有过经验, 所以对JAAS完全不了解. 对SASL也是首次接触. 因为kafka官方文档写的实在太简单(仅仅是指https://kafka.apache.org/documentation.html#zk_authz_new这一节), 在尝试和翻阅了好多(过时的)资料之后, 终于算是成功部署了. 但依然很多不知其所以然的地方.

    3. 对SSL有一定了解, 对Listenr配置也有一定了解了 . 所以打算先看一下Zookeeper的认证权限控制, 这个之前还没有接触过.

    对ZooKeeper认证与权限控制目的

    大的目的很简单, 因为提供对公的服务, 相比公司内部使用来说, 有安全隐患, 需要做一定的安全保护措施, 也就是上面提到的, “有SSL加密传输的, 而且有认证和权限控制机制的Kafka集群”.

    具体怎么样做到”更安全”这个目的呢?(也就是我们的更精确一些的目的是什么呢?) 引述一下kafka官方文档中一段话.

    The metadata stored in ZooKeeper for the Kafka cluster is world-readable, but can only be modified by the brokers.
    The rationale behind this decision is that the data stored in ZooKeeper is not sensitive, but inappropriate manipulation of that data can cause cluster disruption.
    We also recommend limiting the access to ZooKeeper via network segmentation (only brokers and some admin tools need access to ZooKeeper).
    

    字面意思很明确, ZK 中存的元信息是任何人都可读的, 但是只能被 Kafka Broker 修改, 因为这些信息不是敏感信息, 但随意改动却可能对 Kafka 造成破坏. 另外建议在网络层面隔离 ZK (因为只有 Broker 和一些管理工具才需要访问Zk )

    我的理解是, 官方建议网络层面隔离ZK, 但是 ZK 本身也会有这样一种选择: 不能匿名登陆, 只可以让认证用户登陆. 但是实践下来, 并非如此. (此处存疑, 后面需要查阅ZK文档). 实践下来的”结论”比较奇怪: ZK 通过 JAAS 设置了用户(以及密码), Kafka 需要使用配置过的用户连接 ZK 并设置ACL. 但是, 1, 匿名用户依然可以连接 ZK, 也可以创建 Znode, 以及对 Znode 设置权限. 只是对 Broker 已经创建并设置好ACL的 Znode 只有只读权限. 2. Kafka 一定要是 JAAS 中配置用户(以及相对应的密码), 否则就会创建 Znode 失败. 1和2两点似乎是矛盾的.

    配置步骤

    首先感谢 RedHat 的这篇文档 https://access.redhat.com/documentation/en-us/red_hat_amq/7.2/html/using_amq_streams_on_red_hat_enterprise_linux_rhel/configuring_zookeeper#assembly-configuring-zookeeper-authentication-str

    配置 ZK 的认证

    ZK 的认证配置可以参考(这个文档是说ZK节点之间的认证, 但Kafka到ZK的认证也就多了一步) https://cwiki.apache.org/confluence/display/ZOOKEEPER/Server-Server+mutual+authentication, 这里有详细的权威的步骤以及说明, 我简单记录一下吧.

    我想提前先提一下 JAAS 配置, 因为这里有个还不明白的地方. ZK 以及 Kafka, 他们的 JASS 配置文件的格式都是一样的, 但简单看了一下 JAAS 的文档, 并没有看到针对这种格式的说明, 所以不明白这种格式是标准, 还是只是 ZK/Kafka 自己定义的格式. 另外, 对于里面的参数, 比如 username=XXX, 是有一个标准, 还是大家各自实现自己的, 也不清楚. [存疑]

    zoo.cfg 配置

    将下面配置写入 zoo.cfg. 先提一下注意点, 里面的第2行第3行是 Zk 节点之间的认证开关, 并不影响 Kafka 到 ZK 的认证.

    quorum.auth.enableSasl=true
    quorum.auth.learnerRequireSasl=true
    quorum.auth.serverRequireSasl=true
    quorum.auth.learner.loginContext=QuorumLearner
    quorum.auth.server.loginContext=QuorumServer
    #quorum.auth.kerberos.servicePrincipal=servicename/_HOST
    quorum.cnxn.threads.size=20
    

    因为我们没有使用 kerberos, 所以把第6行注释了.

    解释一下各行的意思:

    quorum.auth.enableSasl=true

    打开sasl开关, 默认是关的

    quorum.auth.learnerRequireSasl=true

    ZK做为leaner的时候, 会发送认证信息

    quorum.auth.serverRequireSasl=true

    设置为 true 的时候, learner 连接的时候需要发送认证信息, 否则拒绝.

    quorum.auth.learner.loginContext=QuorumLearner

    JAAS 配置里面的 Context 名字.

    quorum.auth.server.loginContext=QuorumServer

    JAAS 配置里面的 Context 名字.

    quorum.cnxn.threads.size=20

    建议设置成 ZK 节点的数量乘2

    bin/zkEnv.sh 添加 jvm 选项

    SERVER_JVMFLAGS="-Djava.security.auth.login.config=/path/to/server/jaas/file.conf"
    

    具体的路径自己配置一下, 另外最好确认一下 SERVER_JVMFLAGS 是不是被使用了, 因为版本不断迭代, 后面也许会有变化.

    JAAS 配置

    Server {
        org.apache.zookeeper.server.auth.DigestLoginModule required
    	    user_super="123456"
    		user_kafka="123456"
    		user_someoneelse="123456";
    
    };
    
    QuorumServer {
           org.apache.zookeeper.server.auth.DigestLoginModule required
           user_zookeeper="123456";
    };
    
    QuorumLearner {
           org.apache.zookeeper.server.auth.DigestLoginModule required
           username="zookeeper"
           password="123456";
    };
    

    QuorumServer 和 QuorumLearner 都是配置的 ZK 节点之间的认证配置, 我们叫他 Server-to-Server authentication , 并不影响 Kafka 的连接认证. Server 是配置的Kafka连接需要的认证信息, 我们叫他 Client-to-Server authentication

    按我的理解说一下配置意思, 不一定准确.

    QuorumServer 和 QuorumLearner 是指 Context 名字, 默认是这样的, 但可以通过上面提到的配置更改默认名字.

    QuorumServer 里面的 user_zookeeper=”123456” , 是特定格式, 代表一个密码为123456的用户, 用户名是zookeeper, Learner 连接的时候需要使用这个用户/密码认证.

    QuorumLearner 里面的配置是说, 做为 learner 连接的时候, 使用配置的用户名/密码认证.

    下面是我还不明白的地方, 现在只能不负责任的说一下. [存疑]

    org.apache.zookeeper.server.auth.DigestLoginModule 应该是指的认证方式, 有些文章中说, 和 Kafka 的 JAAS 配置需要一致, 但我测试下来并非如此.
    我自己实践下来, ZK 中一定要使用 org.apache.zookeeper.server.auth.DigestLoginModule, 但Kafka中可以使用 org.apache.zookeeper.server.auth.DigestLoginModule, 也可以使用 org.apache.kafka.common.security.plain.PlainLoginModule

    对机制并不明白, 所以也是云里雾里.

    对于 Server Context 配置, RedHat 文章中说, super 用户自动获得管理员权限. 我也不明白为啥, 在这里可以配置多个用户, Kafka 选一个用就可以了, 一般我们起名叫 kafka.

    打开 Client-to-Server authentication

    把下面的配置写到 zoo.cfg

    requireClientAuthScheme=sasl
    authProvider.<IdOfBroker1>=org.apache.zookeeper.server.auth.SASLAuthenticationProvider
    authProvider.<IdOfBroker2>=org.apache.zookeeper.server.auth.SASLAuthenticationProvider
    authProvider.<IdOfBroker3>=org.apache.zookeeper.server.auth.SASLAuthenticationProvider
    

    这里的IdOfBroker是指ZK节点的myid. 后面的 org.apache.zookeeper.server.auth.SASLAuthenticationProvider 是指什么还不明白 [存疑]

    ZK 的配置就到这里了, 权限控制(ACL)是另外一个话题. 后面再说.

    紧接着说一下 , 如何配置 Kafka 使用认证连接 ZK.

    Kafka 需要的配置

    打开开关

    在 config/server.properties 里面添加下面一行配置

    zookeeper.set.acl=true
    

    JVM选项中配置JAAS配置文件路径信息

    在合适的地方, 添加下面这样的配置, 我在 bin/kafka-run-class.sh 添加的

    KAFKA_OPTS="-Djava.security.auth.login.config=./config/jaas.conf"
    

    配置 JAAS

    jaas.conf 配置中添加如下内容

    Client {
        org.apache.kafka.common.security.plain.PlainLoginModule required
    	username="kafka"
    	password="123456";
    
    };
    

    这样起来之后, Kafka 创建和使用的 Znode 都会被设置了ACL, 其他用户只能看, 不能修改.

    Read More...

    算法导论笔记 6-3 建堆

    先写一个 go 语言的程序如下

    package main
    
    import (
    	"fmt"
    	"math"
    	"math/rand"
    	"strings"
    	"time"
    )
    
    func maxHeapify(A []int, i int) {
    	var (
    		size  = len(A)
    		left  int
    		right int
    		max   int
    	)
    
    	for {
    		left = 2*i + 1
    		right = 2*i + 2
    		max = i
    
    		if left < size && A[i] < A[left] {
    			max = left
    		}
    		if right < size && A[max] < A[right] {
    			max = right
    		}
    
    		if max == i {
    			return
    		}
    		A[i], A[max] = A[max], A[i]
    		i = max
    	}
    }
    
    func buildMaxHeap(A []int) {
    	length := len(A)
    	for i := length/2 - 1; i >= 0; i-- {
    		maxHeapify(A, i)
    	}
    }
    
    func GA(N int) (A []int) {
    	A = make([]int, 10)
    	for i := 0; i < N; i++ {
    		A[i] = N - i
    	}
    	A[0] = 0
    	return
    }
    func RGA(N int) (A []int) {
    	rand.Seed(time.Now().UnixNano())
    
    	A = make([]int, 10)
    	for i := 0; i < N; i++ {
    		A[i] = rand.Intn(N * N)
    	}
    	return
    }
    
    func isHeap(A []int) bool {
    	size := len(A)
    	for i := 0; i < size; i++ {
    		left := 2*i + 1
    		right := 2*i + 1
    		if left < size && A[left] > A[i] {
    			return false
    		}
    		if right < size && A[right] > A[i] {
    			return false
    		}
    	}
    	return true
    }
    
    func printTree(A []int) {
    	var (
    		currentHeight      = 0
    		startOfCurrentLine = 0
    		height             = int(math.Ceil(math.Log2(float64(len(A)) + 0.5)))
    	)
    	for i := 0; i < len(A); i++ {
    		if i == startOfCurrentLine {
    			jstring := make([]string, height-currentHeight)
    			for j := 0; j < height-currentHeight; j++ {
    				jstring[j] = " "
    			}
    			currentHeight++
    			fmt.Printf("\n%s", strings.Join(jstring, ""))
    			startOfCurrentLine = 2*startOfCurrentLine + 1
    		}
    		fmt.Printf("%d ", A[i])
    	}
    	fmt.Println("\n")
    }
    
    func main() {
    	count := 100
    	for i := 0; i < count; i++ {
    		A := RGA(10)
    		//printTree(A)
    		buildMaxHeap(A)
    		fmt.Println(isHeap(A))
    		//printTree(A)
    	}
    }
    

    6.3-1

    6.3-2

    我们的算法是基于上一节的 Max-Heapify 基础之上的, 即: 对每一个结节做 Max-Heapify 的时候, 需要他的子树已经是最大堆了. 自上而下不满足这个前提条件.

    6.3-3

    这个是为了证明建堆的时间复杂度是O(n) , 先不证了, 略

    Read More...

    算法导论笔记 6.2 章 - 维护堆的性质

    6.2-1

    6.2-2

    6.2-3

    会停止比较, 不进入递归, 直接返回

    6.2-4

    因为 left 和 right 都大于 heap-size , 所以不会进去递归, 直接返回了

    6.2-5

    func maxHeapify(A []int, i int) {
    	var (
    		size  = len(A)
    		left  int
    		right int
    		max   int
    	)
    
    	for {
    		left = 2*i + 1
    		right = 2*i + 2
    		max = i
    
    		if left < size && A[i] < A[left] {
    			max = left
    		}
    		if right < size && A[max] < A[right] {
    			max = right
    		}
    
    		if max == i {
    			return
    		}
    		A[i], A[max] = A[max], A[i]
    		i = max
    	}
    }
    

    6.2-6

    对于已经倒排排序的数组A, 把A[-1]提到最前面, 这个时候, max_heapify 的运行时间就是 ln(n), 像 [1,9,8,7,6,5,4,3,2]

    Read More...

    算法导论 第6章 堆

    写在最前

    1. 节点A的高度 h 的定义是, A到叶子节点的边的个数. 所以 1,2,3 这个堆的高度是1

    2. 证明 i 的子节点是 2i+1 和 2i+2 , 可以用数据归纳法证明. 如果对于 i 成立, 那么 i+1 的子节点是 2i+2+1, 2i+2+2 , 所以对 i+1 也成立. 所以 i 的父节点是 floor(i/2)

    6.1-1

    先来计算高度为 h 的完全二叉树, 元素个数为多少.

    第 i 层的元素个数是 2**(i-1) , 设总元素个数 S = 1 + 2 + 4 + ... + 2**(n-1)

    2 * S = 2 + 4 + ... + 2**n

    S= 2S-S= 2**n-1

    因为高度 h=n-1, 所以高度为 h 的堆中, 元素最多是 2**(h+1) - 1 个, 最少是 2**h

    6.1-2

    由 6.1-1 可知, 2**h <= n <= 2**(h+1) - 1 => h <= ln(n) < h+1 => h<=ln(n) && h > ln(n)-1 , 所以 h = ln(n).floor

    6.1-3

    略吧

    6.1-4

    叶子结点上

    6.1-5

    是的, 因为满足定义 A[parent(i)] >= A[i]

    6.1-6

    不是 6 < 5

    6.1-7

    i 的父节点是 floor(i/2), 所以从 floor(i/2)+1 的节点都是没有子节点的, 也就是叶子节点

    Read More...

    算法导论学习笔记5 随机算法

    5.3-1

    我觉得Marceau教授说的挺有道理. 我的想法是把i=2的时候做为初始状态, 只要证明交换过A[1]之后, 每种可能的子数组A[1..1]的概率是1/n. 这个结论应该是”明显”的.

    5.3-2

    按我的理解应该是不可以的. 如果初始的时候, 第一个数字是X的概率小, 那么程序跑完之后, 第一个数字不是X的概率就会变大, 而不 1/n 了.

    我们来写程序来验证一下 5.3-1 和 5.3-2 的结果吧.

    package main
    
    import (
    	"fmt"
    	"math/rand"
    	"time"
    )
    
    func shuffle(array []int) {
    	rand.Seed(time.Now().UnixNano())
    
    	var (
    		tmp   int
    		index int
    		n     = len(array)
    	)
    
    	for i := 0; i < n; i++ {
    		index = rand.Intn(n-i) + i
    		tmp = array[index]
    		array[index] = array[i]
    		array[i] = tmp
    	}
    }
    
    func generate_array(n int) []int {
    	array := make([]int, n)
    	for i := 0; i < n; i++ {
    		array[i] = i
    	}
    	return array
    }
    
    func main() {
    	var (
    		loop = 6000
    		N    = 3
    	)
    
    	for i := 0; i < loop; i++ {
    		array := generate_array(N)
    		shuffle(array)
    		fmt.Printf("%v\n", array)
    	}
    }
    

    看5.3-1的结果, 还是很平均的.

    % go run 5.3.1.go | sort | uniq -c
     990 [0 1 2]
    1038 [0 2 1]
     965 [1 0 2]
     991 [1 2 0]
    1002 [2 0 1]
    1014 [2 1 0]
    

    5.3-2的结果, 第一位永远不是0

    package main
    
    import (
    	"fmt"
    	"math/rand"
    	"time"
    )
    
    func shuffle(array []int) {
    	rand.Seed(time.Now().UnixNano())
    
    	var (
    		tmp   int
    		index int
    		n     = len(array)
    	)
    
    	for i := 0; i < n-1; i++ {
    		index = rand.Intn(n-i-1) + i + 1
    		tmp = array[index]
    		array[index] = array[i]
    		array[i] = tmp
    	}
    }
    
    func generate_array(n int) []int {
    	array := make([]int, n)
    	for i := 0; i < n; i++ {
    		array[i] = i
    	}
    	return array
    }
    
    func main() {
    	var (
    		loop = 6000
    		N    = 3
    	)
    
    	for i := 0; i < loop; i++ {
    		array := generate_array(N)
    		shuffle(array)
    		fmt.Printf("%v\n", array)
    	}
    }
    
    % go run 5.3.2.go | sort | uniq -c
    2951 [1 2 0]
    3049 [2 0 1]
    

    5.3-3

    这些题目.. 都是谁想来杀我脑细胞的..

    完全用教材中的示例去套已经不行了, 得到的结果貌似是”不能证明”. 但是直觉感觉是可以的. 先放下, 来写个程序验证下吧.

    package main
    
    import (
    	"fmt"
    	"math/rand"
    	"time"
    )
    
    func shuffle(array []int) {
    	rand.Seed(time.Now().UnixNano())
    
    	var (
    		tmp   int
    		index int
    		n     = len(array)
    	)
    
    	for i := 0; i < n-1; i++ {
    		index = rand.Intn(n)
    		tmp = array[index]
    		array[index] = array[i]
    		array[i] = tmp
    	}
    }
    
    func generate_array(n int) []int {
    	array := make([]int, n)
    	for i := 0; i < n; i++ {
    		array[i] = i
    	}
    	return array
    }
    
    func main() {
    	var (
    		loop = 6000
    		N    = 3
    	)
    
    	for i := 0; i < loop; i++ {
    		array := generate_array(N)
    		shuffle(array)
    		fmt.Printf("%v\n", array)
    	}
    }
    

    运行结果

    % go run 5.3.3.go | sort | uniq -c | sort -k2
     892 [0 1 2]
    1157 [0 2 1]
    1073 [1 0 2]
    1123 [1 2 0]
     864 [2 0 1]
     891 [2 1 0]
    

    第一位是2的概率小一些.. 想了一会, 用一个反例来证明这个办法不行吧.

    比如 0 1 2 这三个排列好的数字, 用5.3.3的程序来跑, 我们来算一下跑完之后2出现在第一位的概率, 是 4/27 . 这样应该能证明这个算法是错误的了. 我最开始的直觉是错的.

    又想了一会, 想到一个更好些的证明吧.

    不失普遍性, 我们假设n=10好了. 在进行到最后一步的时候, 设特定的数字x(比如说1)出现在第1位的概率是p, 那么最后一步进行之后, x在第一位的概率是 p*9/10 , p*9/10=1/10 => p=1/9. 同理, x出现在第2-9位的概率也是1/9, 加起来的概率为1, 也就是说x出现在最后的概率需要为0, 显然前面进行的操作到最后一步时, 满足不了x在最后出现的概率为0, 那也保证不了最后一步之后, 这个数列是个随机数列.

    5.3-4

    我看教材的时候, 里面说, 如果数列中的每一个特定的数字出现在一个特定位子的概率都是1/n, 也不能保证他就是一个随机数组, 我就想这会是什么情况呢? 这个题目给出了一个简单又有力的反例.

    如果初始数组不是随机的, 比如是0,1,2,3,4,5,6,7,8,9, 那么这个算法过后, 每个元素A[i]出现在任意特定位置的概率都是1/n (因为offset是1-n中每个数字的概率就是1/n), 但他显然不是随机数组, 因为初始数列的排列并没有打乱.

    5.3-5

    优先级数列中, 每个数字都不一样的概率如下, 记N=n**3, 则概率为 p=(N-1)*(N-2)*(N-3)*...*(N-n)/N**n , p > (N-n)**n/N**n = ((N-n)/N)**n = (1-n/N)**n , 只需要证明 (1-1/n**2)**n > 1-1/n , 这个不知道怎么证明, 只是写程序看出来, 这里的2不能再小了, 哪怕小于1.99, 这个不等式也是不成立的. #TODO#

    5.3-6

    最简单的实现应该是保证没有重复的优先级. 如果想快一些就第一次先不管, 然后再对重复的部分排序一次, 这次保证没有重复的优先级.

    package main
    
    import (
    	"fmt"
    	"math/rand"
    	"sort"
    	"time"
    )
    
    func permute_by_sorting(array []int) []int {
    	rand.Seed(time.Now().UnixNano())
    
    	var (
    		n                     = len(array)
    		N                     = n * n * n
    		priority_array        = make([]int, n)
    		sorted_priority_array = make([]int, n) // sort priority_array to sorted_priority_array
    		shuffled_array        = make([]int, n)
    
    		existed = map[int]bool{}
    	)
    	for i := 0; i < n; i++ {
    		r := rand.Intn(N)
    		for {
    			if _, ok := existed[r]; !ok {
    				break
    			}
    			r = rand.Intn(N)
    		}
    		existed[r] = true
    		priority_array[i] = r
    		sorted_priority_array[i] = priority_array[i]
    	}
    
    	sort.Slice(sorted_priority_array, func(i, j int) bool { return sorted_priority_array[i] < sorted_priority_array[j] })
    
    	idx_map := make(map[int]int)
    	for i := 0; i < n; i++ {
    		if _, ok := idx_map[sorted_priority_array[i]]; !ok {
    			idx_map[sorted_priority_array[i]] = i
    		}
    	}
    
    	for i := 0; i < n; i++ {
    		shuffled_array[i] = -1
    	}
    
    	for i := 0; i < n; i++ {
    		e := priority_array[i]
    		new_idx := idx_map[e]
    		for shuffled_array[new_idx] != -1 {
    			new_idx++
    		}
    		shuffled_array[new_idx] = array[i]
    	}
    
    	return shuffled_array
    }
    
    func main() {
    	var (
    		N    = 2
    		loop = 6000
    	)
    
    	array := make([]int, N)
    	for i := 0; i < N; i++ {
    		array[i] = i
    	}
    
    	for i := 0; i < loop; i++ {
    		shuffled_array := permute_by_sorting(array)
    		fmt.Println(shuffled_array)
    	}
    }
    
    

    5.3-6

    归纳法. 假设 random_sample(n-1, m-1) 返回的子集中, 每一个数字出现的概率都是 (m-1)/(n-1) . 接下来的一步中, 选到 n 的概率是 1/n + (m-1)/n = m/n , 选到不是 n 的其他特定一个数字的概率是 (m-1)/(n-1) + ((n-m)/(n-1)) * (1/n) = m/n

    初始情况分析, 我还是觉得 Marceau 教授说的有道理, 从 m == 1 分析更符合人的常识吧.

    package main
    
    import (
    	"fmt"
    	"math/rand"
    	"sort"
    	"time"
    )
    
    func random_sample(n []int, m int) []int {
    	if m == 0 {
    		return []int{}
    	}
    
    	length := len(n)
    	//fmt.Println(length)
    	s := random_sample(n[:length-1], m-1)
    	i := n[rand.Intn(length)]
    
    	var in_s = false
    	for _, j := range s {
    		if j == i {
    			in_s = true
    			break
    		}
    	}
    
    	if in_s {
    		s = append(s, n[length-1])
    	} else {
    		s = append(s, i)
    	}
    	return s
    }
    
    func main() {
    	rand.Seed(time.Now().UnixNano())
    
    	var (
    		loop = 10000
    		N    = 5
    		m    = 3
    	)
    
    	array := make([]int, N)
    	for i := 0; i < N; i++ {
    		array[i] = i
    	}
    
    	for i := 0; i < loop; i++ {
    		s := random_sample(array, m)
    		sort.Slice(s, func(i, j int) bool { return s[i] <= s[j] })
    		fmt.Println(s)
    	}
    }
    
    Read More...