我有一个长度为N的未排序向量。向量中的每个元素恰好出现两次(向量长度为偶数)。我有一个自定义排序算法,目标是迭代,直到向量达到每个元素都与其副本相邻的状态。Unsorted vector = {A,F,J,E,F,A,J,E}
A valid sorted state = {A,A,J,J,E,E,F,F}
Another valid sorted state = {J,J,A,A,F,F,E,E}
所以我的问题在于,检查排序状态是否有效的最快方法是什么,这样我就可以加快迭代速度,对于长向量,这将决定我的大部分缩放能力。
3条答案
按热度按时间e4yzc0pl1#
一些快速和肮脏的,但我不知道它会永远工作:
这依赖于两个相同的值总是彼此相邻的事实,一个不重复,下一个重复。似乎与测试集一起工作:
它非常快,在我的机器上,用百分之五秒的时间浏览一百万个长度的向量:
dgsult0t2#
其中一个选项涉及将
vector
(因为length
是even
,并且某个元素恰好出现两次)转换为两行矩阵,获取unique
并测试行数是否为1。如果重复的值相邻,则在将dim
属性与matrix
相加时,第二行将与第一行完全相同或者稍微快一点
e4eetjau3#
另一个选项是使用
rle
函数:试验: