Задачка

[NetRaider]

Что-то тут активности почти никакой...

Предлагаю всем, кто хочет решить следующую задачу:

Реализовать функцию обращения(reverse) слов в строке. Например:
"1111" -> "1111"
"abcd dcba" -> "dcba abcd"
"123456 23" -> "654321 32"
"www kelehs moc" -> "www shelek com"
и т.д.

Условия:
1)Слова состоят из алфавитно-цифровых символов.
2)Разделитель слов - один или несколько пробелов.
3)Других символов нет.

Прототип ф-ии: void word_reverse(std::string& str)

Победителю приз - другая задачка  

[RXL]

Предпочитаю C.

Код:

void word_reverse(char *s) {
  char *w,c;
  int i,l;

  for(w=s;*w;w++) if(*w!=' ') {
    for(l=0;w[l]!=' ' && w[l];l++);
    for(i=0;i<(l/2);i++) | c=w[i]; w[i]=w[l-i-1]; w[l-i-1]=c; }
    w+=l;
    }
  }

[NetRaider]

Код:

void word_reverse(char *s) {
  char *w,c; 
  int i,l; 

  for(w=s;*w;w++) if(*w!=' ') {
    for(l=0;w[l]!=' ' && w[l];l++); 
    for(i=0;i<(l/2);i++) { c=w[i]; w[i]=w[l-i-1]; w[l-i-1]=c; }
    w+=l; 
    }
  }

Тут баг есть  . Запись за границу входного буфера.

[RXL]

Действительно. Тогда вот так:

Код:

void word_reverse(char *s) {
  char *w,c; 
  int i,l; 

  for(w=s;*w;w++) if(*w!=' ') {
    for(l=0;w[l]!=' ' && w[l];l++);
    for(i=0;i<(l/2);i++) { c=w[i]; w[i]=w[l-i-1]; w[l-i-1]=c; }
    w+=l;
    if(*w) break;
    }
  }

[grozny]

мой вариант (оформлено как консольное приложение, MSVC 7.1):

Код:

#include "stdafx.h"

