Linkman的学习记录

我觉得还缺少一些东西，比如最小纪录时间和最大纪录时间。
在 最小纪录时间 段中最多只需要保存一个数据，加上其他一些算法就可以过滤掉部分噪音。噪音不单浪费空间时间，而且会在最终的数值分析阶段带来麻烦，因为一般都会选用好几套工业算法，噪音越多会使得各套工业算法结果的差越大。
在差值虽然不大于COMPRESS_RATE的情况下，如果持续N久（最大纪录时间）都没有一个纪录的话，可以考虑增加一个纪录点。这样可以用一点点的存储空间换取极大的数据精度。
选用最大纪录时间另一个考虑是，使得数据查询跨越的范围不会太大。如果一年的数据变化都不超过COMPRESS_RATE，那么查询前不久的数据的话，就需要翻到一年前的数据文件中。
每一个标签需要的最小纪录时间和最大纪录时间都不一样，需要咨询相关的工作人员。

还有像数字量、枚举量、模拟量、最小数据点、量程、刻度、各异常信号等信息估计你应该考虑了。

只是面试题呀，老兄！

对于死区压缩算法，我觉得PI使用的“旋转门”压缩算法比较好，和数据变化的同方向行走既能提高数据精度又能减少数据记录点。
可惜那是PI的专利，所以不可以明着宣传：）

如果不谈面试题，你的发言很有见地，谢谢了

rt

呵呵，我们是采用的改进型“旋转门”压缩算法

rt

局部变量我等你有空哦，你答应我的

当然，如果一个面试人员能对这两道题说三道四，那更是我们要找的人：）

是你说再给我打电话的呀？！
不过最近确实事比较多，msn吧

网络有点问题，上面回复多了一个：（

看不到你呀，加我吧：liaochangbin@hotmail.com

// SimpleTest.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <stdlib.h>
#include <math.h>

typedef struct stDataInfo
{
time_t nSecond; // 时间，以秒为单位
short nMill; // 毫秒
double fValue; // 值
} DataInfo;

typedef struct _LINK
{
const DataInfo * data;
_LINK * next;
} LINK;

LINK * NewLink()
{
LINK * ptr = (LINK*)malloc(sizeof(LINK));
if(ptr)
{
ptr->data = NULL;
ptr->next = NULL;
}
return ptr;
}


#define COMPRESS_RATE 1.0
bool NeedStore(const DataInfo * data, double last)
{
if (abs((data->fValue - last)) > COMPRESS_RATE)
return true;
return false;
}

int Compress(const DataInfo *pDataList, int nDataCount, DataInfo **pResultDataList)
{
if (*pResultDataList != NULL || pResultDataList == NULL || pDataList == NULL)
return -1;


LINK * header = NewLink();
LINK * current = header;
double last = 0;
const DataInfo * data = pDataList;
int count = 0;
for (int i = 0; i < nDataCount; i++, data++)
{
if (NeedStore(data, last))
{
current->data = data;
count++;
LINK * ptr = NewLink();
current->next = ptr;
current = ptr;
}
last = data->fValue;
}

*pResultDataList = (DataInfo *)malloc(sizeof(DataInfo) * count);
DataInfo * pResultIt = *pResultDataList;
current = header;
while (current->next != NULL)
{
memcpy(pResultIt++, current->data, sizeof(DataInfo));
LINK * temp = current;
current = current->next;
free(temp);
}
return count;
}

typedef struct stTimeInfo
{
time_t nSecond; // 时间，以秒为单位
short nMill; // 毫秒
} TimeInfo;




int DataCompare(const void * p1, const void * p2)
{
const DataInfo * d1 = (const DataInfo *)p1;
const DataInfo * d2 = (const DataInfo *)p2;
int test = (int)(d1->nSecond - d2->nSecond);
if (test == 0)
return (d1->nMill - d2->nMill);
return test;
}


#define DO_COMPARE(p1, p2) (*compare)(p1, p2)
typedef int (*compare_func)(const void *, const void *);

void * lower_bound(
   const void *key,
   const void *base,
   size_t num,
   size_t width,
   compare_func compare
   )
{
char *lo = (char *)base;
char *hi = (char *)base + (num - 1) * width;
char *mid;
size_t half;
int result;

while (lo <= hi)
{
if ((half = num / 2) != 0)
{
mid = lo + (num & 1 ? half : (half - 1)) * width;
result = DO_COMPARE(key, mid);
if (result == 0)
return mid;
else if (result < 0)
{
hi = mid - width;
num = num & 1 ? half : half-1;
}
else
{
lo = mid + width;
num = half;
}
}
else if (num)
{
return lo;
}
else
break;
}

return lo;
}

