海屿文章列表

Boyer-Moore多数表决算法

问题陈述

假设你有一个未排序的值列表。你想知道列表中是否存在该列表中一半以上元素的值。如果有则这个值是什么?尽可能高效地完成此任务。

出现此问题的一个常见原因可能是容错计算。执行多个冗余计算,然后验证大多数结果是否一致。‘

简单的解决方案

简单的解决方案是哈希表。时间复杂度是O(N),空间复杂度是O(N)。

Boyer-Moore多数表决算法

首先检查该count值。如果计数等于0,则将设置candidate为当前元素的值。接下来,首先将元素的值与当前candidate值进行比较。如果它们相同,则增加count1。如果它们不同,则减少count1。

candidate = 0
count = 0
for value in input:
  if count == 0:
    candidate = value
  if candidate == value:
    count += 1
  else:
    count -= 1

最终 candidate 即为众数,该算法空间复杂度是O(1)。

我们用下面一组数据来理解,我们把 5 看成 -1 ;0 看成 +1 ,只要不同就相互抵消,相同的元素相加,多的一方一定会把另一方抵消掉。下面是计算过程:

[5, 5, 0, 0, 0, 5, 0, 0, 5]

[1, 2, 1, 0, 1, 0, 1, 2, 1]  // count 取值

[5, 5, 5, 5, 0, 0, 0, 0, 0]  // candidate 取值

推广

每次删除三个不相同的数,最后留下的可能是出现次数超过1/3的数,这个思想可以推广到出现次数超过1/k次的元素有哪些。需要注意的是最后还需要再遍历一遍结果,判断次数最多和次多的是不是超过了⌊ n/3 ⌋次。

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int m = 0, n = 0, cm = 0, cn = 0;
        for (int i : nums) {
            if (m == i) {
                ++cm;
            } else if (n == i) {
                ++cn;
            } else if (cm == 0) {
                m = i;
                cm = 1;
            } else if (cn == 0) {
                n = i;
                cn = 1;
            } else {
                --cm;
                --cn;
            }
        }
        cm = cn = 0;
        for (int i : nums) {
            if (i == m)
                ++cm;
            else if (i == n)
                ++cn;
        }
        vector<int> res;
        const int N = nums.size();
        if (cm > N / 3)
            res.push_back(m);
        if (cn > N / 3)
            res.push_back(n);
        return res;
    }
};

并行计算

Finding the Majority Element in Parallel

以 [1, 1, 1, 2, 1, 2, 1, 2, 2] 为例,我们可以将其拆开。

分组1:
[1, 1, 1, 2, 1]
candidate = 1
count = 3

分组2:
[2, 1, 2, 2]
candidate = 2
count = 2

可以将第1部分的结果视为与[1,1,1]相同,而将第2部分的结果视为与[2,2]。

参考文章:

https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html

Javascript 中的 RAII?

RAII 的全称是 “Resource Acquisition is Initialization” 1(资源获取即初始化),它是C++之父Bjarne Stroustrup提出的设计理念,目的是确保异常下的资源管理。换句话说,不管当前作用域以何种方式退出,都会执行资源释放等操作。

C++中 RAII 应用很广,C++11 中的两种基本的锁类型,lock_guard 和 unique_lock ,通过对lock和unlock进行一次薄的封装,实现了自动unlock。

std::lock_guard其功能是在对象构造时将mutex加锁,析构时对mutex解锁,这样一个栈对象保证了在异常情形下mutex可以在lock_guard对象析构被解锁,lock_guard拥有mutex的所有权。

使用try { ... } finally { ... }语句也可以实现类似效果。

下面是在 Node 中写文件为例,我们需要显式关闭流。

function hello(cb) {
  var stream = fs.createWriteStream('example.txt')
  stream.write('Hello World')
  stream.close()
}

如果在两者之间抛出异常,流将泄漏;至少直到下一次垃圾回收为止。

我们可以使用闭包或Promise,创建流然后调用处理程序,最后的finally确保我们可以正确关闭流。

function usingWriteStream(name, handler) {
  var stream = fs.createWriteStream('example.txt')
  try {
    return handler(stream)
  } finally {
    stream.close()
  }
}

