理论篇-数据结构之哈希表

直接定址表

当数据量有限时，通过将数据一一映射到数组，可以获得O(1)的时间复杂度。

direct_addressing

哈希表

当真正被存储的数据量比实际可能的数据量要小很多时，哈希表就显示出它的威力来了。

hash_table_01

关键字

尽可能的将关键字使用数字表示

哈希函数

一个好的哈希函数的标准: 任何一个关键字都有平等的机会映射到哈表表的每个槽位，并且与其他关键字无关。

通常使用的哈希算法有: 1. 取模

实现原理

通过使用哈希函数将关键字映射到数组的下标地址，但是，由于哈希表空间有限，所以会出现两个不同的关键字映射到了同一个数组下标的情况，因此需要冲突解决。

冲突解决的方法有: 1. 链式 2. 开放定址

hash_table_02

负载因子

负载因子=已存节点数量/槽的数量，应尽量保持其值小于等于1。

应用

哈希表一般用于字典的底层实现

展开全文 >>

理论篇-一致性哈希算法

DHT

DHT(distributed hash table)分布式哈希表，是一种分布式存储方法。一致性哈希算法是DHT的一种实现。

普通哈希

普通哈希算法是一个将范围很大的集合通过哈希函数映射到范围固定的集合上的一种方法。

问题

普通哈希算法有自己的局限性，比如在分布式缓存中，如果增减服务器，会造成大面积的缓存失效。具体例子: 假设我们现在有100台服务器，机器编号为0-99，之前关键字为101的请求会路由到101%100=1这台机器。现在我们需要增加一台机器，那么关键字为101的请求将会路由到101%101=0这台机器，最终导致缓存访问失效。

一致性哈希算法(consistent hashing)

一致性哈希有如下几个特性:

  • 冗余少
  • 负载均衡
  • 过度平滑
  • 存储均衡
  • 关键词单调

实现

展开全文 >>

理论篇-各种锁

乐观锁与悲观锁

乐观锁

乐观锁其实本质没有使用任何锁，原名是乐观并发控制(Optimistic Concurrency Control)。原理是乐观的假设不会发生冲突，只有在真正更新数据时才会检查是否冲突。通常使用版本号等实现。

使用场景:

  • 冲突少的场景下

在数据库中的使用方法如下:

1
2
3
select status, version from goods where id=xxx
对数据做一些修改
update goods set status=2, version=version+1 where id=xxx and version={version}

悲观锁

悲观锁是悲观的认为会发生冲突，所以需要拿到锁之后再对数据做一些操作。

使用场景:

  • 冲突多的场景

在数据库中使用方法如下:

1
2
3
4
5
begin    # 开启一个事务
select status from goods where id=xxx
对数据做一些修改
update goods set status=2 where id=xxx
commit   # 提交事务

展开全文 >>

实战篇-python面试

数据类型及变量

引用

1
2
3
4
5
6
7
8
9
10
11
a = 1
def f(a):
    a = 2
f(a)
print a      # 1
-------------------
a = []
def f(a):
    a.append(1)
f(a)
print a      # [1]

涉及python中的引用以及可变量与不可变量的知识

字符串格式化

1
2
3
4
5
6
name = "x"
"hi there %s" % name   # hi there x
name= ("x", )
"hi there %s" % (name, ) # hi there x
"hi there {0}".format(name)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class MyClass():
    def __init__(self):
        self.__superprivate = "hello"
        self._semiprivate = "world"
    def f(self):
        print self.__superprivate
mc = MyClass()
print mc.__dict__
print mc._semiprivate
mc.f()
print mc.__superprivate
--------output--------
{'_MyClass__superprivate': 'hello', '_semiprivate': 'world'}
world
hello
Traceback (most recent call last):
  File "test.py", line 32, in <module>
    print mc.__superprivate
AttributeError: MyClass instance has no attribute '__superprivate'
  • __foo__: 一种约定，python内部的名字，用来区别用户自定义的名字，以防冲突
  • _foo: 一种约定，程序员用来指定私有变量的形式
  • __foo: 真正的私有变量，会变成_classname__foo

is与==

1
2
is比较引用地址
==比较值

类相关

__new__与__init__

  • __new__是一个类方法，__init__是一个实例方法
  • __new__返回一个创建的实例，__init__什么都不返回
  • __new__执行后__init__才执行

类的各种方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def foo(x):
    print("foo %s" % x)
    
class A(object):
    def foo(self, x):
        print("foo %s %s", self, x)
    
    @classmethod
    def class_foo(cls, x):
        print("class_foo %s %s", cls, x)
        
    @staticmethod
    def static_foo(x):
        print("static_foo %s", x)
\ 实例方法 类方法 静态方法
a = A() a.foo(x) a.class_foo(x) a.static_foo(x)
A 不可用 A.class_foo(x) A.static_foo(x)

实例方法的本质是foo(a, x)，类方法的本质是class_foo(A, x)，静态方法的本质是普通方法，只是作用域不同

类的各种变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Person:
    name = "aaa"
    
p1 = Person()
p2 = Person()
p1.name = "bbb"
print p1.name     # bbb
print p2.name     # aaa
print Person.name # aaa
-----------------------
class Person:
    name = []
p1 = Person()
p2 = Person()
p1.name.append(1)
print p1.name    # [1]
print p2.name    # [1]

单例

参看源码

自省机制

自省就是程序执行时能知道对象的类型。

1
2
3
4
5
type()
dir()
getattr()
hasattr()
isinstance()

推导式

