#School #life duangsuse 清明好！放假三天！

三天里不打算熬夜。

#CS #fix 下面我来给大家解释一下停机问题和 NP 困难到底是什么，和我这里提到的 NP-hard 和停机问题指的是什么。


== 上个消息里，我对 NP-hard 和 停机问题 的理解

NP-hard: 就是 NP 完全问题，算法上，就是指很难解决的问题，比如旅行商问题和集合覆盖问题，这类问题的最优解通常要枚举出幂(mì)集（所有可能出现的子集甚至序列），使用穷举法，他们的时间复杂度甚至可能是 O(n!) （n! 代表 factorial(n)）

这是相当恐怖的时间复杂度，这意味着只要需要处理的数据集足够大 — 并不需要太大的数据输入，程序就无法在一个合理的时间内得到解了。

故此，一般使用贪婪算法得到近似解。

也可以了解一下 Ackerman 函数，但由于我不是特别了解算法和线性代数、离散数学什么的.... 也要学啦。
啊因为提到了 Ackerman 函数，不如再提一下 Collatz 函数 Collatz 猜想

这是错误的理解（指 NP-hard = NP-complete），而且 NP-hardness 和 NP-completeness 也不是一个概念

停机问题: 一个确定性问题，当时被我当成了一个命题（误会，因为确定性问题不一定是命题...）

就是说：有没有一个程序，可以判断所有程序是否能在有限的时间内完成计算？

这应该不是一个命题（不是陈述句）

不过可以改成陈述句的形式，这涉及到自然语言处理（语言学）的内容... 欸话说大家知道啥是谓词么？谓词（predicate）在计算机科学中也是一个专业术语。

猫"是"动物

—

我(r)"爱"(v)你

(r)


主 动(谓词) 宾

汉语的谓词包括动词和形容词


欸话说，机器学习是个好东西，让程序自己根据数据来造更有意义的数据是很有趣的事情，对 NLP 来说，可是我不知道 HMM(隐马尔科夫链) 这些东西... 话说 Regex 模式匹配用的状态机 DFA, NFA 什么的也不清楚，只是刚好入门软件工程而已，电子电路和数控、CAD、PLC/PLA 什么的也不了解... 尤其是线性代数和优化问题、机器学习、DIP、3D Modeling(欸怎么跨界了？) 什么的...

https://github.com/hankcs/HanLP/

但其实呢，停机问题是（在图灵完全的模型里）判断一个程序是否能在有限时间内完成的确定性问题，并且，当然地，这个解决方案得是停机的

这是不可能解决的问题。因为如果能判断的话，就只能证明这个问题不可判断了，或者说（从某王博客上抄的，我记得他有发）

（没抄到... 忘记哪篇博文了）

The halting problem is the problem of determining, when running an arbitrary program with an input, whether the program halts (finish running) or does not halt (run forever).

也可以参考理发师悖论

因为如果有一个程序可以判断它自己是否停机，它就可以利用判断的结果进行相反的操作（比如判断是否停机，如果是，则直接无限循环，否则就真正让程序停机）

https://weblogs.asp.net/dixin/lambda-calculus-via-c-sharp-24-undecidability-of-equivalence #CSharp

借用一下里面直接的结果（过程很长，而且 Lambda calculus 比较需要一些时间 beta-reduction...）：
So (IsNotHalting IsNotHalting) is reduced to True, which means IsNotHalting halts with IsNotHalting.

Therefore, if IsHalting exists, it leads to IsNotHalting with the following properties:

+ If IsNotHalting halts with IsNotHalting, then IsNotHalting does not halt with IsNotHalting
+ If IsNotHalting does not halt with IsNotHalting, then IsNotHalting halts with IsNotHalting.

This proves IsNotHalting and IsHalting cannot exist.

👆 一言蔽之：如果能定义出函数 停机？，就能定义出一个不停机？函数

(define 不停机？
  λf. If (停机？ (f f))
    (λx. (eternity))
    (λx. True))

然后，如果

+ (停机？ (不停机？ 不停机？)) 是停机的（True），则它反而不停机
+ (停机？ (不停机？ 不停机？)) 是不停机的（False），则它反而是停机的


枚举停机函数可以给出的任何答案（True，False）都无法给出让 (停机？ (不停机？ 不停机？)) 满足其定义的结果
所以就无法回答这个问题。这其实是逻辑问题。

