2. Counting

數水果的問題 The fruit-counting problem

寫程式是模仿你解決問題的邏輯，讓電腦幫你重複做，大量的做。因此，重要的是你解決問題的邏輯。數物件、數水果就是個很實用的演算法邏輯，教你怎麼計算一堆物品中，每個物件各有幾個。相關範例有：

• 全班有這麼多人，我想算算每個科系有多少人，好知道系所比例安排專題。

• 你被當好人跑腿，幫全班買飲料，結果一票人買了很多種飲料，只好一杯一杯畫正字。

• 計算某一篇文章裡面，每個字出現幾次（字頻）；依照010、1020依此類推計算學生的成績分布。

問題定義：考慮一個狀況，有一個跟一座山一樣多的水果，不知道有幾種水果，也不知道有幾顆，你必須要數出各種水果有幾顆，你會怎麼數？

其他程式語言會怎麼解決這個問題？若你今天在用Excel處理的話，會使用COUNTIF函式，作法如下Excel skills: How do I get the distinct/uniq。如果你是用R來處理的話，那就會是count(vec)。

步驟一：嘗試說明邏輯

以下這個例子將帶你從最基礎的語法，用Python最基礎的資料型態來「計數（counting）」。

1. 先想想若你在數水果實際上你是怎麼數？Ans. 一顆一顆數。

2. 那你怎麼記住哪一種水果有幾顆？Ans. 拿出一張紙，看到一種沒看過的水果，就新增一個「對應」，將水果名稱對應到0，然後在對應的欄位數值遞增一。若已經看過該水果，那就直接找到那個欄位遞增一即可。

步驟二：標準化邏輯

1. 先拿出一張紙做對應表，上面一行要寫水果名，下面一行為他所對 到的水果數量

2. 把水果排成一列準備一個一個數

3. 對在該列中的每顆水果

   • 如果我沒看過他

     • 就在對應表記下該水果，登記該水果為1顆。

   • 若我有看過他

     • 就把對應表上的那個水果所對應到的格子下面的數字加1。

步驟三：英文來描述之

1. build a look-up table to record each fruit and number of the fruit(calls it dictionary), naming as fruit_count

2. keep all fruits in a list named fruit_list

3. for each fruit in fruit_list:

   • If the fruit does not appear in fruit_count

     • Create a mapping in fruit_count to map the fruit name to 1

   • else

     • increase the mapped value of the fruit name in fruit_count

用Python來寫寫看

要寫程式前要先認識一個符號「=」（Assignment），語法為「 variable = value」透過Assignment可以把右方的數值或運算的結果assign給左方的變數。通常左方都是一個變數，Python比較特別的是，他左方可以是多個變數，只要是右方所要Assign的數值數量和左方的變數數量相同即可。關於Assignment可觀看Py01. Basic的Assignment一節。

• Assigning an empty dictionary to a vriable fruit_count = {}

• Assigning a list with several terms to a variable fruit_list = ['a', 'b', 'c', 'a', 'd', 'a', 'w', 'b']

• var[] Brackes are used to access a list or a dictionry fruit_list[1] fruit_count["a"]

• a = a + 1 is a typical incrementer 遞增運算 fruit_count[fruit] = fruit_count[fruit] + 1

• list is ordered fruit_list[2]

• dictionary is unordered fruit_count["b"]

# Create an empty dictionry to store the key to value pairs
fruit_count = {} # dictionary, key to value pairs

# Create a list to store all things to count
fruit_list = ['apple', 'apple', 'banana', 'apple', 'banana', 'grape', 'banana', 'apple'] # A list of fruit

# For each fruit in the list...
for fruit in fruit_list:
    if fruit not in fruit_count:
        fruit_count[fruit] = 1
    else:
        fruit_count[fruit] += 1  

print(fruit_count)
fruit_count

{'apple': 4, 'banana': 3, 'grape': 1}

Print all pairs

# Print the dictionary
print(fruit_count)

# Print all keys
print(fruit_count.keys())

# Print all values mapped by keys
print(fruit_count.values())

# Print all key-to-value pairs
print(fruit_count.items())

{'apple': 4, 'banana': 3, 'grape': 1} dict_keys(['apple', 'banana', 'grape']) dict_values([4, 3, 1]) dict_items([('apple', 4), ('banana', 3), ('grape', 1)])

for key in fruit_count:
    print(key, fruit_count[key])

apple 4 banana 3 grape 1

V1. Using list.count(key) to count the frequency of something

fruit_count = {} # dictionary, key to value pairs

fruit_list = ['apple', 'apple', 'banana', 'apple', 'banana', 'grape', 'banana', 'apple'] # A list of fruit

for fruit in fruit_list:
    if fruit not in fruit_count:
        fruit_count[fruit] = fruit_list.count(fruit)
print(fruit_count)
fruit_count

V2. Using dict.get()

