工程职业伦理作业

案例为个人作业内容,firesheep案例 (内容见图片)
思考题:用多种伦理方法给出判断。你认为哪一种或几种伦理学方法更适合当前的中国国情,为什么?

答:
西季威克认为,伦理学是关于“应当”的研究,因而首先必须研究人们据以推断他们应当做什么的合理程序。这些合理程序即“伦理学方法”。
(1) 伦理学方法有功利主义、义务论、契约论、美德伦理、实用主义、伦理利己主义。
(2) 不同的伦理学方法会有不同的判断:
① 功利主义伦理 从一个严格不偏不倚的观点来促进整个世界中的善,并寻求实现最大化利益和效用的行为,该伦理学方法会认为埃里克·巴特勒的做法有得有失。“得”在于吸引了大量媒体和普罗大众的关注,倒逼玩忽职守的网站站点主动做出改变,采用安全的HTTPS协议传输,保障大众的网络安全,从长远看减少网络劫持的发生。“失”在于他为心怀不轨的人提供了便利的工具,甚至在短期内让网络劫持事件频繁发生,对社会公众造成较大损失。但这些情况,会在各网站站点普遍采用HTTPS安全协议后会得到缓解和根治。所以,功利主义的伦理学方法论会赞同埃里克·巴特勒的观点。
② 义务论 以遵循“最高道德原则”的方式确立人的责任和义务,强调正确的行为就是要严格遵守和履行我们所具有的义务,该伦理学方法会认为埃里克·巴特勒的做法是不符合规范、不正当的,义务论认为一个选择或行动是否正确取决于它是否符合某个指定的规范,正当优先于善。工程师的首要责任原则带有了绝对命令的性质,埃里克·巴特勒为网络劫持的传播提供了开源软件工具,这是在助纣为虐,一个履行法定义务的公民、遵守职业伦理章程的工程师所不应该做的。
③ 契约论 通过一个规则性的框架体系,把个人行为的动机伦理地看作是一种社会协议。该伦理学方法会认为埃里克·巴特勒的做法是可取的。契约论寻求自利与利他统一的途径,注重客观社会伦理、组织伦理关系以及工程职业实践、社会交往过程中的客观制度性建设。埃里克·巴特勒有自由制作软件并向大众推广的利己的权利,同时他作为信息科技工程师组织的一员,也深知网络安全组织控诉网络劫持隐患多年,但电子商务网站仍然不予理睬的现状,我不入地狱谁入地狱,用曝光下的潜在风险唤醒媒体和大众,逼迫网站站点做出改变。
④ 美德伦理 认为工程的内在善,必须关注公众的利益,工程的个人善必须关涉工程师在工作中的意义,它与创造有用的安全的公基产品和服务的个人承诺相联系。该伦理学方法会认为埃里克·巴特勒的做法是可取的。埃里克·巴特勒制作网络劫持软件并开源,是出于改变现状的内在善的推动,并未受到知名度、威望等行为可能带来的外在善,干扰他们的公共义务。
⑤ 实用主义 会认为埃里克·巴特勒的做法是可取的。由于对道德复杂性合理的妥协和各式各样的两难困境的敏感性有着最好的理解,坚持在原则的应用方面更加灵活和宽容。埃里克·巴特勒的做法会影响社会犯罪率上升、大众对他褒贬不一的评价等困境,但这种方法后来也被Facebook等公司的行为验证了是有用的!比起网络安全组织长达多年的控诉实用多了。
⑥ 伦理利己主义 试图将道德价值降低为利己的观点被称为伦理利己主义。该伦理学方法会认为埃里克·巴特勒的做法是不可取的。巴特勒做劫持工具软件,受到舆论的关注和他人的抨击,不仅没有把自身的利益最大化最为第一目标,还使自己陷入困境。
(3)我认为,实用主义和契约论更适合当前的中国国情。实用主义“黑猫白猫,抓到老鼠就是好猫”;同时,工程师在自利性的基础上要利他,要注重客观社会伦理、组织伦理关系以及工程职业实践社会交往过程中的客观制度性建设,善恶并非非此即彼,契约论表达了对职业活动中道德选择的现实多样性的认识与尊重。
功利主义、义务论、美德伦理 既对现代工程活动复杂性下的伦理困境力不从心,又常常忽视工程活动中和谐共生的伦理期望。表现在:
i) 功利主义和义务论都相信存在着某些普遍的规则它们为行动的道德正确性提供了标准,行为是立足于普遍的考虑,道德就是建立在普遍的和不偏不倚的合理性的法则之中,所以规范的有效性完全不依赖于工程师偶然具有的欲望和倾向,这太过于理想化,没有很好的实践指导价值。
ii) 道德并不只是用来界定人际生活得以可的最小条件,更重要的是道德也是人性自我完善的一种最重要的方式,而人性的完善是相互促进的。
伦理利己主义 中自我的利益是有争议的,远比利己主义所暗示的要复杂的多。
但是我们也要意识到实用主义、契约论也存在着自身的局限,仍然需要根据国情,具体问题具体分析。

