Самый быстрый способ создать вектор индексов из матрицы расстояний в C ++

Question

У меня есть матрица расстояний D размера n на n и константа L в качестве входных данных. Мне нужно создать вектор v, содержащий все записи в D, чтобы его значение было не более L. Здесь v должно быть в определенном порядке v = [v1 v2 .. vn], где vi содержит записи в i-й строке D со значением не более L. Порядок записей в каждом vi не важен.

Интересно, есть быстрый способ создания v с использованием вектора, массива или любой структуры данных + парализация. То, что я сделал, это использовал для циклов, и это очень медленно для больших n.

vector<int> v;
for (int i=0; i < n; ++i){
    for (int j=0; j < n; ++j){
        if (D(i,j) <= L) v.push_back(j);
    }
}

Answer 1

Лучший способ в основном зависит от контекста. Если вы ищете парализацию GPU, вам стоит взглянуть на OpenCL.

Для парализации на основе ЦП стандартная библиотека C ++ #include <thread>, вероятно, является лучшим выбором, но вы должны быть осторожны:

• Потоки требуют времени для создания, поэтому, если n относительно мало(<1000 или около того) это замедлит вас </li>
• D (i, j) должен читаться несколькими потоками одновременно
• v должен быть доступен для записи несколькими потоками, aстандартный вектор не обрежет его

v может быть двухмерным вектором с подвекторами vi, но они должны быть инициализированы до параллизации:

std::vector<std::vector<int>> v; 
v.reserve(n);                    
for(size_t i = 0; i < n; i++)
{
    v.push_back(std::vector<int>());
}

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

size_t threadAmount = std::thread::hardware_concurrency(); //How many threads should run hardware_concurrency() gives you a hint, but its not optimal
std::vector<std::thread> t;                                //to store the threads in
t.reserve(threadAmount-1);                                 //you need threadAmount-1 extra threads (we already have the main-thread)

Чтобы запустить поток, вам нужна функция, которую он может выполнить. В данном случае это для чтения части вашей матрицы.

void CheckPart(size_t start, size_t amount, int L, std::vector<std::vector<int>>& vec)
{
    for(size_t i = start; i < amount+start; i++)
    {
        for(size_t j = 0; j < n; j++)
        {
            if(D(i,j) <= L)
            {
                vec[i].push_back(j);
            }
        }
    }
}

Теперь вам нужно разбить вашу матрицу на части примерно n / threadAmount строк и запустить потоки. Конструктор потока нуждается в функции и ее параметре, но он всегда будет пытаться скопировать параметры, даже если функция хочет ссылку. Чтобы предотвратить это, вам нужно принудительно использовать ссылку с std::ref()

int i = 0;
int rows;
for(size_t a = 0; a < threadAmount-1; a++)
{
    rows = n/threadAmount + ((n%threadAmount>a)?1:0);
    t.push_back(std::thread(CheckPart, i, rows, L, std::ref(v)));
    i += rows;
}

Теперь потоки работают, и все, что нужно сделать, это запустить последний блок в главной функции:

SortPart(i, n/threadAmount, L, v);

После этого вам нужно дождаться окончания потоков и очистить их:

for(unsigned int a = 0; a < threadAmount-1; a++)
{
    if(t[a].joinable())
    {
        t[a].join();
    }
}

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

Answer 2

Принимая во внимание комментарии, я сделал соответствующие исправления (выделено).

Вы искали советы по написанию кода производительности, потоков, инструкций asm (если ваша сборка неименно то, что вы хотите) и OpenCL для параллельной обработки? Если нет, я настоятельно рекомендую!

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

Также, использование new вместо vector может быть быстрее, как мы видим здесь: Использование массивов или std:: векторы в C ++, какой разрыв в производительности? - , и я тестировал, и с vector это на 6 секунд медленнее, чем с new, что занимает всего 1 секунду. Я предполагаю, что безопасность и простота управления гарантируют, что использование std :: vector нежелательно, когда кто-то ищет производительность, даже если использование new не так сложно, просто избегайте переполнения кучи при вычислениях и не забывайте использовать delete[]

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