Algorithm(leetcode 算法题)

Sliding Puzzle

这道题其实意外的简单,但是看完题我居然想不出怎么做……

应该说是思维的一种惯性吧,看到这种的题目类型第一反应还是正向搜索策略,或者说是思考如何判断哪条路线是正确的,哪一步应该如何行走,进而引申到步骤的策略算法上

然后就死活都想不出来了……

打开评论区瞄了一眼,发现基本策略就是暴力搜索,即漫天纷飞的 BFS 和少量的 DFS以及更少量的 A*……(我果然还是太天真了)

然后仔细想了想,一共就 6 个格子,所有排列可能性也就 6! = 720 种,耗时短到可以忽略不计了,此时不暴力何时暴力……Orz

基本的 BFS 解法↓:

from copy import copy
from pprint import pprint
class Solution(object):
  def getZeroPosition(self, board):
    for i in range(0, 2):
      for j in range(0, 3):
        if board[i][j] == '0':
          return (i, j)
  def slidingPuzzle(self, board):
    board = [[str(j) for j in i] for i in board]
    queue, dire = [(self.getZeroPosition(board), 0, board)], [(-1, 0), (1, 0), (0, -1), (0, 1)]
    visited = [''.join(board[0])+''.join(board[1])]
    while True:
      first = queue[0]
      queue.remove(first)
      firstStr = ''.join(first[2][0]) + ''.join(first[2][1])
      visited.append(firstStr)
      if firstStr == '123450':
        return first[1]
      else:
        step = first[1] + 1
        for i in range(0, 4):
          x, y = first[0][0] + dire[i][0], first[0][1] + dire[i][1]
          if x >= 2 or x < 0 or y >= 3 or y < 0:
            continue
          # newBoard = copy(first[2])
          newBoard = [[j for j in i] for i in first[2]]
          newBoard[first[0][0]][first[0][1]] = newBoard[x][y]
          newBoard[x][y] = '0'
          newStr = ''.join(newBoard[0])+''.join(newBoard[1])
          if newStr in visited:
            continue
          queue.append(((x,y), step, newBoard))
      if len(queue) == 0:
        return -1

值得一提的是这回的题目从看题到编码全程都是在手机上完成的,在搬家前夜开始做题,电脑已经打包收拾好了懒得再拿出来了所以就在手机上完成了 python 的编码。因为平常在电脑上写 py 都不用 IDE,直接 Linux 命令行下跑,手机上的这个 Pythonista 代码补全和提示、运行报错和变量查看都很方便

enter image description here

也许是因为解法确实简单或者单纯人品好,这次提交的代码一次就 AC 了,性能还不错(不太明白这道题这么简单为什么 AC 率会这么低)

enter image description here

虽然很快就写完了并且 AC 了不过在写的过程中还是感受到了自己不够细致的毛病体现在了编码上:本来该是 x>0 的条件写成 x>=0,即使有了补全提示还是会写错变量名,可能是因为短时间记忆力不强的关系有时甚至会一下忘了自己前几行都写了些什么……


Review(阅读并点评至少一篇技术文章)

Nonblocking I/O

这篇文章如标题所言,是对非阻塞 I/O 的一个全面系统的说明。从 Linux 内核层面叙述各种不同类型 I/O 发生时相关的存储结构(文件描述符、条目等)会发生什么变化,对进程、内核有什么影响等等,同时还对比了几种不同 I/O 的适用场景及缺点

前半部分说明了描述符、文件条目的概念,介绍了系统内管理进程和文件描述符的方式以及描述符与 inode 的关系等等。对水平触发和边缘触发两种描述符的准备状态也配以图文做了详细的描述

后半部分重点叙述了多路复用 I/O 在信号驱动模式、轮询模式下内核的具体变化、发生在底层系统真正的调用等,对和常见形式有所区别的的 BSD 上的内核事件轮询也提供了相关描述对比。最后还提及了概念易混淆(异步/同步与非阻塞/阻塞)的 POSIX AIO

重点部分的目录大致如下↓

  • 非阻塞描述符

    • 描述符准备状态
    • 水平触发
    • 边缘触发
  • 描述符的多路复用

    • 非阻塞的多路复用 I/O
    • 信号驱动式多路复用 I/O
    • 轮询式多路复用 I/O
      • Select
      • Poll
    • BSD 上的内核事件轮询

全文结构清晰,叙述原理深入内核,配图的手写风格也不错,值得一读

Notes on Distributed Systems for Young Bloods

这篇的内容也如标题所言是为分布式学习的新手们提供的一些要点:

  • 分布式系统的不同之处在于它会频繁的失败
  • 编写实现一个健壮的分布式系统比实现一个健壮的单机系统要难
  • 健壮的开源分布式系统比同等条件下的单机系统要少见得多
  • 协调非常困难
  • 能用内存解决的问题都微不足道
  • “运行慢”会是你遇到的最难 debug 的问题
  • 在你的系统上引入对背压(backpressure)能力的实现
  • 想方设法使其部分可用
  • 度量(Metrics)是完成工作的唯一途径
  • 使用百分值而不是平均值
  • 学会估计容量
  • 功能标志(feature flag)是基础架构的展开方式
  • 明智的选择 id 空间
  • 利用本地数据
  • 不该将缓存数据写到持久化存储中
  • 计算机能做到的,比你觉得他能做到的更多
  • 使用 CAP 原理来评判系统
  • 将服务抽取出来