通过分析 JDK 源代码研究 TreeMap 红黑树算法实现

转载自 https://www.ibm.com/developerworks/cn/java/j-lo-tree/index.html

TreeSet 和 TreeMap 的关系

为了让大家了解 TreeMap 和 TreeSet 之间的关系,下面先看 TreeSet 类的部分源代码:

从上面代码可以看出,TreeSet 的 ① 号、② 号构造器的都是新建一个 TreeMap 作为实际存储 Set 元素的容器,而另外 2 个构造器则分别依赖于 ① 号和 ② 号构造器,由此可见,TreeSet 底层实际使用的存储容器就是 TreeMap。

与 HashSet 完全类似的是,TreeSet 里绝大部分方法都是直接调用 TreeMap 的方法来实现的,这一点读者可以自行参阅 TreeSet 的源代码,此处就不再给出了。

对于 TreeMap 而言,它采用一种被称为“红黑树”的排序二叉树来保存 Map 中每个 Entry —— 每个 Entry 都被当成“红黑树”的一个节点对待。例如对于如下程序而言:

当程序执行 map.put(“ccc” , 89.0); 时,系统将直接把 “ccc”-89.0 这个 Entry 放入 Map 中,这个 Entry 就是该“红黑树”的根节点。接着程序执行 map.put(“aaa” , 80.0); 时,程序会将 “aaa”-80.0 作为新节点添加到已有的红黑树中。

以后每向 TreeMap 中放入一个 key-value 对,系统都需要将该 Entry 当成一个新节点,添加成已有红黑树中,通过这种方式就可保证 TreeMap 中所有 key 总是由小到大地排列。例如我们输出上面程序,将看到如下结果(所有 key 由小到大地排列):

TreeMap 的添加节点

对于 TreeMap 而言,由于它底层采用一棵“红黑树”来保存集合中的 Entry,这意味这 TreeMap 添加元素、取出元素的性能都比 HashMap 低:当 TreeMap 添加元素时,需要通过循环找到新增 Entry 的插入位置,因此比较耗性能;当从 TreeMap 中取出元素时,需要通过循环才能找到合适的 Entry,也比较耗性能。但 TreeMap、TreeSet 比 HashMap、HashSet 的优势在于:TreeMap 中的所有 Entry 总是按 key 根据指定排序规则保持有序状态,TreeSet 中所有元素总是根据指定排序规则保持有序状态。

红黑树

红黑树是一种自平衡排序二叉树,树中每个节点的值,都大于或等于在它的左子树中的所有节点的值,并且小于或等于在它的右子树中的所有节点的值,这确保红黑树运行时可以快速地在树中查找和定位的所需节点。

