去吃饭的路上又想到了两种方法，不过两个都不能做到同时时间复杂度 O(n) 空间复杂度 O(1)

第一种就是利用 HashMap（或者 HashSet），HashMap 插入查询的时间复杂度是 O(1)，但是空间复杂度（理论上）是 O(n), n 是保存的数据个数

所谓 HashMap，就是一个数据结构，它是 Python 里的 dict、Ruby 里的 Hash、Lua 里的（一种情况，Lua 的 table 有两个部分，它融合了数组和 Hash）table、JavaScript 里的 Object、Java 和 Rust 里的 HashMap
C++ stl 的 std::map 我就不清楚，可能是 HashMap 吧

比如说，这里有一个 HashMap m：

m.put(2, '2')
m.put(3, '3')
m.put( object with hashCode method, value )
m.get( object with hashCode method )
m.get(2) #=> '2'

它内部可以这么弄（当然实际上实现基本都是基于桶 buckets 和取余、散列值碰撞时以列表替换的方法，比较复杂这里不说）：

[, , '2', '3']

只是个例子，反正 hashCode 就是能把 Object 映射到 int (哈希值)，从而做到『映射到不需要逐个 equals() 判断的空间』而已

这个算法的时间复杂度的确是 O(n)，但是空间做不到不随着输入长度 m 的变化而变化...（最差情况，空间是 O(m)）

极端情况下，也可以预先分配一个（输入的索引，在 C 里面是 size_t，假设环境是 x86，就只有 32 位二进制）能容下所有 i32 整形数的容器充当散列映射空间（这时候映射函数就是 lambda x: x 了emmm），非常 dirty

第二种方法是二分查找、线性查找和快速排序... 都看出来了

时间不可能是 O(n)（除非使用并行的快速排序，但是依然得遍历第二次...）空间则可以是 O(1) （不需要任何的额外分配）

线性查找的复杂度是 O(n**2)
二分的是 O(log2 n)
快速排序 + 线性扫描的如果使用并行快排，复杂度可能是 O(n)，但是又有点感觉让人站不住脚。

总而言之... 我觉得是不是可能需要使用位运算并查集、离散化查重什么的...

其实这就是一个 set 的 uniq 算法（list to set）
有很多计算机科学家实现过，但是我算法上很浅薄，无从下手

我把所有我学过的算法和数据结构，所有线性表，Array, Linked List, Queue, Deque, Stack, 循环线性表什么的，简单查找二分查找快速查找什么的
Hash map、所有树（Binary Search Tree）、排除 dfs, bfs, dijkstra 算法、动态规划算法、贪婪算法都考虑过了，没找到可能 space O(1) 的同时还能 O(n) 的...

#Telegram #life

也是和 drakeet 之前的事情弄的（

毕竟我也是有点看不太惯现在在 M$ 的离开大学五年然后技术除了熟练度几乎没有任何长进，一直在写简单的逻辑从未有过别的想法的... 呃... 虽然这是有点过分了

我没有居高临下，我和他是平级的

反而是 drakeet 一直是把自己当成长辈，我只是作为 CS 爱好者

这也是我一直以来对技术交流的态度，我和对方都是爱好者而已

作为爱好者来看待

难道 Kotlin/Common 的程序员不是 JVM 程序员？

难道 String 不是 CharSequence？

可是这也正是我曾经对他说的话，我个人并没有什么特别的在提高自己的地位...

我只是一直在尝试学习...

学习是没有错的... 可能大家学的方向是有点不一样而已，但我真的是作为一个交际人，我相信我绝对不是自傲的

比如说，我可能倾向学杂七杂八的东西，别人专门写应用，

drakeet 开始是写应用，可后来他表示『他的逆向工程技能很不错』（这话是他说的）

然后我不服才『自大』的，我说的也只是（客观评价了一下逆向工程方面 drakeet 真实能力）
这不能说是我默认是自恃技术怎么样

