数组加减法. ( 积分: 20 )

L

L.Ming

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-07-03

• #1

一个记录型数组: TAarData = Array of TData
Tdata 是一个记录类型
现在有两个TAarData类型的数组A,B,现在想在A内减去与B相同的行.因为数据量太大,有什么更有效率的方法可行?

 

W

wr960204

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-07-03

• #2

MMX,SSE2之类的做优化.
MMX理论上来说可以提高一倍速度.SSE2可以在MMX的基础上再提高一倍.
但是实际上由于要预先处理数据所以实际效率要低一点.

 

F

FishEatsCats

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-07-12

• #3

用hash解决
A 长度 m
B 长度 n
需要一个辅助空间 长度为 n 排序2叉树 查询速度为 log2 N

遍历 B 一次 利用一个时间复杂度 O(P)的公式 得到 B 每个元素 的 hash ,插入到辅助空间
然后遍历A判断

时间复杂度为 O(mlog2N+np),其中 p 为小量
你看呢

 

E

errorcode

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-07-17

• #4

好像记得有个问题跟LZ相同，比较的是两个整型数组，也是用hash方法

解题思路是：
hashtable : array [0..maxsize] of boolean;

for I := 0 to m - 1 do
hashtable[ a ] := True;

for I ;= 0 to n - 1 do
if hashtable[ b ] then
begin
// b in a
end;

在 b in a 的情况下，就可以做自己事了。复杂度最底: O(M+N)

 

W

wr960204

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-08-01

• #5

我觉得也只有hash表效率比较高

 

L

L.Ming

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-08-02

• #6

hash表哪里有详细介绍,不太明白.

 

小

小龙银行

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-08-08

• #7

"b in a&quot
是什么意思？

 

X

xiaohongna

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-08-14

• #8

这也是一个死贴了~~
hash是一种离散算法，用空间换时间。但是在使用之前你要先建立一个hash表，这个地方就比较麻烦了，要感觉你的这个Tdata里面的数据 使用合适的 hash函数来离散数据。
当然你这个Tdata里面有数据是具有规律性的就比较好建hash表了。

我不推荐你使用这种方法，现在慢就慢在每次要找是否有相同的记录 ，最简单的方法就是对一个表进行排序，然后用2分法查找是否有相同的记录，这样比较简单，效率很提高很多。
我经常处理这样类型的数据~~一般都是4w条记录左右，我就用快速排序+2分法查找，感觉很快，仅停顿一下就处理完了。我觉得这是速度和复杂度的一个折中。

 

L

L.Ming

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-08-15

• #9

没有关联到数据库的.

 

K

Kisber

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-09-24

• #10

如果是整数，就用 errorcode 的方法，很快。
如果不是整数，就用 xiaohongna 的方法，因为我时常也是这么做的。

 

弯

弯矛

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-09-29

• #11

[^]