至于 Drakeet 开始提出的那个问题呢，涉及到偏序理论，明天我会解释一下。

—
5 没有被手动排序过，5 排在 1 前面，4 被手动排序过，4 也在 1 前面，但 5 和 4 却无法得出谁在谁前

#doge 已经用上了 Doge 提供的 proxy!

via Electron-ssr

有了汪的 proxy，不用再害怕 tg 的数码狗 MTProto proxy 爆炸了。

#geekapk 我也不是不想继续 github.com/duangsuse/GeekApk(肯定要重写的), 只是现在真的没有时间啊，哪怕写了后端，服务也部署了（虽然都很幼稚，我该去学学 J2EE AS 架构、JPA、JTA、JAX-RS 什么的）
没有 Android 客户端依然是白搭，肯定需要至少十天时间我才敢动键盘。

#OOP #Android 让我来枚举一些会用的技术栈『术语』
MVP, MVVM, DDD, Databinding 🤔
Model-view-presenter, Model-View-ViewModel, Persistence Model and Domain Model(新找到的)

可能还有数据验证（不过可能不在『Client side』）。

我觉得嘛，就是因为这种软件工程太模式化了呃，所以有这些专门造出来引用这些模式的名词。
但是，也就是拿来说自己的开发模式而已。

希望不会有人因为这些东西就随便喷呢？（跑

话说现在的 #web 时代也真是好啊，不仅底层的事情完全不用操心了，应用层都有一大堆框架帮你解决...

我这周就要写上一两个（包括 PreferenceProxy 和 BinaryStreamIO）

现在开始讲解方才 @drakeet 的排序问题

5 没有被手动排序过，5 排在 1 前面，4 被手动排序过，4 也在 1 前面，但 5 和 4 却无法得出谁在谁前

至于这个偏序理论（因为冰封这翻译得很全）（指原文... 因为好像最后没有翻译完）呢，其实是蛮大的知识体系，主要是和数学一些其他的杂七杂八东西比如几何学、集合什么的绑在一起了

https://baike.baidu.com/item/%E5%81%8F%E5%BA%8F%E5%85%B3%E7%B3%BB/943166?fromtitle=%E5%81%8F%E5%BA%8F

这里就说一点会用的，简单快速了解一下：


关系是什么？在这里关系就是一个命题！

1 < 5 ==> ✅
1 < 0 ==> ❎
forall a b. (a < b AND b < a -> b = a) ==> ❎

前序（Preorder）：

集合上的二元关系 sqsubseteq 满足自反性和传递性，就称 sqsubseteq 是 前序
where 二元关系的自反性(reflexive)：二元关系 R，forall x. x R x 成立则 R 有自反性
// 比如，(=) 这个二元关系具有自反性（forall x in {R}. (=) x x），而 (~=) 这个二元关系则没有
二元关系的传递性(transitive)：二元关系 R，若有 a R b、b R c 成立，则 a R c 也成立
// 比如，(<) (lessThan) 这个二元关系具有传递性，若 1 < 5，且 5 < 10，则 1 也 lessThan 10

偏序（Partial Order）：反对称的前序称为偏序
where 反对称性：二元关系 R，若 a R b 且 b R a 蕴含 a = b，则 R 有反对称性
// 比如，(==) 是对称的（a == b 蕴含 b == a），而 (<=) 则是反对称的（a <= b 且 b <= a 蕴含 a = b）


那么这就是基本的序（Order）们。当然这么解释很容易被喷（很多知识点只字未提，而且讲的太片面），请大佬们体谅。

欸我怎么突然看到了二叉树的前序/中序/后序遍历了？

== 我们知道啥是（有序）线性表，那什么是顺序，怎么让线性表变得有序

为什么我们想要『有序』的列表？可能是因为我们希望用户看到的列表是有序的，或者，我们想进行诸如二分查找这种算法优化的操作，必须在有序列表上进行。

要排序一个列表，在 Java 里面我们需要一个谓词（比方说，lessThan），可惜 Java 7 里没有直接传递『函数指针』（在我们，也就是 Java 的用户，或者说 Java 开发者们看来）的方法