为了理解 TreeMap 的底层实现,必须先介绍排序二叉树和红黑树这两种数据结构。其中红黑树又是一种特殊的排序二叉树。

排序二叉树是一种特殊结构的二叉树,可以非常方便地对树中所有节点进行排序和检索。

排序二叉树要么是一棵空二叉树,要么是具有下列性质的二叉树:

  • 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  • 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  • 它的左、右子树也分别为排序二叉树。

图 1 显示了一棵排序二叉树:

图 1. 排序二叉树
图1

对排序二叉树,若按中序遍历就可以得到由小到大的有序序列。如图 1 所示二叉树,中序遍历得:

创建排序二叉树的步骤,也就是不断地向排序二叉树添加节点的过程,向排序二叉树添加节点的步骤如下:

  1. 以根节点当前节点开始搜索。
  2. 拿新节点的值和当前节点的值比较。
  3. 如果新节点的值更大,则以当前节点的右子节点作为新的当前节点;如果新节点的值更小,则以当前节点的左子节点作为新的当前节点。
  4. 重复 2、3 两个步骤,直到搜索到合适的叶子节点为止。
  5. 将新节点添加为第 4 步找到的叶子节点的子节点;如果新节点更大,则添加为右子节点;否则添加为左子节点。

掌握上面理论之后,下面我们来分析 TreeMap 添加节点(TreeMap 中使用 Entry 内部类代表节点)的实现,TreeMap 集合的 put(K key, V value) 方法实现了将 Entry 放入排序二叉树中,下面是该方法的源代码:

上面程序中粗体字代码就是实现“排序二叉树”的关键算法,每当程序希望添加新节点时:系统总是从树的根节点开始比较 —— 即将根节点当成当前节点,如果新增节点大于当前节点、并且当前节点的右子节点存在,则以右子节点作为当前节点;如果新增节点小于当前节点、并且当前节点的左子节点存在,则以左子节点作为当前节点;如果新增节点等于当前节点,则用新增节点覆盖当前节点,并结束循环 —— 直到找到某个节点的左、右子节点不存在,将新节点添加该节点的子节点 —— 如果新节点比该节点大,则添加为右子节点;如果新节点比该节点小,则添加为左子节点。

TreeMap 的删除节点

当程序从排序二叉树中删除一个节点之后,为了让它依然保持为排序二叉树,程序必须对该排序二叉树进行维护。维护可分为如下几种情况:

(1)被删除的节点是叶子节点,则只需将它从其父节点中删除即可。

(2)被删除节点 p 只有左子树,将 p 的左子树 pL 添加成 p 的父节点的左子树即可;被删除节点 p 只有右子树,将 p 的右子树 pR 添加成 p 的父节点的右子树即可。

(3)若被删除节点 p 的左、右子树均非空,有两种做法:

  • 将 pL 设为 p 的父节点 q 的左或右子节点(取决于 p 是其父节点 q 的左、右子节点),将 pR 设为 p 节点的中序前趋节点 s 的右子节点(s 是 pL 最右下的节点,也就是 pL 子树中最大的节点)。
  • 以 p 节点的中序前趋或后继替代 p 所指节点,然后再从原排序二叉树中删去中序前趋或后继节点即可。(也就是用大于 p 的最小节点或小于 p 的最大节点代替 p 节点即可)。

图 2 显示了被删除节点只有左子树的示意图:

图 2. 被删除节点只有左子树
图2

图 3 显示了被删除节点只有右子树的示意图:

图 3. 被删除节点只有右子树
图3
图3

图 4 显示了被删除节点既有左子节点,又有右子节点的情形,此时我们采用到是第一种方式进行维护:

图 4. 被删除节点既有左子树,又有右子树
图4

图 5 显示了被删除节点既有左子树,又有右子树的情形,此时我们采用到是第二种方式进行维护:

图 5. 被删除节点既有左子树,又有右子树
图5