1
2
3
4
5
[x for x in xrange(3)]    # [0, 1, 2]
[x for x in xrange(10) if x%2 == 0]  # [0, 2, 4, 6, 8]
[[x, y] for x in xrange(2) for y in xrange(2)]  # [[0, 0], [0, 1], [1, 0], [1, 1]]
{key: value for (key, value) in iterable}

迭代器与生成器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
mylist = [1, 2, 3]
for i in mylist:
    print i
for i in mylist:
    print i
mygenerator = (x for x in range(3))
for i in mygenerator:
    print i
for i in mygenerator:
    print i
    
---- output ----
1
2
3
1
2
3
0
1
2
  • 迭代器的本质是: __iter__和__next__
  • 生成器的本质是: yield

函数

*args和**kwargs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def print_everything(*args):
    for count, thing in enumerate(args):
        print '{0} {1}'.format(count, thing)
print_everything('apple', 'banana', 'cabbage')
def table_things(**kwargs):
    for key, value in kwargs.items():
        print '{0}={1}'.format(key, value)
table_things(apple='fruit', cabbage='vegetable')
---- output ----
0 apple
1 banana
2 cabbage
cabbage=vegetable
apple=fruit

装饰器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def makebold(fn):
    def wrapped():
        return '<b>' + fn() + '</b>'
    return wrapped
def makeitalic(fn):
    def wrapped():
        return '<i>' + fn() + '</i>'
    return wrapped
@makebold
@makeitalic
def say():
    return 'hello world'
print say()
---- output ----
<b><i>hello world</i></b>

闭包

  • 必须有一个内嵌函数
  • 内嵌函数必须引用外部函数中的变量
  • 外部函数的返回值必须是内嵌函数

lambda表达式

1
2
f = lambda x, y, z: x+y+z
f(1, 2, 3)  # 6

函数式编程

1
2
3
4
5
6
7
print filter(lambda x: x>5, [1, 2, 3, 4, 5, 6, 7])
print map(lambda x: x**2, [1, 2, 3, 4, 5, 6, 7])
print reduce(lambda x, y: x*y, range(1, 4))
---- output ----
[6, 7]
[1, 4, 9, 16, 25, 36, 49]
6

鸭子类型

作用域

  • 本地作用域(local)
  • 当前作用域被嵌入的作用域(enclosing local)
  • 全局/模块作用域(global)
  • 内置作用域(built-in)

全局解释器锁(GIL)

协程

拷贝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import copy
a = [1, 2, 3, 4, ['a', 'b']]
b = a
c = copy.copy(a)
d = copy.deepcopy(a)
a.append(5)
a[4].append('c')
print a
print b
print c
print d
---- output ----
[1, 2, 3, 4, ['a', 'b', 'c'], 5]
[1, 2, 3, 4, ['a', 'b', 'c'], 5]
[1, 2, 3, 4, ['a', 'b', 'c']]
[1, 2, 3, 4, ['a', 'b']]

垃圾回收机制

GC主要使用引用计数(reference counting)来跟踪和回收垃圾。在引用计数的基础上通过”标记-清除”(mark and sweep)解决容器对象可能产生的循环引用问题，通过”分代回收”(generation collection)以空间换时间的方法提高垃圾回收效率。

引用计数

PyObject是每个对象必有的内容，其中ob_refcnt就是引用计数器。当一个对象有新的引用时，ob_refcnt就增加，当引用它的对象被删除时，ob_refcnt就减少。引用计数器为0时，该对象的生命就结束了。

  • 优点
    • 简单
    • 实时性
  • 缺点
    • 维护引用计数消耗资源
    • 循环引用

标记-清除机制

基本思路是先按需分配，等内存空间不够时从寄存器或程序栈上的引用出发，遍历以对象为节点，以引用为边构成的图，把所有可访问的对象打上标记，然后清扫一遍内存空间，把所有没标记的对象清除。

分代回收

分代回收的基本思想: 将系统中的所有内存块根据其存活时间分为不同的集合，每个集合就成为一个代，垃圾回收频率随着“代”的存活时间的增大而减小，存活时间通常利用经过几次垃圾回收来衡量。

展开全文 >>

理论篇-编程语言

类型

动态/静态类型: 当声明一个变量时，若需明确指定该变量的类型，则该语言是静态类型，否则是动态类型

强弱类型: 若某个变量的类型确定之后，则只能对其进行该类型的操作，则该语言是强类型，否则是弱类型

类型 例子
动态 强类型 python
动态 弱类型 php lua
静态 强类型
静态 弱类型 c c++

展开全文 >>

理论篇-python编程之基础

在python的世界中，万物皆对象。

  • 可作用于多种类型的通用型操作都是以内置函数或表达式的形式出现的，类型特定的操作是以方法调用的形式出现的

数据类型

类型 例子
number 1234, 3.14
string ‘xxx’
list [1, [2, 3], 4]
dict {“xxx”:[1, 2], “a”: “b”}
tuple (1, ‘xxx’, 4)
file f = open(‘xxx’, ‘r’)
set set(‘abc’)
other core types boolean type None
program unit types function module class

字符串

  • 以字符序列的形式存储的
  • 支持负索引
  • 不可变
  • 字符串方法
  • 格式化操作
1
2
3
4
5
6
7
a = "aaa"
b = "bbb"
a + b > "aaabbb"
a * 2 > "aaaaaa"
"%s %s" % ("hello", "world")
"{0} {1}".format("hello", "world")

展开全文 >>

tag:

    缺失模块。
    1、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    2、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: true
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

王彪<br>计算机科学与技术专业<br>email:841824090@qq.com<br>2009-2013 苏州大学<br>2013-2015 苏州思必驰信息科技有限公司<br>2016-2017 美团<br>2017-至今 搜狗