iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 9
1

今天我們來看各家有什麼樣的資料結構來存放 Key-value pair 囉!而這樣的結構又是一對一的映射關係,也就是一個 Key 只會對到一個 Value。而我們要挑戰的題目也很簡單,先輸入一個數字告訴程式,接下來會有幾個名字 => 電話號碼的組合要輸入,都輸入完之後就開始輸入名字來找到剛才的電話號碼。如果打了一個沒有在裏頭的名字,就會顯示 Not found 並且結束程式。那就開始吧!


Python 3

n = int(input())
d = dict()

for _ in range(0, n):
  name, number = input().split()
  d[name] = number
  
while True:
  name = input()
  if name in d:
    print("{}={}".format(name, d[name]))
  else:
    print("Not found")
    break
  • 首先從 input() 接收 User input 後,並轉換成 int 存到 n ,這表示我們接下來要接收 n對 Key-value pair。 d = dict(),表示我們在這邊宣告 d是一個 Dictionary,就是 Python 內用來存放 K-V pair 的結構啦!(接下來會慢慢解釋)。接著我們透過 iterate range(0, n) ,這是 Python 常見的做法,因為 Python 沒有 C-style for-loop 所以 for _ in range(0, n) 表示我們接下來要做 n 次 code block 內的事情, _ 表示我們不 care range(0, n) 每次回傳什麼。 input().split() 是接收輸入並且以空白當作 separator 來把一個字串變成 list of string,例如 'abc def'.split() 會變成 ['abc', 'def'] ,而我們期望 User 輸入的就是 <name> <number> (以空格隔開)。而這個得到的 list 因為有兩個 elements,分別賦予給 namenumberd[name] = number 就是說把 key 是 name 而 value 是 number 的 pair 存進這個 Dictionary。如果今天要取出來也是直接 d[name] 就可以得到 number 了,如果給了一個沒有在這個 Dictionary 的 Key 會怎樣呢?答案是會噴錯。 為了避免,可以使用 <dictionary>.get(<key>, <default>) ,此時如果 <key> 不在的話會回 None 或是 <default> 如果有定義的話。
  • 最後我們來看 while ,這是一個無限迴圈,每次從 User input 接收一個要查詢的名字存到 namename in d 可以讓我們知道 name 有沒有在 d 這個 dictionary 裏頭,有的話就返回 true,反之為 false。然後就是印出來啦!如果名字不在裏頭,就 break 結束迴圈。
  • Dictionary 和 List 很像,長度可變,值可變,兩個都接受巢狀結構。比較大的差異是一個用 index 一個則是用 Key 來存取元素。而 Dictionary 可說是相當自由,不管是 Key 還是 Value 都可以是任意的 Type,也就是說你的 Key 可以又是整數,又是浮點數或布林。想了解更多關於 Dictionary 可以參考這裡囉!
  • 至於 Python 的 Dictionary 不意外地就是由 Hash table 來實作,Hash table 基本上在存取的時間上是 O(1),不過當數量一多的時候可能就不是囉!(提示:實作上會有機會使用到 linked list),想知道更多關於 Hash table 的可以參考這裡囉!

Scala

import scala.io.StdIn

object Solution {