TreeMap 删除节点采用图 5 所示右边的情形进行维护——也就是用被删除节点的右子树中最小节点与被删节点交换的方式进行维护。

TreeMap 删除节点的方法由如下方法实现:

红黑树

排序二叉树虽然可以快速检索,但在最坏的情况下:如果插入的节点集本身就是有序的,要么是由小到大排列,要么是由大到小排列,那么最后得到的排序二叉树将变成链表:所有节点只有左节点(如果插入节点集本身是大到小排列);或所有节点只有右节点(如果插入节点集本身是小到大排列)。在这种情况下,排序二叉树就变成了普通链表,其检索效率就会很差。

为了改变排序二叉树存在的不足,Rudolf Bayer 与 1972 年发明了另一种改进后的排序二叉树:红黑树,他将这种排序二叉树称为“对称二叉 B 树”,而红黑树这个名字则由 Leo J. Guibas 和 Robert Sedgewick 于 1978 年首次提出。

红黑树是一个更高效的检索二叉树,因此常常用来实现关联数组。典型地,JDK 提供的集合类 TreeMap 本身就是一个红黑树的实现。

红黑树在原有的排序二叉树增加了如下几个要求:

  • 性质 1:每个节点要么是红色,要么是黑色。
  • 性质 2:根节点永远是黑色的。
  • 性质 3:所有的叶节点都是空节点(即 null),并且是黑色的。
  • 性质 4:每个红色节点的两个子节点都是黑色。(从每个叶子到根的路径上不会有两个连续的红色节点)
  • 性质 5:从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
Java 实现的红黑树

上面的性质 3 中指定红黑树的每个叶子节点都是空节点,而且并叶子节点都是黑色。但 Java 实现的红黑树将使用 null 来代表空节点,因此遍历红黑树时将看不到黑色的叶子节点,反而看到每个叶子节点都是红色的。


Java 中实现的红黑树可能有如图 6 所示结构:

图 6. Java 红黑树的示意
图6

备注:本文中所有关于红黑树中的示意图采用白色代表红色。黑色节点还是采用了黑色表示。

根据性质 5:红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点,因此从根节点到叶子节点的路径中包含的黑色节点数被称为树的“黑色高度(black-height)”。

性质 4 则保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的两倍。假如有一棵黑色高度为 3 的红黑树:从根节点到叶节点的最短路径长度是 2,该路径上全是黑色节点(黑节点 – 黑节点 – 黑节点)。最长路径也只可能为 4,在每个黑色节点之间插入一个红色节点(黑节点 – 红节点 – 黑节点 – 红节点 – 黑节点),性质 4 保证绝不可能插入更多的红色节点。由此可见,红黑树中最长路径就是一条红黑交替的路径。

由此我们可以得出结论:对于给定的黑色高度为 N 的红黑树,从根到叶子节点的最短路径长度为 N-1,最长路径长度为 2 * (N-1)。

提示:排序二叉树的深度直接影响了检索的性能,正如前面指出,当插入节点本身就是由小到大排列时,排序二叉树将变成一个链表,这种排序二叉树的检索性能最低:N 个节点的二叉树深度就是 N-1。

红黑树和平衡二叉树

红黑树并不是真正的平衡二叉树,但在实际应用中,红黑树的统计性能要高于平衡二叉树,但极端性能略差。

红黑树通过上面这种限制来保证它大致是平衡的——因为红黑树的高度不会无限增高,这样保证红黑树在最坏情况下都是高效的,不会出现普通排序二叉树的情况。

由于红黑树只是一个特殊的排序二叉树,因此对红黑树上的只读操作与普通排序二叉树上的只读操作完全相同,只是红黑树保持了大致平衡,因此检索性能比排序二叉树要好很多。

但在红黑树上进行插入操作和删除操作会导致树不再符合红黑树的特征,因此插入操作和删除操作都需要进行一定的维护,以保证插入节点、删除节点后的树依然是红黑树。

添加节点后的修复

