应当如何快速统计两个HashSet的union/intersection的结果的元素个数？

Neutron3529 发表于 2020-06-21 13:31

这是刷面试题17.26遇到的问题。

相同的算法，python能过，Rust超时

（能忍吗……）

13 小时前	超出时间限制	N/A	N/A	Rust
13 小时前	通过	1692 ms	37 MB	Python3

在本地试了一下，是Rust的优化出了问题。

代码

#![feature(test)]

use std::time::Instant;
use std::collections::HashSet;

//#[cfg(codegen = "opt-level=2")]试过这么写，但是不行
fn compute_similarities(docs: Vec<Vec<i32>>) -> Vec<String> {
        let now = Instant::now();
        let mut ans:Vec<String>=Vec::with_capacity(64);
        let mut set:Vec<HashSet<_>>=Vec::with_capacity(docs.len());
        set.push(docs[0].iter().collect());
        for i in 1..docs.len(){
            set.push(docs[i].iter().collect());
            for j in 0..i{
                let n=set[i].intersection(&set[j]).fold(0,|s,_x|s+1) as f64;
                if n>0.5{
                    let t=set[i].union(&set[j]).fold(0,|s,_x|s+1) as f64;
                    ans.push(format!("{id1},{id2}: {similarity:.4}",id1=j,id2=i,similarity=n/t+1e-9));
                }
            }
        }
            println!("{}", now.elapsed().as_nanos() as f64/1e9);
        ans
    }
fn data()->Vec<Vec<i32>>{
vec![vec![...],...]//大概800KB的样子
}
extern crate test;
fn main(){
println!("Program Start!");
println!("{:?}",(compute_similarities(test::black_box(data()))).get(0..5));
}

不使用优化，编译超快，但需要20+秒才能执行完毕

打开rustc的优化，需要编译十多秒钟（因为data实在太大），然后~1秒出结果。

显而易见的，我们其实只需要对函数compute_similarities进行优化，然后就能得到~1s的执行速度

想问一下Rust里面有没有什么对单个函数打开优化指令的方法。

或者如何在debug模式下高效计算两个HashSet的交/并的元素个数

(如果并没有类似的办法，我只能用出疫情期间学到的新型检测方法，给人分组，然后检测组与组之间有没有公共元素，以此减少计算了……)

评论区

写评论

作者 Neutron3529 2020-06-29 03:22

试着优化了一下内存占用

现在小于200秒的程序，已经可以做到内存占用11MB了

.drain(..)是个好函数

--
👇
lagudomeze:

use std::collections::{hash_set::Iter, HashMap, HashSet};
use std::iter::FromIterator;

impl Solution {
    pub fn compute_similarities(docs: Vec<Vec<i32>>) -> Vec<String> {
        // 文档长度缓存
        let mut length_cache = HashMap::with_capacity(500);
        // 倒排索引 记录term -> ids的map
        let mut ii = HashMap::with_capacity(500);

        let mut ans = Vec::new();

        // 缓存文档交叉的交叉元素数目
        let mut im = HashMap::with_capacity(128);

        for (id, terms) in docs.iter().enumerate() {
            // 缓存文档长度
            length_cache.insert(id as i32, terms.len() as i32);

            im.clear();

            for term in terms {
                let ids: &mut HashSet<i32> = ii.entry(*term).or_default();
                // 缓存文档交叉的交叉元素数目
                for id in ids.iter() {
                    *im.entry(*id).or_insert(0i32) += 1i32;
                }
                ids.insert(id as i32);
            }

            for (j, intersec) in im.iter() {
                ans.push(format!(
                    "{},{}: {:.4}",
                    j,
                    id,
                    *intersec as f64 / (terms.len() as i32 + length_cache[&j] as i32 - intersec) as f64 + 1e-9
                ));
            }
        }
        ans
    }
}

用了类似倒排东西

执行用时：208 ms 内存消耗：20.1 MB

lagudomeze 2020-06-22 15:45

use std::collections::{hash_set::Iter, HashMap, HashSet};
use std::iter::FromIterator;

impl Solution {
    pub fn compute_similarities(docs: Vec<Vec<i32>>) -> Vec<String> {
        // 文档长度缓存
        let mut length_cache = HashMap::with_capacity(500);
        // 倒排索引 记录term -> ids的map
        let mut ii = HashMap::with_capacity(500);

        let mut ans = Vec::new();

        // 缓存文档交叉的交叉元素数目
        let mut im = HashMap::with_capacity(128);

        for (id, terms) in docs.iter().enumerate() {
            // 缓存文档长度
            length_cache.insert(id as i32, terms.len() as i32);

            im.clear();

            for term in terms {
                let ids: &mut HashSet<i32> = ii.entry(*term).or_default();
                // 缓存文档交叉的交叉元素数目
                for id in ids.iter() {
                    *im.entry(*id).or_insert(0i32) += 1i32;
                }
                ids.insert(id as i32);
            }

            for (j, intersec) in im.iter() {
                ans.push(format!(
                    "{},{}: {:.4}",
                    j,
                    id,
                    *intersec as f64 / (terms.len() as i32 + length_cache[&j] as i32 - intersec) as f64 + 1e-9
                ));
            }
        }
        ans
    }
}

