我有两个 Record
类数组。类 Record
是这样定义的
class Record{
char* string; //the word string
int count; //frequency word appears
}
这是定义的两个数组(已经初始化)
Record recordarray1=new Record[9000000]; //contains 9000000 unsorted Records
Record recordarray2=new Record[8000000] //contains 8000000 unsorted Records
目的是找到两个数组之间匹配的字符串,并将它们添加到一个新数组中,在新数组中将它们的计数加在一起,如果有一个字符串不在另一个数组中,则只需添加到新数组中。为此,我尝试先对两个数组进行排序(按字符串的字母顺序),然后比较 recordarray2
,如果字符串匹配则推进 recordarray2
的索引,否则推进recordarray1
的索引,直到找到一个。如果找不到,则将其添加到新数组中。
不幸的是,这种方法太慢了,使用 STL 排序,排序本身需要 20 多秒。有没有我缺少的更快的标准排序方法?
最佳答案
如果我理解正确,你的算法应该采用 O( nlogn + mlogm
[对两个数组进行排序] + n + m
[遍历数组并进行比较] )
。
它可能不是什么优化,但您尝试只对一个数组进行排序并使用二进制搜索来检查另一个数组的元素是否存在。所以现在应该花费 O( n
[将一个数组复制为新数组] + nlogn
[对其进行排序] + mlogn
[到二进制搜索第二个元素到排序的新元素] )
。
HTH
关于c++ - 合并一个类的两个数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5907478/