Здорово теоретики, можно ли распараллелить подобную задачу?
Есть два плотных одномерных плотных массива целых чисел разной длины (от тысяч до миллионов интов), в одном значения не упорядочены и повторяются, второй отсортирован по возрастанию и значения не повторяются, надо найти для каждого элемента из первого вектора минимальное значение из второго вектора, которое больше или равно ему, но не больше чем на заданную величину, которая одинакова для всех.
Вот для наглядности код на julia, который выполняет эту задачу в одном цикле в одном потоке:
| Код |
# for example
A = Int32[2, 3, 3, 15, 4, 4, 8, 32, 9, 9, 9, 13, 14]
B = Int32[1, 4, 5, 6, 7, 9, 10, 15, 23, 54]
limit = 10
sortA = sort(A)
inds = sortperm(sortperm(A))
sortR = zeros(Int32, length(A))
b = 1
for i = 1 : length(sortA)
while B[b] < sortA[i]
b += 1
if b == length(B)
break
end
end
if B[b] <= (sortA[i] + limit)
sortR[i] = B[b]
end
end
R = sortR[inds]
# result:
R == [4, 4, 4, 15, 4, 4, 9, 0, 9, 9, 9, 15, 15] # -> true
|
|