Например, имеются массивы data[N], hole[M], N≥M. В data хранятся данные, а в hole — в порядке возрастания, индексы, отмечающие пустые точки. Нужно дефрагментировать этот массив, т.е. обменять элементы так что бы данные лежали непрерывно. При этом, порядок в котором они они пишутся не важен. Что-то вроде:
8 holes:
3 5 6 16 22 23 25 26
in:
00 01 02 -- 04 -- -- 07 08 09 10 11 12 13 14 15 -- 17 18 19 20 21 -- -- 24 -- -- 27 28 29
out:
00 01 02 29 04 28 27 07 08 09 10 11 12 13 14 15 24 17 18 19 20 21 -- -- -- -- -- -- -- --В наивной последовательной реализации (набросал на python)
id_hole = len(hole)-1
id_tail = len(data)-1
for j in range(0,len(hole)):
dst = hole[j]
while(id_hole>=j):
if hole[id_hole] >= id_tail:
#skip
id_tail = id_tail-1 #atomic
id_hole = id_hole-1 #atomic
else:
#move
data[dst],data[id_tail] = data[id_tail],data[dst]
id_tail = id_tail-1 #atomic
breakПредполагается, что с этим будет работать код на CUDA, в пределах одного блока тредов.
