时间有限, 有空待续…

. . .

. . .

python的单例实现方式茫茫多, 讲道理, 其实是违背python之禅的:

There should be one– and preferably only one –obvious way to do it. 用一种方法，最好是只有一种方法来做一件事

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

>>> import this
The Zen of Python, by Tim Peters

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren't special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one-- and preferably only one --obvious way to do it.
Although that way may not be obvious at first unless you're Dutch.
Now is better than never.
Although never is often better than *right* now.
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea -- let's do more of those!

. . .

曾在使用Win0系统进行数据交换过程中发现，网上邻居上怎么找都找不着其他电脑，为何呢？也是用了很多办法，一次次失败后最后终于解决了，原来在很多优化/安全软件“整理”过的电脑中，有他们认为危险但实际非常重要的设置被强行关闭了。接下来我们看看怎么处理。

先参考下面几张图设置一波

. . .

基于比较的排序算法复杂度的理论下界为 O(nlog n)，同时指出了：

每一次判定 a < b ，都相当于回答了一次「是否问题」。按照已有的知识，若要尽可能快地完成排序，就要让每一次大小判断的结果落在两种答案之一的概率接近；若不然，则这次比较带来的信息量较小，也就需要更多次的比较来完成排序。

此篇建立在这些知识的基础上，首先探讨以下三个问题，而后引出号称「在所有情况下，都能较快完成排序任务的内省式排序（Introspective Sort）」：

1. 为什么堆排序一般快不过快速排序？
2. 快速排序快得无懈可击吗？
3. 插入排序什么时候快？

为什么在平均情况下快速排序比堆排序要优秀

堆排序是渐进最优的比较排序算法，达到了O(nlgn)这一下界，而快排有一定的可能性会产生最坏划分，时间复杂度可能为O(n^2)，那为什么快排在实际使用中通常优于堆排序？

• 虽然quick_sort会n^2（其实有稳定的nlgn的版本），但这毕竟很少出现。heap_sort大多数情况下比较次数都多于quick_sort，尽管大家都是nlgn。那就让倒霉蛋倒霉好了，大多数情况下快才是硬道理。
• 堆排比较的几乎都不是相邻元素，对cache极不友好，这才是很少被采用的原因。数学上的时间复杂度不代表实际运行时的情况.快排是分而治之，每次都在同一小段进行比较，最后越来约接近局部性。反观堆排，堆化过程中需要一直拿index的当前元素A和处于index*2 + 1 的子元素B比较, 两个元素距离较远。(局部性原理是指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。)
• 在快排的迭代过程中，我们所处理的 [比基准大的数]，[比基准小的数] 序列中，在进行两个数之间大小比较时，在该局部范围内，产生“大于”或者“小于”的可能性是一样的。这意味着每比较一次必然会产生一次有意义的比较结果，会缩减接下来迭代的扫描工作量。
• 我们再来看看堆排序。在每一次进行重新堆调整的时候，我们在迭代时其实就已经知道，上一层的结点值一定是比下面大的。为了打乱堆结构把最后一个元素与顶堆互换时，此时我们也已经知道，互换后的元素是一定比下一层的数要小的。而在迭代时为了调整堆我们还是要进行一次已经知道结果的比较，这无疑是没有什么价值的，也就是产生了一次没有意义的比较，对接下来的迭代工作量并没有任何进展。

. . .