我没有在他面前说我逆向工程比他强，但我的确是至少在这方面努力比他多，你们也看到了，至少我逆向分析了纯纯写作和 CoolApk 的 liba.so

liba.so 是机器代码写的，就是这样我也能还原其逻辑，而当时 drakeet 眼里就是：如果我用 NDK 集成写校验逻辑，我就会什么都做不了（黑盒）

也是，毕竟我不应该不看人家的性格...

我以为大家都是爱好者，可他觉得我是爱好者，他是工程师...

所以为人还是多学习少撕逼
以后遇到这种人，就只说好的，绝口不提任何负面的评价

你说上面的，其实我自己大概也注意到了（因为我自我感觉，如果这些信息不准确，我可能会被喷，如果我把自己的姿态降到不能再低，显然信息准确性怎么样都好）

我说的比较随性，这也是因为平时在 @dsuse 里 CS 广播发多了的原因导致我总是这样不带感情的提这些东西...

希望你没有感觉自己被冒犯到就好 🐱

下面的

但是年轻人 🐸

就是出来体验生活的，为什么不多尝试一点（

我可没有说我是长者呦，这里有一个地方误会了，因为我多加了个折行，其实我的意思是：

但是年轻人就是出来体验生活的，为什么不多尝试一点（

我没有以『年轻人』称呼你（虽然似乎我高二比你大一点）
而是说所有『年轻人』都最好出来体验生活，多尝试一点...

为了防止撞库攻击，很多人都建议任何密码相同（或相关）的用户修改自己的密码。

～想法～
所以，改成什么？
1.自己要能记忆
2.不同网站/程序不一样
3.不同密码之间无关连

思考了一下
希望：“即使断网也能查看密码”
所以要在本地完成计算。
同时“希望能在任何平台算出密码”
所以不想使用密码管理器。


～实施～
于是决定：
1.想好一个"盐"（可以有任何字符，长度也可以很大），记下来。
2.将其和要设置的网站的域名拼接
3.计算sha256
4.取最后几位作为该网站密码，位数建议多点（8-12）。


～问题～
优点？
即使有人脱了数据库，拿到了你的密码，也无法登录；
不需要密码管理软件，防止被密码管理软件坑到（也不需要钱钱购买）；

缺点？
上一条中，如果针对你个人进行攻击，根据你的社会信息猜测盐值，或暴力猜测"盐"值（猜盐-计算sha256-比较脱库获得的网站密码）
需要手工记下sha256的最后几位，可能对记忆力不好的用户是个挑战。

可能的因为操作不当的漏洞？
在shell执行时，history里会留下记录；
如果偷懒复制粘贴，可能会被有剪贴板访问权限的程序偷了密码。

为什么sha256而不是md5？
因为其计算起来比md5慢，这样可以略微增加暴力破解者的计算成本，而对于用户，也不会感知缓慢。

copyright @AlPlank 1989-8103

#public

#Parser #PL

NLP 我不会，但是解析器理论我会一些，你想请教什么？我正准备写我的第一个 Java 解析组合子框架

NLP 部分和我们编译原理的解析器理论是相通的，但首先

+ 我只会写比较好看的递归下降法解析器
+ 实际上在 Parser Compiler (Compiler Compiler, 比如 re2c, yacc, bison) 和 Scanner generator 领域（对应 Lex-Yacc Style Parsers）

他们基本都用 NFA, DFA 这种自动机（上面的 NFA, DFA 都只是根据下一个状态属性命名的自动状态机的类型）
实际上，函数式编程向的人们基本都会直接用一段程序的状态替代这种（到状态机匹配指令和状态表的）编译器 + 状态机
而且递归下降法也很快，基于递归下降和 LR 的解析组合子也能解析很多很复杂的文法，基于组合子自动机的也可以自动做诸如左递归消除的解析器优化

