---
# System prepended metadata

title: DS 讀書會 - 第 5 週
tags: [' tossug', hackpad-import]

---

---
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:

![](http://interactivepython.org/runestone/static/pythonds/_images/listvdict.png)

*   [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)

莊智凱
