Убить goto
От: Шахтер Интернет  
Дата: 16.02.06 13:43
Оценка:
Что-то много всякой фигнёй в последнее время страдаем (особенно философской).

Вот фрагмент кода (слияние двух отсортированных последовательностей).
Задача -- красиво убить goto.


template <class Range> 
template <class Collector>
typename ResultAttributes<typename Collector::FunctorType>::ResultType 
 UnionGenType<Range>::operator () (Collector collector) const
 {
  Range a=a_,b=b_;
  
  typedef typename Collector::FunctorType FunctorType;
  
  FunctorType fun(collector);
  
  if( !a ) goto finish_b;
  if( !b ) goto finish_a;
  
  for(;;)
    switch( Cmp(*a,*b) )
      {
       case CmpLess :
        {
         fun(*a);
         ++a;
             
         if( !a ) goto finish_b;
        }
       break;
           
       case CmpGreater :
        {
         fun(*b);
         ++b;
             
         if( !b ) goto finish_a;
        }
       break;
           
       case CmpEqual :
        {
         fun(*a);
         ++a;
         ++b;
             
         if( !a ) goto finish_b;
         if( !b ) goto finish_a;
        }  
      }  
      
  finish_a:
  
  for(; +a ;++a) fun(*a);   
  
  goto finish;
  
  finish_b:
  
  for(; +b ;++b) fun(*b);   
  
  finish:
  
  return ResultAttributes<FunctorType>::GetResult(fun);
 }
В XXI век с CCore.
Копай Нео, копай -- летать научишься. © Matrix. Парадоксы
Re: Убить goto
От: Кодт Россия  
Дата: 16.02.06 14:34
Оценка:
Здравствуйте, Шахтер, Вы писали:

Красиво, но несколько затратно (делаем лишние проверки).
while(a && b)
{
  switch(Cmp(*a,*b))
  {
  case CmpLess:    fun(*a); ++a; break;
  case CmpEqual:   fun(*a); ++a; ++b; break;
  case CmpGreater: fun(*b); ++b; break;
  }
}
while(a) { fun(*a); ++a; }
while(b) { fun(*b); ++b; }


Чтобы сэкономить — кешируем результаты проверок.
bool af=a, bf=b;
while(af && bf)
{
  switch(Cmp(*a,*b))
  {
  case CmpLess:    fun(*a); ++a; af=a; break;
  case CmpEqual:   fun(*a); ++a; af=a; ++b; bf=b; break;
  case CmpGreater: fun(*b); ++b; bf=b; break;
  }
}
if(af)
  do { fun(*a); ++a; } while(a);
else
if(bf)
  do { fun(*b); ++b; } while(b);

Наконец, можно делать вот так
#define try_finish(x,y) if(!(x)) { while(y) { fun(*(y)); ++(y); } return; }
// или инлайн-функцией

try_finish(a,b);
try_finish(b,a);

while(true)
{
  switch(Cmp(*a,*b))
  {
  case CmpLess:    fun(*a); ++a;      try_finish(a,b); break;
  case CmpGreater: fun(*b); ++b;      try_finish(b,a); break;
  case CmpEqual:   fun(*a); ++a; ++b; try_finish(a,b); try_finish(b,a);
  }
}
Перекуём баги на фичи!
Re[2]: Убить goto
От: night beast СССР  
Дата: 16.02.06 14:44
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Шахтер, Вы писали:

К>Красиво, но несколько затратно (делаем лишние проверки).
К>
К>while(a && b)
К>{
К>  switch(Cmp(*a,*b))
К>  {
К>  case CmpLess:    fun(*a); ++a; break;
К>  case CmpEqual:   fun(*a); ++a; ++b; break;
К>  case CmpGreater: fun(*b); ++b; break;
К>  }
К>}
К>while(a) { fun(*a); ++a; }
К>
К>


for ( ; ;) {
   if ( !a ) { while(b) { fun(*b); ++b; } break; }
   if ( !b ) { while(a) { fun(*a); ++a; } break; }

   switch (...)
}

Поправлено форматирование. — Кодт
Re: Убить goto
От: srggal Украина  
Дата: 16.02.06 15:10
Оценка:
Здравствуйте, Шахтер, Вы писали:

Ш>Вот фрагмент кода (слияние двух отсортированных последовательностей).
Ш>Задача -- красиво убить goto.

