次访问 条评论

浅谈Python Dict 原理

前言:最近在知乎上看到很多Python职位的面试都会问Python的数据结构。很多大公司,比如知乎,在面试python的工程师的时候都会很注重基础;
比如会问:python内置的list dict set等使用和原理。collections 模块里的deque,Counter,OrderDict等。 常用的排序算法和时间复杂度。

今天我就简单说说我学到的关于Python Dict 的见闻。

于是,首先我查看到《流畅的python》一书的第3章。

  1. 首先我们看看Python是如何用散列表来实现dict类型。

什么是散列表:
散列表其实是一个稀疏数组(总是有空白元素的数组称为稀疏数组)。
在一般的数据结构教材中,散列表里的单元通常叫作表元(bucket)。在 dict 的散列表当中,每个键值对都占用一个表元,每个表元都有两
个部分,一个是对键的引用,另一个是对值的引用。因为所有表元的大小一致,所以可以通过偏移量来读取某个表元。

散列算法:
1.为了获取 my_dict[search_key] 背后的值,Python 首先会调用hash(search_key) 来计算 search_key 的散列值,把这个值最低的几位数字当作偏移量(貌似是hash(key) 和 数组的长度-1 作 与运算,hash(key)& (size-1),在散列表里查找表元(具体取几位,得看当前散列表的大小)。

2.若找到的表元是空的,则抛出 KeyError 异常。若不是空的,则表元里会有一对 found_key:found_value。

3.这时候 Python 会检验 search_key == found_key 是否为真,如果它们相等的话,就会返回 found_value。

4.如果 search_key 和 found_key 不匹配的话,这种情况称为散列冲突。

5.Python 解决散列冲突的方法用的是开放地址法。
如下图所示:
Sample Image Added via Markdown

Python dict的特性:

1.字典在内存上的开销巨大。
由于字典使用了散列表,而散列表又必须是稀疏的,这导致它在空间上的效率低下。
2.键查询很快。
dict 的实现是典型的空间换时间:字典类型有着巨大的内存开销,但它们提供了无视数据量大小的快速访问——只要字典能被装在内存里。
3.往字典里添加新键可能会改变已有键的顺序。
无论何时往字典里添加新的键,Python 解释器都可能做出为字典扩容的决定。扩容导致的结果就是要新建一个更大的散列表,并把字典里已有的元素添加到新表里。

关于Python的开放地制法解决hash冲突的实现可以参考下
https://harveyqing.gitbooks.io/python-read-and-write/content/python_advance/python_dict_implementation.html

Sample Image Added via Markdown

若要了解详细的内部机制,推荐阅读
http://python.jobbole.com/85040/

次访问 条评论

堆排序学习总结

在学习《算法》一书中了解到:
优先队列是一种抽象的数据类型,优先队列最重要的操作就是删除最大元素和插入元素。
实现优先队列可以用数组,链表,最好的方式还是用堆。

我们可以把任意优先队列变成一种排序方法。将所有元素插入一个查找最小化元素的优先队列,然后再重复调用删除最小元素的操作将它们按顺序删去。用无序数组实现的优先队列这么做相当于进行一次选择排序。用基于堆得优先队列这样做等同于堆排序!

要了解堆首先得了解一下二叉树,在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。

二叉树又分为满二叉树(full binary tree) 和 完全二叉树(complete binary tree)

满二叉树:一棵深度为 k,且有 2k - 1 个节点称之为满二叉树

Sample Image Added via Markdown

完全二叉树则满足序号和满二叉树的完全对应。

Sample Image Added via Markdown

如下图,是一个堆和数组的相互关系
Sample Image Added via Markdown

对于给定的某个结点的下标 i,可以很容易的计算出这个结点的父结点、孩子结点的下标:

  • Parent(i) = floor(i/2),i 的父节点下标
  • Left(i) = 2i,i 的左子节点下标
  • Right(i) = 2i + 1,i 的右子节点下标

堆排序原理

堆排序就是把最大堆堆顶的最大数取出,将剩余的堆继续调整为最大堆,再次将堆顶的最大数取出,这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作:

最大堆调整(Max-Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点(左子树不一定大于右子树)
创建最大堆(Build-Max-Heap):将堆所有数据重新排序,使其成为最大堆
堆排序(Heap-Sort):移除位在第一个数据的根节点,并做最大堆调整的递归运算

继续进行下面的讨论前,需要注意的一个问题是:数组都是 Zero-Based,这就意味着我们的堆数据结构模型要发生改变

相应的,几个计算公式也要作出相应调整:

Parent(i) = floor((i-1)/2),i 的父节点下标
Left(i) = 2i + 1,i 的左子节点下标
Right(i) = 2(i + 1),i 的右子节点下标

最大堆调整(MAX‐HEAPIFY)的作用是保持最大堆的性质,是创建最大堆的核心子程序,作用过程如图所示:

Sample Image Added via Markdown

源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
def heapsort(arr):
def max_heapify(arr, index, heap_size):
"""
# 最大堆调整(MAX‐HEAPIFY)的作用是保持最大堆的性质。 将堆的末端子节点作调整,使得子节点永远小于父节点
# 意思就是要让index这元素去到它该去的位置
《算法》P200
由上至下的对有序化(下沉)
如果我们把堆想象成一个严密的黑色会组织,每个子节点都表示一个下属(父节点则表示它的直接上级),name这些操作就可以得到很有趣的解释。
max_hepify这个方法就相当于一个领导,如果占着老大的位置,但如果自己下属有比自己厉害的就要退位让贤。自己去到该去的层次
注意的是:这方法是有惰性的。调用一次该方法仍然不行。如果该index的左右子树都小于自己的话,它就不会递归了。
这个方法只是让index尽量下沉下去。如果是堆有序的话,那么执行该方法后index位置就是该位置最大的值
"""
while True:
imax = index
ileft = 2 * index + 1
iright = 2 * index + 2
if ileft < heap_size and arr[index] < arr[ileft]:
imax = ileft
if iright < heap_size and arr[imax] < arr[iright]:
imax = iright
if imax != index:
arr[imax], arr[index] = arr[index], arr[imax]
index = imax
else:
break
def build_maxheap(arr):
"""
# 将堆所有数据重新排序,使其成为最大堆
创建最大堆(Build-Max-Heap)的作用是将一个数组改造成一个最大堆,接受数组和堆大小两个参数,Build-Max-Heap 将自下而上的调用 Max-Heapify 来改造数组,建立最大堆。
因为 Max-Heapify 能够保证下标 i 的结点之后结点都满足最大堆的性质,所以自下而上的调用 Max-Heapify 能够在改造过程中保持这一性质。
如果最大堆的数量元素是 n,那么 Build-Max-Heap 从 Parent(n) 开始,往上依次调用 Max-Heapify。
"""
iparent = len(arr) // 2 - 1 # 最后一个节点的父节点
for i in range(iparent, -1, -1):
max_heapify(arr, i, len(arr))
def sort(arr):
build_maxheap(arr) # build后左子树 还是可能大于 右子树的.所以这并不是一个有序数组
print(arr)
for i in range(len(arr)-1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
max_heapify(arr, 0, i) # 这里这个i 相当于比当前的length - 1;第i个元素为当前最大的元素,就被固定死了。不再访问它
return arr
return sort(arr)
if __name__ == '__main__':
print(heapsort([5,4,7,3,8,2,11,15,17,16,13,10,9,12,1]))
次访问 条评论

TCP/IP 的一些学习

还记得两三年前,去一个大数据公司面试。首先要笔试,题目中有道题目就是填空TCP报文的表格。
首先我们看看TCP的报头:

Sample Image Added via Markdown

当时觉得这是啥玩意呀。考这东西跟大数据有毛线关系。今天,才明白,这些都是计算机的基础。基本功来的,跑不了。

下面我们可以通过一张图就能比较清晰地展现TCP/IP建立连接的过程。也就是我们常说的3次握手,4次挥手。

我们先看3次握手的过程:
Sample Image Added via Markdown

1.首先Server端是处在一个Listen的状态。经常你用netstat可以看到,比如打开了一个web 服务,就卡看到80端口处在listen状态
2.由客户端发送一个Segment(传输层的数据包单位)到服务的,主要内容有 SYN=1,seq=x(一个随机数)。发送后,客户端状态变为SYN-SENT
3.服务端收到客户端发送的Segment,状态变为SYN-REVD,并发送一个SYN=1,ACK=1,seq=y,ack=x+1 的Segment返还给客户端。表示自己收到了你的消息。
4.客户端收到服务端返还的内容后,状态就变成了ESTABLISHED。表示成功建立了连接。并且再次发送一个ACK=1,ack=y+1,seq=x+1 的Segment。
5.服务端收到客户端发来的Segment后,状态变为ESTABLISHED。成功完成3次握手。

建立一次连接,需要3次握手,也就是说发送3个数据包即可建立连接。发送的数据包内容中我们可以发现一点规律。ack的数值内容都是对方发送给自己的seq数值 +1 。

接下来我们看看4次挥手的过程。
Sample Image Added via Markdown

1.首先由终端的提出方(假设是客户端)发送一个FIN=1,seq=u 的Segment到服务端。发送后客户端状态变为FIN-WAIT-1
2.服务端收到了客户端的Segment后状态变为CLOSE-WAIT,并反回一个ACK=1,seq=v,ack=u+1 的Segment给客户端。
3.客户端收到了服务端返回的消息后状态变为FIN-WAIT-2,此时服务端并没有关闭,意思是告诉客户端,请您耐心等待,我看看还有什么数据没有给你的,把剩下的数据发给你先。
4.过了片刻,服务端发送一个FIN=1,ACK=1,seq=w,ack=u+1 的Segment给客户端。然后服务端状态变为了LAST-ACK。
5.客户端收到了服务端发来的消息后,状态变为了TIME-WAIT。并发送ACK=1,seq=u+1,ack=w+1的Segment。表示我知道了,我再等等你(2MSL)还有什么话跟我说的。没有的话我就关了。
6.服务端收到客户端发送的消息后,状态就变为CLOSED了。

从网上找到自己的答案

Use the Right Search Engine

成为一个程序员也有一段时间了。回过头来想想看以前做的事情,只想说:非常low!

我记得东哥那时候推荐我用bing或者翻墙上谷歌。我当时可是一脸懵逼,感觉用习惯了,也觉得没什么不好的地方。

不说其他的,就说程序这块吧。当你运行代码碰到一个报错信息时候,直接用google搜的话很快就能找到解决方案。比如Python的话google返回的很有可能是stackoverflow这些链接。linux的是askubuntu的这些链接。

而百度返回的很有可能是Oschina或者Csdn等等。然而很多好的解答都是在stackoverflow那些网站。

English is Important

有些比较少罕见的问题,国内搜索引擎压根就找不到,国内压根就没有这方面答案。你必须从国外的网站获取解答。比如 Github issue 、Quora或者官方文档。

more >>

Spark 的宽依赖和窄依赖

说说Spark 的宽依赖和窄依赖

宽依赖和窄依赖

  众所周知,在Spark中可以对RDD进行多种转换,父RDD转换之后会得到子RDD,于是便可以说子RDD的诞生需要依赖父RDD。在Spark中一共有两种依赖方式,分别是宽依赖和窄依赖。

rdd 的 toDebugString 可以查看RDD的谱系

more >>

Spark 数据倾斜调优

关于Spark 的数据倾斜的问题

数据倾斜的现象

  1、绝大多数task执行得都非常快,但个别task执行极慢。比如,总共有1000个task,997个task都在1分钟之内执行完了,但是剩余两三个task却要一两个小时。这种情况很常见。

  2、原本能够正常执行的Spark作业,某天突然报出OOM(内存溢出)异常,观察异常栈,是我们写的业务代码造成的。这种情况比较少见。

数据倾斜的原理

  数据倾斜的原理很简单:在进行shuffle的时候,必须将各个节点上相同的key拉取到某个节点上的一个task来进行处理,比如按照key进行聚合或join等操作。此时如果某个key对应的数据量特别大的话,就会发生数据倾斜。比如大部分key对应10条数据,但是个别key却对应了100万条数据,那么大部分task可能就只会分配到10条数据,然后1秒钟就运行完了;但是个别task可能分配到了100万数据,要运行一两个小时。因此,整个Spark作业的运行进度是由运行时间最长的那个task决定的。

  因此出现数据倾斜的时候,Spark作业看起来会运行得非常缓慢,甚至可能因为某个task处理的数据量过大导致内存溢出。

more >>

浅谈SPARK 的 广播变量

简单谈谈SPARK 广播变量的用法

首先我们看看官网的文档对Broadcast的描述:

  • Broadcast variables allow the programmer to keep a read-only variable cached on each machine rather than shipping a copy of it with tasks.

  • 意思就是说广播变量让你可以在每个节点机器上缓存一个只读的变量,而减少了在每个任务中复制一份的繁琐。

  • Spark还尝试使用高效地广播算法来分发变量,进而减少通信的开销。
  • Spark的动作通过一系列的步骤执行,这些步骤由分布式的洗牌操作分开。Spark自动地广播每个步骤每个任务需要的通用数据。这些广播数据被序列化地缓存,在运行任务之前被反序列化出来。这意味着当我们需要在多个阶段的任务之间使用相同的数据,或者以反序列化形式缓存数据是十分重要的时候,显式地创建广播变量才有用。

创建的方法很简单

more >>

浅谈SPARK 的 combineByKey 算子

理解comebineByKey的原理

SPARK的combineByKey算子和aggregate类似。首先我们看看官网的文档:

  • combineByKey(createCombiner, mergeValue, mergeCombiners, numPartitions=None, partitionFunc=)

  • Turns an RDD[(K, V)] into a result of type RDD[(K, C)], for a “combined type” C. Note that V and C can be different – for example, one might group an RDD of type (Int, Int) into an RDD of type (Int, List[Int]).

  • Users provide three functions:
    createCombiner, which turns a V into a C (e.g., creates a one-element list)
    mergeValue, to merge a V into a C (e.g., adds it to the end of a list)
    mergeCombiners, to combine two C’s into a single one.

都是将类型为RDD[(K,V)]的数据处理为RDD[(K,C)]。这里的V和C可以是相同类型,也可以是不同类型。

combineByKey函数主要接受了三个函数作为参数,分别为createCombiner、mergeValue、mergeCombiners。

这三个函数足以说明它究竟做了什么。理解了这三个函数,就可以很好地理解combineByKey。

more >>

浅谈SPARK 的 aggregate 算子

理解aggregate的原理

刚开始我觉得SPARK的aggregate算子比较难理解的。首先我们看看官网的example

>>> seqOp = (lambda x, y: (x[0] + y, x[1] + 1))
>>> combOp = (lambda x, y: (x[0] + y[0], x[1] + y[1]))
>>> sc.parallelize([1, 2, 3, 4]).aggregate((0, 0), seqOp, combOp)
(10, 4)
>>> sc.parallelize([]).aggregate((0, 0), seqOp, combOp)
(0, 0)    

看了后,我就一脸懵逼了,两个lambda函数中的x,y各自代表什么东西呢?

我们先看看官网的aggregate 用法说明:

Aggregate the elements of each partition, and then the results for all the partitions, using a given combine functions and a neutral “zero value.”

The functions op(t1, t2) is allowed to modify t1 and return it as its result value to avoid object allocation; however, it should not modify t2.

The first function (seqOp) can return a different result type, U, than the type of this RDD. Thus, we need one operation for merging a T into an U and one operation for merging two U

more >>