Заполните индекс стандартной библиотекой C++
Имея некоторые данные в
struct Data {
std::size_t some_other_data = 0;
std::size_t id = 0;
};
которые хранятся в std::vector. Я хочу создать индекс для элементов по их id и добавить его в индексный файл большего размера.
Если я хочу реализовать это с помощью алгоритма стандартной библиотеки C++, каким путем мне следует следовать?
Вот код на «простом» C++, который это делает:
#include <cstddef>
#include <vector>
struct Data {
std::size_t some_other_data = 0;
std::size_t id = 0;
};
int main()
{
std::vector<std::size_t> collected_indexes;
std::vector<Data> dict = { { 2, 2 }, { 0, 0 }, { 1, 1 } };
std::vector<std::size_t> index(dict.size());
// The code I want to rewrite shorter with std
for (std::size_t i = 0; i < index.size(); ++i) {
index[dict[i].id] = i;
}
collected_indexes.append_range(index);
// End of code
}
Было бы неплохо, если бы предложенное решение можно было использовать с Execution_policies, чтобы сделать его параллельным.
Обновлять
Люди были сбиты с толку моим вопросом и спрашивали, что именно я ищу. Вот как я это реализовал сейчас (рабочая демо):
auto old_size = collected_indexes.size();
collected_indexes.resize(collected_indexes.size() + dict.size());
std::for_each(std::execution::par_unseq,dict.begin(), dict.end(),
[&](auto& dict_entry) {
std::size_t i = &dict_entry - dict.data();
collected_indexes[old_size + dict[i].id] = i;
});
Но этот грязный хак сделан с единственной целью спросить, как это можно хорошо написать с использованием стандартной библиотеки C++ без «диапазонов».
Я уверен, что при использовании правильного алгоритма эту проблему можно решить естественным путем, не доставая данные из-под капота.
К сожалению, библиотека C++ содержит лишь несколько основных алгоритмов. Если алгоритма, который вы ищете, здесь нет, значит, его не существует.
ОТ, но что, если один из элементов имеет идентификатор 10 (или что-то большее, чем dict.size())?...
@PepijnKramer, производительность имеет решающее значение, поэтому std::unordered_map о новом/удалении и т. д. не может быть и речи; Я отошел от нее в этой задаче именно после профилирования. Структура используется в многопоточности, а создание многопоточности std::unordered_map (или использование существующих параллельных unordered_map) обходится дорого. Размер данных составляет гигабайты.
@SamVarshavchik, тут скорее всего дело в формулировках. Я не ищу готовый алгоритм, мой вопрос, как это реализовать с помощью std. Я был уверен, что комбинация std::transform с лямбдой должна сработать. Что-то вроде auto old_size = collected_indexes.size(); collected_indexes.resize(collected_indexes.size() + dict.size()); std::transform(dict.begin(), dict.end(), collected_indexes.begin() + old_size, [&](auto& dict_entry) { return dict_entry.id; });
@Super-intelligentShade, это невозможно по предварительным условиям, поэтому нет смысла проверять код. Именно так генерируются id и index.
вы можете упростить код с помощью диапазонов или сделать его более быстрым и многопоточным с помощью openmp, вы не можете использовать и то, и другое.
@JeJo, нет, я был уверен, что что-то вроде auto old_size = collected_indexes.size(); collected_indexes.resize(collected_indexes.size() + dict.size()); std::transform(dict.begin(), dict.end(), collected_indexes.begin() + old_size, [&](auto& dict_entry) { return dict_entry.id; }); должно сработать. Я ищу что-то вроде этого, очень похожее на ответ ниже, но с «std», поскольку мне нужно параллельное выполнение, которого все еще нет в «диапазонах».
@AhmedAEK, я не спрашиваю о ranges. Я спрашиваю о решении std, таком как 'auto old_size =collected_indexes.size(); collected_indexes.resize(collected_indexes.size() + dict.size()); std::transform(dict.begin(), dict.end(),collected_indexes.begin() + old_size, [&](auto& dict_entry) { return dict_entry.id; });'
@JeJo, косвенность неверна. Мой «простой» код C++ редко перемещается по индексному массиву на основе значений, в то время как std::transform ожидает передать его линейно от начала до конца. Мне нужно каким-то образом изменить алгоритм, пройдя через некоторый фиктивный диапазон от 1 до n и в лямбда-выражении разреженно обращаясь к массиву индексов.
@JeJo, пожалуйста, прочти мой раздел «Обновления» по этому вопросу. Этот код работает, но он уродлив. В любом случае, это показывает идею кода, который я хочу иметь. Но я все еще не уверен, можно ли написать это короче, используя какой-нибудь другой алгоритм вместо std::for_each.
@SamVarshavchik, я обновил вопрос, добавив в раздел «Обновление» хакерский способ решения проблемы с целью объяснить, что я имел в виду под «решением с помощью алгоритма стандартной библиотеки C++ (как здесь это назвать короче?)». Не могли бы вы вернуться и сказать, видите ли вы лучший способ применения алгоритмов C++ STD LIB?
Сейчас на ум приходит цитата Скотти из «Звездного пути III»: «Чем больше вы задумываетесь о водопроводе, тем легче заткнуть канализацию». Похоже, что самопровозглашенные уберхакеры C++ зачастую пытаются превзойти самих себя, придумывая как можно более сложные смеси для решения простейших задач. Единственная их практическая цель — хвастаться: в конце концов, чем более запутан код, тем большим экспертом в C++ должен быть его автор, не так ли?
@DamirTenishev посмотри последнее обновление моего ответа.
@DamirTenishev, если ваше единственное возражение против ranges - это отсутствие параллелизма, взгляните на этот пример: godbolt.org/z/13n88GM1n Он использует std::for_each для параллельного выполнения, но использует преимущества std::views::enumerate из c++23 для создания индексы.
@SamVarshavchik, единственная цель - научиться простым способом реализовывать вещи с помощью C++STDLIB. Когда я пишу цикл и при проверке кода кто-то приходит и заменяет 7 строк на одну std::transform на std::bind и пару предикатов, а затем спрашивает: «Почему бы вам не использовать повторно C++STDLIB», я ошибаюсь. Когда я пытаюсь проверить, что такого способа/алгоритма не существует, я снова ошибаюсь. Где золотая середина? Когда я говорю «мой код прост», люди говорят «забыли о циклах, смотрите диапазоны и каналы, мы больше не думаем циклами» и т. д. и т. п.
Похоже, вы открыли для себя золотое правило C++: если вы спросите десять разработчиков C++, как лучше всего реализовать <X>, вы получите как минимум одиннадцать разных ответов.
@SamVarshavchik, так каков ваш подход к изучению библиотек в стиле строительных блоков, таких как stdlib, в действии, если не пытаться реализовать с их помощью код? Вы просто читаете книги или виртуально представляете, как это будет работать? Люди показывают короткие, лаконичные и очень читаемые решения с диапазонами, представлениями и каналами, и я хочу им следовать. Что плохого в попытке применить новые подходы к простым задачам, чтобы увидеть, как это работает (не в коде, а в логике и подходе)? Я привык пытаться принять решение, использовать ли его, каков ваш подход?
@Супер-умный Шейд, спасибо. Пожалуйста, посмотрите мой комментарий под вашим ответом. Остался последний шаг, если это еще возможно.
Да, когда я изучал C++, я <вздох> <шок> читал учебники. Я открыл главу 1 и начал читать. Затем глава 2, глава 3 и так далее. В какой-то момент кто-то приобретает достаточный опыт и знания, чтобы иметь возможность чему-то учиться, просто просматривая технические справочные материалы. В основном именно так я обновил свою базу знаний до C++20. Но если кто-то начинает со старта, не существует коротких путей к использованию организованной учебной программы, основанной на учебниках.
@SamVarshavchik, я не на старте. Я прочитал массу книг по C++ и даже написал одну. Я написал тонны кода, который работает в производстве. Я просто изучаю новые вещи в языке так, как раньше: читаю спецификации, чтобы узнать основы, читаю книги, чтобы найти идеи, читаю код, чтобы найти лучшие идеи, пишу код и смотрю, как он работает. Я не вижу ничего плохого в подходе «попробуй и получи» и не понимаю, к чему вы ведете. Я также не вижу, что плохого в том, чтобы пытаться и спрашивать.
@DamirTenishev Я добавил это в свой ответ и изменил порядок так, чтобы более поздние версии были вверху.
@Super-intelligentShade, спасибо тебе огромное! Это было именно то, что я искал. Позвольте мне подождать до завтра возможных лучших решений (как это рекомендуется в SO), и я приму ответ.
Ответы 1
ЗАКЛЮЧИТЕЛЬНОЕ ОБНОВЛЕНИЕ
Как обсуждалось в комментариях, вот версия без взлома, использующая ranges и работающая непосредственно с collected_indices. Он также включает закомментированную альтернативу с использованием параллельного выполнения.
#include <algorithm>
#include <execution>
#include <ranges>
#include <vector>
using std::execution::par_unseq;
namespace views = std::views;
struct Data
{
std::size_t some_other_data;
std::size_t id;
};
int main()
{
std::vector<Data> dicts[2]
{
{ { 2, 2 }, { 0, 0 }, { 1, 1 } },
{ { 1, 1 }, { 2, 2 }, { 0, 0 } }
};
std::vector<std::size_t> collected_indices;
// The code I want to rewrite shorter with std
for (auto&& [i, dict] : views::enumerate(dicts))
{
auto old_size = collected_indices.size();
collected_indices.resize(old_size + dict.size());
auto index = collected_indices | views::drop(old_size) | views::take(dict.size());
for (auto&& [j, e] : views::enumerate(dict)) index[e.id] = j;
// parallel version
/* auto view = views::enumerate(dict);
std::for_each(par_unseq, view.begin(), view.end(),
[&](auto&& e) { auto&& [i, d] = e; index[d.id] = i; }
);
*/ }
}
Ссылка: https://godbolt.org/z/86EWsWoa1
ОБНОВЛЕНИЕ 3
Вот решение, которое использует std::for_each для параллельного выполнения и std::views::enumerate из библиотеки ranges для ленивого создания индекса:
#include <algorithm>
#include <cstddef>
#include <execution>
#include <ranges>
#include <vector>
using std::execution::par_unseq;
struct Data
{
std::size_t some_other_data;
std::size_t id;
};
int main()
{
std::vector<Data> dict { { 2, 2 }, { 0, 0 }, { 1, 1 } };
std::vector<std::size_t> index(dict.size());
// The code I want to rewrite shorter with std
auto view = std::views::enumerate(dict);
// or:
// auto view = std::views::zip(std::views::iota(0u, dict.size()), dict);
std::for_each(par_unseq, view.begin(), view.end(),
[&](auto&& e) { auto&& [i, d] = e; index[d.id] = i; }
);
}
Ссылка: https://godbolt.org/z/dsEE3fG1T
ОБНОВЛЕНИЕ 2
Вот еще одно решение с использованием std::for_each. Это менее хакерски, чем ваше обновление, но также немного менее эффективно (поскольку оно должно создавать и заполнять список индексов):
#include <algorithm>
#include <cstddef>
#include <execution>
#include <vector>
using std::execution::par_unseq;
struct Data
{
std::size_t some_other_data;
std::size_t id;
};
int main()
{
std::vector<Data> dict { { 2, 2 }, { 0, 0 }, { 1, 1 } };
std::vector<std::size_t> index(dict.size()), is(dict.size());
std::iota(is.begin(), is.end(), 0);
// The code I want to rewrite shorter with std
std::for_each(par_unseq, is.begin(), is.end(),
[&](auto i) { index[dict[i].id] = i; }
);
}
Ссылка: https://godbolt.org/z/jv8Mn5Thh
ОБНОВЛЯТЬ
Вот пример использования tbb, как упоминалось в комментариях:
#include <cstddef>
#include <tbb/blocked_range.h>
#include <tbb/parallel_for.h>
#include <vector>
using range = tbb::blocked_range<std::size_t>;
struct Data
{
std::size_t some_other_data;
std::size_t id;
};
int main()
{
std::vector<Data> dict { { 2, 2 }, { 0, 0 }, { 1, 1 } };
std::vector<std::size_t> index(dict.size());
// The code I want to rewrite shorter with std
tbb::parallel_for(range{0, dict.size()}, [&](range r) {
for (auto i = r.begin(); i != r.end(); ++i) index[dict[i].id] = i;
});
}
ОРИГИНАЛЬНЫЙ ОТВЕТ
Не намного короче, но, может быть, читабельнее (на мой не столь скромный и крайне предвзятый взгляд):
#include <cstddef>
#include <ranges>
#include <vector>
namespace views = std::views;
struct Data
{
std::size_t some_other_data;
std::size_t id;
};
int main()
{
std::vector<Data> dict { { 2, 2 }, { 0, 0 }, { 1, 1 } };
std::vector<std::size_t> index(dict.size());
// The code I want to rewrite shorter with std
for (auto&& [i, e] : views::enumerate(dict)) index[e.id] = i;
}
Ссылка: https://godbolt.org/z/Kx1xPrh8z
Спасибо за вклад, это помогает, но то же самое, что и в предыдущем ответе (от JeJo выше), я прошу решение с помощью std, а не с помощью ranges, так как я хочу получить выгоду от параллельного выполнения.
@DamirTenishev в вашем конкретном примере параллельное выполнение, скорее всего, не сильно поможет из-за затрат, связанных с созданием потоков и синхронизацией. Если только не происходит какая-то другая обработка, о которой вы не упомянули.
Понятно, но я хочу попробовать и измерить с помощью профилировщика. Чтобы попробовать, мне нужен код. Итак, цикл закрывается. :)
Я могу привести пример с параллельным выполнением, но он не будет короче... Причина, по которой я выбрал ranges, заключается в том, что их алгоритмы принимают диапазон, тогда как std алгоритмы требуют begin и end итераторов.
В цикле есть par_unseq и i не является атомарной переменной. Будет ли этот код вообще работать или это просто приведет к неопределенному поведению? Если нет, то почему, если i можно изменить параллельно во многих потоках с неожиданными результатами, поскольку он не является атомарным?
@DamirTenishev Да... ты прав, это вообще не сработает... :) Ну, у меня это действительно сработало, потому что, как я уже говорил ранее, компилятор выполнит это последовательно. Но в целом этого не будет. Единственный вариант, который я могу предложить, - это использовать tbb.
Под tbb вы имеете в виду tbb concurrent_unordered_map? Я уже пробовал, но это снижает производительность, поскольку размер данных огромен (гигабайты) и использование карт с новыми/удалением и т. д. дорого.
Вы должны были поместить все эти данные в свой первоначальный вопрос... :facepalm:
Нет, я думал о parallel_for с blocked_range, который дает необходимые индексы.
Я решил проблему с помощью чистой стандартной библиотеки C++ (см. раздел «Обновление» моего вопроса), но это решение все еще «хакерское». Все еще ищу, подойдет ли здесь какой-нибудь другой алгоритм.
Спасибо за решение с tbb, оно помогает, поэтому я проголосовал за него, но не могу его принять, поскольку вопрос все еще касается C++stdlib. Я не очень хорошо знаком с синтаксисом tbb::parallel_for, разве то, что вы опубликовали, не использует вложенные циклы (один для tbb и один внутри)?
Да, вам все еще нужен цикл внутри parallel_for, но tbb «разобьет» ваши данные и создаст несколько потоков, чтобы загрузить ваш процессор. Кстати, посмотрите мое последнее обновление без использования tbb.
Спасибо, это именно то, что я имел в виду под «фиктивным диапазоном от 1 до n» в моем комментарии к @JeJo в моих комментариях под моим вопросом, но мои массивы dict и index довольно велики, как я писал (гигабайты), и получаю еще один может привести к ограничению памяти. Диапазоны позволили бы выдуманный манекен с std::ranges::views::iota(1, 9);, было бы неплохо реализовать здесь что-то подобное, чтобы избежать такого потребления памяти.
Еще раз спасибо! Еще один вопрос, который я пытался поднять здесь: рекомендуемый вами подход с for (auto&& [i, e] : views::enumerate(dict)) index[e.id] = i; лучшим с точки зрения этого вопроса (создание конвейерной версии), или это просто первое пришедшее на ум решение по конвейеру или «лучшее» один? Я спрашиваю, потому что чувствую, что это можно решить более элегантно, например `collected_indexes.append_range(dict | std::views::transform(...));', но я не вижу способа. Просто любопытно найти более элегантное решение здесь.
Я подумал, что это самое элегантное решение (и несколько питоническое, если вы знаете Python). К сожалению, я не могу .append_range() скомпилировать на godbolt...
Его можно легко заменить на 'collected_indexes.insert(collected_indexes.end(), index.begin(), index.end());` ради этого примера.
Может быть, вам стоит вместо этого использовать
std::unordered_map<std::size_t,Data>в словаре? Где ключ — это идентификатор вашего элемента данных. Карты обычно представляют собой структуру данных, используемую в словарях.