Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Офтопик
Перезагрузить страницу Длинная пробельная строка
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Rocky Rocky вне форума
Member
 
Сообщений: 1,405
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.10.2004
По умолчанию 02.12.2008, 18:40

Всем привет! Не знаю где расзместить тему, так что если надо, ув. модераторы перенесите ее...

Задали такую задачку на одном собеседовании.

Цитата:
Длинная пробельная строка
В библиотеке, которую вы используете, есть строковый класс String. Вы пишете функцию для создания пробельной строки. К сожалению, класс String обладает неудобным интерфейсом и вам приходится написать следующий код:

String spaces(int n) {
String s;
for (int i = 0; i < n; ++i)
s = s + ' ';
return s;
}

Если вы вызовете эту функцию для создания строки из миллиона пробелов, то время ее работы окажется чрезмерно большим.
Сколько времени работает функция spaces?
Напишите как можно более быструю функцию spaces, не меняя класса String. Этот класс снабжен операциями + (конкатенация), = (присвоение), литералами “” (пустая строка) и ‘ ‘ (один пробел).
Сколько времени будет работать быстрая функция spaces?
Напишите и протестируйте быстрый вариант функции spaces.
Сам класс String
Код:
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <iostream>

class String {
public:
            String     ();
            String     (char c);
            String     (const String& s);
           ~String     ();
    String& operator = (const String& s);
    String  operator + (const String& s) const;
    int     length     () const;
private:
                       String (const String& s1, const String& s2);
                 void  swap   (String& s);
    static const char* make   (int size1    , const char* pS1    , 
                               int size2 = 0, const char* pS2 = 0  );
    static       void  copy   (char *pD, int size, const char *pS);

          int   size;
    const char* pString;
};

String spaces (int n);

int main() {
    const std::clock_t start = clock();

    String s = spaces(100000);

    const std::clock_t finish = clock();
    const double duration = static_cast<double>(finish - start) / CLOCKS_PER_SEC;

    std::cout << "length " << s.length() << '\n';
    std::cout << "duration " << duration << '\n';
    return 0;
}

String::String() 
: size    (0   ), 
  pString (NULL)  {
}
String::String(char c)
: size    (     1     ), 
  pString (make(1, &c))  {
}

String::String(const String& s)
: size    (     s.size            ), 
  pString (make(s.size, s.pString))  {
}

String::~String() {
    delete [] pString;
}

String& String::operator =(const String& s) {
    String temp(s);
    swap(temp);
    return *this;
}

String String::operator +(const String& s) const {
    return String(*this, s);
}

int String::length() const {
    return size;
}

String::String(const String& s1, const String& s2)
: size    (     s1.size            + s2.size             ), 
  pString (make(s1.size, s1.pString, s2.size, s2.pString))  {
}

void String::swap(String& s) {
    const int         size    = s   . size  ;
    const char*       pString = s   . pString;

                s   . size    = this->size  ;
                s   . pString = this->pString;

                this->size    =       size  ;
                this->pString =       pString;
}

const char* String::make(int size1, const char* pS1, 
                         int size2, const char* pS2  ) {
    char *buffer = new char[size1 + size2];
    if (buffer == 0) {
        assert(false);
        return 0;
    }
    copy(buffer        , size1, pS1);
    copy(buffer + size1, size2, pS2);
    return buffer;
}

void String::copy(char *pD, int size, const char *pS) {
    if (pD != 0) {
        if (pS == 0) {
            std::memset(pD, 0, size);
        } else {
            std::memcpy(pD, pS, size);
        }
    }
}

String spaces(int n) {
    String s;
    for (int i = 0; i < n; ++i)
        s = s + ' ';
    return s;
}

У меня с их программой получалось время выполнения ~37 сек. Я сделал так, что время составило 0 сек. Так вот мне сказали, что можно еще быстрее )))))) Забавно как-то ))

