LINUX.ORG.RU
Форум — Development  

c++ расплющить вложенный цикл?

 , ,


2

1

Например, есть что-то такое. 

constexpr int n{4};
int shape[n];
for (int j0=0; j0<shape[0]; ++j0) {
	for (int j1=0; j1<shape[1]; ++j1) {
		for (int j2=0; j2<shape[2]; ++j2) {
			for (int j3=0; j3<shape[3]; ++j3) {
				/* return iterator to do external stuff ? */
			}
		}
	}
}
Хочется с помощью шаблонной магии преобразовать обход вложенного цикла к плоскому виду, что-то вроде функции: 
template<n>flatten (int *shape, ...) -> iterator
c юзкейсом ala 
int shape[4];
for (auto entry : flatten<4>(shape)) {
	/* do external stuff */
}
Хочется сделать это без дополнительного выделения памяти и runtime-time рекурсии. Куда копать?

★★★★★

Последнее исправление: thunar (всего исправлений: 2)

Ответ на: комментарий от thunar

Ну вот вообще без рекурсии:

namespace flatten1 {
template<size_t N>
generator<int> flatten(int *shape)
{
    std::array<int, N> i{0};
    int n = 0;
    bool process = true;

    while (process) {

        for (i.back() = 0; i.back() < shape[N-1]; ++i.back()) {
            n++;
            co_yield n;
        }

        if (N > 1) {
            for (auto j = N-1; j >= 1; --j) {
                auto const index = j - 1;
                if (++i[index] == shape[index]) {
                    if (index == 0) {
                        process = false;
                        break;
                    }
                    i[index] = 0;
                    continue;
                }
                break;
            }
        }
    }
}
}

Я не помню, но std::array<int, N> нормально создатся на стеке.

hatred ★★★
()
Ответ на: комментарий от hatred

Или вот вариант с «генерацией» шейпа, по типу как у @rupert:

namespace flatten2 {
template<size_t N>
generator<std::array<int, N>> flatten(int *shape)
{
    std::array<int, N> i{0};

    bool process = true;
    int start = 1; // hack, to avoid modification generator<>::promise_type::initial_suspend() to std::suspend_never()

    while (process) {

        for (i.back() = start; i.back() < shape[N-1]; ++i.back()) {
            co_yield i;
        }

        if (N > 1) {
            for (auto j = N-1; j >= 1; --j) {
                auto const index = j - 1;
                if (++i[index] == shape[index]) {
                    if (index == 0) {
                        process = false;
                        break;
                    }
                    i[index] = 0;
                    continue;
                }
                break;
            }
        }

        start = 0;
    }
}
}
hatred ★★★
()

Все зависит от:

  1. того что хочется в этом цикле делать.

  2. хочется ли его делать параллельным.

  3. насколько тело цикла толстое (насколько критичны накладные расходы).

Варианты обственно такие:

  1. делаем один целочисленный счетчик по всей области и на каждой итерации переводим его в j0…3. Плюсы - это просто и хорошо параллелится. Минусы - это дорого (лишние телодвижения), но при условии что нужны j0…3. Если не нужны то это самый быстрый варинат.

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

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

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

AntonI ★★★★
()
Последнее исправление: AntonI (всего исправлений: 2)
Ответ на: комментарий от AntonI

Всё разобрался. Я в постановке перемудрил — оказалось, что итератор не нужен, достаточно рекурсивного шаблона с коллбэк-лямбдой, а в неё уже можно напихать всего при необходимости.

thunar ★★★★★
() автор топика
Последнее исправление: thunar (всего исправлений: 1)
Ответ на: комментарий от thunar

достаточно рекурсивного шаблона с коллбэк-лямбдой

Какой ты всё-таки скучный). Тут тебе таких решений накидали, а ты!

Кстати, по поводу коллбэк-лямбды: https://github.com/arximboldi/zug, https://sinusoid.es/zug/transducer.html#zip
Я думаю, что можно zip-нуть сразу несколько shape диапазонов, и потом по этому зипу пройтись, как по простому итератору туплов.

rupert ★★★★★
()
Development