---
hackpadID: 0GIlFIuQVOG
hackpadWorkspace: tossug
tags: hackpad-import, tossug
---
# DS 讀書會 - 第 5 週

12/16/2014

[« 回首頁](/JwdmDZwMwE3BacBGApgDngFkwYx/NAVjQxlgCZgkdo0AjNIA)

## 討論範圍

* Big-O 兩題練習題
* Analysis
* Performance of Python Data Structures - Programming Exercises

## 預定進度

相信大家都已進入狀況，這次進度是 Stacks 全部：

* Basic Data Structures
* Objectives - Infix, Prefix and Postfix Expressions

## 認領狀態

* Balanced Symbols (A General Case)
* [RJ Hsiao](/ep/profile/BzrOLagTOUQ)
* Converting Decimal Numbers to Binary Numbers
* [RJ Hsiao](https://tossug.hackpad.com/ep/profile/BzrOLagTOUQ)
* Infix, Prefix and Postfix Expressions
* [Ted Wu](/ep/profile/xo5A62wXl3B)

## 心得筆記

List Comprehensions

* [](https://docs.python.org/3/tutorial/datastructures.html#list-comprehensions)https://docs.python.org/3/tutorial/datastructures.html#list-comprehensions
* [](http://www.secnetix.de/olli/Python/list_comprehensions.hawk)http://www.secnetix.de/olli/Python/list_comprehensions.hawk

Hashing

* 請參閱 Sorting and Searching 一節。

Hash table:

* [](http://en.wikipedia.org/wiki/Hash_table)http://en.wikipedia.org/wiki/Hash_table

Collision resolution

* Separate chaining
* Open addressing
* Robin Hood hashing
* 2-choice hashing

Well-known probe sequences:

* Linear probing
* Quadratic probing
* Double hashing

## Ubuntu 14.04使用Python繪圖

** 準備**

* sudo apt-get install ipython3 
* sudo apt-get install python3-matplotlib

** 使用**

* import matplotlib.pyplot as plt
* 紀錄X，Y對應的點
* 設定x, y軸說明
* 每條曲線繪圖
* 顯示

* #!/usr/bin/env python3
* import matplotlib.pyplot as plt
* import timeit

* # Dirty hack for passing grow list size
* g_base = 0

* def test1():
* l = []
* for i in range(g_base):
* l = l + [i]
* return l

* def test2():
* l = []
* for i in range(g_base):
* l.append(i)
* return l

* def test3():
* l = [i for i in range(g_base)]
* return l

* def test4():
* l = list(range(g_base))
* return l

* if __name__ == "__main__":
* t_record = [[0 for x in range(10)] for x in range(4)]
* t_degree = [i for i in range(10)]
* t_lines = (’concat’, ’append’, ’comprehension’, ’list range’)

* # Collect data (execute time)
* for i in range(1, 11):
* g_base = 120 * i
* t_degree[i - 1] = g_base

* print("\n\nAdd list with %d" % g_base)
* t1 = timeit.Timer("test1()", "from __main__ import test1")
* t_elapse = t1.timeit(number=1000)
* t_record[0][i - 1] = t_elapse
* print("concat ", t_elapse, "milliseconds")

* t2 = timeit.Timer("test2()", "from __main__ import test2")
* t_elapse = t2.timeit(number=1000)
* t_record[1][i - 1] = t_elapse
* print("append ", t_elapse, "milliseconds")

* t3 = timeit.Timer("test3()", "from __main__ import test3")
* t_elapse = t3.timeit(number=1000)
* t_record[2][i - 1] = t_elapse
* print("comprehension ", t_elapse, "milliseconds")

* t4 = timeit.Timer("test4()", "from __main__ import test4")
* t_elapse = t4.timeit(number=1000)
* t_record[3][i - 1] = t_elapse
* print("list range ", t_elapse, "milliseconds")

* # Prepare to plot
* plt.xlabel(’Create size’)
* plt.ylabel(’Create time’)
* for i in range(4):
* plt.text(t_degree[9], t_record[i][9], t_lines[i])
* plt.plot(t_degree, t_record[i], label=t_lines[i])

* legend = plt.legend(loc=’upper center’, shadow=True, fontsize=’x-large’)
* plt.show()

## Dictionaries

**[Description on Python web site](https://docs.python.org/3.4/tutorial/datastructures.html#dictionaries) **

* Dictionaries are sometimes found in other languages as “**associative memories**” or “**associative arrays**”.
* Unlike sequences, which are indexed by a range of numbers, dictionaries are **indexed by keys**.
* sequences → indexed by numbers
* dictionaries → indexed by keys
* Keys can be any **immutable type**; strings and numbers can always be keys.

* Possible key type:

* string
* number

* You can’t use lists as keys, since lists can be modified in place using  index assignments, slice assignments, or methods like append() and  extend().

* An unordered set of **key: value** pairs.

* Example code:

* >>> tel = {’jack’: 4098, ’sape’: 4139}
* >>> tel[’jack’]
* ...   4098

**How does python implement dictionary**

<undefined>* [Python Web site](https://docs.python.org/3.4/faq/design.html#how-are-dictionaries-implemented) </undefined>

* Dictionaries are implemented as resizable hash tables.

| hash | key | value |
| 0 | k0 | v0 |
| 1 | k1 | v1 |
| ... | ... | ... |

* Dictionaries work by computing a hash code for each key stored in the dictionary.
* The [hash()](https://docs.python.org/3.4/library/functions.html#hash) built-in function.
* The hash code varies widely depending on the key and a per-process seed; for example:
* “Python” could hash to -539294296
* “python”, could hash to 1142331976
* The hash code is then used to calculate a location in an internal array where the value will be stored.
* key → hash(key) → where value is stored → value

| hash | key | address | value |
| 0 | k0 | address of v0 | v0 |
| 1 | k1 | address of v1 | v1 |
| ... | ... | ... | ... |

* Assuming that you’re storing keys that all have different hash values, this means that dictionaries take constant time – **_O_(1)**.
* To retrieve a key
* Means that **no sorted order** of the keys is maintained.

<undefined>* **Stack Overflow**</undefined>

* [](http://stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented)[http://stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented](http://stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented)

<undefined>* **Laurent Luce’s Blog - Python dictionary implementation**</undefined>

* [](http://www.laurentluce.com/posts/python-dictionary-implementation/)[http://www.laurentluce.com/posts/python-dictionary-implementation/](http://www.laurentluce.com/posts/python-dictionary-implementation/)

**Because of being indexed by keys**

* Get item and set item operations on a dictionary are **_O_(1)**.
* Checking to see whether a key is in the dictionary or not is also **_O_(1)**.

* [Table 3: Big-O Efficiency of Python Dictionary Operations](http://interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/Dictionaries.html#tbl-dictbigo) 

| operation | Big-O Efficiency |
| copy | O(n) |
| get item | O(1) |
| set item | O(1) |
| delete item | O(1) |
| contains (in) | O(1) |
| iteration | O(n) |

**Lists v.s Dictionaries**

* Do the same things to compare the difference between lists and dictionaries

* import timeit
* import random

* print("i,\t\tlist,\t\tdict")
* for i in range(100,10001,200):
* t = timeit.Timer("random.randrange(%d) in x"%i,
* "from __main__ import random,x")
* x = list(range(i))
* lst_time = t.timeit(number=10) # Check the i is in list x or not
* x = {j:None for j in range(i)}
* d_time = t.timeit(number=10) # Check the i is in dictionary x or not
* print("%4d,\t%5.3f,\t%5.3f" % (i, lst_time, d_time))

* PS. The code above is modified from the example [Listing 6](http://interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/Dictionaries.html#lst-listvdict) 

* According to the example [Listing 6](http://interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/Dictionaries.html#lst-listvdict), the result could be this figure:


* [Figure 4: Comparing the in Operator for Python Lists and Dictionaries](http://interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/Dictionaries.html#fig-listvdict) 

* Summary:
* Dictionary is more efficiency than list, especially in the condition of large amount of elements.
* But memory ...

## 活動簽到

[Carl Su](https://tossug.hackpad.com/ep/profile/n5euV0AaWLn)

[FourDollars](https://tossug.hackpad.com/ep/profile/tgNQRpN8EgG)

[Jonathan Hsieh](https://tossug.hackpad.com/ep/profile/v2IkzygwDuI)

[Kevin](https://tossug.hackpad.com/ep/profile/t1WzUr1rPTe) [C](https://tossug.hackpad.com/ep/profile/t1WzUr1rPTe)[hen](https://tossug.hackpad.com/ep/profile/t1WzUr1rPTe)

[Manuel Stallman](https://tossug.hackpad.com/ep/profile/GgkcGJEol5r)

[Robert D. Wei](https://tossug.hackpad.com/ep/profile/u8S8v3LRs8U)

[StarNight](https://tossug.hackpad.com/ep/profile/sDJQZaRfOhF)

[Ted Wu](https://tossug.hackpad.com/ep/profile/xo5A62wXl3B)

[violetson](https://tossug.hackpad.com/ep/profile/oJusv72f72w)

[Wen00072](https://tossug.hackpad.com/ep/profile/H12yKD7rYmT)

莊智凱