前端小白的算法之路(一)

栏目: 编程工具 · 发布时间: 5年前

内容简介:曾经有一个年少轻狂的职场小白,在前端圈子里摸爬滚打将近两年,本计划在js的道路上越走越远,以至于每天沉浸在js红皮书里不能自拔,突然有一天脑抽想找leader比划两下,于是出现了下面的对话:(如果你对这个问题感兴趣或者觉得自己NB,可以停下来试着写一下这个算法,不要偷看我的代码哈:smiley:高手略过:joy:)看到这个问题,第一反应很简单,无非就是先排个序,然后看情况再分配任务,于是有了下面的

曾经有一个年少轻狂的职场小白,在前端圈子里摸爬滚打将近两年,本计划在js的道路上越走越远,以至于每天沉浸在js红皮书里不能自拔,突然有一天脑抽想找leader比划两下,于是出现了下面的对话: 小白:leader,您最近在干嘛?手里有需要亟待解决的难题吗?leader:咦,确实有哎,咱的项目随着业务的不断发展,日均PV也越来越多,公司的两台机器已经快满足不了需求,现在需要解决一下机器的问题。小白:那还不简单,就是多搞几台机器,四核换八核,可以并行处理就OK了。leader:小伙子想法很美好啊,钱从哪来?那我先问你个简单的问题,你写个算法出来。 于是这个问题应用而生,小白也开始了苦苦的算法中。。。

问题阐述

假设一台双核处理器可以并行处理任务,它们的处理速度都为1k/s,每个任务均以k为单位,如[300, 600, 300, 500, 1000, 700,300],且每个任务不能拆分必须由单独的核来执行,求一堆任务的最短时间算法?

(如果你对这个问题感兴趣或者觉得自己NB,可以停下来试着写一下这个算法,不要偷看我的代码哈:smiley:高手略过:joy:)

算法之路

看到这个问题,第一反应很简单,无非就是先排个序,然后看情况再分配任务,于是有了下面的 第一版程序

let arr = [300, 600, 300, 500, 1000, 700, 300];
function task(arr) {
    let left = [];
    let right = [];
    let lefts = 0;
    let rights = 0;
    let flag = true; // 第一次累加最大值 第二次累加最小值 平分两组任务
    // 平分两组任务
    let newArr = arr.sort((a, b) => b - a);
    if (flag) {
        left.push(newArr[0]);
        right.push(newArr[1]);
        newArr = newArr.slice(2);
    } else {
        left.push(newArr[newArr.length - 1]);
        right.push(newArr[newArr.length - 2]);
        newArr = newArr.slice(0, newArr.length - 2);
    }
    // 开关循环 第一次加最大值 第二次加最小值 依次累加
    flag = !flag; 
    // 两组任务分别之和
    lefts = left.reduce((a, b) => a + b);
    rights = right.reduce((a, b) => a + b);
    // 只剩下一个任务或0个任务时,最终结果计算
    if (newArr.length <= 1) {
        if (newArr.length == 1) {
            if ((lefts - rights) > newArr[0]) {
                return lefts;
            } else {
                right.push(newArr[0]);
                rights = right.reduce((a, b) => a + b);
                return rights;
            }
        } else {
            if (lefts < rights) {
                return rights;
            } else {
                return lefts;
            }
        }
    }
    // 递归调用实现循环
    return task(newArr);
};
console.log("最短时间为:" + task(arr) + 's');
复制代码

基本思路就是 先把一堆任务排序,然后开始分配,第一次给第一台机子最大值,第二台机子次大值,第二次给第一台机子最小值,第二台机子次小值,依次递归调用累加,直至最后结束,如果是奇数个任务最后剩下一个任务的话,需要把这个任务分给时间较小的一组,最后返回一组时间较大的即是最终所需的最短时间。

显然这个程序是有问题的,于是开始了研究,多天之后依旧没有给出正确的答案,凭借一己之力显然不能解决,然后开始在segmentfault上提问,没想到很快就有人回复了, 是NP-hard问题。近似算法参见 partition problem

看到回复后迫不及待的开始Google,竟然让我大吃一惊, 2000年,美国克莱数学研究所公布了世界七大数学难题,又称千禧年大奖难题。其中P与NP问题被列为这七大世界难题之首 ,看到这大大激发了我对这一问题的研究热情,于是开始了NP问题的研究。

NP-hard,其中NP是指非确定性多项式(non-deterministic polynomial,缩写NP)。所谓的非确定性是指,可用一定数量的运算去解决多项式时间内可解决的问题。NP-hard问题通俗来说是其解的正确性能够被“很容易检查”的问题,这里“很容易检查”指的是存在一个多项式检查算法。相应的,若NP中所有问题到某一个问题是图灵可归约的,则该问题为NP困难问题。

旅行推销员问题就是最著名的NP问题之一,当然我要解决的这个问题( 多线程多机调度问题 )也属于NP问题之一,一般使用 贪心算法 来解决,于是我就开始了贪心算法之路。

算法描述