В код не вдумывался но от условия повеяло std::merge
... << RSDN@Home 1.1.4 stable rev. 510>>
Re[3]: Убить goto
От: Кодт Россия  
Дата: 16.02.06 15:54
Оценка:
Здравствуйте, night beast, Вы писали:

К>>Красиво, но несколько затратно (делаем лишние проверки).

NB>for ( ; ;) {
NB>   if ( !a ) { while(b) { fun(*b); ++b; } break; }
NB>   if ( !b ) { while(a) { fun(*a); ++a; } break; }

NB>   switch (...)
NB>}

Тоже неплохо. Кстати, всё равно есть лишние проверки.
Перекуём баги на фичи!
Re[4]: Убить goto
От: night beast СССР  
Дата: 16.02.06 16:56
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, night beast, Вы писали:

К>>>Красиво, но несколько затратно (делаем лишние проверки).

К>
NB>>for ( ; ;) {
NB>>   if ( !a ) { while(b) { fun(*b); ++b; } break; }
NB>>   if ( !b ) { while(a) { fun(*a); ++a; } break; }

NB>>   switch (...)
NB>>}
К>

К>Тоже неплохо. Кстати, всё равно есть лишние проверки.

никто и не спорит чисто субъективно -- все изменения в обном месте.

кстати, вспомнился занятный факт: continue в switch действует на внешний цикл.
таким образом, если в исходном тексте break заменить на continue, go to -- на break, и после switch
поставить break, то все должно работать.
не утверждаю, что это будет красивее
Re: Убить goto
От: Аноним  
Дата: 16.02.06 18:40
Оценка:
Если подразумевается классическое слияние то одной строчки не хватает: 
Ш>       case CmpEqual :
Ш>        {
Ш>         fun(*a);
>>>>>>>>>>>>fun(*a);
Ш>         ++a;
Ш>         ++b;
             
Ш>         if( !a ) goto finish_b;
Ш>         if( !b ) goto finish_a;
Ш>        }  
Ш>      }  
...      
Ш>
Re[2]: Убить goto
От: Шахтер Интернет  
Дата: 17.02.06 09:26
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Если подразумевается классическое слияние то одной строчки не хватает:

Нет, строится объединения множеств. Результирующая выходная последовательность строго монотонная.
В XXI век с CCore.
Копай Нео, копай -- летать научишься. © Matrix. Парадоксы
Re[3]: Убить goto
От: kan_izh Великобритания  
Дата: 17.02.06 13:31
Оценка:
Шахтер wrote:

> А>Если подразумевается классическое слияние то одной строчки не хватает:
> Нет, строится объединения множеств. Результирующая выходная
> последовательность строго монотонная.

А чем std::set_union не устраивает? Там, кстати, нет goto (по крайней мере в MSVC7.1 имплементации).
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[4]: Убить goto
От: Шахтер Интернет  
Дата: 17.02.06 13:46
Оценка:
Здравствуйте, kan_izh, Вы писали:

_>Шахтер wrote:

>> А>Если подразумевается классическое слияние то одной строчки не хватает:
>> Нет, строится объединения множеств. Результирующая выходная
>> последовательность строго монотонная.

_>А чем std::set_union не устраивает? Там, кстати, нет goto (по крайней мере в MSVC7.1 имплементации).

Этот вопрос оффтопик и вообще идиотский.
Не пробовал в автомобиль на бензиновом движке заливать диз-топливо?
В XXI век с CCore.
Копай Нео, копай -- летать научишься. © Matrix. Парадоксы
Re[5]: Убить goto
От: kan_izh Великобритания  
Дата: 17.02.06 14:03
Оценка: +1 -1 :)
Шахтер wrote:

>> > А>Если подразумевается классическое слияние то одной строчки не хватает:
>> > Нет, строится объединения множеств. Результирующая выходная
>> > последовательность строго монотонная.
> _>А чем std::set_union не устраивает? Там, кстати, нет goto (по крайней
> мере в MSVC7.1 имплементации).
> Этот вопрос оффтопик и вообще идиотский.
> Не пробовал в автомобиль на бензиновом движке заливать диз-топливо?
Если говорить метафорами, то твой вопрос выглядит "Я вот тут изобрёл велосипед, но колесо квадратное. Кто сможет
выпрямить?". Я лишь порекомендовал взглянуть на уже готовый. Не устраивает, так не устраивает, но хоть посмтотри как
круглые колёса делаются.
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[2]: Убить goto
От: _JoKe_  
Дата: 17.02.06 15:40
Оценка:
Здравствуйте, Кодт, Вы писали:
К>Красиво, но несколько затратно (делаем лишние проверки).
К>
К>while(a && b)
К>{
К>  switch(Cmp(*a,*b))
К>  {
К>  case CmpLess:    fun(*a); ++a; break;
К>  case CmpEqual:   fun(*a); ++a; ++b; break;
К>  case CmpGreater: fun(*b); ++b; break;
К>  }
К>}
К>while(a) { fun(*a); ++a; }
К>while(b) { fun(*b); ++b; }
К>


