Haskell家的软件简直是巨坑，我就说之前怎么只要编译和GPU有关的代码就失败= =

这次编译darknet终于发现，是Leksah的头文件和Windows SDK的头文件有重定义冲突，把Leksah的路径从PATH里去掉，问题就解决了

具体报啥错我忘了，反正是一个x开头的头文件有重定义

如题，竟然是Windows SDK版本的原因= =

在网上找了半天好像都没人遇到这个问题，看到这个才受到启发：https://forum.juce.com/t/missing-corecrt-h-and-windows-h-files-vs-2017/29195

如果新建了v141工具集的项目，再把Windows SDK版本设置为最新的话，就会找不到SDK里的头文件。要在设置里明确制定SDK的版本才行（例如我的是10.0.17763.0）。估计是VS2017支持自动识别的最高SDK版本是10.0.16299.0，超过了这个版本的话就不能自动识别了，导致IntelliSense认为找不到Windows SDK。

在粗读 Reservoir-based sampling over large graph streams to estimate triangle counts and node degrees 论文的时候，第一句就读到不认识的东西，真是开幕雷击= =

在详细了解后，发现蓄水池采样算法本身是一个十分简单的算法，采用巧妙的方法解决了一个如下的“简单”问题：

如何在内容和长度均未知的数据流中，仅遍历一遍，且在O(n)的时间复杂度内，任意、随机地选出m个数据来？*

* 问题相较于参考资料有所改变，将在文尾具体解释。

长度和内容均未知的数据流带来了以下问题：

1. 不一定能够使用存储设备完全储存（进一步说的话，可以特指内存）；
2. 不能预测且无法回看。

针对于题目的任意和随机性来看的话，上述第2点带来的问题就是，必须要对当前数据流中的任意元素进行等价的操作。也就是说，决定任何一个数据去或留（即是否加入最终选出的m个元素的集合）的时机，对于任何元素来说都应该是一样的。对于这种意义下的“操作时机”，我认为可以大致分为三类：

1. “当机立断”：获取到该数据的同时就对于数据的去向进行决定。此时，程序的内存占用量是可预测的，（按照单线程考虑的话）同一时刻内不会存有两个数据流内的数据；
2. “前看”：类似于编译原理中的前看原理，但是需要通过在程序中自行设立单独的“前看缓冲区”，通常来说，前看的深度是固定的；
3. “我全都要”：最让人喜闻乐见的方式，全读入内存，慢慢折腾。

显然，3是首先要排除的。题目中有提到数据流的长度是未知的，很有可能超出当前可能的内存容量。

那么问题的解决策略只能在1或者2中着手。由于本人数学水平实在有限，无法断定并证明其中某种思路的可行性，因而在此，只能说明，蓄水池采样算法是使用思路1，借助随机函数实现对于任意长度序列的所及元素选择。

接下来对于算法，使用类Java伪代码进行描述：

InputStream in;                    // 数据流
Data current;                      // 当前数据
Data ans[] = new Data[m];          // 为要选出的元素预留空间
Random rand = new Random();        // 随机数产生器
Integer index = 0;                 // 已读取的数据数量计数

while(in.hasNext()) {
    current = in.next(); index++;  // 读取了一个数据
    if(index <= m) {
        // 先把“蓄水池”填满，此时不存在元素冲突问题
        // 下标=元素个数-1
        ans[index - 1] = current;
    } else {
        // 从当前已读取的数据编号范围内选出一个，把刚读入的数据“放到”这个位置
        // 这里的randInt取值区间是左闭右开的
        Integer slot = rand.nextInt(0, index);
        if(slot < m) {
            // 若是这个位置是前m个之内的话，替换数据
            ans[slot] = current;
        }
        /* 否则不做任何处理 */
    }
}
return ans;

然后就是简单扼要的原理说明了。

先说结论：使用蓄水池采样算法，可以在仅遍历一遍数据流、且在O(n)时间复杂度的情况下，使得每个数据被选出的概率均为\frac{m}{N}。

证明如下：

将“数据能够在蓄水池中保留至结束”这一事件S(Select)分解为两个互相独立、串联的事件 [数据能够进入蓄水池I(In), 数据能够保留在蓄水池中K(Keep)]，则可以表示如下：

P(S)=P(I) \times P(K)

从上面的算法描述代码可以看出，第1 \sim m个元素进入蓄水池的概率为1，即

