Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Распараллелить поиск в неупорядоченных данных 
:(
    Опции темы
andrey2185
Дата 22.9.2022, 23:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 2
Регистрация: 22.9.2022

Репутация: нет
Всего: нет



Здорово теоретики, можно ли распараллелить подобную задачу?

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

Вот для наглядности код на 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



PM MAIL   Вверх
andrey2185
Дата 24.9.2022, 11:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 2
Регистрация: 22.9.2022

Репутация: нет
Всего: нет



решение - поэлементно для А выполнять бинарный поиск в В
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.0881 ]   [ Использовано запросов: 20 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.