https://github.com/LineageOS/android_frameworks_base/blob/gingerbread-release/tools/aapt/Resource.cpp #Android #bin

#blog #recommended https://bindog.github.io/

我只能最后改正之前错误的 NP-hard 问题什么的了... 其余的，下周说、下周做吧。 🤐

时间真的不够用

0. 这是什么

本频道上上周讲事的时候，讲错了一点，必须即时修正（皮一下，玩个个人的梗）
（我是在强调我修错修的快！）（所以不要告 typo）（是即时编译的即）

虽然我这周很多事情没有做（比如重写别人的 TextTag，比如写 SimpleCat 解释器和策划 NaiveCat、还有写 BinaryStreamIO、用 GeekSpec 1.0 重写 GeekApk 服务定义... 等等十几项）
（也会导致我下周在学校里不能看新书了，我要看文学书.... 这么多都是必须写的堆在哪里...）

但是我这个人呢，一直重视改错的，我和王垠一样总是在更新自己（又皮一下，又玩个个人的梗）（终于说了句大实话）

（好啦 duangsuse 毒舌...）
（只是玩梗而已，无恶意啦）

1. 这个问题出在哪里

-> 某条历史回顾消息广播

2. 是啥类型的问题

很智障的计算机科学定义混淆

3. 你打算怎么改

👇

=> 最后一次，drakeet 提到一个数组（线性表）优先级排序的问题（OI 入门内容，所谓初等内容都是 dfs bfs 这种的，计算机可解的数学问题，游戏模拟、递归算法、关系代数，稍微搞基一点的离散化、编译原理、神经网络）
就是你们之前看到纯纯支持 Book 的 Chapter 手动排序的特性，他在群里讨论了一下，（想了一段时间）说是逻辑上冲突无法实现，我表达了一下自己的看法『你可以做 Pin Chapter 的功能啊，我觉得应该会用得到』，但是 drakeet 觉得这依然是 NP-hard 问题（他觉得这类似停机问题，是不能解决的，我的观点大概就是不必须使用优先级排序，排序什么的有很多方法，都好说，『半自动排序半手动』是完全可行的），我最后甚至用 Ruby 写了个算法实现（就是能够 Pin 数据的 Array，并且可以自动 sort，sort 完手动 pin 的数据依然在表头部），结果就被踢了.... 🙁


出错的部分在这段话里，这里提到的 Chapter 现在在纯纯写作中被称为『文章』应该，反正纯纯写作把文章集合称为『书』Book，然后文章就是你们编辑（随机插入删除）的东西，我对这些名称不负责，就是表示这些。


『drakeet 觉得这依然是 NP-hard 问题』

👉 后面和『停机问题』逻辑并列

这是错误的，因为停机问题和 NP-hard 不是一种概念

并且，停机问题也不是『不能解决』的，实际上，停机问题早就被证实了

好了这周就这么多

#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)