Каков наиболее эффективный метод сопоставления индексов с требуемым набором чисел?
В небольшом фрагменте кода на C++ я перебираю массив с индексами (0–7) и требую наилучшего способа вычисления заданного набора значений a и b из некоторой функции, принимающей i в качестве входных данных.
i: 0 1 2 3 4 5 6 7
---------------------------
a: -1 1 -2 2 1 -1 2 -2
b: 2 2 1 1 -2 -2 -1 -1
Очевидным решением является использование операторов if. Немного покопавшись и почитав, это лучшее, что я смог придумать:
int a = (i%4 == i%2) ? (!(i>=4 ^ i%2) ? -1 : 1) : (!(i>=4 ^ i%2) ? -2 : 2);
int b = (i%4 == i%2) ? (i>=4 ? -2 : 2) : (i>=4 ? -1 : 1);
Я считаю этот код очень неуклюжим и хотел бы знать наиболее оптимизированный способ сделать то же самое.
Если вы выполняете поиск много раз, вы можете использовать встроенную функцию ssse3 в качестве справочной таблицы. См. intel.com/content/www/us/en/docs/intrinsics-guide/…
Общее практическое правило: никогда не просите о самом лучшем, лучшем и т. д. при переполнении стека. Это быстро меняющиеся цели, которые требуют от вас написания полной спецификации системы, а ответы, которые вы получаете, практически бесполезны для тех, кто задает тот же вопрос. К тому же в реальной жизни никто не платит вам за то, чтобы вы предоставляли самое лучшее. Они платят вам достаточно хорошо, чтобы удовлетворить требования.
Почему бы просто не использовать два базовых массива? Это происходит быстро на всех последних основных процессорах (x86-64), пока данные находятся в кеше. Например, начиная с хотя бы Intel Skylake (2015) и AMD Zen (2017), вы можете загружать 2 элемента за такт (с задержкой 3-4 такта в L1). Ваш запутанный код неэффективен, и ему также необходимо извлекать данные из кеша... Простой доступ к массиву всегда должен быть лучше на таком процессоре. Это также должно быть верно для большинства архитектур ARM. Сначала сделайте это просто (см. KISS), а затем профилируйте для оптимизации на целевом процессоре.
Очевидным решением является использование операторов if (я не согласен). Очевидное решение — создать таблицу выходных значений и просто проиндексировать ее. Вы заранее знаете, каковы выходные значения для каждого значения i, так зачем же что-либо вычислять?
Ответы 1
Я бы выбрал парные массивы constexpr, или c-массив и структуру, или любую их комбинацию.
Полностью непроверенный код
using PairsArray = std::array<std::pair<int, int>, 8>;
constexpr PairsArray PA {
{ -1,2 }, { 1,2 }, { -2, 1 }, {2, 1} // and so on
}
constexpr int DoStuff(int i) {
return PA[i].first*3+PA[i]*-2;
}
Потенциальный расчет вызовов DoStuff, если это можно сделать во время компиляции.
Пожалуйста, определите критерии «наиболее эффективного метода».