Вобщем, если кому не лень, кто как думает написать функцию spaces(...)?
Ответить с цитированием
  (#2 (permalink)) Старый
Garik Garik вне форума
Member
 
Сообщений: 6,201
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 07.06.2002
По умолчанию 02.12.2008, 18:54

Очень интересно... И как же тебе удалось её оптимизировать?
Ответить с цитированием
  (#3 (permalink)) Старый
Jonano Jonano вне форума
Специалист
 
Аватар для Jonano
 
Сообщений: 3,541
Сказал(а) спасибо: 2
Поблагодарили 14 раз(а) в 14 сообщениях
Регистрация: 19.04.2005
По умолчанию 02.12.2008, 19:26

Код:
String spaces(int n) 
{
    String s = "";
    
    int counter = 0;
    
    while(counter < n)
    { 
         String tmp = ' ';
         int i = 1;
         while(i*2 + counter < n)
         {
             tmp = tmp + tmp;
             i*=2;
         }
         s = s + tmp;
         counter += i;
    }
    return s;
}
У тебя кстати, в посте в функции main стоит 100000, а не миллион.
Ответить с цитированием
  (#4 (permalink)) Старый
Rocky Rocky вне форума
Member
 
Сообщений: 1,405
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.10.2004
По умолчанию 02.12.2008, 22:05

Цитата:
У тебя кстати, в посте в функции main стоит 100000, а не миллион.
Угу, это задание такое )) я тоже обратил внимание.

Еще один момент:

Цитата:
Этот класс снабжен операциями ...... литералами ”” ...............
А вот в реализации класса конструктора, принимающего char* нет.
Так что
Код:
String s = "";
не скомпилмтся. Ну это не суть важно..

Мой код был такой:
Код:
String spaces2(int n) 
{
    String s, sSpace(' ');
    if (n < 8)
    {
        for (int i = 0; i < n; ++i)
        {
            s = s + sSpace;
        }
        return s;
    }
    
    sSpace = sSpace + sSpace + sSpace + sSpace;
    const int n2 = n / 8;
       for (int i = 0; i < n2; ++i)
    {
        s = s + sSpace;    
    }

    return s + s;
}
// это как у них
length 100000
duration 34.159

//твой вариант
length 100000
duration 0.01

//мой варинт
length 100000
duration 0.01


А можно овообще так сделать (называется карманник):
Код:
#define private public
...........
class String {/*ничего не менял, все по-прежнему*/};
...........

//дальше можно извращаться по-разному, хоть через memset напрямую писать, только память выделить надо
String spaces(int n) 
{
    std::string sss;
    sss.resize(n, ' ');
    String sRetVal;
    sRetVal.pString = String::make(n, sss.c_str());
    sRetVal.size = n;
    return sRetVal;
}
Хоть так делать и нельзя, но условий задачи он не нарушает, а работает практически мгновенно.

//результаты такие
length 100000
duration 0
Ответить с цитированием
  (#5 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,266
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 03.12.2008, 00:56

Они, вероятно, хотели увидеть что-то такое:
Код:
String spaces (int n) 
{
  String tmp, res;
  tmp = " "; // пробел
  res = "";  // пустая строка
  for (int mask = 1; mask < n; mask <<= 1)
  {
    if (n & mask)
    {
      res = res + tmp;
    }
    tmp = tmp + tmp;
  }
  return res;
}
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Jonano Jonano вне форума
Специалист
 
Аватар для Jonano
 
Сообщений: 3,541
Сказал(а) спасибо: 2
Поблагодарили 14 раз(а) в 14 сообщениях
Регистрация: 19.04.2005
По умолчанию 03.12.2008, 11:23

Цитата:
А вот в реализации класса конструктора, принимающего char* нет.
Так что
Код:
String s = "";
не скомпилмтся. Ну это не суть важно..
Ну тогда String s; просто

Рокки, ты попробуй наши варианты прогнать на скорость. Желательно с миллисекундами. Ну и со своими результатами сравни. Вот и будет тебе ответ, что быстрее всего.
Ответить с цитированием
  (#7 (permalink)) Старый
Rocky Rocky вне форума
Member
 
Сообщений: 1,405
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.10.2004
По умолчанию 03.12.2008, 13:23

Я уже прогнал. Твой вариант примерно как и мой (который без #define private public -- ф-я spaces2). Вариант Alexiski на 2-3 сотых секунды получился быстрее. Т.е. если у нас с тобой ~ 0.03 сек, то у Alexiski ~ 0.01 (усреднял из примерно 10-ти раз). Кстати забавно, я к сожалению плохо знаю побитовые сдвиги, надо бы подтянуть. Ну, разумеется если напрямую писать в данные класса, то получается самый быстрый вариант.
Ответить с цитированием
  (#8 (permalink)) Старый
Влад Влад вне форума
Специалист
 
Сообщений: 3,884
Сказал(а) спасибо: 1
Поблагодарили 25 раз(а) в 25 сообщениях
Регистрация: 27.06.2002
Адрес: Санкт-Петербург
По умолчанию 03.12.2008, 17:55

Миллион (да!) пробелов, GCC 3.4.5, Release, -O3, Wix XP SP2, CPU 3 ГГц HT, RAM 1 Гб:
Код:
Перв.     очень много! устал ждать
Rocky      19.140 s
Alexeiski   0.015 s
Jonano      0.046 s
На MSVC++ 2005 тот же код: код Rocky немного улучшил время (до 18.6 сек.), остальные без изменения.


The difference between theory and practice is that in theory, there is no difference between theory and practice, but in practice, there is.
Ответить с цитированием
  (#9 (permalink)) Старый
Rocky Rocky вне форума
Member
 
Сообщений: 1,405
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.10.2004
По умолчанию 03.12.2008, 18:59


Фиг знает, дома Athlon 3000+, OpenSuse 10.2, VirtualBox, WinXP SP2, msvc2005. Под винду 1Гб RAM, получается 0.03 s и компилировал в дебаге без оптимизации.
Ответить с цитированием
  (#10 (permalink)) Старый
Jonano Jonano вне форума
Специалист
 
Аватар для Jonano
 
Сообщений: 3,541
Сказал(а) спасибо: 2
Поблагодарили 14 раз(а) в 14 сообщениях
Регистрация: 19.04.2005
По умолчанию 03.12.2008, 19:03

Цитата:
получается 0.03 s
Это 100000 или 1000000?
Ответить с цитированием
  (#11 (permalink)) Старый
Rocky Rocky вне форума
Member
 
Сообщений: 1,405
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.10.2004
По умолчанию 03.12.2008, 19:04

это сто тыщ. Как в коде было изначально )))))))) Я типа хитрый
Ща винду запущу, попробую миллион
Ответить с цитированием
  (#12 (permalink)) Старый
Rocky Rocky вне форума
Member
 
Сообщений: 1,405
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.10.2004
По умолчанию 03.12.2008, 19:21

Вот с миллионом (с усреднением из 10 раз):

Код:
1: 0.0461  //Alexiski
2: 190.05 //Rocky 1 (а со сто тыщ 1.5 сек, не знаю откуда я взял до этого 0.03, пойду выпью яду :D)
3: 0.1682  //Jonano
4: 0.01  //Rocky 2

Система та же, что выше писал, тока release -O2 (O3 не знаю где поставить, там тока O1, O2 и Ox)... Влад, там точно у тебя в посте 19.140 сек, нолик нигде не затерялся? Пипец я тупой ))))))))))))
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
Rocky Rocky вне форума
Member
 
