如何從緩存任意結果的結構中刪除過多的「克隆」調用？

Question

我正在讀Rust書第二版中的the section on closures。在本節的最後，有一個練習來擴展前面給出的Cacher實現。我試了一下：

use std::cmp::Eq; 
use std::hash::Hash; 
use std::clone::Clone; 

struct Cacher<T, K, V> 
where 
    T: Fn(K) -> V, 
    K: Eq + Hash + Clone, 
    V: Clone, 
{ 
    calculation: T, 
    values: HashMap<K, V>, 
} 

impl<T, K, V> Cacher<T, K, V> 
where 
    T: Fn(K) -> V, 
    K: Eq + Hash + Clone, 
    V: Clone, 
{ 
    fn new(calculation: T) -> Cacher<T, K, V> { 
     Cacher { 
      calculation, 
      values: HashMap::new(), 
     } 
    } 

    fn value(&mut self, arg: K) -> V { 
     match self.values.clone().get(&arg) { 
      Some(v) => v.clone(), 
      None => { 
       self.values 
        .insert(arg.clone(), (self.calculation)(arg.clone())); 
       self.values.get(&arg).unwrap().clone() 
      } 
     } 
    } 
} 

在創建了一個終於有效的版本之後，我真的很不滿意它。真正讓我感到困擾的是cacher.value(...)有5（！）個電話給clone()。有沒有辦法避免這種情況？

Answer 1

您的懷疑是正確的，該代碼包含過多的致電clone()，擊敗Cacher旨在實現的非常優化。

從頭開始的是致電self.values.clone() - 它在每個單獨的訪問上創建整個高速緩存的副本。但是，正如你可能發現自己，只是刪除.clone()不會編譯。這是因爲借方檢查員認爲整個持續時間爲match的地圖。由HashMap::get返回的共享引用指向地圖內的項目，這意味着雖然它存在，但禁止爲同一地圖創建另一個可變引用，這是HashMap::insert所要求的。對於代碼編譯，你需要分割的比賽，以迫使共用的參考走出去的範圍insert之前被調用：

// avoids unnecessary clone of the whole map 
fn value(&mut self, arg: K) -> V { 
    if let Some(v) = self.values.get(&arg).map(V::clone) { 
     return v; 
    } else { 
     let v = (self.calculation)(arg.clone()); 
     self.values.insert(arg, v.clone()); 
     v 
    } 
} 

這是好多了，可能是「足夠好」的最實際目的。已經緩存了該值的熱路徑現在僅由一個克隆組成，而實際上該路徑是必需的，因爲原始值必須保留在哈希映射中。 （另請注意，克隆並不需要是昂貴的或暗示深度複製 - 所存儲的值可以是一個Rc<RealValue>，其購買對象共享免在這種情況下，clone()簡單地增加在對象上的引用計數。）

在高速緩存未命中的情況下，密鑰必須被克隆，因爲calculation聲明來使用它。不過，單個克隆就足夠了，因此我們可以將原始arg傳遞給insert，而無需再次克隆。然而，密鑰克隆仍然感覺不必要 - 計算功能不應該要求它正在轉換的密鑰的所有權。刪除此克隆歸結爲修改計算函數的簽名以通過引用來獲取密鑰。改變T性狀邊界來T: Fn(&K) -> V允許value()以下配方：

// avoids unnecessary clone of the key 
fn value(&mut self, arg: K) -> V { 
    if let Some(v) = self.values.get(&arg).map(V::clone) { 
     return v; 
    } else { 
     let v = (self.calculation)(&arg); 
     self.values.insert(arg, v.clone()); 
     v 
    } 
} 

現在只剩下整整兩個調用clone()，一個在每個代碼路徑。就價值克隆而言，這是最佳的。但細心的讀者仍然會通過一個詳細的嘮叨着：在HashMap::insert一次調用HashMap::get，然後一次：在高速緩存未命中的情況下，哈希表查找將有效地發生爲相同的鍵兩次。如果我們可以重複使用第一次完成的工作並僅執行一次哈希映射查找，那將會很好。這可以通過用entry()替換get()和insert()來實現：

// avoids the second lookup on cache miss 
fn value(&mut self, arg: K) -> V { 
    match self.values.entry(arg) { 
     Entry::Occupied(entry) => entry.get().clone(), 
     Entry::Vacant(entry) => { 
      let v = (self.calculation)(entry.key()); 
      entry.insert(v.clone()); 
      v 
     } 
    } 
} 

可運行例如in the playground。

Answer 2

我解決同樣的練習，並與下面的代碼結束：

use std::thread; 
use std::time::Duration; 
use std::collections::HashMap; 
use std::hash::Hash; 
use std::fmt::Display; 

struct Cacher<P, R, T> 
where 
    T: Fn(&P) -> R, 
    P: Eq + Hash + Clone, 
{ 
    calculation: T, 
    values: HashMap<P, R>, 
} 

impl<P, R, T> Cacher<P, R, T> 
where 
    T: Fn(&P) -> R, 
    P: Eq + Hash + Clone, 
{ 
    fn new(calculation: T) -> Cacher<P, R, T> { 
     Cacher { 
      calculation, 
      values: HashMap::new(), 
     } 
    } 

    fn value<'a>(&'a mut self, key: P) -> &'a R { 
     let calculation = &self.calculation; 
     let key_copy = key.clone(); 
     self.values 
      .entry(key_copy) 
      .or_insert_with(|| (calculation)(&key)) 
    } 
} 

它不僅使在value()方法的關鍵的一個副本。它不會複製結果值，而是返回帶有生命週期說明符的引用，該參數等於封裝的Cacher實例的生命週期（這是邏輯的，我認爲，因爲映射中的值將繼續存在，直到Cacher本身被丟棄）。

這是一個測試程序：

fn main() { 
    let mut cacher1 = Cacher::new(|num: &u32| -> u32 { 
     println!("calculating slowly..."); 
     thread::sleep(Duration::from_secs(2)); 
     *num 
    }); 

    calculate_and_print(10, &mut cacher1); 
    calculate_and_print(20, &mut cacher1); 
    calculate_and_print(10, &mut cacher1); 

    let mut cacher2 = Cacher::new(|str: &&str| -> usize { 
     println!("calculating slowly..."); 
     thread::sleep(Duration::from_secs(2)); 
     str.len() 
    }); 

    calculate_and_print("abc", &mut cacher2); 
    calculate_and_print("defghi", &mut cacher2); 
    calculate_and_print("abc", &mut cacher2); 
} 

fn calculate_and_print<P, R, T>(intensity: P, cacher: &mut Cacher<P, R, T>) 
where 
    T: Fn(&P) -> R, 
    P: Eq + Hash + Clone, 
    R: Display, 
{ 
    println!("{}", cacher.value(intensity)); 
} 

，其輸出：

calculating slowly... 
10 
calculating slowly... 
20 
10 
calculating slowly... 
3 
calculating slowly... 
6 
3 

Answer 3

如果去掉返回值的要求，就不需要通過利用來執行任何克隆的Entry：

use std::thread; 
use std::time::Duration; 
use std::collections::HashMap; 
use std::collections::hash_map::Entry; 
use std::hash::Hash; 
use std::fmt::Display; 

struct Cacher<P, R, T> 
where 
    T: Fn(&P) -> R, 
    P: Eq + Hash, 
{ 
    calculation: T, 
    values: HashMap<P, R>, 
} 

impl<P, R, T> Cacher<P, R, T> 
where 
    T: Fn(&P) -> R, 
    P: Eq + Hash, 
{ 
    fn new(calculation: T) -> Cacher<P, R, T> { 
     Cacher { 
      calculation, 
      values: HashMap::new(), 
     } 
    } 

    fn value<'a>(&'a mut self, key: P) -> &'a R { 
     let calculation = &self.calculation; 

     match self.values.entry(key) { 
      Entry::Occupied(e) => e.into_mut(), 
      Entry::Vacant(e) => { 
       let result = (calculation)(e.key()); 
       e.insert(result) 
      } 
     } 
    } 
} 

fn main() { 
    let mut cacher1 = Cacher::new(|num: &u32| -> u32 { 
     println!("calculating slowly..."); 
     thread::sleep(Duration::from_secs(1)); 
     *num 
    }); 

    calculate_and_print(10, &mut cacher1); 
    calculate_and_print(20, &mut cacher1); 
    calculate_and_print(10, &mut cacher1); 

    let mut cacher2 = Cacher::new(|str: &&str| -> usize { 
     println!("calculating slowly..."); 
     thread::sleep(Duration::from_secs(2)); 
     str.len() 
    }); 

    calculate_and_print("abc", &mut cacher2); 
    calculate_and_print("defghi", &mut cacher2); 
    calculate_and_print("abc", &mut cacher2); 
} 

fn calculate_and_print<P, R, T>(intensity: P, cacher: &mut Cacher<P, R, T>) 
where 
    T: Fn(&P) -> R, 
    P: Eq + Hash, 
    R: Display, 
{ 
    println!("{}", cacher.value(intensity)); 
} 

你可以然後選擇以進行克隆另一個結構來包裝這個：

struct ValueCacher<P, R, T> 
where 
    T: Fn(&P) -> R, 
    P: Eq + Hash, 
    R: Clone, 
{ 
    cacher: Cacher<P, R, T>, 
} 

impl<P, R, T> ValueCacher<P, R, T> 
where 
    T: Fn(&P) -> R, 
    P: Eq + Hash, 
    R: Clone, 
{ 
    fn new(calculation: T) -> Self { 
     Self { 
      cacher: Cacher::new(calculation), 
     } 
    } 

    fn value(&mut self, key: P) -> R { 
     self.cacher.value(key).clone() 
    } 
}