#define RET_SUCCESS  0 // 刚好找到对应的时间点
#define RET_NO_EQUAL  1 // 未找到对应的时间点，但找到两个时间之间的点，需要进行二分插值
#define RET_BEYOND_MIN  2 // 时间比最小时间小
#define RET_BEYOND_MAX  3 // 时间比最大时间大
#define RET_NO_DATA  4 // 数据列表无数据
#define RET_PARAMETER_ERROR 5 // 参数错误
int FindDataByTime(DataInfo *pDataList, int nDataCount, TimeInfo *pTime, double *pResultData)
{
if (nDataCount < 1)
return RET_NO_DATA;
if (!pDataList || !pTime || !pResultData)
return RET_PARAMETER_ERROR;

DataInfo key = {pTime->nSecond, pTime->nMill, 0};
DataInfo * pos = (DataInfo*)lower_bound(&key, pDataList, nDataCount, sizeof(DataInfo), DataCompare);
DataInfo * start = pDataList;
DataInfo * stop = pDataList + nDataCount - 1;
int result;
compare_func compare = DataCompare;

*pResultData = pos->fValue;

if (pos == start)
{
if (DO_COMPARE(&key, start) == 0)
return RET_SUCCESS;
else
return RET_BEYOND_MAX;
}
if (pos == stop)
{
if (DO_COMPARE(&key, stop) == 0)
return RET_SUCCESS;
else
return RET_BEYOND_MIN;
}

result = DO_COMPARE(&key, pDataList);
if (result == 0)
return RET_SUCCESS;
else
return RET_NO_EQUAL;
}

#include <iostream>
void PrintDataList(const DataInfo * data, int count)
{
for (int i = 0; i < count; i++, data++)
{
std::cout << data->nSecond << ":"  << data->nMill << "\t" << data->fValue << std::endl;
}
}


#define DATA_COUNT (100)

double rand_value()
{
return 100 + ((double) rand() / (double) RAND_MAX) * 3 - 1;
}

int _tmain(int argc, _TCHAR* argv[])
{
DataInfo datas[DATA_COUNT];
for (int i = 0; i < DATA_COUNT; i++)
{
datas[i].nSecond = i / 10;
datas[i].nMill = (i % 10);
datas[i].fValue = rand_value();
}


DataInfo * result = NULL;
int count = Compress(datas, DATA_COUNT, &result);


// Test find
TimeInfo key = {0, -1};
double value1 = 0;
double value2 = 0;

int ret1 = FindDataByTime(result, count, &key, &value1);
int ret2 = FindDataByTime(datas, DATA_COUNT, &key, &value2);
std::cout << ret1 << "\t" << value1 << std::endl;
std::cout << ret1 << "\t" << value2 << std::endl;

free(result);
return 0;
}

/*
写了1个小时多一点 1个小时还是有点难度 主要是 lower_bound 用的太熟了,写个C版花了些时间调试

另外 作为招聘的题目 还是应该给个生成模拟数据的函数和一些调试函数

再者
1 不需要更改的参数 特别是指针 建议传成const 这样看着舒服一些,也能避免一些潜在的问题
2 由函数传进的指针要重分配,还是传个 ** 比较好

*/

李嘉是有心人呀，请与我联系吧

对第一题李嘉的答案：
我认为水平很一般

/*
对第一题李嘉的答案：
我认为水平很一般，主要问题表现在：
if (*pResultDataList != NULL || pResultDataList == NULL || pDataList == NULL) 是有问题的
应用　ASSERT（）　或　ATLASSERT（）做为判断


LINK * header = NewLink(); 
没有对内存分配失败处理（稳定性差）

分配了两份内存处理（LINK　和*pResultDataList）效率是非常差的。
对于实时库这样的代码肯定是不合格的
我认为可一次分配好 nDataCount内存
*pResultDataList = (DataInfo *)malloc(sizeof(DataInfo) * nDataCount); 
*/



//ppData返回保存值
//dwSize返回保存值个数
//方法返回HRESULT运行状态
HRESULT Compress( const DataInfo* parrData, DWORD dwCount, DataInfo** ppData, DWORD& dwSize ) throw()
{
ATLASSERT( parrData != NULL && ppData == NULL );

HRESULT hr = S_OK;
size_t size = sizeof( DataInfo );
DataInfo* pData = reinterpret_cast< DataInfo* > ( malloc(size * dwCount) );
if( pData == NULL )
return E_OUTOFMEMORY;

DWORD dwAdded = 0;
for( DWORD i = 0; i < dwCount; i++ )
{
//比较是否要保存（代码略）
*(pData + dwAdded) = parrData[i];
++dwAdded;
}

*ppData = pData;
dwSize = dwAdded;

return hr;

}

谢谢老周捧场。

你们都没认真审题，第一题已说得很清楚：pResultDataList已由调用者分配内存，不需要在内部分配内存。