fruit_count = {} 
fruit_list = ['apple', 'apple', 'banana', 'apple', 'banana', 'grape', 'banana', 'apple'] # A list of fruit

for fruit in fruit_list:
    fruit_count[fruit] = fruit_count.get(fruit, 0) + 1
print(fruit_count)
fruit_count

V3. Using set(fruit_list) to guarantee value unique

fruit_count = {}
for k in set(fruit_list):
    fruit_count[k] = fruit_list.count(k)
fruit_count

V4. by comprehensive dictionary

fruit_count = {k:fruit_list.count(k) for k in set(fruit_list)}
fruit_count

V5. by Counter()

from collections import Counter
fruit_list = ['apple', 'apple', 'banana', 'apple', 'banana', 'grape', 'banana', 'apple'] # A list of fruit
fruit_count = Counter(fruit_list)
fruit_count

案例：計算班級中各系人數

這個例子和數水果幾乎一模一樣，只是把水果種類換成每個學生的科系而已。

stu_dict = {}
stu_list = ["soc", "soc", "econ", "bio", "psy", "psy", "econ", "poli", "econ"]

for student in stu_list:
    stu_dict[student] = 0
for student in stu_list:
    stu_dict[student] += 1
print(stu_dict)

案例：計算Wikipedia文章詞頻

「計數」其實是很多程式會應用到的演算邏輯。其他的演算邏輯單元還包含搜尋、排序等等，這些都是運算思維的一部分。在這個例子中，我打算要用計數邏輯來計算一篇Wikipedia文章的詞頻（Term frequency），亦即該篇文章中每個字出現幾遍，相當於把字詞當成上述範例中的水果。因此，一開始我需要把一篇文章斷開成單詞並存成如前面例子中的List。我會用Python的Wikipedia套件來取得某個Wikipedia頁面的摘要，這個套件為第三方套件，通常你的電腦都還沒安裝過這個套件，所以你需要在Terminal.app或cmd.exe中用 pip install wikipedia 安裝這個套件。

「計數」其實是很多程式會應用到的演算邏輯，其他的演算邏輯單元還包含搜尋、排序等等，這些都是運算思維的一部分。

1. Loading text

Read wikipedia summary

import wikipedia 
import string
string_a  = wikipedia.summary("Big_data", sentences = 10)
type(string_a)
string_a

output

2. Tokenization and text preprocessing

接下來，我會對文字做斷詞和基本的前處理

Tokenization and pre-processing

print(type(string.punctuation))
translator = str.maketrans('','',string.punctuation)
string_a = string_a.translate(translator)
string_a = string_a.lower()

words = string_a.split()
print(type(words))
print(words[:10])

output

3. Computing term frequency

Term frequency

word_freq = {}
for w in words:
    if w not in word_freq: # dictionary key-value initilization
        word_freq[w] = 0
    word_freq[w] += 1
print(word_freq)

output

Comprehension

（延伸學習）如何依據Dictionary value排序Dictionary：sorted(list_of_dict, key=itemgetter(dict_key), reverse=True)，但這屬於未在程式初始會被載入的套件，因此要載入from operator import itemgetter。

Sorted term frequency

from operator import itemgetter
for w, f in sorted(word_freq.items(), key=itemgetter(1), reverse = True)[:20] :
    if f > 1:
        print(w, '\t', f)

result

sorted by dict value II

4. Plotting term frequency

%matplotlib inline
import matplotlib.pyplot as plt
plt.hist(word_freq.values(), facecolor='green', alpha=0.5, bins=20)

案例：成績百分制轉等第制

最近台灣也開始用等第制來給分，一方面是為了符合國際的標準，另一原因據說是為了避免學生對成績太錙銖必較，雖然我自己的感覺是，學生對於為何從A+和A的差別更計較了，甚至會來追問，原始成績是多少，為何會變成A。不過，很多老師在給分還是採用百分制，學校在讓老師上傳成績的時候，就有個選項是可自動把百分制轉為等第制，這個範例是這件事的簡化版，我們只轉出A、B、C和F四種等第。

首先，先造一筆測試資料，分別是75個由35~99間的隨機整數，可重複取出。再來，初始化一個Dictionary來存放每個等第的個數（一開始均為0）。最後，使用if-elif-else條件判斷式來判斷每一筆成績落在哪個區間。

# Generating 75 random integers
import random
grades  =  [random.randint(35, 100) for i in range(0, 75)]

# Initializing level frequency
grade_dict = {'F':0, "C":0, "B":0, "A":0}

# Counting level frequency
for g in grades:
    if 100 >= g >= 80:
        grade_dict["A"] += 1
    elif 79 >= g >= 72:
        grade_dict["B"] += 1
    elif 71 >= g >= 60:
        grade_dict["C"] += 1
    else:
        grade_dict["F"] += 1
print(grade_dict)