небольшая коррекция для пущей красоты

switch(Cmp(*a,*b))
{
 case CmpEqual:   fun(*a); ++b;
 case CmpLess:    fun(*a); ++a; break;
 case CmpGreater: fun(*b); ++b; break;
}
... << RSDN@Home 1.1.4 @@subversion >>
Re: Убить goto
От: Olegator  
Дата: 18.02.06 21:05
Оценка: 10 (1)
Здравствуйте, Шахтер, Вы писали:

Ш>Что-то много всякой фигнёй в последнее время страдаем (особенно философской).

Ш>Вот фрагмент кода (слияние двух отсортированных последовательностей).
Ш>Задача -- красиво убить goto.

А можно ли в объединяемые множества добавить по элементу? Если да, то нужно вставить в концы обеих последовательностей бесконечность.
... << RSDN@Home 1.1.4 stable rev. 510>>
Re[2]: Убить goto
От: Шахтер Интернет  
Дата: 20.02.06 08:06
Оценка:
Здравствуйте, Olegator, Вы писали:

O>Здравствуйте, Шахтер, Вы писали:

Ш>>Что-то много всякой фигнёй в последнее время страдаем (особенно философской).

Ш>>Вот фрагмент кода (слияние двух отсортированных последовательностей).
Ш>>Задача -- красиво убить goto.

O>А можно ли в объединяемые множества добавить по элементу? Если да, то нужно вставить в концы обеих последовательностей бесконечность.

Мысль красивая. Но, боюсь, что не реализуемая, поскольку бесконечное значение не предусмотрено в тех типах, которые используются с этим шаблоном.

Тем не менее -- засчитаю за решение.
В XXI век с CCore.
Копай Нео, копай -- летать научишься. © Matrix. Парадоксы
Re[2]: Убить goto
От: Шахтер Интернет  
Дата: 20.02.06 08:24
Оценка:
Здравствуйте, Olegator, Вы писали:

O>Здравствуйте, Шахтер, Вы писали:

Ш>>Что-то много всякой фигнёй в последнее время страдаем (особенно философской).

Ш>>Вот фрагмент кода (слияние двух отсортированных последовательностей).
Ш>>Задача -- красиво убить goto.

O>А можно ли в объединяемые множества добавить по элементу? Если да, то нужно вставить в концы обеих последовательностей бесконечность.

Можно ничего не вставлять, а использовать усовершенствованную функцию сравнения.

template <class Range>
CmpResult CmpFirstElement(Range a,Range b)
 {
  if( !a )
    {
     return (!b)?CmpEqual:CmpGreater;
    }

  if( !b ) return CmpLess;

  return Cmp(*a,*b);
 }


К сожалению, этот способ вносит ненужный оверхед тоже.
В XXI век с CCore.
Копай Нео, копай -- летать научишься. © Matrix. Парадоксы
Re[3]: Убить goto
От: _JoKe_  
Дата: 20.02.06 08:33
Оценка:
_JK>
_JK>switch(Cmp(*a,*b))
_JK>{
_JK> case CmpEqual:   /*fun(*a);*/ ++b;
_JK> case CmpLess:    fun(*a); ++a; break;
_JK> case CmpGreater: fun(*b); ++b; break;
_JK>}
_JK>


комент забыл поставить
... << RSDN@Home 1.1.4 @@subversion >>
Re: Убить goto
От: Vain Россия google.ru
Дата: 20.02.06 12:53
Оценка: 10 (1)
Здравствуйте, Шахтер, Вы писали:

Ш>Что-то много всякой фигнёй в последнее время страдаем (особенно философской).

Ш>Вот фрагмент кода (слияние двух отсортированных последовательностей).
Ш>Задача -- красиво убить goto.

