Можете ли вы переписать этот фрагмент без goto?

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

Ограничения:

  1. current=current->child() стоит дорого (это shared_ptr), поэтому я хотел бы свести к минимуму использование этой операции любой ценой.
  2. После операции current должен быть последним найденным дочерним элементом.
  3. cnt должен подсчитывать каждого дочернего элемента, с которым он сталкивается.
  4. cnt++ будет заменен какой-либо другой операцией (или несколькими операциями) и должен появиться только один раз :)

код:

insideloopy:
cnt++;
if ( current->hasChild() )
{
    current = current->child();
    goto insideloopy;
}

Редактировать: Извините, ребята, изначально забыл упомянуть, что cnt++ должен появляться только один раз. Это будет какая-то операция на узле, и поэтому она должна быть там только один раз. Я также пытаюсь избежать вызова другой функции.


person Ron    schedule 19.08.2009    source источник
comment
Вы должны указать, на каком языке   -  person John Sheehan    schedule 19.08.2009
comment
Похоже, кому-то нужна помощь с домашним заданием...   -  person Tony    schedule 19.08.2009
comment
не домашняя работа :) ,.. реальная работа :) заморозил мозги   -  person Ron    schedule 19.08.2009
comment
насколько дорогим является shared_ptr?   -  person George Godik    schedule 19.08.2009
comment
кажется, что вы перебираете узлы только 1 ветки... не дерева.   -  person xtofl    schedule 19.08.2009
comment
Я сделал некоторое профилирование, сравнивая итерацию дерева с необработанными указателями и общими указателями. Не вдаваясь в подробности, вот некоторые краткие цифры: 20000 итераций по 1 дереву: Необработанные указатели: 150 мс Общий указатель неоптимизированной реализации: 1400 мс Общий указатель оптимизирован: 577 мс. Shared_ptr работает медленнее, так как подсчитывает ссылки, и каждый раз, когда вы выполняете current=current->child(), в фоновом режиме происходит множество вещей по сравнению с простым необработанным назначением указателя. Так что ради преимуществ, которые они дают, я возьму на себя замедление.   -  person Ron    schedule 19.08.2009
comment
@xtofl, это всего лишь небольшой фрагмент кода итерации. Что правильно повторяет только одну ветвь.   -  person Ron    schedule 19.08.2009


Ответы (8)


insideloopy:
cnt++;
if ( current->hasChild() )
{
    current = current->child();
    goto insideloopy;
}

Я люблю бесконечные циклы.

while (true) {
   cnt++;
   if (!current->hasChild()) break;
   current = current->child();
}

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

person Stefano Borini    schedule 19.08.2009
comment
Фантастика! Хорошая работа. Я просто не мог заставить свой мозг работать сегодня утром. - person Ron; 19.08.2009
comment
Это немного лучше, чем версия с бесконечным циклом LorenVS, из-за перевернутой логики. Я все еще думаю, что использование моего оператора запятой оправдано и более читабельно: P - person Thorarin; 19.08.2009
comment
@unknown: разве ты не говорил, что пытаешься избежать лишних «если»? - person Artem Barger; 19.08.2009
comment
Разве while(true) в значительной степени не становится безусловным прыжком? - person Ron; 19.08.2009
comment
Я тоже предпочитаю обратную логику здесь, но я чувствую, что версия LorenVS на 6 минут раньше была лишена принятого представителя ответа. ;) Придется довольствоваться моим жалким +1. - person Aardvark; 19.08.2009
comment
Извините, LorenVS, я не уверен, кто был первым, поскольку вы в итоге отредактировали свой ответ (после того, как я уточнил требования). Что отражает «время ответа», первое сообщение или последнее редактирование? - person Ron; 19.08.2009
comment
имхо, разрыв - это просто скрытый переход. - person xtofl; 19.08.2009

Оригинальный ответ

Предполагая, что это C или C++:

while (cnt++, current->hasChild())
{
    current = current->child();
}

Обычно я не большой поклонник оператора запятой, но я тоже не люблю повторяться :)

Обновленный «забавный» ответ

Узнав, что cnt++ на самом деле является многострочной операцией, этот конкретный синтаксис будет далеко не идеальным. Что-то большее в соответствии с вашим принятым ответом было бы лучше.

Если вы хотите быть действительно крутым, это также сработает:

do 
{
    cnt++;
} while (current->hasChild() && (current = current->child()));

Теперь я чувствую себя очень грязным, злоупотребляя коротким замыканием на операторе && :)

Разумный ответ

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

while (true)
{
   cnt++;
   if (!current->hasChild()) break;
   current = current->child();
}

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

Единственное, что идет вразрез с этим решением, — это если ваша операция с узлом представляла собой длинный фрагмент кода. Я не против бесконечных циклов, если я могу сразу увидеть, где они заканчиваются. Опять же, если бы он был действительно длинным, он все равно должен был бы быть функцией.

