[c++] возможно ли произвольное число циклов без рекурсии?

Anna74

В c++ надо написать в зависимости от текущего значения целого параметра k>0
Надо k вложенных циклов, пределы для простоты одинаковые, только переменные цикла естественно разные, в самом внутреннем цикле все счетчики используются для вычисления некого выражения.

vall

правильный ответ — "да"

#include <stdlib.h>

#include <stdio.h>



int main (int argc, char **argv) {

	int r, l, i;

	int *a;



	l = atoi(argv[1]);

	r = atoi(argv[2]);

	a = calloc(l, sizeof(int;

next:

	for (i = 0; i < l; i++)

		printf("%d ", a[i]);

	printf("\n");

	for (i = 0; i < l; i++) {

		if (++a[i] < r)

			goto next;

		a[i] = 0;

	}

	return 0;

}

okis

Надо k вложенных циклов

простой массив счетчиков использовать можно?

Dasar



void main

{

   int k = 10;

   int m = 100;

   int counters[k+1]; //ячейка counters[k] используется для маркировки признака конца

   

   for (begin(counters, k);is_next(counters, k);next(counters,k, m

   {

      ...

   }

}



void begin(int* counters, int k)

{

   for (int i = 0; i < k+1; ++i)

     counters[i] = 0;

}

void next(int * counters, int k, int m)

{

   for (int i = 0; i < k; ++i)

   {

      counters[i]++;

      if (counters[i] < m)

        return;

      counters[i] = 0;

   }

   counters[k] = 1;

}

bool is_next(int * counters, int k)

{

  return counters[k] == 0;

}

Serab

сишно, и назнвание is_next, имхо, криво. Но работает

vall

bool next(int* counters, int k, int m) {

   for (int i = 0; i < k; ++i)

   {

      if (++counters[i] < m)

        return true;

      counters[i] = 0;

   }

   return false;

}

как-то так

Dasar

как-то так

я об этом думал, но тогда цикл снаружи придется делать менее "красивым":



   for (begin(counters, k);)

   {

      ...

      if(!next(counters, k, m

        break;

   }

ps
а делать изменение счетчика из под проверки условия, имхо, не кошерно

Dasar

хотя вот так можно сделать.



void main

{

   int k = 10;

   int m = 100;

   int counters[k];

   bool is_continue = true;   



   for (begin(counters, k); is_continue; is_continue = next(counters,k, m

   {

      ...

   }

}



void begin(int* counters, int k)

{

   for (int i = 0; i < k; ++i)

     counters[i] = 0;

}

bool next(int * counters, int k, int m)

{

   for (int i = 0; i < k; ++i)

   {

      counters[i]++;

      if (counters[i] < m)

        return true;

      counters[i] = 0;

   }

   return false;

}

Serab

NOooooooooooooooooooooo

Dasar

или даже так:



void main

{

   int k = 10;

   int m = 100;

   int counters[k];



   for (bool is_continue = begin(counters, k); is_continue; is_continue = next(counters,k, m

   {

      ...

   }

}



bool begin(int* counters, int k)

{

   for (int i = 0; i < k; ++i)

     counters[i] = 0;

   return true;

}

bool next(int * counters, int k, int m)

{

   for (int i = 0; i < k; ++i)

   {

      counters[i]++;

      if (counters[i] < m)

        return true;

      counters[i] = 0;

   }

   return false;

}

Dasar

почему нет?

Serab

о боже, я не могу. Т.е. ты добавил в функцию return true только чтобы присвоить более лакончино значение переменной? Тогда уж сделал бы хотя бы return false если k = 0 (на самом деле еще лучше если k = 0 или m = 0).

Dasar

о боже, я не могу.

ничего ты не понимаешь в красоте

Тогда уж сделал бы хотя бы return false если k = 0 (на самом деле еще лучше если k = 0 или m = 0).

это само собой
ps
а чем тебе начальный вариант с is_continue не понравился?

Ivan8209

Ну, реализуешь ты стек вызовов руками, и что?
Можно и вообще без подпрограмм писать в таком случае.
---
"Нахер нужны выпускники мехмата, если они за третий класс
математику не знают... Мозг высшей геометрией разрушен."

vall

я об этом думал, но тогда цикл снаружи придется делать менее "красивым":

use do-while, Luke

Dasar

use do-while, Luke

не красиво. задание начальных условий оторвано от цикла

Serab

ну вообще мне не нравится смешение идиом. Есть две идиомы итераторов, имхо. Либо



for( init; isValid; advance ) {

  doSmth;

}

либо если у тебя одна прибаблялка, тогда уж



init;

do

{

  doSmth;

} while( tryAdvance );

т.е. зачем скрывать, что у тебя там одна итерация в любом случае выполняется?
С одной прибавлялкой полюбому нельзя проверить валидность итератора.
Эта идиома (твой цикл for) приобретает смысл только во втором случае: заходим в цикл при опредленных условиях (begin вернул true и еще проверяем условие в конце каждой итерации. Через другие циклы это вроде лакончино не запишешь. И формально этот is_continue (оставим лингвистику в стороне, но имя тоже ппц

) и есть переменная цикла как бэ.

Serab

ничего ты не понимаешь в красоте

о, я теперь не буду делать функции void вообще, буду везде делать return true, вдруг заодно придется присвоить какой-нибудь перменной true, можно будет сократить код :smirk:

Dasar

это контракт между циклом и "enumerable" в виде двух функций: begin и next. Это измененный вариант контракта из четырех функций begin, end, next, сравнение, когда сравнение с концом переносится внутрь функций begin и next
ps
контракт не обязательно должен оформляться в виде реализации ооп-interface-а

Dasar

т.е. зачем скрывать, что у тебя там одна итерация в любом случае выполняется?

второй вариант как раз получается полным, там такого уже нет, и контракт позволяет корректно обработать и вырожденные случаи

Serab

у тебя просто везде попытка приклеить isValid либо к одной, либо к другой функции. Это меньше писанины, но интерфейс не упрощает.

Dasar

Это меньше писанины, но интерфейс не упрощает.

менее наглядный, но также и менее вычислительно-затратный, чем стандартный c++-контракт: begin, end, ++, сравнение

Dasar

у тебя просто везде попытка приклеить isValid либо к одной, либо к другой функции.

закономерный перенос. Во многих случаях функции begin, next уже имеют внутреннее знание (как в данном случае) о необходимости продолжения цикла, соответственно, явный вызов функции isValid приносит лишь дополнительные накладные расходы

Serab

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

Dasar

преждевременная оптимизация же, затрудняющая общение с итератором.

это утверждание подразумевает, что когда-то делается окончательная оптимизация, но в реальности никакой окончательной оптимизации не происходит.

В конце концов это итератор, на одно приращение итератора чаще всего приходится куча действий по выполнению самой итерации.

какой на твой взгляд оверхед не надо оптимизировать? 80%? 20%? 5%? 1%? 0.1%?
ps
замечу, что enumerable из foreach - это дальнейшее развитие предложенного контракта.



enumerable_begin(ref state)

{

  state =  специальное_начальное_состояние;

}

enumerable_next(ref state)

{

   if (state == специальное_начальное_состояние)

      return begin(ref state);

   return next(ref state);

}

enumerable_current(state)

{

   return state;

}

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

Serab

это утверждание подразумевает, что когда-то делается окончательная оптимизация, но в реальности никакой окончательной оптимизации не происходит.

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

какой на твой взгляд оверхед не надо оптимизировать? 80%? 20%? 5%? 1%? 0.1%?

это проценты от чего? Если от времени выполнения всего алгоритма, то из-за 5% в большинстве случаев заморачиваться бы не стал (опять же, бывают исключения но что это за программа, которая на 20% состоит из приращения итераторов? Может быть, ее адеватнее написать без всяких излишеств с итераторами, а просто как-нибудь аццки быстро?

Dasar

то перед релизом юзают профилировщик

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

Dasar

но что это за программа, которая на 20% состоит из приращения итераторов

все программы по обработке информации, а это почти все инет-сервисы и бизнес приложения.

Serab

все программы по обработке информации, а это почти все инет-сервисы и бизнес приложения.

Давай-ка пример конкретный, потому что по моему опыту все "программы по обработке информации" упираются в медленный доступ к памяти, а не в итераторы.

Serab

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

но узкое место в коде приращения итератора должен заметить, думаешь нет?

ppplva

Если этот код заинлайнится в сотню мест - нет.

Serab

можно же отключить инлайн конкретных функций :confused:

Dasar

но узкое место в коде приращения итератора должен заметить, думаешь нет?

common-профайлер тебе не скажет смог ли у тебя цикл влезть в кэш(и по коду, и по данным а это меняет производительность в несколько раз.

Dasar

Давай-ка пример конкретный, потому что по моему опыту все "программы по обработке информации" упираются в медленный доступ к памяти, а не в итераторы.

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

Serab

common-профайлер тебе не скажет смог ли у тебя цикл влезть в кэш(и по коду, и по данным а это меняет производительность в несколько раз.

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

Serab

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

по моему опыту, это неверно в 90% случаев (обработка графов, разреженные матрицы). Дело в том, что даже такой большой итератор, как в обсуждаемой теме, легко помещается в кэш (а еше чаще в регистры, если итераторы более простые, а их большинство а тормозит как раз произвольный доступ к памяти. Поэтому я и попросил более конкретный пример, потому что то, о чем ты говоришь, для меня новость. Нет, я могу придумать, например, умножение плотных матриц или еще какие-нибудь последовательные паттерны доступа, но и здесь если там floating point, то все это может скрыться в конвейере.

Dasar

давай начнем с простого вопроса, как бы ты оформил итератор из исходного поста?

Serab

Если считать, что надо создать именно итератор, то вообще, учитывая [c++], я бы нагородил ООП, конечно же, но так уж я считаю, не стоит писать C-style в плюсах.





for( Counter c = Counter(k); c.IsValid; c++ ) {

  // Тут c[i] дает значение соответствующего разряда.

}



class Counter {

public:

    Counter(int nestedIterations, int iterationLength_) :

        iterationLength(iterationLength_

        data(nestedIterations + 1)

    {}



    bool IsValid const

    {

        return data.back == 0;

    }



    Counter& operator++

    {

        Assert(IsValid;



        for( int i = 0; i < data.size - 1; i++ ) {

            data[i]++;

            if( data[i] < iterationLength ) {

                return *this;

            }



            data[i] = 0;

        }



	data.back = 1;



        return *this;

    }



    Counter operator++(int) const

    {

        Counter old(*this);

        ++(*this);

        return old;

    }



    int operator[](int i) const

    {

        return data[i];

    }

private:

    int iterationLength;

    std::vector<int> data;

};

Dasar

при таком итераторе на оверхед уйдут 20-50% производительности

И, кстати, как-то так автоматически получилось, что можно заоптимизировать IsValid: закэшировать это в поле класса и менять его в конструкторе и функции Next.

если закэшировать IsValid, то это и будет один в один вариант с предложенным, только у тебя он в ООП-обертке.

Serab

при таком итераторе на оверхед уйдут 20-50% производительности

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

Serab

если закэшировать IsValid, то это и будет один в один вариант с предложенным, только у тебя он в ООП-обертке.

Да, но у меня сохранится последовательность и понятность интерфейса и это не приведет к модификации кода. Вообще, мы тут не ООП обсуждаем, это я написал просто чтобы полностью ответить на твой вопрос "как бы я...".

Dasar

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

Serab

Откуда такие выводы? Я заинтересован в написании быстрого кода, ок? Но это не отменяет того, что твое утверждение про %% не имеет смысла в данном виде по двум причинам, которые я написал.

Serab

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

Ivan8209

> если у тебя отсутствует задача писать максимально быстрый код
А у тебя эта задача присутствует?
Когда это ты начал программировать медленные микроконтроллеры?
---
"А что такое line rate? Заодно обоснуй это мнение."

Dasar

Когда это ты начал программировать медленные микроконтроллеры?

лет с 13-ти

Dasar

Сейчас подредактировал.

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

Dasar

Я заинтересован в написании быстрого кода, ок?

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

Serab

Ладно, поехали.



using namespace std;



class Counter {

public:

    Counter(int nestedIterations, int iterationLength_) :

        iterationLength(iterationLength_

        data(nestedIterations + 1)

    {}



    bool IsValid const

    {

        return data.back == 0;

    }



    Counter& operator++

    {

	//Assert(IsValid;



        for( int i = 0; i < data.size - 1; i++ ) {

            data[i]++;

            if( data[i] < iterationLength ) {

                return *this;

            }



            data[i] = 0;

        }



	data.back = 1;



        return *this;

    }



    Counter operator++(int)

    {

        Counter old(*this);

        ++(*this);

        return old;

    }



    int operator[](int i) const

    {

        return data[i];

    }

private:

    int iterationLength;

    std::vector<int> data;

};



const int k = 10;

const int m = 10;



void test1

{

	int sum = 0;

	for( Counter c = Counter(k, m); c.IsValid; ++c ) {

	  for( int i = 0; i < k; i++ ) {

		  sum += c[i];

	  }

	}



	cout << sum << endl;

}



bool begin(int* counters, int k)

{

   for (int i = 0; i < k; ++i)

     counters[i] = 0;

   return true;

}



bool next(int * counters, int k, int m)

{

   for (int i = 0; i < k; ++i)

   {

      counters[i]++;

      if (counters[i] < m)

        return true;

      counters[i] = 0;

   }

   return false;

}



void test2

{

   int counters[k];



   int sum = 0;

   for (bool is_continue = begin(counters, k); is_continue; is_continue = next(counters,k, m

   {

      for( int i = 0; i < k; i++ ) {

		  sum += counters[i];

	  }

   }



   cout << sum << endl;

}



int _tmain(int argc, _TCHAR* argv[])

{

	double start, end;

	start = getCPUTime;

	test1;

	end = getCPUTime;

	cout << end-start << endl;



	start = getCPUTime;

	test2;

	end = getCPUTime;

	cout << end-start << endl;

	return 0;

}

getCPUtime основано на GetProcessTimes. Core i5. Студия 2010, все оптимизации врублены.

Это практически 5% производительности.
При несколько други параметрах (5^14) получается побольше, тут ~15%:

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

Serab

да, действительно, но это не так важно: как минимум это исправляется одним if'ом в конструкторе, может быть можно и поизящнее.

Serab

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

я так не говорил. Я говорил, что не хочу жертвовать читабельностью ради ускорения в 5%.

Dasar

Это практически 5% производительности.
При несколько други параметрах получается побольше, тут ~15%:

это потери чисто на некорректно выбранную объектную обертку, а измерь еще некэшированный вызов IsValid (про что и утверждалось, что он вносит существенные тормоза)

Serab

не, IsValid снимается, просто я раньше бред написал. Он сейчас и так работает за O(1).
Вообще, с точки зрения производительности твои два способа отличаются только тем, где хранить is_continue: в отдельной перменной или в конце массива :grin:

rosali

Разумные значения k в пределах нескольких десятков. Напиши рекурсию, но на шаблонах, и сделай switch который по конкретному значению k диспатчит в нужный истанс.
Тред не осилил, простите если уже было

Serab

да, круто, только неясно, зачем swich, если это как бэ просто параметр шаблона.

Serab

Вообще, мой поинт в том, что итераторы вообще можно как угодно писать, ООП-не ООП, главное в питон не интеропить, на производительности в сколько-нибудь реальных приложениях это скажется копеечно, поэтому тут в первую очередь стоит думать о читабельности/интерфейсе, а не микрооптимизациями заниматься.

Ivan8209

Я бы сказал, что в большинстве реальных проектов, даже более
критичных по производительности, чем то, что клепает ,
цена вменяемого интерфейса значительно выше, чем цена
микрооптимизации.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."

Dasar

достаточно часто, невозможность сделать хороший интерфейс упирается в отсутствие запаса по производительности.

Ivan8209

Видимо, ты такой хороший программист, что у тебя это упирается
в отсутствие запаса по производительности, почти во всех моих
случаях, упирались в недостаток времени на переработку кода.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."

Serab

некорректно выбранную объектную обертку

что значит некорретно выбранную? Зачем вообще писать на плюсах в си-стиле? Тогда можно писать на Си.

Dasar

такой алгоритм обычно появляется в переборных задачах

что значит некорретно выбранную?

в твоем коде более тесно связаны текущий вариант и пространство вариантов, чем текущий вариант и действия по его обработке.

Serab

в твоем коде более тесно связаны текущий вариант и пространство вариантов, чем текущий вариант и действия по его обработке.

вот читаю это и даже забыв, что сам написал, думаю, что "все правильно сделал".

Dasar

намекну тогда по другому:
код построения пространства вариантов от задачи к задачи обычно не меняется, а вот вид состояния в каждой задаче уникален.
у тебя же состояние задачи и код построения пространства вариантов смешаны в одном классе

smit1

да, круто, только неясно, зачем swich, если это как бэ просто параметр шаблона.

run-time -> compile-time

Serab

а, точняк

Serab

Короче, у тебя что-то дофига теории, я тебя попросил конкретики по производительности, ты не соизволил ее привести, сказал, что у меня будет на 20-50% медленее, что оказалось в самом вырожденном случае пургой. Теперь ты выдумываешь еще какие-то обобщения. Ты не видел задачу ОПа, я не видел, поэтому мы рассуждаем с общих позиций практик программирования, я предлагаю такую, которая работает в 90% случаев, не переусложняя код и не навешивая лишних тормозов. Тем более у него не сказано ни о какой комбинаторике: он четко написал, что ему надо k вложенных циклов без рекурсии, никаких дополнительных требований не было.
То, что ты не сильно заботишься о читабельности, видно хотя бы из отношения к именованию функций.

Dasar

что у меня будет на 20-50% медленее, что оказалось в самом вырожденном случае пургой.

ты же код в сообщении пост фактум поправил..

Serab

а, ты про тот цикл. Он вообще не в кассу был, я там тупанул, оно вообще не работало в том виде. В любом случае, я и с той реализацией могу привести пример, где будет меньше 20% разница (например, внутри цикла sleep зафигачить так что это уже мелочи: главная мысль тут не в конкретных цифрах, а в том, что не стоит преждевременно оптимизировать код под производительность.

Dasar

не стоит преждевременно оптимизировать код под производительность.

ты хотя бы правильные утверждения приводи:
не стоит преждевременно в ущерб читабельности оптимизировать код под производительность

Serab

начались придирки :crazy:

Если хочешь, то я могу стоять и за "вообще не стоит", даже без ущерба читабельности.

Dasar

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

Serab

быстрый, если это не идет в ущерб понимаю или скорости разработки

вот, скорость разработки, это уже серьезнее

В общем, я не понимаю, почему ты спорил. Да, я написал косячный код, но ведь спор еще до этого был. Ты спросил "как бы ты написал", вот считай, я текущий код показал. Я и сам говорил, что то, что он ООП — дело десятое. Но ведь раньше шел разговор о скорости, по-моему, тут достаточно явно продемонстрировано, что на скорость оформление итератора повлиять не может, даже если нагородить ООП. И это не была программа на работу с данными, это чистая голая прогонка итератора: просто чистейший минимум, любое утяжеление тела цикла приводит к уменьшению разницы, вылезание за кэш, которое происходит в любой программе, "работающей с данными", вообще уменьшит эту разницу проактически до нуля.

Dasar

Но ведь раньше шел разговор о скорости, по-моему, тут достаточно явно продемонстрировано, что на скорость оформление итератора повлиять не может, даже если нагородить ООП.

вот только заметь что для оформления итератора ты почему-то взял не стандартную для C++ (из stl) идиому оформления итераторов, а придумал какую-то свою.

Serab

Не смешно самому? Я могу еще в три раза больше нагородить, ты же понимаешь, что вывод от этого не изменится.
Можно было и из STL'я взять, там даже random access несложно реализовать. Просто почему-то я исторически не фан STL'я, не считаю его за аксиому.

Dasar

Можно было и из STL'я взять

покажи, пожалуйста, такой вариант и его производительность.
ps
оценку скорости разработки тоже желательно указать

Dasar

мне не нравится твое решение тем, что ты в нем делаешь преждевременную инкапсуляцию. Ты инкапсулировал состояние counters-ов, хотя задачей это еще и не требовалось.
Если хочется C++, то вот такое решение достаточно чистое без лишних напластований кода, которые постановкой задачи еще не требуются.



void main

{

   int m = 100;

   std::vector<int> counters(10);



   for (bool is_continue = begin(counters, m); is_continue; is_continue = next(counters,m

   {

      ...

   }

}



bool begin(std::vector<int>& counters, int m)

{

   for (int i = 0; i < counters.size; ++i)

     counters[i] = 0;

   return counters.size > 0 && m > 0;

}

bool next(std::vector<int>& counters, int m)

{

   for (int i = 0; i < counters.size; ++i)

   {

      if (++counters[i] < m)

        return true;

      counters[i] = 0;

   }

   return false;

}

Serab

class Counter {

public:

    Counter(int nestedIterations, int iterationLength_) :

        iterationLength(iterationLength_

        data(nestedIterations + 1)

    {

		if( nestedIterations == 0 || iterationLength_ == 0 ) {

			data.back = 1;

		}

	}



	// An end iterator

	Counter :

		iterationLength(0

		data(1)

	{

		data[0] = 1;

	}



	bool operator <(const Counter& rhs) const

	{

		if( !rhs.isValid ) {

			return isValid;

		}

		

		// Doesn't really matter for this particular test

		//Assert(data.size == rhs.data.size && iterationLength == rhs.iterationLength);

		for( int i = data.size - 1; i >= 0; i-- ) {

			if( data[i] < rhs.data[i] ) {

				return true;

			} else if ( rhs.data[i] < data[i] ) {

				return false;

			}

		}



		return false;

	}



    Counter& operator++

    {

	//Assert(isValid;



        for( int i = 0; i < data.size - 1; i++ ) {

            data[i]++;

            if( data[i] < iterationLength ) {

                return *this;

            }



            data[i] = 0;

        }



	data.back = 1;



        return *this;

    }



    Counter operator++(int)

    {

        Counter old(*this);

        ++(*this);

        return old;

    }



    int operator[](int i) const

    {

        return data[i];

    }

private:

    bool isValid const

    {

        return data.back == 0;

    }



	int iterationLength;

    std::vector<int> data;

};



const int k = 10;

const int m = 10;



void test1

{

	int sum = 0;

	const Counter end;

	for( Counter c = Counter(k, m); c < end; ++c ) {

	  for( int i = 0; i < k; i++ ) {

		  sum += c[i];

	  }

	}



	cout << sum << endl;

}

такая херь дает

где-то 30% проигрыша. Но это опять же только итератор.

Serab

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

Но опять же, я тут только спорил с тем, что аргументы микрооптимизации имеют смысл, а свой код я привел на твой вопрос "как бы ты написал".
Ладно, если что завтра продолжим, приятных сновидений

Dasar

const Counter end;
for( Counter c = Counter(k, m); c < end; ++c ) {

не похоже на классический итератор из stl
к классике ближе будет что-то такое:



    CountersSpace space(3, 2);

    for (Counters c = space.begin; c != space.end; ++c)

    {

       ...

    }



class CountersSpace;



class Counters

{

public:

  Counters& operator ++;

  bool operator != (const Counters& other);



  std::vector<int> state;

private:

  Counters(CountersSpace &space, bool isEnd = false);

  CountersSpace& space;

  friend class CountersSpace;

};



class CountersSpace

{

  Counters *_end;

public:

  CountersSpace(int k, int m):m(m k(k)

  {

    _end = new Counters(*this, true);

  }

  ~CountersSpace

  {

    delete _end;

  }

  int m;

  int k;

  const Counters& end

  {

     return *_end;

  }

  Counters begin

  {

    return Counters(*this);

  }

};





Counters::Counters(CountersSpace &space, bool isEnd):space(space)

{



  state.resize(space.k + 1);

  if (isEnd)

  {

    state[space.k] = 1;

  }

  else

  {

    state[space.k] = space.k > 0 && space.m > 0 ? 0 : 1;

  }

}

Counters& Counters::operator ++

{

  for (int i = 0; i < state.size - 1; ++i)

  {

    if (++state[i] < space.m)

      break;

    state[i] = 0;

  }

  state[space.k] = 1;

  return *this;

}

bool Counters::operator != (const Counters& other)

{

  if (&this->space != &other.space)

    return true;

  for(int i = 0; i < state.size; ++i)

  {

    if (state[i] != other.state[i])

      return true;

  }

  return false;

}

Dasar

у тебя кстати код бажный, циклится для случаев m=1

elenangel

switch нужен затем, что шаблон нельзя раскрывать не константным выражением.

Serab

не похоже на классический итератор из stl
к классике ближе будет что-то такое:

не обязательно, там есть istream_iterator. Такое да, более распространенный, для контейнеров.

Serab

да, я даже не могу нормально скатать код поправил.

Serab

не, ну ты тут намеренно неэффективно написал с там сравнением итераторов :grin:

Хотя тут уже не поспоришь, ты просто можешь сказать, что так проще

Но ты опять пытаешься соскочить на обсуждение ООП

Dasar

Но ты опять пытаешься соскочить на обсуждение ООП

так насколько я понял, мой код тебе не понравился только тем, что в нем нет ООП. или чем-то другим?
я согласен, что использование std::vector код делает чище.
но вот использование объектной обертки для counters - имхо, излишне:
  кода становится больше,
  вводятся излишние запреты (например, запрещен прямой доступ к изменению счетчиков
  добавляются лишние состояния.

Serab

вообще, ты немного напутал. begin/end — это схема получения итераторов у контейнеров, это не входит в контракт самих итераторов, так что мой вариант там норм.

Serab

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

Dasar

begin/end — это схема получения итераторов у контейнеров, это не входит в контракт самих итераторов, так что мой вариант там норм.

я исхожу из тезиса, что отсутствие опечаток и полнота решения должны легко перепроверяться за минимальное кол-во перескоков по коду, и за минимальное чтение строчек кода.
Идиома begin/end таким свойством обладает более чем. Достаточно проверить, что begin/end взяты из одного источника, и это дает гарантию, что все элементы будут перечислены, при этом не произойдет зацикливания и т.д.
Предложенный тобой пример такого критерия не имеет, например, по следующим примерам сложно сказать правильные они или не правильные, и что выведут:



//если я забыл какой вариант правильный: начальный должен быть пустой или с числами, 

//  то что является напоминаем правильного варианта?

for( Counter c = Counter(2, 3); c < Counter; ++c ) {..}

for( Counter c = Counter; c < Counter(2, 3); ++c ){..} 



for (Counter c = Counter(2, 3); c < Counter(2, 4); ++c){..} //так можно?



for (Counter c = Counter(2, 3); c < Counter(4, 3); ++c){..} //а так?



Counter c; ++c; //такое правомерно?

Serab

ну это я не знаю, просто взял идею с istream_iterator'а, к нему подобные вопросы тоже имеются, хотя совместимость разных итераторов там более-менее понятна (не должно быть ее на первый взгляд). Да, мне стоило реализовать только != и тогда было бы проще, определить ее только по отношению к конечному и к самому себе, и было бы довольно полно.

Serab

Ну короче

В этом контракте:

for( bool is_continue = begin(...); is_continue; is_continue = next(...) ) {...}

Меня убило то, что валидность расплывается на две функции. Т.е. можно хотеть избавиться от лишней функции isValid но имхо, так цена слишком велика.
Все-таки тогда уже логично пойти C#-путем и сделать что-то вроде

for( begin(...); next; ) {...}

здесь до вызова next нельзя пользоваться состоянием итератора.
Минус: не подходит под сишный for выглядит чужеродно (не initialize-test-increment).
Т.е. итог такой, что в Си-плюсах родным выглядит именно идиома initialize-test-increment. Как-то так. Обе конструкции, которые есть в этом посте, не так плохи (включая твою, которая мне сперва не понравилась но они чужеродны и при первой встрече вызывают wft (как у меня выше). Но если привыкнуть, то пользоваться можно, наверное, но я пока не вижу плюсов их насаждать в новом коде

Dasar

Меня убило то, что валидность расплывается на две функции.

Если разбираться, то в твоем решении с классом Counter за валидность реально отвечают тоже две функции: конструктор и operator++, а функции IsValid просто является заглушкой для доступа к состоянию этих функций.
По сути, ты просто добавил промежуточный абстрактный слой, сказав, что клиентскому коду не фига знать о таких деталях (что валидность обеспечивается и проверяется в двух функциях, а не в одном месте и это правильное решение с точки зрения классического ООП, но в тоже время - это неправильное решение с точки зрения современных подходов типа agile, где утверждается, что код надо писать только в тот момент, когда он требуется.

Dasar

Все-таки тогда уже логично пойти C#-путем и сделать что-то вроде
code:for( begin(...); next; ) {...}

у C# другой контракт, примерно, следующий - если убрать объектную оболочку:



var state = null;

for (bool is_continue = next(ref state); is_continue; is_continue = next(ref state

{

}

Serab

у C# другой контракт

for (bool is_continue = next(ref state); is_continue; is_continue = next(ref state

===

while(next(ref state

Serab

agile отменяет метрику WTFs/min?

beluchy

вы не должны этого хотеть

пределы для простоты одинаковые, только переменные цикла естественно разные, в самом внутреннем цикле все счетчики используются для вычисления некого выражения.



#include <stdlib.h>

#include <stdio.h>



int ipow(a,b){

  int r=1;

  while(b--) r *= a;

  return r;

}



int main(int argc, char **argv){

  if (argc < 2) return 1;

  int k = atoi(argv[1]);

  int l = atoi(argv[2]);

  printf("Nested loops: %d\nIndex limit: %d\nIndexes values:\n", k, l);

  int i,j;

  for (i=0; i < ipow(l,k); i++){

    for (j=k-1; j >=0; j--){

      printf("%d ", (i%ipow(l,j+1/ipow(l,j;

    }

    printf("\n");

  }

  return 0;

}



$ ./nested_cycles_unroll.x 2 3

Nested loops: 2

Index limit: 3

Indexes values:

0 0 

0 1 

0 2 

1 0 

1 1 

1 2 

2 0 

2 1 

2 2

jakal222

 

#include <stdio.h>

#include <stdlib.h>

int global_a = 0;







typedef struct Lst{

	struct Lst *next;	

	void (*implementint,struct Lst*);

}List;



void my_func(int b, List*p){

	int i = 0;

	for (; i<b; ++i){

		p->implement(b,p->next);

		}

	}



void norm_func(int b, List*p){

	++global_a;

	}



List* def{

	List * head = NULL;

	

	head = (List*)malloc(sizeof(List;

	head->implement = my_func;

	head->next = NULL;

	return head;		

	}

void add(List*head){

	

	List*t = head;

	while(t->next!=NULL){

		t = t->next;

		}

	List * p = t->next;

		

	p= (List*)malloc(sizeof(List;	

	p->implement = my_func;

	p->next = NULL;		

	t->next = p;

	}

void stop(List * head){

	List*t = head;

	while(t->next!=NULL){

		t = t->next;

		}

	List*p = t->next;

	p = (List*)malloc(sizeof(List;

	p->implement = norm_func;

	p->next = NULL;	

	t->next = p;

	}

int countToNULL(List*head){

	List*p = head;

	int count = 0;

	while(p!=NULL){

		count++;

		p=p->next;

		}

	return count;

	}

	

int main(int argc, char* argv[]){

	int i = 0;

	List * good_list = NULL;		

	good_list = def;

	for (; i<2; ++i){		

		add(good_list);

		}

	stop(good_list);

		

	printf("nodes: %d", countToNULL(good_list;

		

	//compute here

	good_list->implement(5,good_list->next);

	printf("\n a = %d\n",global_a);

	

	return 0;

}

elenangel

typedef struct Lst{
struct Lst *next;
void (*implementint,struct Lst*);
}List;

советую выяснить, что такое stl вообще и std::list - в частности

Serab

советую выяснить, что такое Си, но код у него с фантазией написан, конечно

elenangel

а при чем тут си?

Serab

он написал прогу на Си

apl13

советую выяснить, что такое stl вообще и std::list - в частности

Еще std::forward_list заодно выясни.

elenangel

Он написал прогу на смеси C и C++ в теме про C++
Смешал код и объявления, использовал однострочный комментарий. Оно конечно скомпилируется gcc и будет работать, но не надо говорить что это чисто хардкорный C.
По-моему это классический случай недопонимания разницы между C и C++.

Serab

http://en.wikipedia.org/wiki/C99

elenangel

ладно, убедил, это Си. Но все равно тема была про C++.

Serab

Тут плюсовое решение только я предлагал, и то засрали тащемта, так что не аргумент.

apl13

Таки да.
Смотри.
Его программа — wrong context.
Твое утверждение — wrong proposition in wrong context.
А теперь они два раза перевернутые. (c)

Оставить комментарий