\tag{1} \forall i \in \{1, 2, ..., m\}, P(I_{i}) = 1

而第1 \sim m个元素中的任意一个要保留到最终的话，假设数据流长度为N，则应该要在接下来N-m次数据读取的操作中均不被替换掉。由于第j个数据输入时共有j种选择，则每一次替换时，蓄水池中的第i个元素有\frac{j-1}{j}的概率不被替换。由此则有第1 \sim m中任意一个元素保留到最终的概率为

\tag{2} \forall i \in \{1, 2, ..., m\}, P(K_{i}) = \frac{m}{m+1} \times \frac{m+1}{m+2} \times ... \times \frac{N-1}{N} = \frac{m}{N}

由(1)(2)可得

\tag{3} \forall i \in \{1, 2, ..., m\}, P(S_{i}) = P(I_{i}) \times P(K_{i}) = \frac{m}{N}

对于第m+1 \sim N个元素，由于此时蓄水池中已经装满元素了，需要以一定概率来替换已有元素，才能决定是否进入集合。由于新元素要进入集合只需替换原有集合中的任意一个即可，则有：

\tag{4} \forall i \in \{m+1, m+2, .... N\}, P(I_{i}) = \frac{m}{i}

可以发现此时位置不同的元素进入蓄水池的几率是随着位置向后推移而逐渐降低的。

继续计算这些元素保留到最终的概率，原理同公式(2)：

\tag{5} \forall i \in \{m+1, m+2, ..., N\}, P(K_{i}) = \frac{i}{i+1} \times \frac{i+1}{i+2} \times ... \times \frac{N-1}{N} = \frac{i}{N}

此时由(4)(5)可得：

\tag{6} \forall i \in \{m+1, m+2, ..., N\}, P(S_{i}) = P(I_{i}) \times P(K_{i}) = \frac{m}{N}

合并(3)(6)，神奇的事情发生了：

\forall i \in \{1, 2, ..., N\}, P(S_{i}) = \frac{m}{N}

证毕。

这也正是本算法的巧妙之处：不论原始数据流有多长，只要带选出的数据量m小于原始数据流的长度N，总能有办法随机、等概率地选出m个元素，即使N完全未知。

原文来自 https://www.jianshu.com/p/7a9ea6ece2af ，作者：邱simple。

在原文中，作者还讲述了分布式蓄水池抽样算法，并给出了Java代码的实现，如有需要可自行浏览。

这里简要说明一下开头提到的与原文中问题的区别。原文中问题还添加了“选出的元素不重复”这一限制条件，但是我认为，添加了该条件后，代码需要做出相应的改动（替换元素时的一些if条件），也不能称之为对原始数据流的等概率选取了，因而在本文中对命题进行了修改。如果有细心的读者发现了我的逻辑问题的话（万一有呢指读者），欢迎指正与交流。

今天在看acmeair的bash脚本的时候，发现里面有这么一行指令：

sed "s#IMAGE_NAME#${IMAGENAME}#g" ${YAML_FILE} > temp.yaml

当时想了一下，感觉那里不对劲：根据网上的教程来看的话，sed的s命令的用法不是类似于's/regexp/repl/g'这种格式吗？

然后仔细一想，既然能发布出来的代码，又是来自可信平台（IBM Cloud），肯定是有其原因的，或者说，至少是可以运行的。然后就动手尝试了一下：

echo '1 2' | sed -e 's/ / ^ /g'     #1
echo '1 2' | sed -e 's# # ^ #g'     #2
echo '1 2' | sed -e 's@ @ ^ @g'     #3
echo '1 2' | sed -e 's\ \ ^ \g'     #4
echo '1 2' | sed -e 's啊 啊 ^ 啊g'   #5

首先显而易见的，1是肯定可行的，可以将1 2这个字符串替换为1 ^ 2。意料之外的是，2-4全部可行，都能够正确地完成替换工作。5属于脑洞大开的想法。在发现前面1-4都能够使用任意单字符作为分隔符的话，那么中文字符可以完成相同的功能吗？

答案是否定的。sed给出了如下的错误信息：

sed: -e 表达式 #1, 字符 2: delimiter character is not a single-byte character↵
sed: -e expression #1, char 13: unknown option to `s'

