P：能够以多项式时间被求解的问题称为P-问题。比如说O(n),O(n^5)，这都是多项式时间。

举个例子，给n个数，找出其中所有的偶数。这个就是P-问题。

NP：首先NP-问题不能以多项式的时间求解；并且，如果我们假设找到了一个答案，这个答案可以以多项式的时间检验该答案是否正确。

比如说，我们要找出所有(1,2,3)的置换，并且第一个元素小于第二个元素。这里一共有3!=3*2*1=6个置换，(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)，符合第一个元素小于第二个元素的置换有3个。如果是(1,2,...,n)的置换，我们则需要至少O(n!)的时间来求解，这是大于多项式时间的。再者，如果给出任意一个备选答案，比如(5,2,1,4,3)，我们只需要花多项式的时间（这里是O(n)时间）来检查这个备选答案是不是真的是一个置换并且第一个元素小于第二个元素。

NP-hard：首如果一个问题通过一些步骤能够化简为一个NP问题，那么这个问题就是NP-hard问题。换句话说，至少是NP的问题称之为NP-hard问题。

著名的NP-hard例子就是旅行商问题。假设有n个城市，找出一条每个城市都访问一次且仅访问一次的最短路线。

就我知道的 :

.remove(value)  --> O(n)

.pop(index) --> O(n-index)

