Мультикарта или отсортированный вектор в параллельной программе
У меня есть программа, которую я должен распараллелить. может содержать большое количество данных. Эти данные могут быть идентифицированы по идентификатору, и больше данных могут иметь одинаковый идентификатор. Каждый поток моей программы восстанавливает все данные с определенным идентификатором и работает над ним.
Мой вопрос для параллельной программы лучшее решение состоит в том, чтобы использовать мультикарту или вектор, отсортированный по идентификатору данных?
Спасибо.
Решение
Абстрагируйте тип данных и реализуйте общее решение. Затем замените два типа данных и посмотрите, какой из них работает лучше.
Другие решения
unordered_map может быть хорошим решением. Поскольку он реализован в виде хэша, идентичные идентификаторы будут заканчиваться в тех же сегментах.
Кроме того, хеш-таблицы хороши при работе с большими наборами данных, поскольку они предоставляют механизм для группировки данных в сегменты, которые могут обрабатываться отдельно.
Это действительно зависит от размера данных. Представьте, что у вас есть данные A B C D размером 2, 10, 20, 30.
Если представить, что у вас 4 потока, у вас будут проблемы с балансировкой нагрузки. Поток A будет выполнять меньше работы, чем остальные. К сожалению, сортировка данных не поможет вам.
Может быть, лучше просто хранить данные в стеке (например) и заставить потоки извлекать из стека работу независимо от идентификатора. Тем не менее, вы синхронизировали стек.
Если вы заранее знаете размеры, содержащиеся в данных каждого идентификатора, вы можете сгруппировать их в блоки, составленные по идентификаторам данных. Эти блоки будут иметь примерно одинаковый размер.
Затем вы можете составить карту, где V будет блоками, а K — идентификатор потока, который будет их вычислять.