海屿文章列表

比较排序与计数排序时间复杂度的证明

比较排序

对于任意的比较排序算法,我们都能将其操作抽象成一颗决策树,这是一颗完全二叉树,它表示了某一排序算法对所有元素的比较操作。下图是插入排序的例子:
批注 2019-09-04 010631.jpg

每一条路径都是一种可能性,所以算法的最坏情况下的排序次数就是决策树的高度。

n个元素,可能的排序结果有A(n,n-1)=n!种,假设此时的树高为h,则叶子节点最多为2^(h+1)

2^(h+1) ≥ n!  
h + 1 ≥ log2(n!)

log(n!) = O(nlogn)

证明:

不等式缩放

log(n!) = log1 + ... + logn ≥ n/2 * log(n/2) = n/2 * logn - n/2 = c1 * logn
log(n!) = log1 + ... + logn ≤ nlogn = c2 * logn

Stirling 近似

76029ac06006a23f29011873c13a7a64541c6acd.svg

a35e8e0205988cf8552eec558d121f764d7e4021.svg

计数排序

计数排序的思想是:在待排序序列中,如果我们能统计出有多少元素小于或等于某一个元素,我们也就知道了该元素的正确位置。
例如:有五个元素小于x,那么就把x放到第六位(对于相同的元素我们认为最早遇到小于后面遇到的)。

实现该算法我们需要三个数组,初始input,结果output和表示元素统计数的count数组。
下面为算法的伪代码:

count = array of k+1 zeros
for x in input:
   count[key(x)] += 1

total = 0
for i in 0, 1, ... k:
   count[i], total = total, count[i] + total

output = array of the same length as input
for x in input:
   output[count[key(x)]] = x
   count[key(x)] += 1

return output

算法可视化

时间复杂度分析:假设在[0,k]的n个元素,数组初始化O(k),构造统计数组C是O(n),统计数累加O(k),排序是O(n)
所以总共时间复杂度为O(k+n)

计数排序是一种典型空间换时间的算法。

性能比较

下面是JS中的性能对比:

Array with 10000000 elements:
n log(n) takes 15.611 seconds
Linear takes 3.896 seconds

参考文章:
https://medium.com/free-code-camp/my-favorite-linear-time-sorting-algorithm-f82f88b5daa1

虚骄之气与狭隘的国家主义

摘取《美国十讲》中第十讲 美国与中国的几句话,很适合当下:

把自己所有的缺点,就是我们发生的坏事情和国内的问题,都怪在外国人身上,这是一种很没出息的表现。所谓“境外敌对势力”也被滥用。把自己国内的问题,由于社会不公而出现的不平之鸣,都说成是“境外敌对势力”策动的。

我们的主流媒体很喜欢夸耀国力,或有选择地、断章取义地转载外国人吹捧中国的话,这会误导公众。中国过去的仁人志士都是有很深的忧患意识,而现在改革开放以后起来的一代人,忧患意识比较少,对实际国情缺乏了解,这是很危险的,但是这不能怪年轻人。

力歌颂“盛世”,给人虚幻的印象,无助于我们自己埋头苦干努力解决自己的问题。

Js 中的 CSP(Communicating Sequential Processes)

dd839ff45691d9737ce18a35a1f27f5c.jpg

什么是 CSP(Communicating Sequential Processes)?

CSP是由托尼霍尔在1978年发表的一种形式语言规范,中文翻译为通信顺序进程,用于描述并发系统中的通信模式。Go语言原生支持,Clojure有core.async。

并发的系统的实现

为了设计并发系统,并发进程/任务/作业/应用程序必须能够进行通信。广泛采用的方法是使用公共存储(数据源)。但是,如果数据源以不需要的顺序写入和读取,则问题是竞争条件和不可靠性。

  • 公共存储

    • Threads
    • Locks
    • 互斥 Mutexes
  • 消息传递 (CSP and Actor Model)

    • Processes
    • Messages
    • No shared data

并发不是并行

例程A将消息放入某个通道。然后停止,直到例程B准备好接收该消息。在服用它之后,B运行直到它接下来接受指令并且退后,因此常规A可以再次运行并且它可以无休止地运行。

没有并行性的并发性:不是操作系统的线程,而是将一个操作系统线程分段使用。

csp_illustration2.png

下面使用js-csp中的一个例子,两个process之间打乒乓球:

import {
 go,
 chan,
 take,
 put,
} from 'js-csp'
const ping = chan()
const pong = chan()
go(function * () {
 yield take(ping)
 console.log('ping')
 yield put(pong, true)
})
go(function * () {
 yield take(pong)
 console.log('pong')
 yield put(ping, true)
})
put(ping, true)
// > 'ping'
// > 'pong'
// > 'ping'
// > 'pong'
// > 'ping'
// > 'pong'
...

