VBGood网站全文搜索 Google

搜索VBGood全站网页(全文搜索)
首页 - 经验之谈 - 探讨高效的排序合并算法
发表评论(0)作者:, 平台:, 阅读:10284, 日期:2000-05-21
探讨高效的排序合并算法





最近在编写一个股票信息处理系统时遇到了这样一个问题:每个股票都要对一大批指标数据进行排序,同时合并其中相同的数据。由于每天都要对上千个股票运算一遍,所以必须提高运算效率。

我先用传统的方法解决这个问题,经过比较,选用了较为简单的和高效的排序方法——“快速排序”,具体算法可参考数据结构等有关书籍。对所有数据排序后再合并相同数据,合并程序较为简便,我开始时采用了这种方法,但后来发现对于这些的数据,先合并后排序速度更快,因为有大量相同的数据。合并是采用“标记”算法,具体如下:(设数据已存放在sData()数组中 ,结果存到Queryp()数组,Amount是数据个数)

'把相同元素置 0

For i = 1 To Amount

If sData(i) <> 0 Then

For j = i + 1 To Amount

If sData(i) = sData(j) Then sData(j) = 0

Next j

End If

Next i

'删除相同元素

Queryp(1) = sData(1)

k = 1

For i = 2 To Amount

If Not (sData(i) = 0) Then

k = k + 1

Queryp(k) = sData(i)

End If

Next i

kMax = k

ReDim Preserve Queryp(kMax)

虽然这样使得运算速度有所高,但是仍然要进行大量的循环运算,占据了程序大部分的运算时间。于是我一直在寻觅一种更为高效的算法。

功夫不负有心人,在仔细分析数据的特征,比较了多种方案之后,我终于找到了一种相当成功的算法,原来要3到4秒的运算缩短到仅需0.1到0.2秒。

我遇到的数据具有以下特征:①相同数据很多,②最大、最小数之间相差不到3,③都是带两位小数的正数。

针对数据的特征,我采用了以下算法:

步骤:

1. 用一个循环找出整数和小数部分的最大、最小值。小数部分的最大、最小值乘以100转为整数。

2. 定义一个二维数组,下标范围分别是整数和小数部分的最小值到最大值。

3. 再用一个循环把所有源数据填入刚才定义的二维数组,填写规则是,源数据的整数和小数部分分别对应二维数组的两个下标。例如,“13.51"填到“A(13,51)"中。

4. 最后顺向或逆向读取二维数组中的非零数据即可得到从小到大或从大到小排列的数据,而且不会含有重复数据。

用VB 编写的程序如下:

'****密集型数据处理****

Dim i As Long, j As Long, k As Long, kMax As Long

Dim Queryp() As Single

ReDim Queryp(Amount)

Dim IntegerPart As Integer, DecimalPart As Integer

Dim IPmax As Integer, IPmin As Integer

Dim DPmax As Integer, DPmin As Integer

Dim DiffDataArray()

'读取数据

ReadData

IPmax = 0: IPmin = 1000

DPmax = 0: DPmin = 99

For i = 1 To Amount

' 找整数和小数部分的最大、最小值

IntegerPart = Int(sData(i))

DecimalPart = (sData(i) - IntegerPart) * 100

If IntegerPart > IPmax Then

IPmax = IntegerPart

ElseIf IntegerPart < IPmin Then

IPmin = IntegerPart

End If

If DecimalPart > DPmax Then

DPmax = DecimalPart

ElseIf DecimalPart < DPmin Then

DPmin = DecimalPart

End If

Next i

ReDim DiffDataArray(IPmin To IPmax, DPmin To DPmax)

'填入数据

For i = 1 To Amount

IntegerPart = Int(sData(i))

DecimalPart = (sData(i) - IntegerPart) * 100

DiffDataArray(IntegerPart, DecimalPart) = sData(i)

Next i

'提取数据

k = 0

For i = IPmax To IPmin Step -1

For j = DPmax To DPmin Step -1

If DiffDataArray(i, j) <> 0 Then

k = k + 1

Queryp(k) = DiffDataArray(i, j)

End If

Next j

Next i

kMax = k

ReDim Preserve Queryp(kMax)

该方法对于本人遇到的这种“密集型”数据最为有效,但是如果遇上“稀疏型”数据,例如最大、最小值相差几千,甚至上万的数据,就没什么优势了,而且会占用较大的内存。

经过改进,我得到了处理稀疏型数据的高效算法。高效的前提条件同样是源数据具有大量相同数据。思路是在前一种方法的基础上增加一个单维数组,用来保存整数部分数据,保存过程中用插入法对其进行排序。因为有大量重复数据,要排序的数据量相对较少。当从二维数组中读取数据时,用单维数组代入二维数组的第一个下标,具体代码下:

'****稀疏型数据处理****

Dim i As Long, j As Long, k As Long, kMax As Long

Dim Queryp() As Single

ReDim Queryp(Amount)

Dim IntegerPart As Integer, DecimalPart As Integer

Dim IPmax As Integer, IPmin As Integer

Dim DPmax As Integer, DPmin As Integer

Dim IPArray() As Integer, IPAamount As Integer

ReDim IPArray(Amount)

Dim DiffDataArray()

'读取数据

ReadData

IPmax = 0: IPmin = 1000

DPmax = 0: DPmin = 99

IPAamount = 0

For i = 1 To Amount

'获取整数和小数部分的最大最小值

IntegerPart = Int(sData(i))

DecimalPart = (sData(i) - IntegerPart) * 100

If IntegerPart > IPmax Then

IPmax = IntegerPart

ElseIf IntegerPart < IPmin Then

IPmin = IntegerPart

End If

If DecimalPart > DPmax Then

DPmax = DecimalPart

ElseIf DecimalPart < DPmin Then

DPmin = DecimalPart

End If

'对整数部分"IPArray()"进行插入法排序 (从大到小)

For j = 1 To IPAamount

If IntegerPart > IPArray(j) Then

IPAamount = IPAamount + 1

For k = IPAamount To j + 1 Step -1

IPArray(k) = IPArray(k - 1)

Next k

IPArray(j) = IntegerPart

Exit For

ElseIf IntegerPart = IPArray(j) Then

Exit For

End If

Next j

If j > IPAamount Then

IPAamount = IPAamount + 1

IPArray(IPAamount) = IntegerPart

End If

Next i

ReDim DiffDataArray(IPmin To IPmax, DPmin To DPmax)

'填入数据

For i = 1 To Amount

IntegerPart = Int(sData(i))

DecimalPart = (sData(i) - IntegerPart) * 100

DiffDataArray(IntegerPart, DecimalPart) = sData(i)

Next i

'提取数据

k = 0

For i = 1 To IPAamount

For j = DPmax To DPmin Step -1

If DiffDataArray(IPArray(i), j) <> 0 Then

k = k + 1

Queryp(k) = DiffDataArray(IPArray

(i), j)

End If

Next j

Next i

kMax = k

ReDim Preserve Queryp(kMax)

具体采用哪种算法,要看数据的性质而定,以下是本人的一些实测数据,仅供参考。如果你有更好的方法,可不要忘记和朋友们分享哦。