其中第一行是在中文环境下的报错信息，第二行是英文环境。可以看到，在常见的环境下，都是不支持将多字节字符作为分隔符的。毕竟在计算机行业中，非英文语言体系的字符基本都可以视作“异端”，往往不能享受到英文字符的“优待”，需要使用一个以上字节进行信息的储存，所以对于只能使用单字节字符作为分隔符的sed来说自然会产生错误。

（思考题：那为何可以使用sed替换中文文本？） （答案是，只要sed将脚本序列和输入的数据流都视为单字节字符流，就可以使用字符序列替换的方法完成任务了）

实际上，在咕果上，能找到和sed分隔符相关的资料少之又少；有人在Unix论坛上发问了，虽然问题最终由作者自己看书解决，但是他并未分享自己看的是哪本书；StackOverflow上还有老哥说这就是注释，根本不能用的，等等。

直到后来看到了这个：https://backreference.org/2010/02/20/using-different-delimiters-in-sed/

博主说了这么一句：

It's a not-so-known fact that sed can use any character as separator for the "s" command.

真是not-so-known，网络上都没什么热门资料阐述这一点的= =

于是问题最终解决：

sed "s#IMAGE_NAME#${IMAGENAME}#g" ${YAML_FILE} > temp.yaml

等价于

sed "s/IMAGE_NAME/${IMAGENAME}/g" ${YAML_FILE} > temp.yaml

顺便给出上面使用的样例的升级版：（工作必备，除了你没人看得懂，专家职称、升职加薪预定）

echo '1 2' | sed -e 's \  \ ^\  g'

附录：对于非s的sed指令，仍然可以通过\*...*的方式，使用任意自定义的字符作为正则表达式的分隔符。

这是从去年开始的黑苹果大坑系列的延续。本来大约在五月份的时候就已经完成配置了，但是当时忙着补课就把记录这茬给忘了= =

机型是在最原始的GL553VD配置上替换了一些硬件。具体改动如下：

1. 网卡由Realtek RTL8723BE替换为Intel AC7265；
2. 新增Samsung PM981系列512G M.2固态硬盘一块。

之前本来用的是qiuchenly的Clover，但是在安装的时候都进不了安装器界面；后来在pcbeta上寻找本机型的支持情况，换了MohammadtaghiFarkhondekar的Clover。但是使用最新版的时候会出现一接入外置HDMI屏幕就立马重启的情况，后来发现需要使用V8而不是最新版，可以避免这个问题。

然后手动升级一下AppleALC.kext、手动安装itlwm.kext以解决声卡和无线网卡两个问题。可能还需要手动升级一下蓝牙的驱动IntelBluetoothFirmware.kext。（手写Intel Wifi驱动也太赞了吧 やばいですね☆）

顺带一提，旧版本AppleALC.kext能够正常驱动外置扬声器，但是耳机糊的没法听；升级版本后问题解决，但是需要注意一下，如果是从Windows重启到Mac OS这种热启动行为的话，外置扬声器是可能出现没有声音的情况的。此时应该从Windows关机后，重新按开机键进入Mac OS，方可解决问题。

安装系统的话，尽量低于10.15系列，因为在该系列下，fn快捷键都失效了。因而我的选择是10.14.6。

记住在安装和二次部署Mac OS的时候一定不要联网（包括有线和无线网）！在安装时联网的话，安装器会联网检查系统版本，不让安装太久以前的系统（根据个人实测，至少在10.15.5发布的时候安装10.14.6会失败的）。此时还是可以断网并使用命令行修改系统时间，继续安装的。二次部署的时候联网，我只能说「前功尽弃，请从头开始安装」——因为我也解释不清为什么会失败，只是知道这样一定出事罢了。

关于手头这块PM981，之前网络上流传有说苹果无法识别一类的，但是根据我的实际使用而言，在合适的配置之下，它不会妨碍系统启动，也能进行基本的使用，可以进行文件的读取（因为是NTFS格式，所以没有测试写入），但是进行高强度的读写时还是会翻车的（从PM981直接读取系统镜像的时候，读取速度达到了惊人的3.1GB/s，近乎满速，但是在验证镜像完整性的时候直接重启了）。这是由于PM981是Windows机型侧的OEM产品，三棒和苹果自然都没有理由为这一款产品在苹果系统上进行适配。如果要使用固态硬盘作为启动磁盘的话，建议还是选择其它在市场上广泛零售，或者是标注了有较好Mac系统兼容性的型号吧。