Skip to main content

9 posts tagged with "math"

View All Tags

租约

· One min read

A lease is a contract that gives its holder specified rights over property for a limited period of time. In the context of caching, a lease grants to its holder control over writes to the covered datum during the term of the lease, such that the server must obtain the approval of the leaseholder before the datum may be written. When a leaseholder grants approval for a write, it invalidates its local copy of the da 租约是一个租约持有人在一定时间内有特别的权限的合约. 在缓存这个场景下,租约保证他的持有人在租约期限内有写的权限 , 所以当服务器

相关阅读​

  • Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency

泛型

· 2 min read

对于没有泛型的情况 比如

max(a : int , b:int){
    xxx
}

入参是a , b ,这两个参数的类型的约束是 int , 也就是这个函数的约束是 max(int , int) 泛型的语义就是:

max(a :<T> , b:<T>){

}

这个约束是什么?

约束变成 max(<T> ,<T>)

作用: 我们的约束变更加范化了,这个如果按照编译原理或者解空间来说,我们可选的映射更多了.

泛型的作用:和类的继承差不多,因为继承既是优点也是缺点.

泛型这个约束也是既有优点也有缺点,泛型的优点是更加接近无类型类型,所以缺点也是大家会滥用无类型的内容

就像继承一样,其实很多继承是没有必要的,或者重构的继承非常难.

说到底,如果我们写了一个通用的轮子,如果和多地方用到了这个轮子,那么如果这个轮子经常更改,就需要考虑用到这个轮子的相关代码是不是要兼容

如果这个轮子被共用的地方少,那么就不用兼容那么多

所以我们抽象就比如面临改动频繁的缺点

约束和结构

· One min read

结构和性质是同构的吗?

约束和结构是同构的吗?

我一直觉得,我们之所以很难维护好业务代码,是因为我们的约束和我们的业务不是同构的,我们一个又一个函数在传递,大部分时间都工作得很好,但是总有一些误差经过传递之后会被触发.

为什么代码庞大之后很难改? 因为经过传递之后依赖太多值了.对于一个函数来说(a , b) -> (c) , 一开始只依赖a和b

过了几天,我们改了a的依赖,a依赖于d,e 然后就这样了(d,e) -> (a)

这样一直迭代后,依赖就没人能理清了

循环不变式loop invariants

· 2 min read

控制流图​

入口和出口​

入口 --->   判断 ---> 出口
        |    |
        |    |
        |____|

对于每个判断,有两个入口: 第一次入口 , 后续的入口 对于每个判断,有两个出口:exit跳出循环, 继续循环

1 第一次入口满足断言 2 每次判断继续循环满足断言

我们可以得出结论: 出口必然满足断言

- 判断不改变断言
- 每个入口都满足断言
可以推出exit满足断言

如何形式化证明​

如果证明,或者如何抽象出这个证明或者我们找到一个同构的问题

循环不变式核心是 满足约束: 1 初始化条件满足断言 2 每次迭代后满足断言 3 循环是可计算的(不是死循环)

其实3只是为了不会死循环,核心条件是1和2

规则系统

· One min read

我一直对所谓的可扩展性什么的很有疑惑，或者说我们要怎么设计一个规则系统，怎么知道这个规则的集合的边界在哪里

第一个例子： 流水线

流水线上每个节点都是一个回调，我们可以随意添加或者删除

有向无环图 等价于原始递归函数

这个规则系统的路径则需要输入来确定，所以和语言是等价的

所以一个规则系统等价于一个语言，所以我们可以使用一些内容来等价和变换

math

· 2 min read

其中一种是基于锁 我之前一直对acid理解有问题，锁和事务的关系，其实是这样的：

1 read(x) 和write(x)是不可以交换顺序的 2 write(x) write(x) 是不可以交换顺序的 3 write(x) 和read(x) 也是不可以交换顺序的

我们的事务 t1和t2 如果完全按照先执行t1再执行t2 就一点问题都没有，就是有点慢，并发低。

那么我们就用一些等价的方法，尽量减少阻塞。我们不锁住整个事务，只对冲突的部分进行锁定，其他就因为等价所以顺序没有关系，因为其他部分没有顺序关系，所以不用上锁，所以并发会上去

类型是什么？ 类型描述了一个特别的集合

结构体是什么？

结构图本质是类型的组合，也就是关系

举个例子

struct{
    int a,
    int b
}

这个本质是 RXR 的关系 ，那一个结构体的变量又是什么？ 是这个关系的一个元素

递归是什么？ 递归是差分方程，递归是不动点，但是递归的内容还得看

什么是可扩展性？

BNF 或者类似的规则系统为什么是正确的？ 靠什么保证？是依赖范畴学或者其他数学的什么定理或者和数学的什么模型一致？ 我一直很好奇规则系统的约束怎么做到的？因为规则系统真的很神奇

induction

· One min read

前言​

归纳法是一个很特别的推理方式。使用自然数的映射。（我的理解可能不太对）

Mathematical induction​

数学归纳法

  • P(0) is true
  • If P(m) is true then so is P(m + 1) for any natural number m. (P(O) & (Vm E w. P(m) =} P(m + 1)) =} Vn E w. P(n).

well define​

Q 的非空子集有最小值

induction 举例​

BNF 是一个典型的递归定义集合（induction define set） 。 归纳法有个很特别的东西，就是用一个很短的表达式描述一个有限集合

Recursive definitions of sets​

举例： 自然数集合：
P(0) = 0 ; P(N+1) = P(N)+1

相关阅读​