#include <ctype.h>
#include <conio.h>
void reverseWord(char*s)
{
    char    c;
    char* beg;  //word begins here
    char* end;  //word ends here
    char* cp=s; //current pointer

    while(*cp)
    {
        beg=cp;end=beg;
        for(cp=end;*end && !isspace(end[1]);end++,cp=end);
        
        if(!*end && end>beg) 
            --end;
        else
            cp+=2;
        
        while(end>beg)
        {
            c=*end;
            *end--=*beg;
            *beg++=c;
        }
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    char phrase1[]="Defines the entry point for the console application   }; 
    //corner cases:
    char phrase2[]=""; 
    char phrase3[]=" ";
    char phrase4[]="blah";
    char* phrase;
    char* phrases[]={phrase1,phrase2,phrase3,phrase4,"\xFF"};

    for(int i=0;*phrases[i]!='\xFF';i++)
    {
        phrase=phrases[i];
        printf("before : '%s'\n",phrase);
        reverseWord(phrase);
        printf("1st run: '%s'\n",phrase);
        reverseWord(phrase);
        printf("2nd run: '%s'\n",phrase);
        printf("==================================\n");
    }
    getch();
    return 0;
}

[grozny]

Пояснения:
- можно улучшить в 2-х местах: сделать обмен через XOR и пооптимальнее организовать вычисления end в серединке. А то он елозит туда-сюда. Дальше думать неохота.
 
В предыдущем решении всё правильно и хорошо. Ну разве что за исключением сравнения с литералом ' ' - макрос isspace(x) портабельнее и яснее. Да и читать тяжело

А мне захотелось написать на указателях, без счётчиков и без целого деления напополам (что есть сдвиг на 1, ну да все в курсе, я полагаю).

[sas]

C++ variant. Did not compile though, so sorry for possible errors

Код:

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

const string FINISH_WORK = "quit";

//
// cin.getline also possible...
string& read_str( string& s )
{
    s = "";

    char c;
    while ( cin.get( c ) && c != '\n' ) 
        s += c;

    return s;
}

string& reverse_words( string& s )
{
    string::iterator si = s.begin(), ei, send = s.end();
    while ( true ) {
        while ( si != send && ::isspace( *si ) ) ++si; 
        if ( si == send ) break;
        ei = si + 1;
        while ( ei != send && !::isspace( *ei ) ) ++ei;
        reverse( si, ei );
        if ( ei == send ) break;
        si = ei + 1;
    }
    return s;
}

int main()
{
    cout << "Reverse chars in all typed words.\n\n\tTo exit please type \""
         << FINISH_WORK << "\" (no double quotes around)\n\n";
    string s;
    while ( true ) {
        cout << "\nPlease enter your sentence below (\"" 
             << FINISH_WORK << "\" to exit):\n";
        if ( read_str( s ) == FINISH_WORK ) break;
        cout << "Original [" << s << "]" << endl; // need endl here
        cout << "Reversed [" << reverse_words( s ) << "]\n"; 
    }
    return 0;
}

Thanks
--- sas

[RXL]

Ну разве что за исключением сравнения с литералом ' ' - макрос isspace(x) портабельнее и яснее. Да и читать тяжело

isspace() работает согласно настройки локали и, как правило, детектит не только пробел (по "С" локали - \f,\r,\n,\t,\v). По заданию же есть только символы isalnum() и разделитель ' ', и поэтому получаются лишние вычисления. На крайний случай можно сделать свой макрос (x==' ').
А чем тяжело читать? На мой вкус и цвет - очень просто и компактно. Чем компактнее, тем меньше глазам по строчкам бегать и легче сосредоточиться на понимании.

[grozny]

isspace() работает согласно настройки локали и, как правило, детектит не только пробел (по "С" локали - \f,\r,\n,\t,\v). По заданию же есть только символы isalnum() и разделитель ' ', и поэтому получаются лишние вычисления. На крайний случай можно сделать свой макрос (x==' ').
А чем тяжело читать? На мой вкус и цвет - очень просто и компактно. Чем компактнее, тем меньше глазам по строчкам бегать и легче сосредоточиться на понимании.

Дык! Именно - согласно локали... Слова могут отделяться не только пробелами. А лишних вычислений там - ещё одно сравнение.
А если на Юникод или широкий символ переходить, то тебе все литералы придётся вылавливать и менять.

Предпочитаю читать код с хорошо отделёнными конструкциями, с одним предписанием на строчку. До меня так быстрее доходит . Дело вкуса, конешно.

[NetRaider]

Слова могут отделяться не только пробелами. А лишних вычислений там - ещё одно сравнение.
А если на Юникод или широкий символ переходить, то тебе все литералы придётся вылавливать и менять.

Могут..., но не в этой задаче

А вот мой монстрик из трех строк:

Код:

void word_reverse(std::string& str, const char delim = ' ') 
{
    std::string::size_type begin = 0, end = 0;
    while(((begin = str.find_first_not_of(delim, end)) != str.npos)) 
        std::reverse(str.begin() + begin, str.begin() + (((end = str.find_first_of(delim, begin)) == str.npos) ? str.length(): end));	
}

[sas]

Слова могут отделяться не только пробелами. А лишних вычислений там - ещё одно сравнение.
А если на Юникод или широкий символ переходить, то тебе все литералы придётся вылавливать и менять.

Могут..., но не в этой задаче

А вот мой монстрик из трех строк:

Код:

void word_reverse(std::string& str, const char delim = ' ') 
{
    std::string::size_type begin = 0, end = 0;
    while(((begin = str.find_first_not_of(delim, end)) != str.npos)) 
        std::reverse(str.begin() + begin, str.begin() + (((end = str.find_first_of(delim, begin)) == str.npos) ? str.length(): end));	
}

Nice!

--- sas

[RXL]

grozny, в принципе согласен, но с "А лишних вычислений там - ещё одно сравнение" не соглашусь. Если бы набор был фиксированный, то наверно да, а у нас набор зависит от локали. Следовательно isspace() выполняет цикл сравнения с группой символов.

NetRaider, здорово.
А нет ли в std::string готовой ф-ии word_reverse() ?

[Гром]

RXL,  

[Serega]

RXL, на самом деле isspace конечно же не сравнивает в цикле, это было бы слишком накладно, все делается с помощью таблицы

[RXL]

Это уже лучше...
Но что делать - условие задачи...

[Alexandru Pojoga]

Может, рекурсивно?

[Гром]

Alexandru Pojoga, ты из румынии и так хорошо читаешь по русски??? Ну дела - во география расширилась.

[grozny]

Может, рекурсивно?

в теории красиво, но очень накладно. Глубина рекурсии в MSVC 6.0 реально то ли 6, то ли 8, но всяко меньше 10.

[Alexandru Pojoga]

Я вообще-то из Молдавии, только живу в Румынии.

>> Глубина рекурсии в MSVC 6.0 реально то ли 6, то ли 8, но всяко меньше 10.

А вот это не понимаю. Как так? Стек же он огромный?

[grozny]

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

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

...
The Stack Allocations (/STACK:reserve[,commit]) option sets the size of the stack in bytes.

To find this option in the development environment, click Settings on the Project menu. Then click the Link tab, and click Output in the Category box. The Reserve text box (or in the reserve argument on the command line) specifies the total stack allocation in virtual memory. The default stack size is 1 MB.

не так уж и дофига по нынешним временам...

[Alexandru Pojoga]

> The default stack size is 1 MB.
> не так уж и дофига по нынешним временам...

Я написал маленькую функцию, у VC6 на каждый call уходит 92 байта (плюс локальные переменные).

В 1 МБ вполне жить можно...  

[grozny]

Да кто б спорил. Зависит от задачи. Мне надо было разобрать списки, содержащие покрытие неких фрагментов памяти на разном кол-ве прогонов и пометить что на каком прогоне исполнялось. Разбивка/сортировка перекрывающихся по прогонам отрезков отлично ложится на рекурсию. НО: при типичной конфигурации в 10 тыс. отрезков/прогон и всего лишь 6 прогонах наступала полная задница всей красивой рекурсии.

[Alexandru Pojoga]

Да уж, рекурсия красива только на бумаге. А так...

[lapulya]

а что подразумевается под словом прогон (может я просто чего то не монимаю)

вот это работает без проблем...

int sum_seq(int a)
{
   return (a-- > 0) ?  a + sum_seq(a) : 0;
}

void main()
{
   int d = sum_seq(1000);
}

[grozny]

прогон = program run , execution . Древнесоветский программерский арго. Тогда все термины переводили во избежание низкопоклонства перед западом (и многие удачно, я бы сказал)

[Alf]

Да уж, рекурсия красива только на бумаге. А так...

По-моему, она и на деле неплохо выглядит. Впрочем, посудите сами:

Код:

#include "stdafx.h"

void ReverceWord(char* &p)
{
  char c;
  if (c = *p) 
    if (' ' != c) {
      ReverceWord(++p);
      printf("%c", c);
    }
}

void ReverceStr(char* &p)
{
  while (*p)
    if (' ' != *p) {
      ReverceWord(p);
      else
        printf("%c", *p++);
    }
}

int main(int argc, char* argv[])
{
  char Buffer[100];
  char *P = Buffer;
  scanf("%[^\n]s", Buffer);
  ReverceStr(P);
  printf("\n");
  return 0;
}

Недостатки:
-Использование стека (правда, с теми ужасами, которые здесь писали про катастрофическую нехватку места в стеке, на практике не сталкивался). Глубина рекурсии равна длине слова во входном тексте. Надеюсь, в реальных текстах слова не настолько длинны, чтобы проблема стала актуальной.

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

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

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


Наконец, рекурсия просто красива сама по себе. Хорошо сказал Дойч: "Итерация свойственна человеку, рекурсия - божественна".

[Anonymous]

Может, рекурсивно?

в теории красиво, но очень накладно. Глубина рекурсии в MSVC 6.0 реально то ли 6, то ли 8, но всяко меньше 10.

Не всяко.
Был уверен, что это не так, но захотелось убедиться воочию. в предыдущую программку ввел "слово" размером 50. Проскочила.
Длиннее было лень буквы считать, тем более что наверняка этот предел уж куда больше.
Раз уж залез в отладчик,заодно глянул на поведение стека (лень было на пальцах байты считать). Оказалось, что на каждый рекурсивный вызов функции ReverceWord отводится 0x5C байт (92 десятичное).
Кстати, заодно уж и в MSDN заглянул. Как отметил grozny, размер стека по умолчанию 1Мб. Если маловато, опция линкера /STACK:reserve[,commit] позволяет установить желаемое значение. Так что для разумного использования рекурсии стек помехой не будет.

[Alf]

Прошу прощения, малость промахнулся. В предыдущем сообщении Гость = Alf

[Алексей++]

for(w=s;*w;w++) if(*w!=' ') {

это цитата из первого пота Эр-Экселя.

зачем в серединке  *w возникло ?

[Джон]

это проверка условия - 0 значит ничего нет - false

[Anonymous]

а, дошло!  

______
1153

[grozny]

Был уверен, что это не так, но захотелось убедиться воочию. в предыдущую программку ввел "слово" размером 50. Проскочила.
Длиннее было лень буквы считать, тем более что наверняка этот предел уж куда больше.

да не настаиваю, что для данной задачи рекурсивное решение - непригодное с практической точки зрения. Всё зависит от граничных условий. 50 буковок - мало, конечно, 1 Мб стэк не вычерпать. И разницы в скорости не ощутить.

А чё, я разве утверждал, что реверсия 50 буковок исчерпает стэк? Если так, то неясно выразился. По-моему, я приводил пример из разбиения отрезков в несколько тыщ отрезков на интерацию и 6-7 итераций на отбой...

Вот фразы на немецком, например, знаш какие длинные бывают - на 200 символов.

А вот попробуй, реверсировать текст "Войны и Мир", например. Всего-то пара мегабайт.

Другой момент - скорость. Исходя из общих соображений, рекурсия (вызов ф-ции) всегда медленнее, чем итерация цикла.

Если не лень, то сравни время обработки набора из, ну скажем, 100000 случайных слов твоего любимого размера (50? ) рекурсивным и развёрнутым алгоритмом.

Мне - лень, 8)  поэтому нагло утверждаю, что рекурсия будет медленнее раза эдак в 3 минимум.

[Alf]

А чё, я разве утверждал, что реверсия 50 буковок исчерпает стэк? Если так, то неясно выразился.

Скорее всего, действительно неясно. Ибо фраза "Глубина рекурсии в MSVC 6.0 реально то ли 6, то ли 8, но всяко меньше 10" действительно может быть понята по-разному. Я воспринял это как глубину вызова, а что имел в виду ты?

Вот фразы на немецком, например, знаш какие длинные бывают - на 200 символов.

Именно это, кстати, мне и пришло в голову, когда писал об ограничениях программы. Ну что ж, если на перевернутые тексты создастся повышенный спрос, выпустим специальную версию для Германии с увеличенным стеком  
А если серьезно, то на один вызов уходит немного меньше 100 байт. Думаю, и 20-килобайтный стек современный комп выделить сумеет.

А вот попробуй, реверсировать текст "Войны и Мир", например. Всего-то пара мегабайт.

А вот запросто. Если посмотришь внимательнее, то увидишь, что на самом деле рекурсивна только функция реверса слова. Уткнулись в пробел - пошла обратная раскрутка стека (собственно, этим-то я и воспользовался для извлечения литер в обратном порядке). Так что максимальная глубина рекурсии равна длине самого длинного слова в тексте.
Вот кабы переворачивать весь текст - другое дело. Но там бы я и не рискнул на рекурсию. Во-первых, и впрямь памяти не напасешься, во-вторых, искать начало и конец цепочки не нужно - она одна, и итерация будет столь же краткой и выразительной, а то и получше.

Другой момент - скорость. Исходя из общих соображений, рекурсия (вызов ф-ции) всегда медленнее, чем итерация цикла.

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

Если не лень, то сравни время обработки набора из, ну скажем, 100000 случайных слов твоего любимого размера (50? ) рекурсивным и развёрнутым алгоритмом.

Давай только выберем, какой из вариантов берем за эталон итеративного подхода. Их много накидали все-таки. С рекурсией проще - выбирать не из чего.

[Kuzmich]

Объясните пожалуйста как это понимать:
(char* p) понятно, а что значит (char* &p)  :?:

[Alf]

Объясните пожалуйста как это понимать:
(char* p) понятно, а что значит (char* &p)  :?:

Я так понял, вопрос ко мне? Проглядел другие варианты, ни у кого больше не нашел эту конструкцию.
Сам по себе значок амперсанда & означает оператор поименования (получения ссылки). Если раньше не приходилось сталкиваться, то проще всего представить его себе как обратный к оператору разыменования *. Наверное, это выглядит сумбурно, поэтому поясню небольшим примером:

Код:

SomeType st; // переменная какого-то типа
SomeType *stp; // указатель на тот же тип
...
stp = &st; // присвоили stp ссылку на st
// отныне stp указывает на st,
//   т.е. *stp и st на самом деле одно и то же

В данном случае конструкция (char* &p) означает, что я передаю в функцию указатель на char по ссылке.
Дело в том, что параметры в С и С++ передаются в функцию по значению, т.е. функция получает копию значения аргумента. Таким образом функции защищают программу от побочных действий (правила хорошего тона диктуют явный возврат значения через результат функции, но не всегда так получается).
Передавая указатель на char по ссылке (фактически передается адрес указателя), я получил возможность в качестве побочного эффекта функции продвигать его на следующий символ, что в данном случае пришлось весьма кстати.
Надеюсь, не запутал еще сильнее?

[grozny]

А чё, я разве утверждал, что реверсия 50 буковок исчерпает стэк? Если так, то неясно выразился.

Скорее всего, действительно неясно. Ибо фраза "Глубина рекурсии в MSVC 6.0 реально то ли 6, то ли 8, но всяко меньше 10" действительно может быть понята по-разному. Я воспринял это как глубину вызова, а что имел в виду ты?

Да, это глубина вызова, но для моей задачи (а не для ревервирования слов), которую я реализовал под MSVC 6 (покрытие отрезков) . Перечитал свой мессадж - и вправду непонятно.  :oops:

Как было: быстренько написал "красивое" рекурсивное решение, протестировал на простеньких случаях (10-20 отрезков) - всё отлично, но на первом же боевом случае (5-6 тыщ отрезков) задачка упала в рекурсии (на глубине то ли 6, то ли 8) и пришлось разворачивать рекурсию в цикл.

А вот попробуй, реверсировать текст "Войны и Мир", например. Всего-то пара мегабайт.

уточняю условие  :twisted: - вся "Война и Мир" - одно слово. Мой пойнт в том, что реализация рекурсии - всегда хрупкая и малопредсказуемая программа. Т.е. малейшие модификации граничных условий убивают твою программу (что часто бывает в реальной жизни, ага - назавтра приходит заказчик  и говорит, что слова у пигмейском языке бывают и 1000 буковок, и вообще он задумывается над реверсированием Торы в 10 книгах .

Применение рекурсии даёт неустойчивое решение к вариации граничных условий, учёно выражаясь.

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

Другой момент - скорость. Исходя из общих соображений, рекурсия (вызов ф-ции) всегда медленнее, чем итерация цикла.

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

Что там у нас? один вызов strlen() на слово (не глядя в код). Против рекурсивного вызова ф-ции на каждой букве. Те самые разы.

Давай только выберем, какой из вариантов берем за эталон итеративного подхода. Их много накидали все-таки. С рекурсией проще - выбирать не из чего.

да пофигу - какой нравится. Я ж утверждаю, что они в разных скоростных категориях. Ну мой, например  

[Alf]

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

Согласен... Мизерная такая вариация граничных условий, на каких-то жалких 6 порядков. Переход с байт в мегабайты, даже и упоминать такой пустяк неловко.
Для натурного эксперимента касательно неустойчивости граничных условий можно взять, скажем, легковой автомобиль и нагрузить его... Нет, не в миллион раз больше максимальной паспортной нагрузки, у меня и гирь столько не найдется. Думаю, хватит и 10-кратной перегрузки. Фото того, что останется, потом выложим на форум.

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

Любые проявления экстремизма не приветствую. По мне, так куда полезнее для практической жизни владеть обоими подходами, а также обладать чувством меры, которое подскажет, когда какой уместнее.
Каюсь, грешен. Кто-то произнес заветное слово "рекурсия", после которого руки сам потянулись немного нахулиганить в этом направлении. В данном случае рекурсия притянута за уши скорее в качестве анекдота, решения наизнанку (которое тем не менее работает в пределах ограничений, установленных автором задачи. Шла бы речь об инверсии терабайтных цепочек, и мысли бы такой не возникло). Сработали застарелые Лиспо-Прологовские инстинкты.
Однако есть же задачи, рекурсивные по самой своей сути. Попробуйте-ка построить итеративный калькулятор арифметических выражений по всем правилам приоритетности операций. Или решить задачу о четырех красках (одна из классических в сборнике Уэзерелла, если кто еще помнит). Безусловно, можно. Но я бы врагу не пожелал. Это вам не реверс цепочек.

[grozny]

Мизерная такая вариация граничных условий, на каких-то жалких 6 порядков

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

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

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

Тем не менее, экстремизм - вредная вещь. Рекурсия, как и goto, должна быть в арсенале любого программиста - бесспорно. Можно жить и без того и без другого, но зачем ограничивать? Важно понимать, чем ты рискуешь (стабильностью продукта) и что теряешь (масштабируемость), применяя рекурсию.

на том и порешим.  

На ЛИСПе (или Прологе) можно написать *всё* и программа для машины Тьюринга представима рекурсией *всегда*.

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