    def main(args: Array[String]) {
        val num = StdIn.readLine().toInt

        def addNewKV(m :Map[String, String], remainNum: Int): Map[String, String] = {
            if (remainNum == 0) m
            else {
                val keyAndValue = StdIn.readLine().split(" ")
                addNewKV(m + (keyAndValue(0) -> keyAndValue(1)), remainNum - 1)
            }
        }

        def searchMap(mapToBeSearched: Map[String, String]): Unit = {
            val nameToSearch = StdIn.readLine()
            mapToBeSearched.get(nameToSearch) match {
                case Some(v) => {
                    println(s"$nameToSearch=$v")
                    searchMap(mapToBeSearched)
                }
                case None => System.exit(0)
            }
        }

        val resultedMap = addNewKV(Map(), num)
        searchMap(resultedMap)
    }
}
  • 在 Scala 我們依舊盡量以 Functional 的方式來撰寫,所以所有的變數都是 Immutable 的唷!在 Scala 類似 Python 的 Dictionary 是 Map,但是 Scala 的 Map 不管是 Key 還是 Value 的 Type 都是一開始就要決定的。你可能會說如果我們要增加 K-V 到 Map 那不就是要 mutable 嗎?不過這邊我們會發現,每次加了新的 K-V 之後都會是一個新的 Map 唷!所以依舊維持所有變數都是 Immutable。
  • 首先我們先將 User input 讀進來並且轉成 Int 存到 num ,接下來我們有一個 Function 叫做 addNewKV ,是個遞迴函數,而且是 Tail recursion,第一個參數是目前的 Map (Key 跟 Value 的 Type 都是 String ( Map[String, String])),而第二個參數 remainNum是現在還要接收幾次 User 的輸入。終止條件是發現 remainNum0 的時候就回傳目前的 Map m 。如果 remainNum 不是 0 就先讀入 User input 並且透過 split(" ") ,來把一個 string 用 " " (也就是空白),來切成 Array of string。再來就是把這個 Array of string 中的 Key ( keyAndValue(0)), value (keyAndValue(1)) 取出後跟 m 相加,也就是會得到一個新的 Map,包含本來的 m 以及剛取出的 K-V。接著把這個新的 Map,和 remainNum-1 當作參數再次執行 addNewKV 。最終這個遞迴函數結束就會得到最終的 Map 囉!
  • 至於 searchMap 這個遞迴函數做的事情很簡單,就只是把剛才得到的 Map 用 User Input 的 Key (存到 nameToSearch)去找看看有沒有在 Map 裏頭。這裡我們找的方式是用 mapToBeSearched.get(nameToSearch) ,這裡會得到 Option type (之前 Rust 有介紹類似概念),再來我們用 Pattern matching 的方式。要是 Key 有存在就回傳Some(value) ,然後我們就把 value 取出來並印出,再繼續執行 searchMap 。直到當我們輸入的 Key 不在 mapToBeSearched 內而得到 None 後,就退出程式囉!
  • 而 Scala 的 Map 有很多種,除了我們這邊用的,當然還有 mutable 版本的 Map,SortedMap (會把 Key 排序),LinkedHashMap (可以記得 insert 順序) 等等。有興趣的可以參考這裡囉!

Golang

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)

	phonebook := make(map[string]string)
	scanner.Scan()
	num, _ := strconv.Atoi(scanner.Text())

	for i := 0; i < num; i++ {
		scanner.Scan()
		record := strings.Split(scanner.Text(), " ")
		phonebook[record[0]] = record[1]
	}

	for scanner.Scan() {
		name := scanner.Text()
		if v, ok := phonebook[name]; ok {
			fmt.Printf("%v=%v\n", name, v)
		} else {
			fmt.Println("Not found")
		}
	}
}
  • 我們看到在 Golang 的世界,類似 Python Dictionary 的是 Map,而其底層也是運用 Hash table 來實作。這邊看到 make(map[string]string) 是在 Golang 去 new 出一個空的 Map (Key 是 string , value 是 string )。Scanner 的用法以前已經講過,這邊就不再贅述。User input 的值被讀進來之後存到 num 。接下來進到建置電話號碼的 Loop,把 User input 讀取進來後透過 strings.Split(scanner.Text, " ") 將字串以空白切開後存成 Array record 。接著就是 phonebook[record[0]] = record[1] 的方式來把 K-V 加到 Map phonebook 裏頭。最後的 For loop 是個無限迴圈,每次也都一樣先從 User input 讀取 ( scanner.Scan()) 並且存到 name ,接著 phonebook[name] 會去把 name 這個 Key 的值取出來。因為這裡 Golang 的 Error handling 不是用 Exception 的方式,而是透過回傳第二個參數來告訴你是不是有這個 Key,也就是這裡 ok 的值,他會是 TrueFalse,所以如果 oktrue 就印出來不然就說 Not found 囉!
  • 這裡除了用 make 也可以用 map[string]string{} 的方式來取得一個空的 Map。假使我們想要走訪一個 Map 內所有的 K-V pair 可以用下面的方式去走訪 Map m