(PS 有几个点没能完全明白可能翻译有误欢迎指正)

再一次确定我是个初学者……因为还是有不少没看懂,或者看懂了也不理解的地方,比如在使用度量标准完成工作这里作者认为“日志会说谎”:

Log files are good to have, but they tend to lie.

并相应的举了一个例子:

it’s very common for the logging of a few error classes to take up a large proportion of a space in a log file but, in actuality, occur in a very low proportion of requests.

字面意思来看是指错误内容虽然会占日志的一大部分但实际上仅仅占请求的极小的一部分?因此如果以日志作为分析原材料并不能很好的度量系统的表现?

后文有提到因为工程师们经常不能准确把握那哪些错误类打印出来有分析的价值,所以这就是“日志会说谎”的原因?这里不太确定,欢迎交流

要点里提到了我们的度量标准通常是百分比而不是平均值,一直知道但对这个概念的理解不是很深,这篇文章里也给出了比较精准的说明:

If the metric doesn’t follow a bell curve, the average is meaningless and leads to incorrect decisions and understanding.

此外,关于功能标志(feature flag),个人觉得概念很接近我们常说的灰度发布,这篇文章中举的上新数据存储服务例子的操作方式设计了以下几个标志用于发布:

  • 写入新数据存储位置标志
  • 从新位置读取数据,检查性能问题
  • 分别从新旧位置读取数据进行对比

一个接一个设置标志打开,调节百分比,直至一个标志相关服务操作 100% 确认完毕后(比如写标志确认路径 100% 正确且数据回填完毕)再打开下一步骤的标志设置 (这就是灰度发布没错啊)


Technique(技术技巧)

命令号输入位置快捷键

这回分享的是几个 Linux 命令行下输入删除的快捷键,已经知道或者熟练使用的朋友们请不要丢我砖头……

  • Ctrl + k:删除当前位置到结尾的所有字符,非常适合清除大量错误的输入,无需死按着 Backspace 不放了……

  • Ctrl + w:删除当前位置到开头的所有字符

  • Alt + D:删除当前位置到当前字符串的末尾,被视为分隔符的包括空格、. 等等(例:xyx.dsfsd.adw,位于y位置时删除后剩下x.dsfsd.adw),命令行较长敲错的部分占总长较少的情况下适用

  • Alt + B:跳转到当前或上一个字符串的首位(例:abc defg h,位于 g 处将跳转到 d,再次将跳转到 a 处)


Share(分享有观点和思考的技术文章)

Google and HTTP

基本内容概括下就是:RSS 之父对 Google 强制推行全面 HTTPS 存在很大意见

在很多中文媒体看到翻译过来的标题党都是:RSS 之父炮轰全面推行 HTTPS 的Google哈哈哈哈

作者不赞同的原因主要是这样的:

  • web 是个开放平台而非集团平台,其超过 25 年并且还在持续发展的活力证明了它的稳定性,而 Google 不过是这个平台的客人,无权修改它的规则

  • 大量已无人维护的 web 服务上存储了数据文件,这些服务还在正常工作,数据文件也还具有价值, 它们无法被转换成 https,如果强制那我们将会失去 web 发展以来具有庞大价值的无数信息

  • 有些数据的传输并不需要加密,如博客、论文等数据资料;真正需要加密传输的诸如私人通讯等,服务的提供者自然会为其加上 https 特性。总而言之在 web 这一环境中任何人无权强制加诸任何规则,包括 Google

作者认为 web 之所以能带来爆炸式增长的奇迹,核心原因之一就是其本身简单的特性,而 Google 的行为会给 web 增添复杂性。此外作者还直言今天 Google 能给用户强制告警使用 https,它们将来很有可能会做得更多,对用户提出更多要求

事实上 Google 在 Chrome 上对 http 网站标注“不安全”某种意义上是一种欺骗和诱导,普通的用户们并不了解所谓的“不安全”是什么内涵,它们只会单纯的不去访问这些本就无需加密的数据文件,因为 Google 的权威“告诉”它们“不安全”(跟早年我们大家相信权威 360 全家桶是真的“为你好”类似的道理)

而关于中间人攻击的安全问题,作者认为即便你使用了所谓“安全”的协议,中间人攻击一样可能发生在浏览器上(例如 https 在一开始不对称秘钥加解密阶段就拦截下了所有请求并开始代替一方进行通信?)。往上再说一层,web 本身就是不安全的,对“安全”的要求同样要付出一定的性能代价(加解密损耗的时间、计算资源,安全报告发送占用的多余的流量等),并不是所有的 web 服务都必须选择付出这一代价

作者最后还提到就算不讨论上述存在的所有问题,我们假设 https 真的是个好主意,既然是好主意为什么要强制呢?,如果真的是个好主意大家自然会采纳,并不需要 Google 通过这种方式来强制

我的看法

  • 本来我个人也觉得全面 https 是个好主意,但本文的作者提出的论据基本都能够使我信服,而且关于老旧数据的观点命中了我的盲区,我确实没到这一点

  • 关于对中间人攻击的说法,个人认为 Google 的说法还是成立的,https 相当于在原本的基础上加一层防护,而并不是说彻底解决中间人攻击这一问题。真正的神偷无论你金库锁得多紧都能偷到宝物,难道因此金库就没必要加锁了吗?多加一层,能多防一些小偷总是有价值的


Comment

此处按惯例留白放皓哥评价(如果有的话)


Written with StackEdit.