鸿 网 互 联 www.68idc.cn

蛙蛙推荐:算法练习:最大间隙问题

来源:互联网 作者:佚名 时间:2022-06-10 14:59
最大间隙问题:给定的n个实数x1,x2...,xn,求这N个数在实轴上相邻两个数之间最大差值。假设对任何实数的下去整耗时是O(1),设计最大间隙问题的线性时间算法。 问题描述: 最大间隙问
最大间隙问题:给定的n个实数x1,x2...,xn,求这N个数在实轴上相邻两个数之间最大差值。假设对任何实数的下去整耗时是O(1),设计最大间隙问题的线性时间算法。 问题描述:
最大间隙问题:给定的n个实数x1,x2...,xn,求这N个数在实轴上相邻两个数之间最大差值。假设对任何实数的下去整耗时是O(1),设计最大间隙问题的线性时间算法。
数据输入:
输入数据由文件名为input.txt的文本文件提供,文件的第一行有一个正整数N,接下来的一行有N个实数x1,x2...,xn
数据输出:
程序运行结束时,将找到的最大间隙输出到output.txt里

这是《算法设计与实验题解》里的一道题,原文中的算法分析是用c写的,我转换成了c#语言,如下
using System;
using System.Diagnostics;
using System.Collections;
using System.IO;
using System.Runtime.InteropServices;

namespace ZuiDaJianXi {
    
class Program {
        
static int MyFloor(double d) {
            cast_struct c 
= new cast_struct { d = d - 0.499999999999 + 6755399441055744.0 };
            
return c.i;
        }

        [StructLayout(LayoutKind.Explicit)]
        
struct cast_struct {
            [FieldOffset(
0)]
            
public double d;
            [FieldOffset(
0)]
            
public int i;
        }
        
static unsafe int MyFloor2(double dval) {
            dval 
= dval - 0.499999999999;
            
const double magic = 6755399441055744.0;
            dval 
+= magic;
            
return *(int*)&dval;
        }
        
static void Main(string[] args) {
            Random rnd 
= new Random();
            
double[] x = new double[10000000];
            
for (int i = 0; i < x.Length; i++)
                x[i] 
= rnd.NextDouble() * 100000000;

            Stopwatch stop 
= Stopwatch.StartNew();
            
//Array.Sort(x);
            
//x = new double[] {1,2,3,4,5};
            
//Array.ForEach(x, d => Console.WriteLine("{0}",d));


            Console.WriteLine(
"最大间隙为:{0},time={1}",
                maxgap(x.Length, x), stop.ElapsedTicks);
            stop.Reset();
            stop.Start();
            Console.WriteLine(
"最大间隙为:{0},time={1}",
                maxgap2(x), stop.ElapsedTicks);
            Console.ReadKey();
        }
        
static double maxgap2(double[] x) {
            Array.Sort(x);
            
double tmp = 0, left = x[0];
            
for (int i = 1; i < x.Length; i++) {
                
double thisgap = x[i] - left;
                left 
= x[i];
                
if (thisgap > tmp) tmp = thisgap;
            }
            
return tmp;
        }
        
static double maxgap(int n, double[] x) {
            
double minx = x[mini(n, x)], maxx = x[maxi(n, x)];

            
//用n-2个等间距的点分割区间[minx,maxx]
            
//产生n-1个桶,每个桶i中用high[i]和low[i]
            
//分别存储桶i的数中的最大数和最小数
            int[] count = new int[n - 1];
            
double[] low = new double[n - 1];
            
double[] high = new double[n - 1];

            
//桶初始化
            for (int i = 0; i < n - 1; i++) {
                count[i] 
= 0;
                low[i] 
= maxx;
                high[i] 
= minx;
            }

            Stopwatch stop 
= new Stopwatch();
            stop.Start();
            
//将n个数放进n-1个桶中
            for (int i = 0; i < n; i++) {
                
//底下这句不知道是基于什么数学原理能把一个数
                
//确定的放入它自己所属的桶里??
                
//int bucket = MyFloor(((n - 2) * (x[i] - minx) / (maxx - minx)));
                int bucket = MyFloor2(((n - 2* (x[i] - minx) / (maxx - minx)));
                
//int bucket = (int)((n - 2) * (x[i] - minx) / (maxx - minx));
                count[bucket]++;
                
if (x[i] < low[bucket]) low[bucket] = x[i];
                
if (x[i] > high[bucket]) high[bucket] = x[i];
            }
            Console.WriteLine(
"入桶时间:{0}",stop.ElapsedTicks);
            
//此时除了maxx和minx外的n-2个数放在n-1个桶中
            
//由鸽舍原理可知,至少有一个桶是空的
            
//这意味着最大间隙不会出现在同一个桶的两个数之间
            
//对每个桶做一次线性扫描即可找出最大间隙
            double tmp = 0, left = high[0];
            
for (int i = 0; i < n - 1; i++) {
                
if (count[i] != 0) {
                    
double thisgap = low[i] - left;
                    
if (thisgap > tmp) {
                        tmp 
= thisgap;
                        Console.WriteLine(
"left = {0},thisgap = {1}", left, tmp);
                    }
                    left 
= high[i];
                }
            }

            
return tmp;
        }

        
static int mini(int n, double[] x) {
            
double temp = x[0];
            
int k = 0;
            
for (int i = 0; i < n; i++) {
                
if (x[i] < temp) {
                    temp 
= x[i];
                    k 
= i;
                }
            }
            
return k;
        }
        
static int maxi(int n, double[] x) {
            
double temp = x[0];
            
int k = 0;
            
for (int i = 0; i < n; i++) {
                
if (x[i] > temp) {
                    temp 
= x[i];
                    k 
= i;
                }
            }
            
return k;
        }
    }
}

经测试,在release模式下,输入数据在100w时,maxgap只比maxgap2快1秒,虽然只是快1秒,甚至debug模式下还要比maxgap2还慢,但算法的复杂度比maxgap2要简单很多。后来查了下原因,主要是因为c#的下取整比较耗时,因此造成入桶的时间占总体耗时的百分之八九十,后来在网上找了一些浮点截断成整形的快速算法,发现和c#自带的int强转double的性能差不了多少,汗了,谁要有更好的Floor算法给提供下。

参考链接:
float与double的范围和精度
http://www.cnblogs.com/tekson/archive/2009/07/16/1524604.html
浮点数到整数的快速转换
http://www.gamergroup.cn/html/38/n-4338.html
代码优化-之-优化浮点数取整
http://blog.csdn.net/housisong/archive/2007/05/19/1616026.aspx
其中MyFloor是脑袋提供的,原题出自网上下载的一个《算法设计与实验题解.pdf》文件 【文章原创作者:韩国高防服务器 http://www.558idc.com/krgf.html 网络转载请说明出处】
上一篇:关于一道C#上机题的一点想法
下一篇:没有了
网友评论
<