算法:Solutions for the Maximum Subsequence Sum Problem

The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6. --from wiki

下面我们分析四种算法的时间性能,由于运行时间相差较大,我们分成两组进行对比:

环境:ubuntu 12.04

时间单位:ms

时间性能:presume that the input is preread

第一组:输入数据元素个数2000

/*************************************************************************
    > File Name: algorithm1.c
    > Author: Simba
    > Mail: dameng34@163.com
    > Created Time: 2012年12月24日 星期一 22时41分56秒
 ************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<sys/time.h>

int maxsubsum1(const int a[], int n)
{
    int thissum, maxsum, i, j, k;

    maxsum = 0;
    for (i = 0; i < n; i++)
    {
        for (j = i; j < n; j++)
        {
            thissum = 0;
            for (k = i; k <= j; k++)
                thissum += a[k];

            if (thissum > maxsum)
                maxsum = thissum;
        }
    }
    return maxsum;
}

int maxsubsum2(const int a[], int n)
{
    int thissum, maxsum, i, j;

    maxsum = 0;
    for (i = 0; i < n; i++)
    {
        thissum = 0;
        for (j = i; j < n; j++)
        {
            thissum += a[j];

            if (thissum > maxsum)
                maxsum = thissum;
        }
    }
    return maxsum;
}

long GetTickCount(void)
{
    struct timeval tv;

    gettimeofday(&tv, NULL);

    return (tv.tv_sec * 1000 + tv.tv_usec / 1000);
}

int main(void)
{
    int i, n = 2000;
    int *ptr = malloc(sizeof(int) * n);
    srand(time(NULL));
    for (i = 0; i < n; i++)
        ptr[i] = rand() % 50 - 25;
    // adopt algorithm  1
    unsigned int utimecost = GetTickCount();
    int result = maxsubsum1(ptr, n);
    utimecost = GetTickCount() - utimecost;
    printf("max subsequence sum is %d, time cost %d\n", result, utimecost);

    // adopt algorithm  2
    utimecost = GetTickCount();
    result = maxsubsum2(ptr, n);
    utimecost = GetTickCount() - utimecost;
    printf("max subsequence sum is %d, time cost %d\n", result, utimecost);

    free(ptr);

    return 0;
}

输出为:

max subsequence sum is 275, time cost 4423 max subsequence sum is 275, time cost 6

第二组:输入数据元素个数 1000000

/*************************************************************************
    > File Name: divide_conquer.c
    > Author: Simba
    > Mail: dameng34@163.com
    > Created Time: 2012年12月24日 星期一 23时24分41秒
 ************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include <sys/time.h> /* struct timeval, gettimeofday(), struct itimerval, setitimer(), ITIMER_REAL */

int divide_conquer(int arr[], int start, int end)
{
    if(start == end)
        return (arr[start] > 0 ? arr[start] : 0);

    int mid = (start + end) / 2;
    int max_left = divide_conquer(arr, start, mid);
    int max_right = divide_conquer(arr, mid + 1, end);
    // mid subsequence

    int max_left_border = 0;
    int tmp_sum = 0;
    int i;

    for(i = mid; i >= start; i--)
    {
        tmp_sum += arr[i];
        if(tmp_sum > max_left_border)
            max_left_border = tmp_sum;
    }

    int max_right_border = 0;
    tmp_sum = 0;
    for(i = mid + 1; i <= end; i++)
    {
        tmp_sum += arr[i];
        if(tmp_sum > max_right_border)
            max_right_border = tmp_sum;
    }

    int max_mid = max_left_border + max_right_border;
    // max subsequence
    int iresult = max_left;
    if(max_right > iresult)
        iresult = max_right;
    if(max_mid > iresult)
        iresult = max_mid;
    return iresult;
}

int maxsubsum3(const int a[], int n)
{
    int j, thissum, maxsum;
    thissum = maxsum = 0;
    for (j = 0; j < n; j++)
    {
        thissum += a[j];

        if (thissum > maxsum)
            maxsum = thissum;
        else if (thissum < 0)
            thissum = 0;
    }

    return maxsum;
}

long GetTickCount(void)
{
    struct timeval tv;

    gettimeofday(&tv, NULL);

    return (tv.tv_sec * 1000 + tv.tv_usec / 1000);
}