template <class Range> 
template <class Collector>
typename ResultAttributes<typename Collector::FunctorType>::ResultType 
 UnionGenType<Range>::operator () (Collector collector) const
 {
  Range a=a_,b=b_;
  
  typedef typename Collector::FunctorType FunctorType;
  
  FunctorType fun(collector);
  
  struct FINISH_HIM {
    static A(Range& a,FunctorType& fun) {
      for(; +a ;++a) fun(*a);
    }
    static B(Range& b,FunctorType& fun) {
      for(; +b ;++b) fun(*b);
    }
  };

  if( !a ) FINISH_HIM::B(b,fun);
  else if( !b ) FINISH_HIM::A(a,fun);
  else
  for(;;)
    switch( Cmp(*a,*b) ) {
       case CmpLess: {
         fun(*a);
         ++a;             
         if( !a ) {
           FINISH_HIM::B(b,fun);
           break;
         }
       } break;           
       case CmpGreater: {
         fun(*b);
         ++b;
         if( !b ) {
           FINISH_HIM::A(a,fun);
           break;
         }
       } break;
       case CmpEqual: {
         fun(*a);
         ++a;
         ++b;
         if( !a ) {
           FINISH_HIM::B(b,fun);
           break;
         }
         if( !b ) {
           FINISH_HIM::A(a,fun);
           break;
         }
       } break; // :)
    }  
  return ResultAttributes<FunctorType>::GetResult(fun);
 }


мож что-где упустил, но общий аргумент должен быть ясен.. Ж)
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[2]: Убить goto
От: Шахтер Интернет  
Дата: 20.02.06 13:37
Оценка:
Здравствуйте, Vain, Вы писали:

V>мож что-где упустил, но общий аргумент должен быть ясен.. Ж)

Упустил то, что невозможен двухуровневый break.
Тут правда можно использовать break; -- continue;


template <class Range> 
template <class Collector>
typename ResultAttributes<typename Collector::FunctorType>::ResultType 
 UnionGenType<Range>::operator () (Collector collector) const
 {
  Range a=a_,b=b_;
  
  typedef typename Collector::FunctorType FunctorType;
  
  FunctorType fun(collector);

  struct Finish
   {
    FunctorType &fun;

    Finish(FunctorType &fun_) : fun(fun_) {}

    void operator () (Range r)
     {  
      for(; +r ;++r) fun(*r);
     }
   } finish(fun);
  
  if( !a ) 
    {
     finish(b);
    }
  else if( !b ) 
    {
     finish(a);
    }
  else 
    for(;;)
      {
       switch( Cmp(*a,*b) )
         {
          case CmpLess :
           {
            fun(*a);
            ++a;
             
            if( +a ) continue;

            finish(b);
           }
          break;
           
          case CmpGreater :
           {
            fun(*b);
            ++b;
             
            if( +b ) continue;

            finish(a);
           }
          break;
           
          case CmpEqual :
           {
            fun(*a);
            ++a;
            ++b;
             
            if( +a )
              {
               if( +b ) continue;

               finish(a);
              }  
            else
              {
               finish(b);  
              }
           }  
          break;
         }

       break;
      }  
      
  return ResultAttributes<FunctorType>::GetResult(fun);
 }
В XXI век с CCore.
Копай Нео, копай -- летать научишься. © Matrix. Парадоксы
Re[3]: Убить goto
От: Cyberax Марс  
Дата: 20.02.06 13:57
Оценка:
Шахтер wrote:
> Упустил то, что невозможен двухуровневый break.
> Тут правда можно использовать break; -- continue;
По-моему, исходный вариант с goto был понятнее
Posted via RSDN NNTP Server 2.0
Sapienti sat!
Re[4]: Убить goto
От: Шахтер Интернет  
Дата: 20.02.06 14:00
Оценка: +2
Здравствуйте, Cyberax, Вы писали:

C>Шахтер wrote:
>> Упустил то, что невозможен двухуровневый break.
>> Тут правда можно использовать break; -- continue;
C>По-моему, исходный вариант с goto был понятнее

Дык о том и речь. Мне кажется, что данный пример демонстрирует вредность догм в программировании. Одна из таких догм -- не используй goto.
Обычно он не нужен. Но иногда его использование совершенно оправдано.
В XXI век с CCore.
Копай Нео, копай -- летать научишься. © Matrix. Парадоксы
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.