应该如何标注泛型使其满足`From/Into`或者`as`的使用条件？

Neutron3529 发表于 2021-02-21 13:37

比如我想写一个欧拉筛：

type T=u32;
/// return primes in [2,n)
fn euler_sieve(n:T)->Vec<T>{
    let mut p:Vec<bool>=vec![false;n as usize];
    let mut prime=Vec::new();
    for i in 2..n{
        if !p[i as usize]{
            prime.push(i);
        }
        for j in prime.iter().cloned(){
            if i*j>=n{break}
            p[(i*j)as usize]=true;
            if i%j==0{break}
        }
    }
    prime
}
fn main(){
    println!("{:?}",euler_sieve(100).len());
}

这里，由于我定义了type T=u32，我可以肆无忌惮地使用Into，From，甚至是as之类的操作

我尝试把type T=u32改成泛型

fn euler_sieve<T>(n:T)->Vec<T>{
...
}

几经尝试都没有成功：

2 | fn euler_sieve<T>(n:T)->Vec<T>{
  |                - this type parameter
...
5 |     for i in 2..n{
  |                 ^ expected integer, found type parameter `T`
...
3 |     let mut p:Vec<bool>=vec![false;n as usize];
  |                                    ^^^^^^^^^^ an `as` expression can only be used to convert between primitive types or to coerce to a specific trait object
------------------------------------------------------------------------
2 | fn euler_sieve<T:{integer}>(n:T)->Vec<T>{
  |                  ^ expected one of 9 possible tokens
------------------------------------------------------------------------
2 | fn euler_sieve<T:integer>(n:T)->Vec<T>{
  |                  ^^^^^^^ not found in this scope

有大神教一下where的用法吗？

评论区

写评论

ywxt 2021-02-26 01:35

use std::{cmp, convert::TryInto, fmt::Debug, ops, usize};

fn euler_sieve<T, U>(n: T) -> Vec<T>
where
    T: TryInto<usize, Error = U>
        + ops::Mul<Output = T>
        + ops::Rem<Output = T>
        + cmp::Ord
        + cmp::Eq
        + Copy,
    U: Debug,
    u8: Into<T>,
    ops::Range<T>: Iterator<Item = T>,
{
    let mut p: Vec<bool> = vec![false; n.try_into().unwrap()];
    let mut prime = Vec::new();
    for i in 2u8.into()..n {
        if !p[i.try_into().unwrap()] {
            prime.push(i);
        }
        for j in prime.iter().cloned() {
            if i * j >= n {
                break;
            }
            p[(i * j).try_into().unwrap()] = true;
            if i % j == 0u8.into() {
                break;
            }
        }
    }
    prime
}
fn main() {
    println!("{:?}", euler_sieve(100).len());
}

还有一种方法就是把循环数字转成usize，然后push时再转回去。

作者 Neutron3529 2021-02-23 10:25

所有u32范围内的素数一共203280221个

如果用u32存储这些素数，返回的Vec大小是775.45MiB

如果用u64(usize)存储这些素数，返回Vec大小1.51GiB

如果把Vec<bool>改成更省空间的Vec<u64>（然后实现一个bitmap），只需要额外512MiB即可完成全部素数的筛选

事实上，有时候我们只需要i32以内的素数，此时返回一个Vec<usize>显然不合适

--
👇
johnmave126: 有一说一，这里泛型作用不大吧，质数定理说明n以内的质数渐进于n/ln(n)，所以n基本上跟最后返回的数组大小差不了几个数量级。并且代码里还用n作为长度创建了一个Vec，而Vec的大小一定是usize，所以基本可以直接推断n是usize了。

johnmave126 2021-02-22 10:32

有一说一，这里泛型作用不大吧，质数定理说明n以内的质数渐进于n/ln(n)，所以n基本上跟最后返回的数组大小差不了几个数量级。并且代码里还用n作为长度创建了一个Vec，而Vec的大小一定是usize，所以基本可以直接推断n是usize了。

作者 Neutron3529 2021-02-21 14:37

感谢回复

这里的确可以先来一个trait ToUsize然后再用宏实现impl ToUsize for i32之类的语句

现在仍然很好奇，这里不能直接用where标注，我们的变量可以Into到usize然后直接写.into()吗？

--
👇
gwy15: https://crates.io/crates/num-traits

gwy15 2021-02-21 13:51

https://crates.io/crates/num-traits

1 共 5 条评论, 1 页