CSP与 Actor 模型

Actor模型,又叫参与者模型,其”一切皆参与者(actor)”的理念与面向对象编程的“一切皆是对象”类似,但是面向对象编程中对象的交互通常是顺序执行的(占用的是调用方的时间片,是否并发由调用方决定),而Actor模型中actor的交互是并行执行的(不占用调用方的时间片,是否并发由自己决定)。

从actor自身来说,它的行为模式可简化为:

  • 发送消息给其它的actor
  • 接收并处理消息,更新自己的状态
  • 创建其它的actor

区别

  • Actor中实体和通信介质是紧耦合的,一个Actor持有一个Mailbox,而CSP中process和channel是解耦的,没有从属关系。从这一层来说,CSP更加灵活
  • Actor模型中actor是主体,mailbox是匿名的,CSP模型中channel是主体,process是匿名的。从这一层来说,由于Actor不关心通信介质,底层通信对应用层是透明的。因此在分布式和容错方面更有优势。

关键概念与实现

  • 顺序处理(processes)
  • 通过通道(channel)进行同步通信
  • 通道的多路复用与交替

channel 是一个队列,Processes 通过channel进行通信,Processes 可以暂停来等待 channel 中的值。
processer 是一个Pull模型的迭代器,它不断从 channel 取出最新的值,如果没有值就暂停执行。

Processes

async function process (inChannel, outChannel) {
  while (true) {
    const msg = await inChannel.take();
    // do stuff with msg
    await outChannel.put(res);
  }
};

我们使用[Symbol.asyncIterator]channer成为可迭代对象,然后使用for-await-of语法会更加简洁,同时通过这个while(true)不难理解 process 一直从channer拉取数据:

public async *[Symbol.asyncIterator](): AsyncIterableIterator<T> {
    while (true) {
        yield await this.take();
    }
}
async function process (inChannel, outChannel) {
  for await(const msg of inChannel) {
    // do stuff with msg
    await outChannel.put(res);
  }
};

Channel

在Channel中实现了messages putters takers racers 这几个队列。
put 操作返回一个Promise,在该Promise中 首先将传入的参数放到messages,然后将resolve函数放到putters,然后判断takers队列是否有值。

  • 如果已经有taker 或racers等待消息,则返回的承诺将立即得到解决
  • 如果taker 和racers都在等待消息,则优先权将给予将检索该消息的接受者

可以对channel队列进行操作,例如过滤,遍历等等,多个channel之间还可以广播,或者合并。

更多资料

https://arild.github.io/csp-presentation/
https://github.com/jfet97/csp
https://pusher.com/sessions/meetup/the-js-roundabout/csp-in-js
Javascript中的CSP快速入门

使用SVG Patterns作为平铺背景

<svg width="100%" height="100%">
    <defs>
        <pattern id="polka-dots" x="0" y="0" width="100" height="100" patternUnits="userSpaceOnUse">
             
            <circle fill="#bee9e8" cx="50" cy="50" r="25">
            </circle>
             
        </pattern>
    </defs>
     
    <rect x="0" y="0" width="100%" height="100%" fill="url(#polka-dots)"></rect>
</svg>

defs标签内定义一个pattern并提供一个id,让后将fill属性指向该ID的URL : fill="url(#polka-dots)"。
效果如下:

更多的属性可以在这里尝试

对比传统的css平铺

😡CSS平铺缺点:

  • 与位图一起使用时,它不可扩展
  • 性能较低
  • 更难以定制
  • 仅限于矩形重复

😀SVG模式专业人士:

  • 轻量级
  • 从CSS自定义
  • 可扩展
  • 能够创建复杂的模式

http://www.heropatterns.com/

⌚️Intl.DateTimeFormat.format 与 Date.toLocaleString

两种方法使用方法基本一致,第一个参数可以接受BCP 47 标准的字符串,或者一个包含区域,时间格式的字符串数组。
第二个参数接受一个格式化的配置项,包含时间样式,时区,格式匹配器。下面是一个格式化utc时间戳的例子。

const DateTimeFormat = new Intl.DateTimeFormat('zh-CN', {
    year: 'numeric', month: 'numeric', day: 'numeric',
    hour: 'numeric', minute: 'numeric', second: 'numeric',
    hour12: false,
});
function formatTime(utc) {
    return DateTimeFormat.format(utc);
}

formatTime(new Date)
// "2019/8/24 02:29:38"

Intl.DateTimeFormat.prototype.format 不需要每次都设置区域设置和选项,所以它的性能更好,但是Intl是ecma402中添加的内容,兼容没有toLocaleString好。