Fade Temple

加权随机抽样

原论文《Weighted Random Sampling》来自Efraimidis、Spiraki， 发表于2005年，以下为部分翻译 问题定义 不放回随机抽样（random sampling without replacement(RS)）问题要求从大小为\(n\)的集合中，随机抽取\(m\)个不同元素。如果所有的元素被抽取出来的概率一致，则称之为均匀随机抽样（uniform RS）。一次遍历解决均匀随机抽样问题在推荐阅读的[1,5,10]中有讨论。在数据流上使用蓄水池类型（Reservoir-type）均匀随机抽样算法在推荐阅读[11]给出。推荐阅读[9]给出了一种可并行计算的均匀随机抽样算法。对于加权随机抽样（weighted random smapling(WSR)），它指的是所有元素都含有权重，每一个元素被取出的概率是由元素本身的权重决定的。WSR问题可以使用以下算法D来定义: 算法D，WRS定义 输入：含有\(n\)个带权重元素的集合\(V\) 输出：含有\(m\)个元素的加权随机抽样结果集\(S\)     1： for \(k = 1\) to \(m\) do     2：     元素\(v_i\)在第\(k\)回合被选出来的概率为\(p_i(k)=\frac{w_i}{\sum_{s_j\in V-S} w_j}\)     3：     从\(V-S\)中选出\(v_i\)，然后插入到S中     4：...

蓄水水池抽样---从未知长度的序列中随机抽取m个元素

在遇到问题时，突然发现了一种精妙的算法，那可真谓是美丽的邂逅。 场景描述 在一个链表(l)里，随机获取m个元素，这m个元素满足给定的条件，并且保证所有满足条件的元素被取出来的概率相等。假设满足条件的元素个数为n，则每一个元素被取出的概率为\(\frac{m}{n}\) 解法 package main import ( "container/list" "math/rand" ) // 假定目标的数据结构 type Data struct { Condition int Value int } func ReservoirSample(l *list.List, m int, cond int) []*Data...

致格沫

如果 你愿意 我可以静静地凝视 你甜甜的微笑 印在我脑海里 你无与伦比的美丽 如果 你愿意 我可以慢慢地倾听 你柔柔的言语 化在我心海里 你花开般的声音 如果 你愿意 我可以细细地珍藏 你留下的东西 放在我梦里 你与我美好的回忆 那么今天 我捧着一颗真诚的心 在远方的冬日里 向你讲述我的思念 向你表白 我的心意 格沫 对于今后那 无尽的晴空 满天的繁星 我们一起度过 你愿不愿意...

苹果电脑上的软件使用技巧

macOS版本：10.13.3 High Sierra VirtualBox的文件夹共享 下载安装完VirtualBox(版本号5.2.6 r120293) 使用另外下载好的ubuntu-17.10.1-server-amd64.iso安装Ubuntu17.10 (Guest OS) 从Settings=>Shared Folders=>点击添加按钮=> 选择宿主机文件夹（如/Users/liqingshou/Work）=> 文件夹名称（随意，如Work）=> 勾起Auto-mount（自动挂载）和Make Permanent（永久创建） 遇到问题 设置完之后，无法在系统里找到对应的挂载文件 发现/mnt或者/media目录都是空的，/dev也找不到，查了才知道需要安装GuestAdditions 下载Extendsion Pack: Oracle_VM_VirtualBox_Extension_Pack-5.2.6-120293.vbox-extpack，并双击安装 启动Ubuntu 在VirtualBox的菜单上找到Device=>Insert Guest Additions CD Image 如果出现 Unable to...

浅析TCP协议

谈到TCP连接，三次握手这个名词都会在大多数人的脑海里浮现。 那么三次握手的过程是什么样的？每个阶段的包都有什么样特征？ 最近把《计算机网络》这本教材的”运输层”这一章重新复习一遍，整理成本文。 TCP连接的特点 面向连接 在使用TCP传输数据之前，必须先建立TCP连接，每一条连接只能连接两个端点，一般我们使用以下四元组来标识一条连接 {(端点1IP, 端点1Port), (端点2IP, 端点2Port)} TCP连接只是一条虚拟的连接，他并不是固定的一条物理链路 可靠交付 TCP提供可靠的交付服务，数据无差错，不丢失，不重复，并且按序到达（对于应用层来说） 与之相对，UDP提供尽最大努力交付 全双工通信 所谓全双工，是指在同一时间，两个端点皆可发送数据和接收数据。 TCP在两端都设置有接收和发送缓冲区: 对于接收缓冲区，它是用来缓存接收到的数据，应用层可以在合适的时候读取缓冲区的内容； 对于发送缓冲区，应用层在发送数据时，只是将数据先放入到发送缓冲区，TCP会在合适的时间将这些数据发送出去。 面向字节流 TCP将应用层交下来的数据看成一连串无结构的字节流，应用层不必关心这些字节流被拆成多少个包来发送，接收方在应用层看到的是和发送端一样大小，一样顺序的字节流 TCP报文段的格式 虽然TCP是面向字节流的，但传输单元实际上是报文段，报文段可分为首部和数据两部分 以下是TCP报文段首部格式 TCP首部的前20个字节是固定的，后续可以跟4N个可选的选项数据 源端口和目的端口: 各占用2字节，所以端口号的范围是0~65535 序号：占用4字节；TCP传输的数据每一个字节都是编号的，此序号表示本次发送的第一个字节编号；当序号增加到2的32次方减1（4G数据）后，又会从0开始 确认号：占用4个字节，表示期望收到的下一个数据的编号，例如B正确收到了A发送过来的一个报文段，编号为501，数据长度为200，则B收到A的最后一个字节编码是700，期望收到的下一个数序序号为701，所以确认号为701 数据偏移：占用4位，表示TCP数据部分距离起整个报文起始位置的偏移，此值的单位为4字节，所以选项的最大长度为...

当我们凶狠地对待这个世界时，这个世界突然变得温文尔雅了。 – 余华《在细雨中呼喊》