Java 8 里，我们有个叫 java.util.Comparator 的接口，很多排序函数（方法）能够接受一个这样的 Comparator，作为它的『序』

Interface Comparator<TypeToBeCompared> {
  int compare(TypeToBeCompared o1, TypeToBeCompared o2);
  boolean equals(Object obj);
}

当然，第二个 equals 方法是希望你去实现 java.lang.Object 的同名方法的，这是说此『比较器』是否和另一个比较器，拥有相同的排序方案。

我们可能期望的『List 顺序』，就是说（我不想在 Java 集合类的其他部分（比如说 SortedXXXX, Double-ended Queue）、线程同步问题上纠缠什么，因为这完全和我们讨论的理论毫无关联，当然也不要拿泛型什么的来说，说泛型当然还是 Rust 的 dalao，比参数式多态高到不知哪里去了，Java 平台是很大，前端也是有有趣之处，但是还没有厉害到知道一点不常见的『秘籍』就可以浅尝辄止了）

forall i. list[i] `predicate` list[i + 1]

比如，我们有一个 List:

val list = listOf(1, 2, 3)

它是一个有序的列表，这个所谓的『序』的谓词就是 (lessThan)，或者说 (比 ? 小)，验证：

list[0] < list[1] ; 1 < 2
list[1] < list[2] ; 2 < 3

list[i] `predicate` list[i + 1] 对于所有可选的 i 来说都是真的

那么基本的数学比较大家都会做，这其实是说自然数 {N} 集上的『顺序』

可以这么定义（Haskell 里）：

{-# LANGUAGE GADTs #-}

data Nat where
  Zero :: Nat 
  AddOne :: Nat -> Nat

instance Eq Nat where
  Zero == Zero = True
  Zero == _ = False  
  _ == Zero = False  
  (AddOne a) == (AddOne b) = a == b

lessThan :: Nat -> Nat -> Bool
lessThan Zero Zero = False
lessThan Zero _ = True 
lessThan _ Zero = False
lessThan (AddOne a) (AddOne b) = lessThan a b

然后我们可以试试

Zero `lessThan` AddOne Zero ==> True
AddOne Zero `lessThan` Zero ==> False

那自然数没啥好说的

说说给个列表，怎么排序吧，OI 基础内容。

[1, 2, 3], (<)，这是个有序列表
[3, 2, 1], (<)，是无序的，怎么让它有序呢（不考虑可变性问题， 只考虑算法）

问问维基百科，我们好像需要『排序算法』，这方面水很深，不过我们只是浅尝辄止。

In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most frequently used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) which require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output.

+ 基于插入的排序算法（Insertion based）
- Insertion sort
- Shell sort
+ 交换法（Exchange based）
- 以不需要死记代码闻名的 Bubble sort
- 以快速和递归著名的 quicksort
+ 选择法（Selection based）
- 简单的 Selection sort
- Heap sort


那么我们简单的使用优化版的 Bubble sort 冒泡排序来进行排序操作

list = [3, 2, 1]
ord = (<)

那么优化的 『Bubble sort』 很简单，也不用死记代码，因为非常简单，这里我就不秀自己能理解某些抽象算法结构而不是幼稚的模式识别了（逃跑）。

for (size i = list.firstIndex; i <= list.lastIndex; i++)
for (size j = i; j <= list.lastIndex; j++)


    unless (list[i] `ord` list[j]) swap(&list[i], &list[j]);

很好记吧？j 之所以可以只从 i..lastIndex 是因为随着比较和交换的进行，前面 i 个元素已经完成了其实是选择排序的『冒泡排序』... 这是 @drakeet 写的那个版本。

[3,2,1]
— i: 0
j 3 < 3
j 3 < 2 [2, 3, 1]
j 2 < 1
[1, 3, 2]

— i: 1
j 3 < 3
j 3 < 2
[1, 2, 3]

— i: 2
j 3 < 3

好吧，其实这只是一种... 它保证了所有元素都互相比较了一次，还有一种正宗的...

do { for ((index, next) in list.indexPairs) unless (list[index] `ord` list[next]) swap(index, next).also { swapped = true } } while (swapped)