+ 不过，这是说编译原理里的解析器理论，和自然语言处理里的还是蛮不一样的

比如说，我们的语法可能是固定的

program = many (_ statement _)
statement
  = define | calculate
  where
    define = string "define" _ identifier _ char '=' _ value
    calculate = string "calculate" _ expr

identifier = [a-zA-Z_] [a-zA-Z0-9_]*
value
  = litInt | litString | litBoolean
  where
    litInt = [0-9]+
    litString = char '"' char* char '"'
    litBoolean = string "true" | string "false"

expr
  = intAdd | stringConcat | booleanAnd
  where
    intAdd = expr '+' expr
    stringConcat = expr '..' expr
    booleanAnd = expr 'and' expr

_ = spaces

猜猜这能匹配什么（当然即使是“辣鸡”的编译原理向解析器也有运算符结合处理的问题，对于不懂递归的人来说这有点烧脑，是真的）

比如

define num = 1
define hundred = 100
define str = "Hello"
define yes = true define no = false （注意这里不需要换行，看上面的语法规则你就知道为什么）
当然如果 ';' 这个字符被视为空白也可以写成
define yes = true; define no = false

calculate "hello" .. " " .. "world"
calculate 1 + 1

二元表达式链看起来不是多么好办（但是可以左递归什么的，可以直接将优先级大的二元运算符比如 "*" "/" 表达式左右都结合优先级小的），不过自然语言处理要“处理”的问题可比这个简单的递归算法复杂得多

上面括号里的情况：

(=) 的前面是规则的名字；后面是规则的模式
one = "1"
(|) 组合一组可能的模式，实际上它的结果是这些模式中任何一种

booleanLiteral = "true" | "false"


Expr = BinAddSub

BinAddSub
  = AtomExp ("+" | "-") AtomExp
  | BinMulDiv

BinMulDiv
  = AtomExp ("*" | "/") AtomExp
  | AtomExp

这样实际上在解析规则的模式字面上定义了优先级，结合性问题估计也可以用类似手段去做

👆 比如说我们的语法可能是固定的

那 NLP 就不是这种情况喽，看 HanLP 它说它用了 Markov 链，这也是一种机器学习预测算法

看架构 NLP 的分词器显然要和解析器互相协作，依据两方的『猜测』决定最终的算法输出，这是我们编译原理里所没有的，何况它还支持监督学习自动识别单词和单词词性词类呢

不管怎么说建议你先学一下编译原理和简单的机器学习，比如 KNN、决策树、朴素贝叶丝分类器
以及语法，比如中文语法

自然语言处理虽然要做到极致的话，是不得不引入越来越多的分析和学习的，但是做事情也要看程度

LLVM Cookbook 的翻译者也是要学 NLP 的，不过他又半道学了一会编译原理，这是个不错的路径选择

你要学习的话，就赶快先试着自己写一个解释器看看，如果这样的能力都没有的话，自然语言处理是很难入门的，（新手村都出不了，跑）

而且最好先写点 NLP 的应用，比如说，主语推导？（将动词的隐式主语推导出来，显式输出出来）

GeekSpec 虽然非常不成熟（而且也没有技术支持...），但是它的确比 Swagger API Tools 的辣鸡 Schema-YAML 语法更优秀，它可以描述的东西是 OpenAPI 3.0 的一个子集

但是！它非常符合直觉，设想一下，如果你要在设计 API 的时候看着一大堆非常空阔的缩进行，你定义一个参数还得按一下缩进，看一个接口有几个参数还得慢慢数，而连自己在设计的接口叫啥名字都不能被很快地看到的话...

我都不敢想是什么样子，OpenAPI 由一群连编译原理和 DSL、面向语言编程都没见过的前端『全栈』工程师来设计... 难道就没有人发现写 OpenAPI 的时候很淡疼？即使是 YAML 换了 JSON 也一样？
（不如隔壁 cucumber.io 它还有门 DSL）