我的评价：
李嘉
1、没有实时数据库的开发经验；
2、对程序性能方面的考虑确实少了些；
3、对C语法用得比较熟练；
4、编程思路比较严密；
5、程序比较规范；
6、心态已比较成熟（我认为能从一段代码中看出一个人的心态）；
7、工作比较主动；

对老周的代码呢，我的评价：
1、好的方面就不说了；
2、感觉被微软洗脑了，呵呵，太多VC专用语法和定义；

“由调用者申请了空间，最大长度为nDataCount”

这个还真没看到。。。
---------------------------

“分配了两份内存处理（LINK　和*pResultDataList）效率是非常差的。 ”

这个就不敢苟同了，做一个LINK结构的目的就是为了节省内存
sizeof(LINK) == 8 
sizeof(DataInfo) = 14
而且，考虑DataInfo可能会有变化，例如2或多个double，这样，sizeof(DataInfo)会更大，考虑这样的情况，假设有N个数据要做Compress，压缩比率大概是0.4,设sizeof(DataInof)为w
我的实现需要的内存数目是
     M1 = N*sizeof(LINK) + 0.4*N*sizeof(DataInfo) = 8N + 0.4Nw 
分配一个大缓存需要的内存数目为
    M2 = wN
大约当 sizeof(DataInof) == 18 之后，M1就会比M2小的多，在此之前，两个数据是差不多的，以下是一些数据，当N=10000
sizeof(DataInof） M1           M2
14                     136000.0 140000
24                     176000.0 240000
所以，为了代码能够有更强的适应性，还是做了一个LINK。

/* 
对第一题李嘉的答案： 
我认为水平很一般，主要问题表现在： 
if (*pResultDataList != NULL || pResultDataList == NULL || pDataList == NULL) 是有问题的 
应用　ASSERT（）　或　ATLASSERT（）做为判断 


LINK * header = NewLink();  
没有对内存分配失败处理（稳定性差） 

分配了两份内存处理（LINK　和*pResultDataList）效率是非常差的。 
对于实时库这样的代码肯定是不合格的 
我认为可一次分配好 nDataCount内存 
*pResultDataList = (DataInfo *)malloc(sizeof(DataInfo) * nDataCount);  
*/ 

1、 ASSERT 是在debug版本下才有用吧，所以拿这个来说事，我感觉不是重点，这个题目重点考察算法，而不是工程能力。


2、LINK * header = NewLink();  
没有对内存分配失败处理（稳定性差） 
new可能 == null 
这个东东，我从来没有遇到过，也不知道哪位高手遇到过。
反正我从来不用。至少在windows的机器上，windows崩溃了，我也不会说new不出来东西

3、分配了两份内存处理（LINK　和*pResultDataList）效率是非常差的。
分配两分比分配一份差，还觉得有点道理。但是说非常差，我就不认同
。
3.1 分配一份的速度比两份快，但是在内存碎片多的情况下，会有个例。就是分配+回收的时间会更多。delete操作的耗时比new多很多
3.2 如果分配两分效率非常差，那么分配一份就能好很多。实际上，瓶颈不是两份的问题
3.3 如果一个地方频繁的需要new内存，非常小，而且很快就回收。应该考虑用内存池

对老周的代码呢，我的评价： 
1、好的方面就不说了； 
2、感觉被微软洗脑了，呵呵，太多VC专用语法和定义；

每个人都会有自己的看法，而且不可能完全相同。
我说点我的看法
“感觉被微软洗脑了，呵呵，太多VC专用语法和定义；“
写VC程序多了，这个习惯自然就出来了。而且，遇到一个专门搞VC下开发的主管，如果是自己的风格或者其他的风格，他说不定会觉得你没有工作经验，怎么风格这样子。（哈哈，因为我遇到过，感觉他还真会说话）

另外，我想请问，李嘉这个程序是否运行检查过结果了？
我给两组数据试试看
0 1 2 3 4 5 6 7 8 9
0 0.5 1.0 1.5 2.0 2.5 3.4
也请 Linkman的学习记录  给出这两组数据的正确答案

-0.9 -0.1 0.1 0.6 1.1 1.5

对于一个实时库核心程序。对任何可能的错误都要去处理，这样才能保证程序7X24时间运行。
“由调用者申请了空间，最大长度为nDataCount” 
这个题目说了。我知道。不说题目，正规的函数定义我那个应是对的。它不会让其他人使用这个函数产生理解上错误。

sizeof(DataInfo) = 14 　？　16

ATLASSERT( parrData != NULL && ppData == NULL ); 使用，如果只对这个函数来说，它是不能保证在RELEASE版传入参数合法。但从一个系统程序来说，如果你写的程序在RELEASE版下都不能保证所传入的主要参数是合法的（如！NULL），也说明你的程序稳定性就不能保证。

(*pResultDataList != NULL   ?

对LINK * header = NewLink();  设要分配　1024　＊　1024（100万个）DataInfo对象是16M内存，是一次分配好还是做100万次分配（最坏情况），对任何一次分配失败都导致函数处理中止。你愿意做一次内存分配失败处理还是做100万次内存处理。一次内存分配和做100万次内存分配谁用的时间多且内存碎片少。学过操作系统内存管理应能好理解。

答题的人真不少呀！
哈哈！说多了，对不起了。
以上只是发表个人的理解吧。

"对任何一次分配失败都导致函数处理中止"
关于new不出内存要做判断，这个我在n个地方见到了
但是就是从来没有听人说起过，他的程序遇到了这种情况。
另外，当一个程序真的new不出内存了，我不知道这个程序还能跑不；不知道操作系统崩溃了多久。
（以上针对目前的服务器，不涉及小型机等高端服务器）

使用链表可以节省空间。当是相比一次new最大空间，效率肯定下降，因为大家说这个实时数据库性能要求高。

可是这里我有一个疑问，如果要这么讲究，那么数据量非常大，比方说1G，甚至2G以上。我相信这个程序理论性能上会很快。但是在现在的机器上会跑得很累。因为应用程序一般无法申请到这么多实内存，多数是虚拟内存。

另外如果是多线程执行任务，这种方法更糟糕。
一个系统不是只有一个程序在跑，每个程序，还是应该注意自己的内存。特别是数据库这种基础软件。
如果真要讲究的话，我想new一个和new一万个都不是最佳的答案，要选用内存池的处理方式。

3、分配了两份内存处理（LINK　和*pResultDataList）效率是非常差的。 
分配两分比分配一份差，还觉得有点道理。但是说非常差，我就不认同
这里只是针对pResultDataList的内存说的。而不是说LINK。

“1次内存分配和做100万次内存分配谁用的时间多且内存碎片少。学过操作系统内存管理应能好理解。 “
这个我想可以找出例子来， 使到1次分配内存更慢，就是内存碎片达到一定程度的特例。



其实说了半天，我觉得大家总爱挑毛病。
我一直疑惑的是，怎么没人去思考程序算法对不对呢。

至于 ATLASSERT 这些习惯。我是觉得，在实际项目中，他的作用也是有限的，而且同样可以有特例，来说明他的作用是0。
给一个也指针，照样可以使程序崩溃。要真正更稳定，C#那种对象引用的方式更安全，但是要付出性能作为代价。


说到new不判断null，不用ASSERT ，这里我介绍另外一种更无法让人接受的思想，好像来自GOOGLE。一段硬盘上的数据变化了，要更改。一般做法是重写到硬盘，但这不是最好的方式；废弃这段数据空间，写到新的地方，这样子快捷而且安全。

呵呵！这种方式，不是普通程序可以使用的。但是他真是有应用的。

再插几句
一个程序如果稳定，但是无法达到性能要求，那么这个程序白写了
一个程序如果存在安全隐患，但是性能达到要求，那么至少可以交出去
当然，每个公司都追求安全和高效的程序

这个题目一直没有看出，他考察程序的性能还是稳定性。
实时数据库，同样在性能和稳定性有要求。作为一个面试者，我可能对这两种要求写不同的代码。

再看了两位的代码。感觉，一个是省内存，一个是性能较好。但是这两者，都会在一些情况下表现出不好的性能
链表：内存分配很多很散的情况下，free的时候耗时较多
大空间：数据量一大，不但影响系统整体性能，而且会突然很慢。

或者用线程池好点，但是相信代码一贴上，各位还是能找到他的缺陷。
如一般小数据量的情况下，性能会有1％－－5％的下降。内存空间会有浪费，还可能同样导致开大内存性能下降。

我如果在一个公司面试，估计写的代码会和李嘉差不多。而且我不会判断==null，会让上层程序去判断。但是我的算法会和李嘉不同。
答案也不一样

关于这个面试题我就关注到这里。谢谢大家

说一句，我不是来面试的。大家说了很多。小康 说的有些道理，当M数量极达到上百万级，一次分配内存和链内存都有问题的，M的最值应在设计时应有所考虑。
我还是第一次在网上交流开发技术。和 Linkman关系不错，才来捧捧场。
哈哈！

如果要投入到实际的应用 按照现有实现 还是要考虑程序的性能 比如多次new/delete的开销 不过这些不是没有办法解决

其他 我觉得算法应该是和数据无关的 算法只和数据结构相关 让自己编写的算法函数能够尽可能多的用在各种地方 这也是我编写代码考虑的一个习惯 所以 在自己的实现里，如过方法可以处理同样多的A数据但不能处理B数据，这是我不能容忍的

不过以上的对于本例有点跑题了，因为题目说已经分配好内存了，在这样的情况下，使用链表是没有任何意义的，没有看清题目，也就是没搞清需求，这个BUG，还是大了一些。

另外 sizeof(DataInfo) == 14 在 2,1 align 通过
事实上 总是应该定义 8 align 的结构，由编译器决定一个结构的大小总是感觉上不太好

To 小康
程序的结果我做了一些简单的测试
int ret1 = FindDataByTime(result, count, &key, &value1); 
int ret2 = FindDataByTime(datas, DATA_COUNT, &key, &value2);
这两个分别是对没有压缩的数据和压缩过的数据做查找看是否返回一致

来的都是朋友，只讨论技术问题。

老周，我与你熟，所以只说你：你那句"我认为水平很一般"，有点伤人自尊呀。

你也是团队领导，以后还会作更大团队的领导，对部下的评价应该只论事，不论人。呵呵

是呀，对不住大家了。向大家道个歉。Linkman说的对，来的都是朋友。

其他 我觉得算法应该是和数据无关的 算法只和数据结构相关 让自己编写的算法函数能够尽可能多的用在各种地方 这也是我编写代码考虑的一个习惯

理论上，算法和数据结构没有关系，但是算法和数据结构要放在一起考虑。程序=算法＋数据结构。算法，数据结构可以单独存在，但是放在一起，才能成为一个程序

“算法函数能够尽可能多的用在各种地方” 这个我不知道怎么去理解。算法不是通用性就好，要结合实际需要来看问题吧。

另外说的测试问题，是指你的程序，针对数据
100 100.5 110  109.9 109.4 108.9 109
能否有这个结果：100 110 108.9

大家讨论得这么热烈，我加贴两位朋友的代码，看各位朋友有什么评价。
其一：

#include <iostream>
#include <list>
#include <algorithm>
#define COMPRESS_RATE 1

using namespace std;

int Compress(list<double>&src,int nDataNum,list<double>&dest);
struct print
{
void operator()(double x)
{
cout<<x<<endl;
}
};
int main()
{
list<double>src,dest;
double temp;
for( int i = 0; i < 4; ++i)
{
cout<<"Enter a double"<<endl;
cin>>temp;
src.push_back(temp);
}
Compress(src,3,dest);
for_each(dest.begin(),dest.end(),print());
}

int Compress(list<double>&src,int nDataNum,list<double>&dest)
{
list<double>::const_iterator iterBegin,iterEnd;
iterBegin = src.begin();
dest.push_back(*iterBegin);
nDataNum--;
iterEnd = iterBegin;advance(iterEnd,2);
while(iterEnd != src.end())
{
if((*iterEnd - *iterBegin) > COMPRESS_RATE || (*iterEnd - *iterBegin) < -(COMPRESS_R
ATE))
{
dest.push_back(*(++iterBegin));
++iterEnd;
nDataNum--;
}
else
{
++iterBegin;++iterEnd;
}
}

dest.push_back(*(--iterEnd));
nDataNum--;
return nDataNum;
}

我的结果是
100 100.5 110  109.9 109.4 108.9 109 -> 109.4 108.9

产生的原因是 将 “只有前后数据变化的绝对值超过常量COMPRESS_RATE” 中的前后理解为相邻的数据

其二：
#define COMPRESS_RATE 0.1

int Compress(double *pDataList, int nDataCount, double *pResultDataList)
{
assert(pDataList != NULL && nDataCount >= 0);
if(nDataCount == 0)
return 0;
pResultDataList[0] = dDataList[0];
int nCount = 1, size = 1;
double *pri = pResultDataList;
double *temp = pDataList + 1;
while(nCount < nDataCount)
{
if(abs(*temp, *pri) >= COMPRESS_RATE)
{
*(++pri) = *temp;
temp++;
size++;
}
nCount++;
temp++;
}
return size;
}

另外，大家为何不评论一下第二题呢，第二题比第一题简单？

第一个
1 if((*iterEnd - *iterBegin) > COMPRESS_RATE || (*iterEnd - *iterBegin) < -(COMPRESS_R 
ATE)) 
----
这个的意图是优化不使用库函数abs，不过我记得好像fabs应该是一个CPU指令（我对汇编基本没了解），再有，||两边的两次浮点减不知道现在的编译器能不能优化成一个。
2 程序的逻辑我认可zhou已经贴出来的，所以觉得好像不用这么多iteration的++
第二个
当if成立了 temp++,出来还要temp++，逻辑没搞清楚，不敢断言是不是有问题，不过觉得好像会出问题。

编一个好的二分查找程序，也不是很容易的事情，请见：
http://blog.csdn.net/drzhouweiming/archive/2007/04/12/1562717.aspx

我的结果是 
100 100.5 110  109.9 109.4 108.9 109 -> 100,110,

产生的原因是 将 “只有前后数据变化的绝对值超过常量COMPRESS_RATE” 中的前后理解为相邻的数据 

------------------
上边的那个粘贴错了，楼主帮忙删一下

#include "TIME.H"

#define RET_SUCCESS 0 // 刚好找到对应的时间点
#define RET_NO_EQUAL 1 // 未找到对应的时间点，但找到两个时间之间的点，需要进行二分插值
#define RET_BEYOND_MIN 2 // 时间比最小时间小
#define RET_BEYOND_MAX 3 // 时间比最大时间大
#define RET_NO_DATA 4 // 数据列表无数据
#define RET_PARAMETER_ERROR 5 // 参数错误

#define ORDER_A 1 // 升序
#define ORDER_D 2 // 降序

#define ORDER_BY_TIME 1
#define ORDER_BY_VALUE 2

#define COMPRESS_RATE 1.0


typedef struct stDataInfo
{
time_t nSecond; // 时间，以秒为单位
short nMill; // 毫秒
double fValue; // 值
} DataInfo;



typedef struct stTimeInfo
{
time_t nSecond; // 时间，以秒为单位
short nMill; // 毫秒
} TimeInfo;


int Compress(DataInfo *pDataList, int nDataCount, DataInfo *pResultDataList);
int FindDataByTime(DataInfo *pDataList, int nDataCount, TimeInfo *pTime, double *pResultData);
int SortList(DataInfo *pDataList, int nDataCount, int OrderBy,int SortOrder);

// twoArithmetic.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include  <math.h>
#include <memory>
#include "twoArithmetic.h"

int main(int argc, char* argv[])
{
DataInfo data[7];

for (int i = 0; i < 7; i++)
{
data[i].nSecond = i * 11;
data[i].nMill = i * 11;
}
data[0].fValue = 100;
data[1].fValue = 100.5;
data[2].fValue = 110;
data[3].fValue = 109.9;
data[4].fValue = 109.4;
data[5].fValue = 108.9;
data[6].fValue = 109;

for (i = 0; i < 7; i++)
{
printf("data[%d]\tvalue:%.1f\tSecond:%d\tMill:%ld\n", 
i, 
data[i].fValue,
data[i].nSecond,
data[i].nMill);
}

TimeInfo target;
double resultV = 0;
target.nMill = 40;
FindDataByTime(data, 7, &target, &resultV);
printf("\nFind Result_Value:%.1f\n", resultV);

int t = 7;
int tt;
DataInfo resultData[7];
tt = Compress(data, t, resultData);
printf("\nCompress Result, len:%d:\n", tt);
for (i = 0; i < tt; i++)
{
printf("resultData[%d]\tvalue:%.1f\tSecond:%d\tMill:%ld\n", 
i, 
resultData[i].fValue,
resultData[i].nSecond,
resultData[i].nMill);
}
return 0;
}
/**********************************************************************
* 函数名称： Compress
* 功能描述： 压缩算法
* 输入参数： DataInfo *pDataList, int *nDataCount
* 输出参数： DataInfo *pResultDataList
* 返 回 值： int 运算结果
* 其它说明： int *nDataCount,双向参数。
作为入参，表示输入的数据个数
作为出参，表示压缩后的结果数
* 修改日期        版本号     修改人           修改内容
* -----------------------------------------------
* 2007/4/10        V0.01      WZG             创建 
***********************************************************************/
int Compress(DataInfo *pDataList, int nDataCount, DataInfo *pResultDataList)
{
// 按值大小创建索引
SortList(pDataList, nDataCount, ORDER_BY_VALUE, ORDER_A);
double prev_Value = 0;
prev_Value = pDataList->fValue;
memcpy(pResultDataList, pDataList, sizeof(DataInfo));
pDataList++;
pResultDataList++;
double newCount = 1;

// 开始压缩
for (int i = 1; i < nDataCount; i++)
{
if (fabs(pDataList->fValue - prev_Value) > COMPRESS_RATE)
{
newCount++;
memcpy(pResultDataList, pDataList, sizeof(DataInfo));
pResultDataList++;
prev_Value = pDataList->fValue;
}
pDataList++;
}

SortList(pResultDataList, newCount, ORDER_BY_TIME, ORDER_A);

return newCount;
}

/**********************************************************************
* 函数名称： FindDataByTime
* 功能描述： 查找算法
* 输入参数： DataInfo *pDataList 为已压缩的数据列表，按时间排序, 
 int nDataCount 为数据个数
 TimeInfo *pTime 为查询的时间
* 输出参数： double *pResultData
* 返 回 值： int 运算结果
* 其它说明： 无
* 修改日期        版本号     修改人           修改内容
* -----------------------------------------------
* 2007/4/10        V0.01      WZG             创建 
***********************************************************************/
int FindDataByTime(DataInfo *pDataList, int nDataCount, TimeInfo *pTime, double *pResultData)
{
// 二分查找
// 假定按时间升序排序
DataInfo* found;
DataInfo* begin_R;
DataInfo* end_R;
DataInfo* listBaseAddr;

// 是否参数错误
if (pDataList == NULL || nDataCount < 0 || pTime == NULL)
{
return RET_PARAMETER_ERROR;
}

// 数据列表是否无数据
if (nDataCount == 0)
{
return RET_NO_DATA;
}

listBaseAddr = pDataList;
begin_R      = pDataList;
end_R        = pDataList + (nDataCount - 1);
found        = pDataList + (nDataCount - 1) / 2;

// 时间比最小时间小
if (pTime->nMill < begin_R->nMill)
{
*pResultData = begin_R->fValue;
return RET_BEYOND_MIN;
}
// 时间比最大时间大
if (pTime->nMill > end_R->nMill)
{
*pResultData = end_R->fValue;
return RET_BEYOND_MAX;
}

// 是否在头尾
if (pTime->nMill == begin_R->nMill)
{
found = begin_R;
*pResultData = found->fValue;
return RET_SUCCESS;
} 
else if(pTime->nMill == end_R->nMill)
{
found = end_R;
*pResultData = found->fValue;
return RET_SUCCESS;
}

while (end_R->nMill >= begin_R->nMill)
{
if (pTime->nMill == found->nMill)
{
*pResultData = found->fValue;
return RET_SUCCESS;
} 
else if (pTime->nMill > found->nMill)
{
begin_R = found;
if (abs(end_R - begin_R) == 1)
{
*pResultData = found->fValue;
return RET_NO_EQUAL;
}
found = found + (end_R - begin_R) / 2;
}else if (pTime->nMill < found->nMill)
{
end_R = found;
if (abs(end_R - begin_R) == 1)
{
*pResultData = found->fValue;
return RET_NO_EQUAL;
}
found = found - (end_R - begin_R) / 2;
}
}

// 未找到对应的时间点，但找到两个时间之间的点，需要进行二分插值
*pResultData = found->fValue;
return RET_NO_EQUAL;
}

/**********************************************************************
* 函数名称： SortList
* 功能描述： 查找算法
* 输入参数： DataInfo *pDataList 为已压缩的数据列表，按时间排序, 
 int nDataCount 为数据个数
 TimeInfo *pTime 为查询的时间
* 输出参数： double *pResultData
* 返 回 值： int 运算结果
* 其它说明： 无
* 修改日期        版本号     修改人           修改内容
* -----------------------------------------------
* 2007/4/10        V0.01      WZG             创建 
***********************************************************************/
int SortList(DataInfo *pDataList, int nDataCount, int OrderBy,int SortOrder)
{
DataInfo temp;
DataInfo *p_temp1;
DataInfo *pBase;

pBase = pDataList;

if (OrderBy == ORDER_BY_TIME)
{
if (SortOrder == ORDER_A)
{
for (int i = nDataCount - 2; i > 0; i--)
{
pDataList = pBase;
for (int j = 0; j <= i; j++)
{
p_temp1 = (pDataList + 1);
if (pDataList->nMill > p_temp1->nMill)
{
temp = *pDataList;
*pDataList = *p_temp1;
*p_temp1 = temp;
}
pDataList++;
}
}
}
else
{
for (int i = nDataCount - 2; i > 0; i--)
{
pDataList = pBase;
for (int j = 0; j <= i; j++)
{
p_temp1 = pDataList + 1;
if (pDataList->nMill < p_temp1->nMill)
{
temp = *pDataList;
*pDataList = *p_temp1;
*p_temp1 = temp;
}
pDataList++;
}
}

}
} 
else if(OrderBy == ORDER_BY_VALUE)
{
if (SortOrder == ORDER_A)
{
for (int i = nDataCount - 2; i > 0; i--)
{
pDataList = pBase;
for (int j = 0; j <= i; j++)
{
p_temp1 = pDataList + 1;
if (pDataList->fValue > p_temp1->fValue)
{
temp = *pDataList;
*pDataList = *p_temp1;
*p_temp1 = temp;
}
pDataList++;
}
}
}
else
{
for (int i = nDataCount - 2; i > 0; i--)
{
pDataList = pBase;
for (int j = 0; j <= i; j++)
{
p_temp1 = pDataList + 1;
if (pDataList->fValue < p_temp1->fValue)
{
temp = *pDataList;
*pDataList = *p_temp1;
*p_temp1 = temp;
}
pDataList++;
}
}

}
}

return 0;
}

用的时间比较长，大概花了3个小时。对VC也只是皮毛而已。知道自己写得不好。可是，既然写出来，还是交上来，让LinkMan看看比较好。

忍不住又回来看了。
有两个经验，
第一个，浮点误差，不是fabs就好，还需要有更多判断。
第二个，用stl的vector，数据量一大，会比直接new，delete出来的还要慢。

编一个好的二分查找程序，也不是很容易的事情，请见： 
http://blog.csdn.net/drzhouweiming/archive/2007/04/12/1562717.aspx 

看了这个文章，看到一半觉得好无聊。纯粹是在吸引眼球。
我也可以找一个二分算法需求的例子，保证可以难道50％以上的中大硕士生（我只了解中大的水平）。但是难点是在二分算法在程序实现的建模，而不是二分算法的本身的实现。

作者举的例子不无道理，但是却掩盖了问题本身，他是在做一个有各种条件的二分程序，难度来于那些多出来的条件，而不是二分算法本身。

阿饭将你的代码的源文件给我发过来吧，这样看得有点晕。
linkman2002@sina.com.cn
请顺便将你的简历发过来

double operator - ( DataInfo& Data, TimeInfo& Time ) throw()
{
return Data.nSecond * 1000 + Data.nMill - 
( Time.nSecond * 1000 + Time.nMill );

}


double operator - ( TimeInfo& Time, DataInfo& Data ) throw()
{
return  Time.nSecond * 1000 + Time.nMill - 
( Data.nSecond * 1000 + Data.nMill );

}


double operator - ( DataInfo& Data1, DataInfo& Data2 ) throw()
{
return  Data1.nSecond * 1000 + Data1.nMill - 
( Data2.nSecond * 1000 + Data2.nMill );

}

int FindDataByTime(DataInfo *pDataList, int nDataCount, TimeInfo *pTime, double *pResultData)
{
if( pDataList == NULL ||
nDataCount < 0 ||
pTime == NULL ||
pResultData == NULL 
)
return RET_PARAMETER_ERROR;

/////////////////////////////////////////
if( nDataCount == 0 )
return RET_NO_DATA;

////////////////////////////////////////////

if( 0 < pDataList[0] - *pTime )
{
*pResultData = pDataList[0].fValue;

return RET_BEYOND_MIN;
}

/////////////////////////////////////////////////////////////
if( 0 < *pTime - pDataList[nDataCount - 1] )
{
*pResultData = pDataList[nDataCount - 1].fValue;

return RET_BEYOND_MAX;
}

////////////////////////////////////////////////////////////

int nFirst = 0;
int nEnd = nDataCount - 1;
while( 1 < nEnd - nFirst )
{
double dTime = *pTime - pDataList[nFirst];
double dDisTime = pDataList[nEnd] - pDataList[nFirst];

int nIdx = nFirst + int ( (nEnd - nFirst + 1) * (dTime / dDisTime) );
ATLASSERT( nIdx <= nEnd );

if( 0 < pDataList[nIdx] - *pTime )
{
nEnd = nIdx;
}
else if( 0 < *pTime - pDataList[nIdx] )
{
nFirst = nIdx;
}
else
{
*pResultData = pDataList[nIdx].fValue;

return RET_SUCCESS;
}


}//while
//////////////////////////////////////////////////////////////

if( nFirst == nEnd )
{
ATLASSERT( nDataCount == 1 );
*pResultData = pDataList[nFirst].fValue;

return RET_SUCCESS;
}


ATLASSERT( 1 < nEnd - nFirst );
//二分插值
double dTime = *pTime - pDataList[nFirst];
double dDisTime = pDataList[nEnd] - pDataList[nFirst];

*pResultData = ( pDataList[nEnd].fValue - pDataList[nFirst].fValue ) 
* ( dTime / dDisTime );

return RET_NO_EQUAL;

}

ATLASSERT( 1 < nEnd - nFirst ); 
//二分插值 
应是
ATLASSERT( 1 ＝＝ nEnd - nFirst ); 
//二分插值 

int nIdx = nFirst + int ( (nEnd - nFirst + 1) * (dTime / dDisTime) ); 
修正[0,1]：
int nIdx = nFirst + int ( (nEnd - nFirst) * (dTime / dDisTime) ); 

老周赶快去干活。
没事写什么程序啊。
没什么意思。
我家装修了，改天过来坐坐。

写程序没什么意思，尤其是不挣钱的程序。

我曾是个证券行业的网管

用过的柜台系统做报表统计的都很慢
但不可能让软件提供商去做大的改动(一升级就出事,这年头证券的东西老升级)

现在似乎流行集中,财务软件好多都搞远程的,很多行业软件也是,但实际使用中,远程带宽比本地的要小的多(毕竟专线的是少数,钱贵也浪费)

提两点建议,不知对不对

1 中心端搞个临时库,用于缓存插入记录,以减少网络带宽不足对其他查询用户的影响
2 各分公司(独立核算的单位)数据在中心端分库存放,再搞个库做总的索引

我对这些都不是很熟悉，学习。

代码要是稍加注释，那就更好懂了。