咳咳... 冒犯一点说，这代码是我在 LayoutFormatter 里看到的（我只能找到一点 给 google 的 PR, 因为基本都是些板凳条凳的代码风格问题（而且还比较盲目地去掉了 id 名里的视图类型、把 UiXXXX 改成了 UIXXXX，不太符合原项目上 camelCase 分词优雅性规则，但是 JDK11 是...），项目依赖管理貌似出现了问题，后来就没被 merge），而它已经被 Drakeet 删掉了... 或者闭源了

好吧，我好歹还是找了一会...

https://github.com/bangarharshit/Gradle-Layout-Formatter/blob/master/buildSrc/src/main/java/com/bangarharshit/layoutformatter/Formatter.java#L202

啊我的眼睛要瞎了，这洋文水平.... 这处理算法逻辑的结构，那么像之前那个秀炸的二进制手算偏移量处理 AxmlParser，我真的... 真的... 无法限制自己的语言... 🤐
啊这个项目是很秀的，秀了一下自己对 Gradle (非 Groovy) 的理解（Plugin，Tasks，Configuration，FileTree），写了个格式化 Plugin，可是我怎么总觉得很奇怪，明明这些工程师知道的那么多，可偏偏不能再懂得多一点... 再多考虑一些东西，再多一点就更好了...

好吧，根据 javaFiles 这个言不及义的局部变量名，我觉得有部分源码可能是“抄”的。因为“我”并不真正理解我所做的事情... 某个新建的 task 需要一个 fileTree 来遍历，作为它实例的变量，那我的 Plugin 就负责注册这个 Task 到 TargetProject，然后设置 fileTree 为 rootProject.fileTree(dir: rootProject.dir, include: ['**/layout/*.xml'])，可惜不直接用 Groovy 写算了。

总之... 我感觉，我应该告别旧时抄代码，不知道自己在做什么的历史了... 扯远了

一言以蔽之：『解析算法』是可用的，但是未免也太... 莫名其妙了.... 而且不 effective，有个该抽提成循环的不抽提，有个方法的名字根本是错的，算了我不说原因...

那么我们看看排序算法。

int i, j;
String temp;
for (i = start; i < end - 1; i++) {
for (j = start; j < end - 1 - i + start; j++) {
if (getLinePriority(lines.get(j)) > getLinePriority(lines.get(j + 1))) {
temp = lines.get(j);
lines.set(j, lines.get(j + 1));
lines.set(j + 1, temp);
}
}
}

不考虑不重要的事情（区间）

for (int i = 0; i < li; i++)
for (int j = 0; j < (li-i) - 1; j++)
if (! (lines[j].compareTo(lines[j+1]) <0) )
{ /* swap(lines[j], lines[j+1]) */ }


🤔 弄了半天是我搞错了... i 果然就是个计数变量，本身就是真正的无优化 bubble sort 的...，就知道我肯定（又）不长脑子！（上一次是我在写快速排序的时候）

最后我们再谈谈最上面的问题

5 没有被手动排序过，5 在 1 前面，4 被手动排序过，4 也在 1 前面，可 5 和 4 谁在谁前？

要排序的集合。{5, 4, 1}

所谓的手动排序，我们认为，就是用户手动给某个元素（或许可以用 hashCode 来标识）指定一个位置，用户希望看到这个元素永远处于那个位置

元素 1 的位置记为 p1
用户把 5 固定在一个位置 p5，并且 p5 在 p1 『前面』（它的 index < p1）
用户把 4 固定在一个位置 p4，并且 p4 也在 p1 前面

可是 5 和 4 谁在前面，能不能成为一个不可解决的问题呢？ 🤔

首先看看满足需求的位置 p5 p4 存不存在：存在

我们以索引的 (<) 偏序集来表示，当然存在的啊！至少，如果我们不考虑来全称量化推广的话。

5，可以对应索引 1
4，就对应 2
1，就对应 3

[5, 4, 1]
约束条件：
p5 < p1 成立
p4 < p1 成立

所以就这里，不存在任何问题。

那么 5 和 4 又谁在前面？ 🤔

其实我很好奇，大家看起来好像我是蛮智障一样（误打误撞错写 drakeet 之前写的交换排序成了类似的选择排序），排序算法都不会写，但是我打包票一旦我理解了一个东西，就肯定是彻底的理解 — 我知道我在做什么，我明白算法的每一个步骤对它处理的影响，而不是瞎猜！

很简单啊？按照之前的手段再比较一下不就好了？

