首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
拉勾
V2EX  ›  JavaScript

请教用 JavaScript 计算这个东西的方法

  •  
  •   70599 · 2018-03-12 18:12:39 +08:00 · 3202 次点击
    这是一个创建于 376 天前的主题,其中的信息可能已经有所发展或是发生改变。
    假设我有一个数组:
    [11,21,34,65,14,5,66,17,88,21,45,61,50]

    我想要算出这个数组中每个值(包含它自己)之后 10 个值的整数平均值,并输出到一个数组。
    当后面的值不到 10 个的时候,就算出它自己到最后 1 个值的平均值。

    觉得是一个简单的事情,可是想了好久一筹莫展,请大家帮忙。
    第 1 条附言  ·  2018-03-12 20:19:01 +08:00
    先感谢大家。

    有朋友提到 refuce,我发帖前看了一些资料,发现它是用来计算数组中所有值的和的。
    因为我表述能力有限,还有些朋友好像没能理解我的意思,我再重新描述一下。

    假设我有个数组 a,里面有 16 个值。
    我想要通过 JS 得到如下数组:
    [a 中第 1 个值到第 10 个值之和的平均值,
    a 中第 2 个值到第 11 个值之和的平均值,
    a 中第 3 个值到第 12 个值之和的平均值,
    ...
    a 中第 13 个值到第 16 个值之和的平均值,
    a 中第 14 个值到第 16 个值之和的平均值,
    a 中第 15 个值到第 16 个值之和的平均值,
    a 中第 16 个值]

    我正在尝试
    第 2 条附言  ·  2018-03-12 22:01:24 +08:00

    经过一番思考后,我用下面的代码满足了需求:

    var aryA = [11,21,34,65,14,5,66,17,88,21,45,61,50];
    var aryB = [];
    
    aryA.forEach(function(e,idx){
    	var lengthAfterCurrent = ((aryA.length - idx) > 10) ? 10 : (aryA.length - idx);		
    	var sum10Ary =[];
    	for(var i = 0; i < lengthAfterCurrent; i++){
    		sum10Ary.push(aryA[idx++]);
    	}
    	var aryBe = Math.round(sum10Ary.reduce(function(a,b){return a + b}) / lengthAfterCurrent);
    	aryB.push(aryBe);
    });
    
    console.log('aryB is '+aryB);
    

    谢谢大家来指教。

    41 回复  |  直到 2018-03-13 23:49:05 +08:00
        1
    zouyyu   2018-03-12 18:18:50 +08:00 via iPhone
    array 有个 slice 方法截取数组 数组循环的时候能取到当前元素索引 。然后递归就可以了
        2
    rrfeng   2018-03-12 18:20:13 +08:00 via Android
    循环一遍不就行了...有啥好计算的
        3
    grantonzhuang   2018-03-12 18:20:16 +08:00 via Android
    reduce 了解一下
        4
    mskf   2018-03-12 18:25:40 +08:00
    lodash 了解一下

    _.chain([11,21,34,65,14,5,66,17,88,21,45,61,50] ).chunk(10).map((arr)=>{return _.sum(arr)/arr.length}).value()
        5
    Building   2018-03-12 18:27:35 +08:00 via iPhone
    怎么会没思路呢,多简单啊,就像这样:

    if( arr.length === 0 ) return []

    if( arr.length === 1 ) return arr

    if( arr.length === 2 )
    var res = []
    res[0] = (arr[0] + arr[1]) / 2
    res[1] = (arr[1])
    return res

    if( arr.length === 3 )
    ......
        6
    SuperMild   2018-03-12 18:33:46 +08:00
    授人以渔。

    通过编程来解决问题,一个关键的技巧是把大问题分解为小问题!

    比如这个问题,可以这样分解:

    首先,取第一组 10 个数,把这 10 个数 print 出来。

    然后,取下一组 10 个数,print 出来。(做完这两个小实验,就证明会用 slice 了)

    然后,写一个循环,把每一组 10 个数都 print 出来。(做完这步,就证明会用循环了)

    然后,把上一步那个循环改一下,不 print 10 个数,而是 print 它们的平均值。(这个小改动不难)

    然后,思考一下怎样把这些平均值塞进一个数组里。

    这就完成了。注意,每一步都不是很难,难的是初学者不习惯这种把大问题分解为小问题的思考方法。
        7
    rabbbit   2018-03-12 18:38:28 +08:00
    [0,1,2,3,4,5,6,7,8,9,10,11,12].map((num, i, arr) =>{return arr.slice(i, i + 11).reduce((x, y)=>{return (x + y) / 11})})
        8
    zohan   2018-03-12 18:40:50 +08:00
    reduce +1
        9
    lambdaxs   2018-03-12 18:43:11 +08:00
    输入数组为 a,输出数组为 b
    a 数组中的每一个元素都可以通过一个映射关系转化为 b 数组中对应的元素
    所以确定可以使用 Array.map 函数,然后来写 map 中的 f
    f 为向后取最大 10 个元素累加求平均的函数
    先实现 f,再把 f 扔到 map 里
    work~~
        10
    rabbbit   2018-03-12 18:49:08 +08:00
    唔,好像写错了
    [0,1,2,3,4,5,6,7,8,9,10,11,12].map((num, i, arr) =>{return arr.slice(i, i + 11).reduce((x, y, i, arr)=>{return (x + y) / arr.length})})
        11
    rabbbit   2018-03-12 18:56:04 +08:00
    上边那个还是不对...
    算了不管了
    [0,1,2,3,4,5,6,7,8,9,10,11,12].map((num, i, arr) =>{return arr.slice(i, i + 11).reduce((x, y)=>{return x + y}) / arr.slice(i, i + 11).length})
        12
    ipwx   2018-03-12 19:26:38 +08:00
    @rabbbit 我看你写了三遍,可是全都是 O(10N) 的。应该写 O(N) 的算法。
        13
    ipwx   2018-03-12 19:27:13 +08:00
    @rabbbit 抱歉,O(N) 应该到不了,O(2N) 应该行。
        14
    ipwx   2018-03-12 19:36:18 +08:00
    @70599 少年,如果你不会“优雅的写法”,为什么不一步一个脚印,用最基础的写法写呢?反正有 V8 的 JIT,用累加器和循环并不慢啊。比如

    再说这个写法其实比上面 @Building @rabbbit 高效才对。因为他们是 O(10N),而这个写法是 O(2N)。
        15
    ipwx   2018-03-12 19:41:30 +08:00
    @70599 好吧,我上面的代码可能理解错了题意。不过应该很好改才对,你也可以试试。
        16
    lightening   2018-03-12 20:21:34 +08:00
    @ipwx o(10n) 和 o(2n) 都是 o(n) 。
        17
    lightening   2018-03-12 20:34:23 +08:00
    怎么会想不出来呢?我就不说聪明的方法了,只说最容易想的笨办法,主要是提供一个解决问题的思路:

    我们要把原数组的每个元素映射到另一个元素,那么:

    array.map((element, index) => {
    doSomethingToEachElement(...)
    })

    每个元素做点什么呢?根据你说的
    > 我想要算出这个数组中每个值(包含它自己)之后 10 个值的整数平均值,并输出到一个数组。
    > 当后面的值不到 10 个的时候,就算出它自己到最后 1 个值的平均值。

    function doSomethingToEachElement() {
    if (remaining.length >= 10) {
    return average( firstTenOf(remaining) )
    } else {
    return average(remaining)
    }
    }

    看一看上述代码,remaining 不知道,average 函数没写。那就补出来。这不用教吧?

    你看很简单,每一行代码都是和你的描述的对应的。把缺的参数补齐,缺的变量怎么计算填上,不就写出来了?
    如果一个问题你没有思路,就根据中文描述,一一对应的先写出来。写出来后,然后再看有没有办法简化。
        18
    qfdk   2018-03-12 20:40:40 +08:00 via iPhone
    简单的问题为啥这么复杂 取 0-9 是个数 算平均 然后 pop 掉第一个数 再取十个 递归就好了 终止条件就是数组长度不为 10
        19
    qppq54s   2018-03-12 20:44:57 +08:00
    let a = [11,21,34,65,14,5,66,17,88,21,45,61,50] ;
    let b = a.length;
    for(let i = 0; i< 10; i++) {a.push(0)};
    let result = [];
    for (let i = 0;i < b; i++) {
    result.push( (a[i] + a[i+1] + a[i+2] + a[i+3] + a[i+4] + a[i+5] + a[i+6] + a[i+7] + a[i+8] + a[i+9])/10);
    }
        20
    AlisaDestiny   2018-03-12 20:53:29 +08:00
    ```javascript
    var arr = [11,21,34,65,14,5,66,17,88,21,45,61,50];
    var sum = 0;
    for(var i=0;i<10 && i<arr.length;i++){
    sum += arr[i];
    }
    while(arr.length > 0){
    var avg = sum / Math.min(arr.length,10);
    console.log("avg:" + avg);
    if(arr.length>10){
    sum += arr[10];
    }
    sum -= arr.shift();
    }
    ```
    复杂度:O(n)
        21
    msg7086   2018-03-12 22:25:42 +08:00
    @ipwx 亲,大 O 的常数倍率需要忽略不计的问题了解一下。
        22
    snw   2018-03-12 23:14:33 +08:00 via Android
    先用最笨拙的方法写就行,以后再优化。
    同意上面说的 V8 跑循环真心快
        23
    nino   2018-03-12 23:21:42 +08:00
    ```
    [...].map((_, index, arr) => avg(arr.slice(index, index + 10)))
    ```

    你要的 reduce 的写法,你的问题是不熟悉 Array.prototype.slice 这个 API 吧
        24
    ipwx   2018-03-12 23:30:46 +08:00 via iPhone
    @msg7086 @lightening 这里可不适用忽略不计……更准确的复杂度是 O(kn) 和 O(2n),其中 k 在本问题中取 10。再说,这么简单一个程序,为啥不用最佳写法?
        25
    ipwx   2018-03-12 23:39:01 +08:00 via iPad
    @msg7086 @lightening 而且所谓的复杂度分析时忽略常数,只是因为不同阶的复杂度,当 N 趋向于无穷时,比值渐进趋向于 0 (或无穷),没有比较常数的必要。比如 O(logN) 和 O(N) 有阶差,此时比较常数没有意义。然而当同阶时,你都忽略常数了,你还比啥?

    复杂度分析理论是为了在没有运行算法的前提下比较算法优劣的理论方法。一切教科书上的定式、过程,都要为了这个目的让路。切记。
        26
    ipwx   2018-03-12 23:43:54 +08:00 via iPad
    @msg7086 @lightening 不过话说回来,不同阶不比常数也不是绝对的。写算法的时候,偶尔也会根据 N 的不同,使用不同阶的算法(因为常数有差别,高阶低常数算法在 N 小的时候反而更快)。比如 GCC C++ STL 中快速排序( O(N log N))的实现,在数据量小的时候(或者递归之后数据量小的时候)是 O(N^2) 的希尔排序。当然,你问我这两个算法的确切常数,我是不确定的,不过反正写 G++ 的人很厉害,我也就相信他们的判断了。
        27
    ipwx   2018-03-12 23:46:14 +08:00 via iPad
    @msg7086 @lightening 好吧根据维基百科(希尔排序),优化过的希尔排序其期望复杂度是 O(N (log N)^2),也就比快速排序的期望复杂度 O(N log N) 慢那么一点。。。
        28
    msg7086   2018-03-13 00:03:49 +08:00
    @ipwx 大 O 描述的是算法与输入项之间增长变化的比率,和具体的算法时间无关。
    比如本题中 O(n)表示的是对于输入项长度 n 来说,算法的增长与 n 的增长是线性关系的。
    别说 O(10n),就算是 O(1000000n),也还是 O(n)。

    如果你要分析算法具体运算量的话,那是 kn 或者 2n,但不是 O(2n)。
    但是实际运算量还要看运算类型,比如加法和内存读写的时间又不能简单相加等等,这算起来就复杂了。

    这和是不是用最佳写法完全无关。
        29
    msg7086   2018-03-13 00:05:02 +08:00
    打字时间过长,一刷新又多了三个回复,无视我上面说的吧。
        30
    Merlini   2018-03-13 00:06:20 +08:00 via Android
    楼主的写法简单易懂,就是这个每次都要重新加一遍有点难受,可不可以利用以前加的值,往动态规划方面靠靠? 当然这只是个人想法。
        31
    msg7086   2018-03-13 00:07:14 +08:00
    TL;DR:大 O 不关心常数。同阶下比较算法快慢不应该用大 O 来表示。
        32
    narcotics   2018-03-13 00:45:34 +08:00 via Android
    循环入队列,满十求和
    和 减去队列头,出队列
    循环
        33
    Sparetire   2018-03-13 01:21:19 +08:00 via Android
    这不就是个滑动窗口,最后窗口缩小的事嘛。。
        34
    lightening   2018-03-13 05:16:10 +08:00
    @ipwx
    对你来说可能是“这么简单一个程序”,不过楼主既然想不出怎么写,那么最佳写法就是他能理解的写法。

    我明白你的意思,10n 和 1n 实际的复杂度确实是有区别的。不过大 O 符号本来只就是阶数符号,我的意思只是说你用 O(10n) 和 O(n) 这两个符号数学上是等价的,你用它们来表示 10 倍的运算量差距不科学。
        35
    zhujinliang   2018-03-13 09:02:31 +08:00
    来了,你们要的 O(n)版本:

    var arr = [11,21,34,65,14,5,66,17,88,21,45,61,50]

    var winSize = 10
    var sum = arr.slice(0, winSize-1).reduce((acc, cur) => acc + cur)
    var arrLen = arr.length
    console.log(arr.map((item, index, arr) => {
    if (index > 0) sum -= arr[index-1];
    if (index+winSize <= arrLen) sum += arr[index+winSize-1];
    return sum / Math.min(winSize, arrLen-index)
    }))
        36
    est   2018-03-13 09:02:54 +08:00 via Android
    window average?

    好像是个经典面试题
        37
    ipwx   2018-03-13 10:27:09 +08:00
    @msg7086 @lightening 确实,我大 O 符号用得不合适,这种细节应该注意一下,哈哈。不过我的意思很明确,这个场景需要考虑常数。
        38
    dd0754   2018-03-13 11:09:47 +08:00
    const arr2 = [11, 21, 34, 65, 14, 5, 66, 17, 88, 21, 45, 61, 50].map((e, i, arr) => {
       const tmp = arr.slice(i, i + 11);
       return tmp.reduce((prev, current) => prev + current) / tmp.length;
    });
    console.log(arr2);
        39
    mashirozx   2018-03-13 11:34:22 +08:00 via Android
    移动平均吗 233
        40
    zouyyu   2018-03-13 13:40:49 +08:00
    function calAVG(array, interval){

    if(!(Array.isArray(array))) throw '参数异常'

    for(let ele of array){
    if(isNaN(parseFloat(ele))){
    throw '数组中有不能转换为数字的元素'
    }
    }

    const result = [],
    INTERVAL = interval || 1,
    reducer = (accumulator, currentValue) => accumulator + currentValue;
    let arrayLength = array.length;
    if(arrayLength <= interval){
    console.info(array.reduce(reducer))
    result.push(array.reduce(reducer)/arrayLength);
    return result;
    }

    for(let[index, value] of array.entries()){
    let endIndex = index + INTERVAL,
    currentArray = array.slice(index, endIndex + 1);

    if(endIndex >= arrayLength){
    result.push(currentArray.reduce(reducer)/(currentArray.length))
    break;
    }
    result.push(currentArray.reduce(reducer)/(INTERVAL + 1));
    }
    return result;
    }
        41
    dacapoday   2018-03-13 23:49:05 +08:00
    [11,21,34,65,14,5,66,17,88,21,45,61,50]
    .reduce((x, y) => {
    x.push([]);
    x.slice(-10).map(a => a.push(y));
    return x;
    }, [])
    .map(x => x.reduce((x, y) => x + y) / x.length);
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2369 人在线   最高记录 4385   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 22ms · UTC 14:21 · PVG 22:21 · LAX 07:21 · JFK 10:21
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1