person Thorarin    schedule 19.08.2009
comment
В этом случае работает очень хорошо, и вы можете упаковать все в одну строку. - person Stefano Borini; 19.08.2009
comment
это действительно очень компактно! :) и будет работать для примера, но cnt++ будет выполнять несколько операций в реальном приложении. Не уверен, как это будет выглядеть. Не большой поклонник оператора запятой либо. - person Ron; 19.08.2009
comment
@Ron: с несколькими утверждениями ваш принятый ответ, вероятно, является лучшим решением. Жаль, что вы не указали это в своем первоначальном вопросе: P @Stefano: Думаю, я бы разделил его на 2 строки. Однако некоторые нацисты в стиле кода не любят опускать фигурные скобки :( - person Thorarin; 19.08.2009
comment
Извини за это. Это был мой первый вопрос здесь, и я никогда не ожидал, что это будет такая гонка, чтобы получить первый ответ! - person Ron; 19.08.2009
comment
На них всегда есть пробег. Хороший компактный вопрос, короткий ответ. Легкие моменты :) - person Thorarin; 19.08.2009
comment
Я обязательно придумаю еще один :) - person Ron; 19.08.2009

cnt++;
while(current->hasChild())
{
   cnt++;
   current = current->child();
}

РЕДАКТИРОВАТЬ:

Если вы хотите, чтобы cnt++ был в вашем коде только один раз:

while(true)
{
    cnt++;
    if(current->hasChild())
       current = current->child();
    else
       break;
}
person LorenVS    schedule 19.08.2009
comment
cnt++ должен появиться только один раз. - person Stefano Borini; 19.08.2009
comment
вы можете избежать оператора if, используя вместо него цикл do while. - person Artem Barger; 19.08.2009
comment
я пытаюсь избежать лишнего, если .. держите его быстро :) - person Ron; 19.08.2009
comment
Это правда, мне это кажется более естественным, но кто знает, может у меня действительно странный стиль кодирования :) - person LorenVS; 19.08.2009
comment
Я лично стараюсь избегать while (true), если это вообще возможно. - person Thorarin; 19.08.2009
comment
Очень близко к решению, которое я в итоге принял. Не уверен, кто был первым, хотя пытался проголосовать за ваш комментарий. - person Ron; 19.08.2009
comment
› Лично я стараюсь избегать while (правда), если это вообще возможно. - person Ron; 19.08.2009
comment
@Торарин. они не являются необходимым злом, при условии, что они заканчиваются, и их держат маленькими. - person Stefano Borini; 19.08.2009
comment
@Stefano: Я согласен, и я не ухожу с пути, чтобы их избегать. Часто они являются лучшим решением, особенно в C#, с которым я обычно работаю. Однако при наличии оператора запятой в данном конкретном случае его легко избежать. - person Thorarin; 19.08.2009

Вы можете использовать break, чтобы выйти из цикла в середине кода:

while (true) {
   cnt++;
   if (!current->hasChild()) break;
   current = current->child();
}
person Guffa    schedule 19.08.2009
comment
@xtofl: Да, но с четко определенной и легко находимой целью. Это имеет большое значение. - person sbi; 19.08.2009

while (current->hasChild())
{
    cnt++;
    current = current->child();
}

Или я что-то упускаю?

person Achim    schedule 19.08.2009

Я бы исследовал возможность заставить current->child() возвращать NULL, когда у него нет дочерних элементов, если он еще этого не сделал - это кажется наилучшим возможным результатом, и оставление его неопределенным в этом случае кажется подверженным ошибкам - и затем использовать:

for (; current; current = current->child())
{
    cnt++;
}
person AProgrammer    schedule 19.08.2009
comment
Вызов current-›child() стоит дорого по сравнению с вызовом hasChild(). поэтому я хочу избежать этого, если это возможно. - person Ron; 19.08.2009
comment
Является ли current-›child() затратным, даже если hasChild() возвращает false? Если это так, я бы просто обернул его предварительным условием hasChild(). - person AProgrammer; 19.08.2009
comment
Однако это нарушило бы второе ограничение: После операции текущий должен быть последним найденным дочерним элементом. - person Thorarin; 19.08.2009

Операторы без перерыва:

notDone=true;
while(notDone){
   cnt++;
   if ( current->hasChild() ){
       current = current->child();
   } else {
       notDone=false;
   }
}
person Greg Miller    schedule 19.08.2009
comment
Избегание перерыва переоценено, имхо. Вы собираетесь доказывать правильность этого алгоритма? Перерыв сделает это намного сложнее? - person Thorarin; 20.08.2009
comment
Break не усложнит задачу — он представит два возможных пути кода к первому оператору после цикла, что требует анализа обоих предыдущих состояний. Но приведенный выше код имеет два возможных пути к концу цикла, где выполняется повторная проверка условия (предложение if и else), что требует анализа обоих предыдущих состояний. остальное просто замаскировано ;-) - person Steve Jessop; 20.08.2009

person    schedule
comment
Так? Здесь можно использовать оператор запятой, если cnt++ должен расширяться до нескольких операторов. Не то чтобы это было хорошей идеей... - person user57368; 20.08.2009
comment
если cnt++ - это несколько операторов, возможно, это должна быть функция. И вы можете легко сделать for(cnt++,i = 0,current=firstChild(); ...; ...), если вам нужно. - person nos; 20.08.2009