Форум программистов
 
Регистрация на форуме тут, о проблемах пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail, а тут можно восстановить пароль

Купить рекламу на форуме 15-35 тыс рублей в месяц

Вернуться   Форум программистов > IT форум > Общие вопросы по программированию, компьютерный форум
Регистрация

Восстановить пароль
Повторная активизация e-mail

Ответ
 
Опции темы Поиск в этой теме
Старый 22.09.2022, 23:57   #1
andrey2185
Новичок
Джуниор
 
Регистрация: 22.09.2022
Сообщений: 4
По умолчанию Эффективное распараллеливание поиска для неупорядоченного набора данных

Привет, подскажите, куда копать, у меня естественно-научное образование, можно ли эффективно распараллелить следующую задачу?

Есть два плотных одномерных плотных массива целых чисел разной длины (от тысяч до миллионов интов), в одном значения не упорядочены и повторяются, второй отсортирован по возрастанию и значения не повторяются, надо найти для каждого элемента из первого вектора минимальное значение из второго вектора, которое больше или равно ему, но не больше чем на заданную величину, которая одинакова для всех.

Вот код на julia, просто для наглядности, но он выполняется в одном потоке, а вот с какой стороны подойти, чтобы выполнить за n тактов на GPU, я который день мучась

Код:
# 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
andrey2185 вне форума Ответить с цитированием
Старый Вчера, 05:06   #2
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 6,872
По умолчанию

Не понял, зачем вы в коде-примере сортируете массив A и ищете перестановки индексов. Сразу ищите элементы из массива A в массиве B и попробуйте вместо линейного поиска использовать бинарный. Тогда, например, если массивы A и B будут оба длиной 1000000 (10^6), то вместо худшего случая линейного поиска с 1000000000000 (10^12) сравнений, будет всего лишь 20000000 (2 * 10 ^7) сравнений. А простейшее распараллеливание на ГПУ - искать каждый элемент массива A в массиве B в отдельном потоке.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Старый Вчера, 18:57   #3
andrey2185
Новичок
Джуниор
 
Регистрация: 22.09.2022
Сообщений: 4
По умолчанию

BDA, да лучше получилось, и проще распараллелить, спасибо
andrey2185 вне форума Ответить с цитированием
Ответ
Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Сравнить два набора данных datetime alex89d Общие вопросы Delphi 3 13.05.2015 14:04
экспорт набора данных из бд в word kate158 Общие вопросы Delphi 9 22.11.2013 15:27
макрос для поиска позиций и вывода данных на лист поиска mr-111 Microsoft Office Excel 12 13.03.2012 15:03
ADO Обновление набора данных Ale-X91 БД в Delphi 6 14.02.2012 14:38
Изменение набора данных BDGrid alex_fcsm БД в Delphi 3 30.01.2010 21:30