int main(void)
{
    int i, n = 1000000;
    int *ptr = malloc(sizeof(int) * n);
    srand(time(NULL));
    for (i = 0; i < n; i++)
        ptr[i] = rand() % 50 - 25;
    // adopt divide_conquer algorithm
    unsigned int utimecost = GetTickCount();
    int result = divide_conquer(ptr, 0, n - 1);
    utimecost = GetTickCount() - utimecost;
    printf("max subsequence sum is %d, time cost %d\n", result, utimecost);
    // adopt algorithm 3
    utimecost = GetTickCount();
    result = maxsubsum3(ptr, n);
    utimecost = GetTickCount() - utimecost;
    printf("max subsequence sum is %d, time cost %d\n", result, utimecost);

    free(ptr);

    return 0;
}

输出为:

max subsequence sum is 2410, time cost 217 max subsequence sum is 2410, time cost 4

分析:

在《data structure and algorithm analysis in c》中有对这四种算法时间性能的分析,依次下来分别是O(n^3),O(n^2),O(nlogn),O(n),即使我们在第二组输入的元素个数是第一组的500倍,第二组的运行时间都要比第一组的小。下图2-2是作者写书时测试的时间列表,显然现在的机器运行得更快。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专知

浅显易懂的分布式TensorFlow入门教程

【导读】分布式TensorFlow可以有效地提神经网络训练速度,但它的使用并不简单。虽然官方提供了文档和示例,如链接【1】,但是它们太难懂了。本文是一篇浅显易懂...

1127
来自专栏数据存储

硬盘IO性能估算入门

IO是输入输出指令,操作系统向存储控制器下发一个读或者写数据的操作指令,控制器下发地址和数据给存储设备,并返回结果给存储控制器,最后到达操作系统。操作系统的一个...

32112
来自专栏吴伟祥

什么是集群、分布式、集中式、伪分布式 转

1. 集中式 将项目等部署到同一台机器上,对机器性能要求比较高,一般会用多台机器备份,否则,如果机器出现死机等状况,整个项目将不能运行。 eg:就好比你要盖...

471
来自专栏Spark学习技巧

Spark的PIDController源码赏析及backpressure详解

浪尖一直觉得spark 的源码值得我们细细品读,帮助解决我们生产中的问题,可以学习大牛的编程思路,学习spark架构设计,学习scala及java编程,到处都是...

743
来自专栏奇点大数据

支付宝如何优化移动端深度学习引擎?

由于移动端资源的限制,大部分深度学习引擎都部署在云端,移动设备获取到输入数据,经过简单的加工,发送给云端,云端服务器经过深度神经网络推断运算,得到结果并反馈给移...

883
来自专栏SDNLAB

ONOS:负载均衡路由算法及应用开发(一)

一、应用介绍 当新流量发起时,本应用将为其选择一条路由路径,这条路径具有全局负载均衡意义上的最小权值(Weight/Cost)。 本应用即将开源在笔者的Gith...

3307
来自专栏嵌入式程序猿

快来趴一趴JTAG那些事(下)

你以为你不知道,其实它一直就在你身边,JTAG是嵌入式开发中在熟悉不过的一个名词了,但是你真的很了解他吗,来一块趴一趴JTAG的那些事,今天来学习JTAG指令 ...

3268
来自专栏IT笔记

Dubbo负载均衡配置

在集群负载均衡时,Dubbo提供了多种均衡策略,缺省为random随机调用。 负载均衡扩展 (1) 扩展说明: 从多个服务提者方中选择一个进行调用。 (2) 扩...

3015
来自专栏大魏分享(微信公众号:david-share)

从PowerVM,KVM到Docker:存储池的配置与调优---第一篇终结(第3子篇)

VIOC 上的 VSCSI 性能调优 在本实验的 VIOC 中,一个磁盘对应 4 条 VSCSI 路径。查看磁盘默认的属性 ; # lsattr -El hdi...

4086
来自专栏开源FPGA

FPGA计算3行同列数据之和

实验:FPGA计算3行同列数据之和 实验要求:PC机通过串口发送3行数据(一行有56个数据,3行共有56*3=168个数据)给FPGA,FPGA计算3行同一列数...

1858

扫码关注云+社区