用了类似倒排东西

执行用时：208 ms 内存消耗：20.1 MB

作者 Neutron3529 2020-06-21 20:15

感谢指导。

现在这个方法已经通过了

就是算得太慢

我准备用疫情检测算法重做一遍

不知道用时会不会更少

（给doc分trunk，每个trunk里面的全部元素做union，之后比较trunk与trunk之间是否存在公共元素，如果有就比较doc与trunk之间是否存在公共元素，最后筛选出存在相似元素的两doc）

（这么做理应更快）

（过几天再试试吧）

--
👇
gwy15: 1. 你的 set 是 Vec<HashSet<&i32>>，肯定慢，而且缓存不友好，用 into_iter()。 2. 不需要 fold，直接 count() 就行了。 3. 不需要重新算 union。充分利用集合的性质。

作者 Neutron3529 2020-06-21 19:48

原来有个函数叫count

话说count用了什么黑科技吗？

我明明试图使用过fold的

但仍然慢了不少

（当然，没用into_iter是我以为所有权会出问题的锅）

（以及，忘记可以不算union了……）

（我的锅）

use std::collections::HashSet;
use std::iter::FromIterator;
impl Solution {
    pub fn compute_similarities(docs: Vec<Vec<i32>>) -> Vec<String> {
        let docs: Vec<HashSet<i32>> = docs.into_iter().map(|v| HashSet::from_iter(v)).collect();
        let mut ans = Vec::new();
        for i in 0..docs.len() {
            if docs[i].len() == 0 {
                continue;
            }
            for j in i + 1..docs.len() {
                if docs[j].len() == 0 {
                    continue;
                }
                let intersec = docs[i].intersection(&docs[j]).count();
                if intersec == 0 {
                    continue;
                }
                let union = docs[i].len() + docs[j].len() - intersec;
                ans.push(format!(
                    "{},{}: {:.4}",
                    i,
                    j,
                    intersec as f64 / union as f64 + 1e-9
                ));
            }
        }
        ans
    }
}

执行用时：1256 ms, 在所有 Rust 提交中击败了 100.00% 的用户内存消耗：7.9 MB, 在所有 Rust 提交中击败了 100.00% 的用户

Mike Tang 2020-06-21 16:50

不能更6。

use std::collections::HashSet;
use std::iter::FromIterator;
impl Solution {
    pub fn compute_similarities(docs: Vec<Vec<i32>>) -> Vec<String> {
        let docs: Vec<HashSet<i32>> = docs.into_iter().map(|v| HashSet::from_iter(v)).collect();
        let mut ans = Vec::new();
        for i in 0..docs.len() {
            if docs[i].len() == 0 {
                continue;
            }
            for j in i + 1..docs.len() {
                if docs[j].len() == 0 {
                    continue;
                }
                let intersec = docs[i].intersection(&docs[j]).count();
                if intersec == 0 {
                    continue;
                }
                let union = docs[i].len() + docs[j].len() - intersec;
                ans.push(format!(
                    "{},{}: {:.4}",
                    i,
                    j,
                    intersec as f64 / union as f64 + 1e-9
                ));
            }
        }
        ans
    }
}

执行用时：1256 ms, 在所有 Rust 提交中击败了 100.00% 的用户内存消耗：7.9 MB, 在所有 Rust 提交中击败了 100.00% 的用户

gwy15 2020-06-21 16:28

你的 set 是 Vec<HashSet<&i32>>，肯定慢，而且缓存不友好，用 into_iter()。
不需要 fold，直接 count() 就行了。
不需要重新算 union。充分利用集合的性质。

use std::collections::HashSet;
use std::iter::FromIterator;
impl Solution {
    pub fn compute_similarities(docs: Vec<Vec<i32>>) -> Vec<String> {
        let docs: Vec<HashSet<i32>> = docs.into_iter().map(|v| HashSet::from_iter(v)).collect();
        let mut ans = Vec::new();
        for i in 0..docs.len() {
            if docs[i].len() == 0 {
                continue;
            }
            for j in i + 1..docs.len() {
                if docs[j].len() == 0 {
                    continue;
                }
                let intersec = docs[i].intersection(&docs[j]).count();
                if intersec == 0 {
                    continue;
                }
                let union = docs[i].len() + docs[j].len() - intersec;
                ans.push(format!(
                    "{},{}: {:.4}",
                    i,
                    j,
                    intersec as f64 / union as f64 + 1e-9
                ));
            }
        }
        ans
    }
}

执行用时：1256 ms, 在所有 Rust 提交中击败了 100.00% 的用户内存消耗：7.9 MB, 在所有 Rust 提交中击败了 100.00% 的用户

1 共 6 条评论, 1 页