对 GeekSpec 来说就不存在这个问题，它的定义式更简洁富于可读性

它是诞生于这条 (https://t.iss.one/dsuse/9017)广播的，我大概花了三四天... 整整三四天啊

searchUser(type:String?{username,nickname,bio}, kw-path:String, sort:String?{created,followers}) -> array:GeekUser
  = user/search/{kw}

想想这类接口，Swagger 又能把它写成几行呢？你写下面这种代码... 又要多花多长时间呢？
对于动辄几十个 HTTP API 接口大一点的应用，直接用 OpenAPI 解决 HTTP 接口定义真的大丈夫？

getAllUsers() -> array:string = /users

(当然这等价于)

GET@getAllUsers() -> array:string = /users

/users:
  get:
    summary: Returns a list of users.
    description: Optional extended description in CommonMark or HTML.
    responses:
      "200": # status code
        description: A JSON array of user names
        content:
          application/json:
            schema:
              type: array
              items:
                type: string

如果你会（用 JavaScript 或者 Ruby）写稍微麻烦一点的算法，就能简单地把 GeekSpec 语言的代码转化为 YAML 结构，就可以实现 GeekSpec 语言对 Swagger Tools 的兼容
（GeekSpec 是 Swagger YAML 的子类型、GeekSpec 实现了 Swagger OpenAPI Spec）

而且基于 GeekSpec 的定义上，还有 Spectrum 工具 (https://t.iss.one/dsuse/9120)(和信号处理无关)做辅助：

spectrum(0.6)> status
[+] Total 67 APIs, method count: GET: 37; POST: 8; PUT: 11; DELETE: 11
receiving ["String", "UserId", "Int", "CategoryId", "AppId", "CommentId", "UserSize", "TimelineSize", "NotificationSize", "AppSize", "CommentSize"]
and returning 67 types (["string", "GeekUser", "Category", "App", "AppUpdate", "Timeline", "Notification", "number", "Comment"])
[+] 55 path params, 3 body params

spectrum(0.9)> tree :args
...
POST /admin/makeUser
* username:String
PUT /admin/resetMetaHash/{uid}
* uid-path:UserId
* shash:String?

而且还支持作为测试客户端

spectrum(0.1)> listUser
[!] Arity mismatch: expected 3 (not optional 0), got 0
[*] NOTE: fill first optional argument to get started
listUser(sort:String?{created, followers}, sliceFrom:UserSize?, sliceTo:UserSize?) -> array:GeekUser
= GET user/all

spectrum(0.2)> listUser 'created'
=> {"timestamp"=>1549876643013,
"status"=>500,
"error"=>"Internal Server Error",
"message"=>"Optional int parameter 'sliceFrom' is present but cannot be translated into a null value due to being declared as a primitive type. Consider declaring it as object wrapper for the corresponding primitive type.",
"path"=>"/user/all"}

#Haha #life （2333 又翻冰封语录///

import Control.Applicative

data Move = U | D | L | R
  deriving (Eq, Show, Read, Enum)

type Map = [[Bool]]
type Point = (Int, Int)

type Hitsory a = [a]
type TracedRoute = (History Move)

dfs :: Map -> Point -> History Point -> Maybe TracedRoute

dfs map target history step
| step == target = Just []
| step `outbounds` map = Nothing
| blocked or walked = Nothing
| otherwise
= firstJust (fmap try [Up, Down, Left, Right])


  where
    (x, y) = step
    blocked = not (map !! x !! y)
    walked = step `elem` history
    outbounds p m = let (px, py) = p
        in px >= length m or py >= length m !! px

tryDfs m t s = dfs m t [] s   

这是个；它递归搜索一个 boolean[][] 数组，返回从某一点到指定点的路径

否则可以选择向正上/下/左/右方尝试移动

据说某个学校（指 CDLFS，成都某外国语学校）初中的 OI 生都会做