贪心算法:(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。

思想: 贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行,根据某个优化测度,每一步都要确保能获得局部最优解。每一步只考虑一个数据,他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加算法停止。

过程:

  1. 建立数学模型来描述问题;
  2. 把求解的问题分成若干个子问题;
  3. 对每一子问题求解,得到子问题的局部最优解;
  4. 把子问题的解局部最优解合成原来解问题的一个解。

解决思路

多线程问题主要是多个服务器可以并行处理多个任务,寻求处理所有任务的情况下,用掉最少时间的问题。因为任务并不局限于在某一个服务器上处理,而且任务不能拆分,所以还是要综合考虑怎么分配任务,属于多线程问题。

核心思路:(n代表任务,m代表机器)

  1. 将n个独立的任务按照时间从大到小排序;
  2. 如果n<=m,则需要的最短时间就是n个任务当中的最大时间;
  3. 如果n>m,则先给每个机器依次分配任务,第一次就分配了m个作业;
  4. 然后循环第一次分配的m个任务时间,选取处理时间最短的机器分配第m+1个任务;
  5. 依次循环所有机器所需时间,并选取最短时间的机器分配下一个任务;
  6. 最后比较返回最长时间的机子时间则为所需的最短时间。

实现过程:

前端小白的算法之路(一)

程序设计

第二版程序:

let arr = [700, 400, 300, 500, 100, 900];
function task(arr) {
    // 1. 任务排序
    let newArr = arr.sort((a, b) => b - a);
    // 2. 两组各取最大值和次大值
    let left = [newArr[0]];
    let right = [newArr[1]];
    newArr = newArr.slice(2);
    // 3. 分别计算两组所用的时间
    let lefts = newArr[0];
    let rights = newArr[1];
    // 4. 比较哪一组时间少就依次把下一个任务分给少的那组
    newArr.forEach((item, index) => {
        if (lefts < rights) {
            left.push(item);
        } else {
            right.push(item);
        }
        // 分别计算每组所用的时间
        lefts = left.reduce((a, b) => a + b);
        rights = right.reduce((a, b) => a + b);
    });
    // 5. 返回较大值则是所用最短时间
    return Math.max(lefts, rights);
};
console.log("最短时间为:" + task(arr) + 's');
复制代码

以上的第二版程序还是以最初的问题双核处理器(相当于两个机子)实现的,经测试正确通过,于是又拓展了多线程多机器的常见问题,就有了最终版的程序。

第三版程序:

let tasks = [300, 600, 300, 500, 1000, 700, 300];
function task(tasks, nums) {
    // 1. 对任务进行从大到小排序
    tasks = tasks.sort((a, b) => b - a);
    // 2. 第一次给nums个机器分配前nums个任务
    let machine = JSON.parse(JSON.stringify(Array(nums).fill([])));
    tasks.forEach((item, index) => {
        if(index < nums) {
            machine[index].push(item);
        }
    });
    // 3. 分别计算每个机器执行任务的时间
    let times = Array(nums);
    machine.forEach((item, index) => {
        times[index] = item.reduce((a, b) => a + b);
    });
    // 4. 全部任务去掉第一次分配的nums个任务
    tasks = tasks.slice(nums);
    // 5. 比较哪台机器用的时间少就给哪台机器分配下一个任务
    tasks.forEach((item, index) => {
        // 给最短时间的机器分配任务
        times.some((items, indexs) => {
            if(items == Math.min(...times)) {
                machine[indexs].push(item);
                return true;
            }
        });
        // 分别计算每台机器的执行时间
        machine.forEach((items, indexs) => {
            times[indexs] = items.reduce((a, b) => a + b);
        });
    });
    // 6. 返回所有机器中时间最长的即是所有任务执行的最短时间
    return Math.max(...times);
};
console.log("最短输出时间为:" + task(tasks, 3) + 's');
复制代码

哈哈,终于可以松口气了,这一路下来也是历尽艰辛,在此非常感谢清华大学的@萝卜的指点迷津,一语惊醒梦中人,让我找到了解法,虽然不是最优的算法,也让我醍醐灌顶,打开了探索算法的大门。以上代码是用JavaScript实现的(你可以用你熟悉的语言实现一下哈:smiley:),其他语言也是一样的逻辑,所以做前端的千万不要在js的世界里妄自尊大,要站在CTO的角度放眼全局,尤其是多熟悉一些算法,这样的话编程思维更有逻辑性,解决问题能力更强,在公司的不可替代性也就更大了。


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

ActionScript 3.0精彩范例词典

ActionScript 3.0精彩范例词典

杨东昱 编 / 2008-5 / 59.00元

《ActionScript 3.0精彩范例词典》列出了最常用的ActionScript语法,并附有详细的程序代码范例,不但教您如何使用、修改ActionScript代码,而且还以实际范例和图解,说明每项语法还能呈现哪些动画效果和功能,对学习ActipScript有所帮助。读者在阅读《ActionScript 3.0精彩范例词典》之后,将能开发出属于自己的ActionScript程序与FLASH动画......一起来看看 《ActionScript 3.0精彩范例词典》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具