function hello() {
  usingWriteStream('example.txt', (stream) => {
    stream.write('Hello World')
  }
}

更进一步,Node中创建流的函数有很多,所以我们还能改造一下,把流的创建函数作为参数。

var usingWriteStream = (name, handler) =>
  usingStream(fs.createWriteStream.bind(null, name), name)

多亏了闭包,我们可以在Javascript中构建类似于RAII的模式,以确保我们的资源不会泄漏。
即使在无法立即识别“资源”的情况下,这在许多情况下也很有用。

例如 Immutable.js 中的 [Map.withMutations()] 使用相似的模式:

const { Map } = require('immutable')
const map1 = Map()
const map2 = map1.withMutations(map => {
  map.set('a', 1).set('b', 2).set('c', 3)
})
assert.equal(map1.size, 0)
assert.equal(map2.size, 3)

这里会创建2个而非4个新的Map,可变 map就是资源。这样可以确保此对象不会轻易泄漏到当前作用之外,并且可以正确地将其转换回不可变 Map。

在C#中有一个 using 语法 ,其实就是 finally 的语法糖。我们可以在TS中去模拟:

interface IDisposable {
    dispose();
}

function using<T extends IDisposable,
    T2 extends IDisposable,
    T3 extends IDisposable>(disposable: [T, T2, T3], action: (r: T, r2: T2, r3: T3) => void);
function using<T extends IDisposable, T2 extends IDisposable>(disposable: [T, T2], action: (r: T, r2: T2) => void);
function using<T extends IDisposable>(disposable: T, action: (r: T) => void);
function using(disposable: IDisposable[], action: (...r: IDisposable[]) => void)
function using(disposable: IDisposable | IDisposable[], action: (...r: IDisposable[]) => void) {
    let disposableArray = disposable instanceof Array ? disposable : [disposable];
    try {
        action(...disposableArray);
    } finally {
        disposableArray.forEach(d => d.dispose());
    }
}


// Usage
class UserNotify { dispose() { console.log("Done"); } }

class Other { dispose() { console.log("Done Other"); } }

using(new UserNotify(), userNotify => {
    console.log("DoStuff");
})
// It will type the arrow function parameter correctly for up to 3 parameters, but you can add more overloads above.
using([new UserNotify(), new Other()], (userNotify, other) => {
    console.log("DoStuff");
})

上面的种种还是没法和RAII比,特别是在释放的资源有多个的时候,只能在 finally 中挨个检查各个资源是否已经被申请。例如:

  void f()
  {
    try {
      acquire resource1;
      … // #1
      acquire resource2;
      … // #2
      acquire resourceN;
      … // #N
    } finally {
      if(resource1 is acquired) release resource1;
      if(resource2 is acquired) release resource2;
      …
      if(resourceN is acquired) release resourceN;
    }
  }

参考文章:

https://stackoverflow.com/questions/47788722/idisposable-raii-in-typescript/47792127#47792127
https://www.zhihu.com/question/20805826

表驱动法(Table-Driven Approach)

1_l7Hjzbw8oHpa39gF8GkW9Q.png

表示原则:把知识叠入数据以求逻辑质朴而健壮。 ——《UNIX编程艺术》

表驱动法是一种编程模式——从表里查找信息而不是使用逻辑语句。
随着逻辑复杂性的增加,if/else 或switch中的代码将变得越来越肿,所以我们常说数据比程序逻辑更易驾驭。表驱动法就是将这些逻辑中的数据与逻辑分开,从而减少逻辑的复杂度。查表方式通常有如下几种:

直接访问

以一个月的天数为例,我们要写一串if/else 或者switch/case 来表达逻辑。

  if(1 == iMonth) {iDays = 31;}
  else if(2 == iMonth) {iDays = 28;}
  else if(3 == iMonth) {iDays = 31;}
  else if(4 == iMonth) {iDays = 30;}
  else if(5 == iMonth) {iDays = 31;}
  else if(6 == iMonth) {iDays = 30;}
  else if(7 == iMonth) {iDays = 31;}
  else if(8 == iMonth) {iDays = 31;}
  else if(9 == iMonth) {iDays = 30;}
  else if(10 == iMonth) {iDays = 31;}
  else if(11 == iMonth) {iDays = 30;}
  else if(12 == iMonth) {iDays = 31;}

但是我们把数据存到一张表里,就不需要冗余的逻辑了。

const month = {
  monthTable: [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31],
  get days(month, year) {
    // (year % 4 === 0) && (year % 100 !== 0 || year % 400 === 0) 闰年逻辑 
    return [month - 1];
  }
}

索引访问

有时通过一次键值转换(对象或者数组),依然无法找到键值。此时可将转换的对应关系写到一个索引表里,即索引访问。而且可以多重索引,或者使用正则匹配。

我们可以利用Map结构的key可以为基本类型这一特点:

const actions = new Map([
  [{identity:'guest',status:1},()=>{/*do sth*/}],
  [{identity:'guest',status:2},()=>{/*do sth*/}],
  //...
])

const onButtonClick = (identity,status)=>{
  let action = [...actions].filter(([key,value])=>(key.identity == identity && key.status == status))
  action.forEach(([key,value])=>value.call(this))
}

进一步的我们也可以利用正则:

const actions = ()=>{
  const functionA = ()=>{/*do sth*/}
  const functionB = ()=>{/*do sth*/}
  const functionC = ()=>{/*send log*/}
  return new Map([
    [/^guest_[1-4]$/,functionA],
    [/^guest_5$/,functionB],
    [/^guest_.*$/,functionC],
    //...
  ])
}

const onButtonClick = (identity,status)=>{
  let action = [...actions()].filter(([key,value])=>(key.test(`${identity}_${status}`)))
  action.forEach(([key,value])=>value.call(this))
}

特别的,对于布尔类型我们还可以使用二维数组或多维数组。

const actions = [
    //!a a
    [1, 2],  // !b
    [3, 4]   //  b 
]

阶梯访问

对于一些无规则的数据,例如等级划分。我们没法使用简单的转换将数据转换为索引,但是我们可以使用一个循环,依次检查区间的上下限。

需要注意的细节

  • 谨慎处理区间端点
  • 可以采用二分/索引加速
const grade = [59,79,84,89,94,100]; 
const level = ["F","E","D","C","B","A"];


const getLevel = g =>{
    for(let i = 0 ; i < grade.length ; i++){
        if(g <= grade[i]) return level[i];
    }
}

表驱动的优势

  • 可读性更强,逻辑一目了然
  • 数据与逻辑解耦,修改数据即可
  • 逻辑可重用

参考文章:

https://www.cnblogs.com/clover-toeic/p/3730362.html
https://juejin.im/post/5dbff51bf265da4d4e3001b2#heading-2
https://medium.com/javascript-in-plain-english/clean-up-your-code-by-removing-if-else-statements-31102fe3b083

JavaScript 中的 Quine

Quine:一个能够打印自己源代码的程序

你可以试试执行以下

!function $(){console.log('!'+$+'()')}()

为什么起作用?上面的代码使用了一些技巧。

获取源代码最简单的方式是使用String

function foo() { return "abc" }
String(foo)

// function foo() { return "abc" }

所以我们第一个版本 可以是这样

function $() { console.log(String($)) } ,但是我们需要再执行 $() 才可以。
所以我我们使用IIFE继续进行改造。

!function $() { console.log(String($)) }()

//function $() { console.log(String($)) }
//true (!undefined的结果为true)

最后加上感叹号即可。

看看下面这个,意思也一样((((function $(){console.log('(((('+$+'()))))')}()))))

更多有意思的例子:

  • (function _(){return'('+_+')()'})()
  • (_=()=>(_=${_})())()

参考文章:

http://rosettacode.org/wiki/Quine#JavaScript
https://2ality.com/2012/09/javascript-quine.html

冲突型社会模式

达伦多夫冲突理论

达伦多夫理论最为重要的基本假设和出发点是“冲突型社会模式”。
现实中不存在一个持续的稳定,各要素都很好整合的结构。
就像一碗水,你可以把它端的相对平,但你永远无法让它绝对水平。而且你越努力把它端平你的手就越容易酸,持续的时间就越短。

达伦多夫提出了四个西方工业社会的变化:

  • 所有权与控制权分离
  • 技术工人增加
  • 中产阶级变化
  • 阶级冲突的制度化

    • 资本与劳动之间的紧张关系已经被制度化缓解了,制度使得两者之间的关系合法化,从而阶级斗争的方法、武器和技术就被置于制度的有效控制之下。这样,阶级斗争就走出了误区,它变为相互平衡的权力之间的合法斗争,资本与劳动的冲突就变成关于工资水平、劳动时间、劳动条件的谈判或协商。

马克思认为资本主义的冲突会越来越激烈,而在西方社会的现实中,这种冲突找到了制度化的调节方式。
工业社会能够处理内在结构造成的冲突,这里的冲突已经变成一种市场关系。

### 冲突的后果
冲突不是坏的,而是社会结构中一个必不可少的,基本的组成。

  • 冲突有助于社会体系的整合。
  • 冲突有助于创造变迁(改良而不是革命,比如在野党通过选举变成执政党,或者体现在立法与政策上)

冲突的调节

有效的调节需要具备一下三个条件:

  • 冲突双方认识到冲突这一客观事实,一味对立否认,强调共同利益,抹杀冲突界限,反而不利于冲突调节,只能酝酿更大的冲突。
  • 冲突的利益群体必须有组织
  • 双方必须遵循正式的游戏规则(所以最为关键的是将冲突规则制度化,保障双方的利益)

引用:

李强 著. 社会分层十讲 (清华社会学讲义) (Chinese Edition) (Kindle 位置 1099-1100). 社会科学文献出版社. Kindle 版本.