遇到了个奇怪的问题

shenhunluo 发表于 2019-05-16 02:26

最近在学算法，写了一个线性时间的获取最大子数组的方法。但是奇怪的是，速度有可能会突然慢很多。代码如下： pub fn quick_find_max_subarray(v:&Vec) -> (usize,usize,i32){ let mut max_array = (0,0,0); let mut i = 0; while(i<v.len()){ let array = find_new_array(&v,i); i = array.1; let mut sum = array.2; if array.2 > max_array.2{ max_array = array; } for j in i..v.len(){ if(sum+v[j]<0){ i=j+1; break; }else{ sum = sum+v[j]; if(sum>max_array.2){ max_array = (array.0,j+1,sum); } } } } return max_array; }

fn find_new_array(v:&Vec,left:usize)->(usize,usize,i32){ for i in left..v.len(){ if(v[i]>0){ let mut sum = v[i]; for j in i+1..v.len(){ if(v[j]<0){ return (i,j,sum) }else{ sum = sum + v[j]; } } return (i,v.len(),sum); } } return (v.len(),v.len(),0); }

主方法： fn main(){ for j in 1..7 { let mut rng = thread_rng(); let mut v = vec![]; for i in 0..(10 as i32).pow(j) { v.push(rng.gen::() % 10); } //println!("{:?}", v); //println!("{:?}", quick_find_max_subarray(&v)); let r = v.len()-1; let t1 = SystemTime::now(); quick_find_max_subarray(&v); let t2 = SystemTime::now(); merge_sort(&mut v, 0, r); let t3 = SystemTime::now(); println!("q-m : {:?}",t2.duration_since(t1).ok().unwrap().as_nanos()/(10 as i32).pow(j) as u128); println!("m-s : {:?}",t3.duration_since(t2).ok().unwrap().as_nanos()/(10 as i32).pow(j) as u128); //println!("{:?}",t3.duration_since(t2).ok().unwrap().as_nanos()/t2.duration_since(t1).ok().unwrap().as_nanos()); } } 典型运行结果第一组： q-m : 24 m-s : 211 q-m : 4 m-s : 192 q-m : 7 m-s : 182 q-m : 3 m-s : 172 q-m : 2 m-s : 177 q-m : 497 m-s : 188 典型运行结果第二组： q-m : 21 m-s : 209 q-m : 5 m-s : 183 q-m : 2 m-s : 181 q-m : 0 m-s : 172 q-m : 172 m-s : 176 q-m : 69 m-s : 189

这到底是什么原因呢？

评论区

写评论

作者 shenhunluo 2019-05-16 13:06

已经发现问题了。。。是我代码的错误。。。

错误代码

pub fn quick_find_max_subarray(v:&Vec<i32>) -> (usize,usize,i32){
    let mut max_array = (0,0,0);
    let mut i = 0;
    while(i<v.len()){
        let array = find_new_array(&v,i);
        i = array.1;
        let mut sum = array.2;
        if array.2 > max_array.2{
            max_array = array;
        }
        for j in i..v.len(){
            if(sum+v[j]<0){
                i=j+1;//问题在这里
                break;
            }else{
                sum = sum+v[j];
                if(sum>max_array.2){
                    max_array = (array.0,j+1,sum);
                }
            }
        }
    }
    return max_array;
}

fn find_new_array(v:&Vec<i32>,left:usize)->(usize,usize,i32){
    for i in left..v.len(){
        if(v[i]>0){
            let mut sum = v[i];
            for j in i+1..v.len(){
                if(v[j]<0){
                    return (i,j,sum)
                }else{
                    sum = sum + v[j];
                }
            }
            return (i,v.len(),sum);
        }
    }
    return (v.len(),v.len(),0);
}

正确代码

pub fn quick_find_max_subarray(v:&Vec<i32>) -> (usize,usize,i32){
    let mut max_array = (0,0,0);
    let mut i = 0;
    while(i<v.len()){
        let array = find_new_array(&v,i);
        i = array.1;
        let mut sum = array.2;
        if array.2 > max_array.2{
            max_array = array;
        }
        for j in i..v.len(){
            i=j+1;//问题在这里
            if(sum+v[j]<0){
                break;
            }else{
                sum = sum+v[j];
                if(sum>max_array.2){
                    max_array = (array.0,j+1,sum);
                }
            }
        }
    }
    return max_array;
}

fn find_new_array(v:&Vec<i32>,left:usize)->(usize,usize,i32){
    for i in left..v.len(){
        if(v[i]>0){
            let mut sum = v[i];
            for j in i+1..v.len(){
                if(v[j]<0){
                    return (i,j,sum)
                }else{
                    sum = sum + v[j];
                }
            }
            return (i,v.len(),sum);
        }
    }
    return (v.len(),v.len(),0);
}

icyhat 2019-05-16 05:15

默认文字是p标签，如果想显示文字的原格式，该网站支持Markdown中的代码写法。

谷歌markdown code，查询使用方法。

这样标记之后，特定的文字可以转换成HTML的pre标签。

e.g.

fn main() {
    println!("hello");
}

对以下内容的回复：

作者 shenhunluo 2019-05-16 02:26

额，这里的代码为什么会排版混乱。。。

1 共 3 条评论, 1 页