按照升序排列，5 (不小于) 4，所以 4 排在 5 前面。

那么这么简单的问题，为啥 drakeet 会提出并且引以为 PureWriter 不支持『同时自动手动排序』的理论？

因为 drakeet 理解这个问题的方式和我有点不一样，我不知道之前更加幼稚的我所想的『看不到所谓有序后面完全可以无序，或者说被 sort API 限制了视野』是不是真的，但我想他的顾虑可能就只是无法在『用户指定位置』和自动排序之间找到平衡点，毕竟我也隐隐约约觉得除了上面的这个问题外，还有更严重的问题，再比如，如果表长有变化（完全可能有 Insert/Delete 这种操作），那『固定』位置应该怎么处理？如果『固定位置』的约束条件开始互相冲突，还能进行（对固定位置的）自动排序吗？

这的确是个问题，不过我打算解决这个问题。如果剩下的时间里还有足够的时间编程和学习抽象模型，我会写一个 PoC 出来，证明对列表的不同部分使用不同的排序算法和『固定位置』是可行的，而且也可以在考虑固定位置的情况下进行插入/删除/更新操作。

算法的思路可能就是：

fixed:
0 | z

list:
1 | a
2 | b
3 | c

view:
— 0 | z
1 | a
2 | b
3 | c

我们认为所有的『区分排序』表都是由两部分组成的：已固定表（实现时使用 fixed index set 和 collect with index 函数实现）和主表

排序的时候，把这『一个表』映射为两个表（main 和 fixed），每个表都会记录它的项目之前的位置，并且在排序之后重新合并为一个新表，看起来就像表的一部分位置单独采用了另一种排序方法一样

[4, $5, 1, 4, 2, $6] => 排序
main:
0 | 4
2 | 1
3 | 4
4 | 2

fixed:
1 | 5
5 | 6

== 单独进行排序和位置合并 ==
原 main / fixed:
[4, 1, 4, 2] [5, 6]
原 main / fixed indices:

[0, 2, 3, 4] [1, 5]

main 和 fixed 在排序的过程中是互相透明的，排序算法单独对两个集合进行排序操作而不能看见另一个集合里的元素，这也符合用户对『固定位置』概念的预期。

刚才的简单交换排序也可以写成：

for (int i = 0; i < li; i++)
for (int j = 1; j < li - i; j++)
if (! (lines[j-1].compareTo(lines[j]) <0) )
swap(lines[j], lines[j-1]);

本质上就是『最大的元素像冒泡一样从表头交换到表尾』
但其实不是冒泡排序...

== 单独进行排序和位置合并（刚才一条太长写不下） ==
原 main / fixed:
[4, 1, 4, 2] [5, 6]
原 main / fixed indices:
[0, 2, 3, 4] [1, 5]


== 单独进行排序 ==
有序 main /fixed
[1, 2, 4, 4] [6, 5]
== 合并回原列表索引
原 main / fixed indices:
[0, 2, 3, 4] [1, 5]

然后二分查找数索引 pair 有序列表 RandomAccess，合并得出结果。

[1, 6, 2, 4, 4, 5]

5 没有被手动排序过，5 在 1 前面，4 被手动排序过，4 也在 1 前面，可 5 和 4 谁在谁前？

或者也可以看作是命题组：

i1 := {a list element position}
exists i5 in {N}. i5 < i1
exists i4 in {N}. i4 < i1

这两个都是成立的，但是，如果要这么想

exists i in {N}. i5 < i < i4 就是不可能的，因为 (<) 是具有传递性的，若 i5 lessThan i，并且 i lessThan i4，那就是说 i5 lessThan i4，这是不符合预期的（逻辑性质比这举的例子有用多了，可惜我不是特别懂）

那如果说
exists i in {N}. 4 < i < 5 也是不可能的，并没有一个自然数比 4 大但是比 5 小，这后面自然也有基础偏序理论和基本数论... （或者说，{N} 是不连续，或者说离散的数集，{R} 则是连续的）但是，把 {N} 换成 {R} 就成立了

#dev #Life #Microsoft #VisualStudio

Visual Studio 2019 发布会今晚 12 点正式开始。

#Haha #Microsoft

翻车现场（直播演示的是快照调试，但是跑很久还没出结果）