for key, value := range m {
  fmt.Println("Key:", key, "Value:", value)
}

Rust

use std::collections::HashMap;
use std::str::FromStr;
use std::io::stdin;

fn main() {
  
    let mut input = String::new();
    stdin().read_line(&mut input).expect("Failed to read input");

    let n = i32::from_str(input.trim()).expect("Failed to parse i32 from string");
    
    let mut phone_book: HashMap<String, String> = HashMap::new();
    
    for _ in 0..n {
        let (name, number) = read_entry();
        phone_book.insert(name, number);
    }
    
    while let Some(query) = read_query() {
        match phone_book.get(&query) {
            Some(number) => println!("{}={}", query, number),
            None => println!("Not found")
        }
    }
}

type Entry = (String, String);

fn read_entry() -> Entry {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input).expect("Failed to read input.");
    
    let components: Vec<&str> = input.trim().split(' ').collect();
    (components[0].to_string(), components[1].to_string())
}

fn read_query() -> Option<String> {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input).expect("Failed to read input.");
    if input.len() <= 0 {
        None
    } else {
        Some(input.trim().to_string())
    }
}
  • 在 Rust 我們比較常用的 Map 是 HashMap。要使用 HashMap 我們必須要先 use std::collections::HashMap; 來做 local name binding。如果我們可以用先知道 Capacity 就可以用 HashMap::with_capacity(uint) 來創建,或者用 HashMap::new() 。而我們將 User input 讀入後存到 input ,但因為 input 是 String,所以要轉成數字。這裡用 i32::from_str() 來作轉換,記得要 use std::str::FromStr; ,為什麼呢?這裡要深究 Rust 中關於 Trait 的部分 ( FromStr 是一個 Trait),詳情可以先參考 Rust 關於 Trait 的部分,這邊就暫時先忽略。再來我們看到 phone_bookHashMap<String, String> Type,並且是用 HashMap::new() 來初始化。
  • 再來我們進到讀取 User 輸入的名字跟號碼。這裡先看 read_entry 這個 Function,其回傳的 Type 是 Entry ,這是什麼呢?這是一個 alias type,實際上是上面定義的 (String, String) 這個 Tuple。而在這個 Function 一樣先把輸入存到 input ,再透過 input.trim().split(' ').collect() 得到一個 Vector of &str 。這邊因為 input.trim().split(' ') 得到的是一個 Iterator,所以要在 invoke collect() 才得到 Vector。而 &str 可以想成是一個不可變的 string。最後這個 Function 就回傳一個 Tuple,也就是我們所定義的 Alias Type Entry 。每次得到一個 Entry ,我們就把他分別存到 namenumber 並且透過 HashMap 的 insert Method 來把 Key ( name) 和 Value ( number) 存到 HashMap phone_book
  • 最後就是一個 while ,每次先 Call read_query()read_query 做的事情很簡單,就是把要查詢的名字讀進來,如果 OK 就回傳 Some(<name>) 否則就是 None 。不過這裡有沒有發現多了一個 let ,這是 Rust 的 while let ,也就是當 read_query() 回傳是 None 時, Some(query) = read_query() 會是 False,於是就跳出 while 了,這是為了簡化我們本來應該要在 while 裡面去 match Option,如果是 None就跳出 while 這件事,可以參考這裡。而在這裡我們一並也把 Some(query) 中的 query 給取出來了。再來就是 match phone_book.get(&query) ,這裡給 &query 是 borrowing type (所有權問題),而 phone_book.get(&query) 會得到 Option,所以這邊當 OptionSome(number) ,就表示有這個 Key,並把 K-V 印出來。但如果是 None 就是 Not found 啦!

結語

今天講的是 Map,大家的實作都差不多,但當然還是有一些不一樣的地方,包含細節的 Hash function 和解決 Collision 的方式,大家可以再深入研究。另外今天也對 Rust 又有更多了解了,哈哈哈!明天見!


上一篇
[Day 7] 一個蘿蔔一個坑
下一篇
[Day 9] 自己和自己的對話
系列文
30 天把自己榨好榨滿的四週四語言大挑戰!30

尚未有邦友留言

立即登入留言