上面 put(K key, V value) 方法中①号代码处使用fixAfterInsertion(e) 方法来修复红黑树——因此每次插入节点后必须进行简单修复,使该排序二叉树满足红黑树的要求。

插入操作按如下步骤进行:

(1)以排序二叉树的方法插入新节点,并将它设为红色。

(2)进行颜色调换和树旋转。

这种颜色调用和树旋转就比较复杂了,下面将分情况进行介绍。在介绍中,我们把新插入的节点定义为 N 节点,N 节点的父节点定义为 P 节点,P 节点的兄弟节点定义为 U 节点,P 节点父节点定义为 G 节点。

插入后的修复

在插入操作中,红黑树的性质 1 和性质 3 两个永远不会发生改变,因此无需考虑红黑树的这两个特性。

下面分成不同情形来分析插入操作

情形 1:新节点 N 是树的根节点,没有父节点

在这种情形下,直接将它设置为黑色以满足性质 2。

情形 2:新节点的父节点 P 是黑色

在这种情况下,新插入的节点是红色的,因此依然满足性质 4。而且因为新节点 N 有两个黑色叶子节点;但是由于新节点 N 是红色,通过它的每个子节点的路径依然保持相同的黑色节点数,因此依然满足性质 5。

情形 3:如果父节点 P 和父节点的兄弟节点 U 都是红色

在这种情况下,程序应该将 P 节点、U 节点都设置为黑色,并将 P 节点的父节点设为红色(用来保持性质 5)。现在新节点 N 有了一个黑色的父节点 P。由于从 P 节点、U 节点到根节点的任何路径都必须通过 G 节点,在这些路径上的黑节点数目没有改变(原来有叶子和 G 节点两个黑色节点,现在有叶子和 P 两个黑色节点)。

经过上面处理后,红色的 G 节点的父节点也有可能是红色的,这就违反了性质 4,因此还需要对 G 节点递归地进行整个过程(把 G 当成是新插入的节点进行处理即可)。

图 7 显示了这种处理过程:

图 7. 插入节点后进行颜色调换
图7

备注:虽然图 11.28 绘制的是新节点 N 作为父节点 P 左子节点的情形,其实新节点 N 作为父节点 P 右子节点的情况与图 11.28 完全相同。

情形 4:父节点 P 是红色、而其兄弟节点 U 是黑色或缺少;且新节点 N 是父节点 P 的右子节点,而父节点 P 又是其父节点 G 的左子节点。

在这种情形下,我们进行一次左旋转对新节点和其父节点进行,接着按情形 5 处理以前的父节点 P(也就是把 P 当成新插入的节点即可)。这导致某些路径通过它们以前不通过的新节点 N 或父节点 P 的其中之一,但是这两个节点都是红色的,因此不会影响性质 5。

图 8 显示了对情形 4 的处理:

图 8. 插入节点后的树旋转
图8

备注:图 11.29 中 P 节点是 G 节点的左子节点,如果 P 节点是其父节点 G 节点的右子节点,那么上 面的处理情况应该左、右对调一下。

情形 5:父节点 P 是红色、而其兄弟节点 U 是黑色或缺少;且新节点 N 是其父节点的左子节点,而父节点 P 又是其父节点 G 的左子节点。

在这种情形下,需要对节点 G 的一次右旋转,在旋转产生的树中,以前的父节点 P 现在是新节点 N 和节点 G 的父节点。由于以前的节点 G 是黑色,否则父节点 P 就不可能是红色,我们切换以前的父节点 P 和节点 G 的颜色,使之满足性质 4,性质 5 也仍然保持满足,因为通过这三个节点中任何一个的所有路径以前都通过节点 G,现在它们都通过以前的父节点 P。在各自的情形下,这都是三个节点中唯一的黑色节点。

图 9 显示了情形 5 的处理过程:

图 9. 插入节点后的颜色调整、树旋转
图9