Сообщений: 1,405
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.10.2004
По умолчанию 03.12.2008, 22:02

Сходил, выпил... помогло

Для миллиона:
Код:
 1: 0.095 s  //Alexiski
2: 0.1523 s  //Rocky 3
3: 0.3195 s //Jonano
4: 0.03 s  //Rocky 2
Вариант Rocky 3
Код:
String sRetVal, sBuf(' '), sEmptyString;
while (sRetval.length() < n)
{
    sRetVal = sEmptyString;
    for (int i = 0; i < 10; ++i) sRetVal = sRetval + sBuf;
    sBuf = sRetVal;
}

return sRetVal;
Ответить с цитированием
  (#14 (permalink)) Старый
Jonano Jonano вне форума
Специалист
 
Аватар для Jonano
 
Сообщений: 3,541
Сказал(а) спасибо: 2
Поблагодарили 14 раз(а) в 14 сообщениях
Регистрация: 19.04.2005
По умолчанию 03.12.2008, 22:22

А вариант Rocky 2 какой?
Ответить с цитированием
  (#15 (permalink)) Старый
Rocky Rocky вне форума
Member
 
Сообщений: 1,405
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.10.2004
По умолчанию 03.12.2008, 22:25

См. вчерашний пост мой, от 21:05

Код:
#define private public
...........
class String {/*ничего не менял, все по-прежнему*/};
...........

//дальше можно извращаться по-разному, хоть через memset напрямую писать, только память выделить надо
String spaces(int n)
{
    std::string sss;
    sss.resize(n, ' ');
    String sRetVal;
    sRetVal.pString = String::make(n, sss.c_str());
    sRetVal.size = n;
    return sRetVal;
}
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача-Паскаль. Длинная арифметика. Ksuuu Pascal 1 24.05.2011 22:57
Длинная арифметика построение двух столбиков СтуденткаЯ Delphi 1 26.12.2010 20:19
Есть ли в C# длинная арифметика Exmap .NET 5 05.08.2008 15:30
Самая длинная ветка в дереве (наверное) Yusuke Prolog 18 05.12.2007 21:26
Командная строка korniec Операционная система Windows 5 20.05.2007 13:03
Бегущая строка strertkjh Pascal 5 14.05.2007 17:22
Адресная строка Алексеев Николай PHP 1 16.11.2006 11:35
Строка наоборот imported_Torch Pascal 6 08.08.2006 06:26
Строка в int как ее переобразовывать Dimitrii Java 5 27.07.2004 08:08
адресная строка zornig PHP 7 17.06.2004 15:41
Длинная строка символов без разделителей Anonymous PHP 1 15.12.2003 02:27



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов