使用HashMap實現類似SQL的RIGHT OUTER JOIN的迭代器適配器

我試圖用類似SQL的連接迭代器擴展bluss的rust-itertools。我使用散列連接策略遇到了RIGHT OUTER JOIN的特定問題（策略本身實際上非常簡單）。使用HashMap實現類似SQL的RIGHT OUTER JOIN的迭代器適配器

迭代器適配器結構需要2個輸入迭代器，其中第二個（右側）被加載到HashMap中。迭代的工作原理如下：

從左側迭代器的項目是對地圖匹配 - 在匹配的情況下，返回這兩個項目
當左迭代器耗盡時，從返回非匹配的值地圖

問題是，我試圖在地圖的價值迭代器存儲與地圖存儲它的迭代狀態沿着第二部分。但正如我在answer中所瞭解的那樣，生鏽是不可能的。不幸的是，我不知道如何做到這一點。

下面是完整的代碼，INNER JOIN適配器，它做的第一部分：

use std::collections::HashMap; 
use std::hash::Hash; 

pub struct HashJoinInner<I, K, V0, V1> where 
    I: Iterator<Item=(K, V0)>, 
    K: Hash + Eq, 
    V1: Clone, 
{ 
    left: I, 
    right: HashMap<K, V1>, 
} 

impl<I, K, V0, V1> HashJoinInner<I, K, V0, V1> where 
    I: Iterator<Item=(K, V0)>, 
    K: Hash + Eq, 
    V1: Clone, 
{ 
    /// Create a `HashJoinInner` iterator. 
    pub fn new<J>(l: I, r: J) -> Self 
     where J: Iterator<Item=(K, V1)> 
    { 
     let mut hm: HashMap<K, V1> = HashMap::new(); 
     for (k, v) in r { 
      hm.insert(k, v); 
     } 
     HashJoinInner { 
      left: l, 
      right: hm, 
     } 
    } 
} 

impl<I, K, V0, V1> Iterator for HashJoinInner<I, K, V0, V1> where 
    I: Iterator<Item=(K, V0)>, 
    K: Hash + Eq, 
    V1: Clone, 
{ 
    type Item = (V0, V1); 

    fn next(&mut self) -> Option<Self::Item> { 
     loop { 
      match self.left.next() { 
       Some((k0, v0)) => match self.right.get(&k0) { 
        Some(v1) => return Some((v0, Clone::clone(v1))), 
        None => continue, 
       }, 
       None => return None, 
      } 
     } 
    } 
}

我將是任何想法感謝。

來源

2015-08-14 milancio

我很抱歉，這些是我在堆棧溢出的第一步，我沒有意識到我可以添加一個答案，我自己的問題。再次感謝您的幫助 - 您的想法幫助我找到解決方案（下面發佈）。 – milancio

您不能存儲Values迭代器，因爲它包含對HashMap的引用。如果您移動地圖，這些引用可能會失效。但是，您可以使用into_iter方法消耗HashMap。它擁有HashMap的所有值，並可以移動到新的結構中。

下面是您的代碼從早期的問題調整。這還不是左連接或右連接。從一個迭代器完成切換到另一個迭代器的切換是複雜的。

use std::collections::hash_map::{HashMap, IntoIter}; 
use std::hash::Hash; 

struct Foo<K, V> 
    where K: Hash + Eq, 
      V: Clone, 
{ 
    iter: IntoIter<K, (V, bool)>, 
} 

impl<K, V> Foo<K, V> 
    where K: Hash + Eq, 
      V: Clone, 
{ 
    fn new<I>(it: I) -> Self 
     where I: Iterator<Item=(K, V)> 
    { 
     let mut map = HashMap::new(); 
     for (k, v) in it { 
      map.insert(k, (v, false)); 
     } 
     Foo { iter: map.into_iter() } 
    } 
} 

impl<K, V> Iterator for Foo<K, V> 
    where K: Hash + Eq, 
      V: Clone, 
{ 
    type Item = V; 
    fn next(&mut self) -> Option<Self::Item> { 
     loop { 
      match self.iter.next() { 
       Some((_, (v, false))) => return Some(v.clone()), 
       Some(_) => continue, 
       None => return None, 
      } 
     } 
    } 
} 

fn main() { 
    let it = (0..).zip("AB".chars()); 
    let foo = Foo::new(it); 
    for v in foo { 
     println!("{}", v); 
    } 
}

但是你不需要做任何的是得到你想要的東西。您可以簡單地創建一個hashmap，並在迭代另一個項目時檢查它。我意外地創建了一個左外連接，但只是將參數翻轉來獲得正確的外連接。^_^

use std::collections::hash_map::HashMap; 
use std::hash::Hash; 

struct LeftOuterJoin<L, K, RV> { 
    left: L, 
    right: HashMap<K, RV>, 
} 

impl<L, K, RV> LeftOuterJoin<L, K, RV> 
    where K: Hash + Eq 
{ 
    fn new<LI, RI>(left: LI, right: RI) -> Self 
     where L: Iterator<Item=LI::Item>, 
       LI: IntoIterator<IntoIter=L>, 
       RI: IntoIterator<Item=(K, RV)> 
    { 
     LeftOuterJoin { 
      left: left.into_iter(), 
      right: right.into_iter().collect() 
     } 
    } 
} 

impl<L, K, LV, RV> Iterator for LeftOuterJoin<L, K, RV> 
    where L: Iterator<Item=(K, LV)>, 
      K: Hash + Eq, 
      RV: Clone 
{ 
    type Item = (K, LV, Option<RV>); 

    fn next(&mut self) -> Option<Self::Item> { 
     match self.left.next() { 
      Some((k, lv)) => { 
       let rv = self.right.get(&k); 
       Some((k, lv, rv.cloned())) 
      }, 
      None => None, 
     } 
    } 
} 

fn main() { 
    let mut left = HashMap::new(); 
    left.insert(1, "Alice"); 
    left.insert(2, "Bob"); 

    let mut right = HashMap::new(); 
    right.insert(1, "Programmer"); 

    for (id, name, job) in LeftOuterJoin::new(left.into_iter(), right) { 
     println!("{} ({}) is a {:?}", name, id, job); 
    } 
}

來源

2015-08-14 14:06:56 Shepmaster

有趣的是，它可能正在工作。剩下的唯一問題是，當我在開始使用地圖時，我將無法測試左側迭代器鍵是否存在於地圖中。但是，使用Option <>對代碼進行一些重構可能會起作用。我會盡力與它一起玩，我會更新問題，以防它的工作。非常感謝您的時間 – milancio

@milancio我已經更新了一個可用的左外連接 – Shepmaster

不幸的是，哈希連接策略不對稱，因此翻轉輸入將無法完成。不保證左邊的迭代器在RAM中是可收集的，只有正確的。這就是它如此高效的原因，因爲左邊的可以是任意大的，並且不需要分類。如果您有興趣，我已經完成[合併加入]（https://github.com/milancio42/rust-itertools/blob/merge-join/src/merge_join.rs）加入;） – milancio

由於使用std::collections::hash_map::IntoIter我已經設法解決這個問題的Shepmaster的想法。

這裏是右外的完整解決方案JOIN使用散列連接策略：

use std::collections::hash_map::{HashMap, IntoIter,}; 
use std::mem; 
use std::hash::Hash; 

#[must_use = "iterator adaptors are lazy and do nothing unless consumed"] 
pub struct HashJoinRightOuter<L, K, RV> { 
    left: L, 
    map: HashMap<K, (RV, bool)>, 
    /// exclusion iterator - yields the unmatched values from the map. It is created once the left 
    /// iterator is exhausted 
    excl_iter: Option<IntoIter<K, (RV, bool)>>, 
} 

impl<L, K, RV> HashJoinRightOuter<L, K, RV> 
    where K: Hash + Eq, 
{ 
    /// Create a `HashJoinRightOuter` iterator. 
    pub fn new<LI, RI>(left: LI, right: RI) -> Self 
     where L: Iterator<Item=LI::Item>, 
       LI: IntoIterator<IntoIter=L>, 
       RI: IntoIterator<Item=(K, RV)> 
    { 
     let mut map: HashMap<K, (RV, bool)> = HashMap::new(); 
     for (k, v) in right.into_iter() { 
      map.insert(k, (v, false)); 
     } 
     HashJoinRightOuter { 
      left: left.into_iter(), 
      map: map, 
      excl_iter: None, 
     } 
    } 

    /// Moves the map to `self.excl_iter` 
    /// 
    /// Once the left iterator is exhausted, the info about which keys were matched is complete. 
    /// To be able to iterate over map's values we need to move it into its `IntoIter`. 
    fn set_excl_iter(&mut self) { 
     let map = mem::replace(&mut self.map, HashMap::<K, (RV, bool)>::new()); 
     self.excl_iter = Some(map.into_iter()); 
    } 
} 

impl<L, K, LV, RV> Iterator for HashJoinRightOuter<L, K, RV> 
    where L: Iterator<Item=(K, LV)>, 
      K: Hash + Eq, 
      RV: Clone, 
{ 
    type Item = (Option<LV>, RV); 

    fn next(&mut self) -> Option<Self::Item> { 
     loop { 
      match self.excl_iter { 
       // the left iterator is not yet exhausted 
       None => match self.left.next() { 
        Some((lk, lv)) => match self.map.get_mut(&lk) { 
         Some(rt) => { 
          rt.1 = true; // flag as matched 
          return Some((Some(lv), Clone::clone(&rt.0))) 
         }, 
         None => continue, // not interested in unmatched left value 
        }, 
        // the left iterator is exhausted so move the map into `self.excl_iter`. 
        None => self.set_excl_iter(), 
       }, 
       // iterate over unmatched values 
       Some(ref mut r) => match r.next() { 
        Some((_, (rv, matched))) => { 
         if !matched { 
          return Some((None, rv)); 
         } else { 
          continue; 
         } 
        }, 
        None => return None, 
       } 
      } 
     } 
    } 
} 

fn main() { 
    let a = (0..).zip("AB".chars()); 
    let b = (1..).zip("XY".chars()); 
    let mut it = HashJoinRightOuter::new(a, b); 
    assert_eq!(it.next(), Some((Some('B'), 'X'))); 
    assert_eq!(it.next(), Some((None, 'Y'))); 
    assert_eq!(it.next(), None); 
}

在我失敗了，因爲我試圖同時存儲數據的開始和它在同一個結構，它沒有引用無論如何。我想真的想要存儲的數據第一，做一些神奇的事情，一旦完成，將移動到另一個領域與其轉型工作。

這也可以用來解決其他自引用結構問題。

來源

2015-08-17 09:22:56 milancio

使用HashMap實現類似SQL的RIGHT OUTER JOIN的迭代器適配器

回答

相關問題