说明下， O(pop())可能一开始由于index查找的原因会误以为是O(1)，但其实在完成删除这个步骤之后，所有在这个被删除位置之后的元素的index都会被向前移一位, 或者说向前补充。 并且pop(）最后会返回被删除的元素值。  

remove（）就很直接了， 从第0个元素找起， 直到找到第一个match的元素并删除(不会像pop一样返回被删掉元素的值)， 然后剩余元素向前补充。 

from collections import defaultdict
mydict = defaultdict(lambda: 0)

然后你call一个不存在的key，得到的就是0

你去看看Python doc有注释，必须是可调用或者是None

dict(A,**B)

A.update(B)

这是道编码题，而且$2^{10}=1024$，会想到二进制编码。先瓶子编号向量$X$为00_0000_0000到11_1110_0111。老鼠喝水操作的矩阵$A$，第一行$A_{1*}=$10_0000_0000，表示一号老鼠喝所有$X=$1x_xxxx_xxxx的水，x表示0和1都喝。$Y_1=A_{1*}X$用于标志从左到右的$X$第一位是0或1。第二行$A_{2*}=$01_0000_0000，表示一号老鼠喝所有$X=$x1_xxxx_xxxx的水。以此类推。

老鼠死掉的编码$Y$就是毒药瓶子的编码，因为$A=I$。比如0号瓶是毒药，$Y$=00_0000_0000；如果1号瓶是毒药，$Y$=00_0000_0001。1代表老鼠死掉。每个瓶子对应唯一的$Y$。

$Y=AX$

进一步，只要$A$是正交基，$X$通过$A$投影，有唯一$Y$对应。

spark.sql('SHOW PARTITIONS db.tbl_merchandise').show()

import shutil

src = 'a.txt'

dst = 'folder_a/b.txt'

shutil.copyfile(src, dst)

先引用一下F

from pyspark.sql import functions as F

然后用下面的表达式提取星期几

F.from_unixtime(F.unix_timestamp(F.col('date_str'), 'yyyy-mm-dd'), 'u')

得到1到7的整数，1是星期一，2是星期二，等等等

beam search在nlp以及sequence modeling还是经常出现的。

假如我们要从上十万个元素中寻找4个元素$Y_1,\cdots,Y_4$使得$P(Y_1,Y_2,Y_3,Y_4|X)$最大，如果要找精确解，我们就要遍历所有的组合，也就是$\binom{10^6}{4}$，大概是$10^{15}$，天文数字，不可能去遍历的。

所以，我们通常找到一个$Y1$，使得$P(Y_1|X)$最大，然后根据

$$P(Y_1,Y_1|X)=P(Y_2|X,Y_1)P(Y_1|X)$$

再去寻找$Y_2$，使得$P(Y_2|X,Y_1)$最大。此次类推，按照这种贪婪算法，我们就能找到$Y_1,\cdots,Y_4$，搜寻次数只需要$4\times 10^6$。

但是显然这样的贪婪搜索不能保证最优性，甚至都无法达到较优。beam search就是对贪婪算法的改良。

beam就是带宽。当beam=3的时候，我们每次保留三个最佳候选然后再进行下一步迭代。

下图就是beam为3的一个搜索树，我们从左往右搜索，每次搜索的最佳的三个点用红色标注。

挺有意思的题目，我自己用两种方法做了一下

第一个方法是生成一个全零的矩阵，然后对四个边重新赋值为1

def func1(n):
    arr = np.zeros([n] * 2)
    arr[[0, -1], :] = 1
    arr[:, [0, -1]] = 1
    return arr

第二个方法是生成一个全一的矩阵，然后对中心区域重新赋值为0

def func2(n):
    arr = np.ones([n] * 2)
    arr[1:-1, 1:-1] = 0
    return arr

第二个方法的代码少一行，但是我自己试了一下对于大矩阵，比如n>1000，方法一明显快不少，矩阵越大快的越明显。应该是方法一更好。

比较时间的代码：

t0 = time.time()
for i in range(100):
    func1(5000)  
t1 = time.time()
for i in range(100):
    func2(5000)  
t2 = time.time()
print(t1-t0, t2-t1)

1.3369219303131104 13.74842095375061

用法如下

SELECT * FROM tab1 LEFT SEMI JOIN tab2 ON (tab1.id = tab2.id);

left semi join和left outer join相似，也和inner join有点相似。但left semi join只返回tab1中的列，不是完整的join，所以是semi join

和left outer join相似：因为left semi join只返回左表里的

和inner join相似：因为left semi join不返回右边里没有的

比如tab1，tab2是

它们inner join的结果是

它们left join的结果是

它们left semi join的结果是

因为表tab1中只有一个id=2，尽管tab2中有多个id=2，我们也只匹配一个，最后返回的时候只得到tab1中的列

对于或运算，只要有一个是True，整个就是True了

>>> x = [True, False, True, False, False]

>>> True in x

True

也可以看整个list中的最大值

>>> x = [True, False, True, False, False, False, False]

>>> max(x)

True

也可以用numpy的any函数

Examples
--------
>>> np.any([[True, False], [True, True]])
True

>>> np.any([[True, False], [False, False]], axis=0)
array([ True, False])

>>> np.any([-1, 0, 5])
True

>>> np.any(np.nan)
True

>>> o=np.array([False])
>>> z=np.any([-1, 4, 5], out=o)
>>> z, o
(array([ True]), array([ True]))
>>> # Check now that z is a reference to o
>>> z is o
True
>>> id(z), id(o) # identity of z and o              # doctest: +SKIP
(191614240, 191614240)

inorder traversal是对树的中序遍历，顺序是 左子树 => 根 => 右子树。

上面的例子中，左子树是空，根是1。在右子树中左子树是3，根是2，右子树是空。合在一起就是1，3，2。

上面这个例子中中序遍历是4->2->5->1->3。

set是一个无序且元素唯一的数据结构，只用add操作没有append的操作。

a = {1, 2}

s.add(3)

import os
num_cpu = os.cpu_count()

https://packaging.python.org/tutorials/packaging-projects/

参考一下标准文档

如果要查看sql_df的schema可进行如下操作

sql_df.printSchema()

先引用一下pyspark的functions

import pyspark.sql.functions as F

然后用Functions中的last_day函数就可以得到当月的最后一天

select(F.last_day(F.col('dates')).alias('last_day_of_month'))

用json_tuple提取，格式为json_tuple(json_field, key)

按照你的字段名字，可以写成下面这样

from pyspark.sql.functions import json_tuple, col

data = spark.table('my_table').withColumn('body_text', json_tuple(col('field2'), 'body'))

from pyspark.sql.types import  IntegerType

df.withColumn('flag', F.col('logintype').isin(['sec', 'fta']).cast(IntegerType()))

spark sql也不一定是基于hadoop之上的，只是现在常用的场景是在hdfs之上使用spark。

Spark是在内存中计算，hive sql是提交后进行MapReduce在磁盘中计算。所以Spark会更快。