备注:图 11.30 中 P 节点是 G 节点的左子节点,如果 P 节点是其父节点 G 节点的右子节点,那么上面的处理情况应该左、右对调一下。

TreeMap 为插入节点后的修复操作由 fixAfterInsertion(Entry<K,V> x) 方法提供,该方法的源代码如下:

删除节点后的修复

与添加节点之后的修复类似的是,TreeMap 删除节点之后也需要进行类似的修复操作,通过这种修复来保证该排序二叉树依然满足红黑树特征。大家可以参考插入节点之后的修复来分析删除之后的修复。TreeMap 在删除之后的修复操作由 fixAfterDeletion(Entry<K,V> x) 方法提供,该方法源代码如下:

检索节点

当 TreeMap 根据 key 来取出 value 时,TreeMap 对应的方法如下:

从上面程序的粗体字代码可以看出,get(Object key) 方法实质是由于 getEntry() 方法实现的,这个 getEntry() 方法的代码如下:

上面的 getEntry(Object obj) 方法也是充分利用排序二叉树的特征来搜索目标 Entry,程序依然从二叉树的根节点开始,如果被搜索节点大于当前节点,程序向“右子树”搜索;如果被搜索节点小于当前节点,程序向“左子树”搜索;如果相等,那就是找到了指定节点。

当 TreeMap 里的 comparator != null 即表明该 TreeMap 采用了定制排序,在采用定制排序的方式下,TreeMap 采用 getEntryUsingComparator(key) 方法来根据 key 获取 Entry。下面是该方法的代码:

其实 getEntry、getEntryUsingComparator 两个方法的实现思路完全类似,只是前者对自然排序的 TreeMap 获取有效,后者对定制排序的 TreeMap 有效。

通过上面源代码的分析不难看出,TreeMap 这个工具类的实现其实很简单。或者说:从内部结构来看,TreeMap 本质上就是一棵“红黑树”,而 TreeMap 的每个 Entry 就是该红黑树的一个节点。

《趣谈Linux操作系统》第3讲学习

操作系统内核导航图

内核导航图示例
操作系统内核体系结构图

找到最新版本的 Linux 代码,在里面找到这几个子系统的对应代码位置:

  • kernel:内核管理核心代码,其中包含了进程管理子系统
  • fs(file system):文件管理子系统
  • mm(memeroy mange):内存管理子系统,这里更多的是CPU体系结构的内存管理,与具体物理内存管理相关的代码在 arch/(某种架构)/mm
  • net:网络子系统
  • drivers:设备子系统,其中存放各种硬件的驱动程序,drivers/block 下存放块设备的驱动程序
查看源码模块位置

用 Seedr 网盘 离线下载BT资源和在线播放视频

blob.jpg

Seedr 是一个可以离线下载BT种子的国外网盘,目前不fq可以使用。

现在百度云的离线下载功能似乎是废了,BT资源基本上就没下载成功过。虽然迅雷的下载速度挺快,但是有些资源就是有针对性地下不了。在百度云和迅雷都下载不了的时候,可以用Seedr试试,把它当做下载的中转站,先将资源离线保存到Seedr,再从Seedr下载到自己的电脑。

Seedr 还是挺良心的一个应用,下载速度不错,界面干净,没有广告,但是有容量限制(可以付费升级),而且只能用来下载BT文件。

blob.jpg

使用的时候,可以通过在输入框粘贴磁力链接或者包含BT文件的网址来添加下载任务,也可以直接上传BT文件来下载。

blob.jpg

下载速度不错,当然那些历史悠久不活跃的种子没戏。

blob.jpg
blob.jpg
blob.jpg

下载完了可以在线播放,但是只有付费升级之后才可以看高清的视频,所以,如果在线观看的画质不能接受,可以将视频下载到本地观看。

blob.jpg
blob.jpg

下载到本地的时候只能发出两个请求,速度在 2M/s 左右,这里似乎限速了。