Правила форума
Внимание!
Проблем собственно в том, что стоит создать файл тысячи на 2 - 3 сток, как программа перестает функционировать, но и это пол беды, основная заключается в том, что на примере 1000 строк время выполнение ужасно долгое...в остальном она функционирует, т.е. на маленьких файлах все отличняком, а вот на таких тестах обваливается - прошу помочь.... очень надо
Задание
Определите две реализации класса String. Требования:
Первая реализация. Каждый экземпляр класса содержит свой динамический буфер для хранения данных
Вторая реализация (использование механизма "copy on write"). Экземпляры классов, содержащие одинаковые данные (такие экземпляры можно получить, например, при операции присваивания либо через конструктор копирования), содержат ссылку на один и тот же буфер с данными.
Основные операторы, которые должны быть реализованы в классе String:
· String& operator = (const String& src)
· String& operator += (const String& right)
· String& operator += (const char* right)
· String operator + (const String& left, const String& right)
· String operator + (const String& left, const char * right)
· String operator + (const char* left, const String& right)
· bool operator == (const String& left, const String& right)
· bool operator != (const String& left, const String& right)
Для сравнения производительности этих двух реализаций напишите тестовую программу.
Код
test.c
// время выводится в тактах!!!
#include <time.h>
#include <iostream>
#include <fstream>
#include <stdio.h>
#include "strin.h"
#include "cont.h"
#include "copywrite.h"
using namespace std;
long long TimeValue=0;
long long time_RDTSC()
{
//asm("rdtsc");
_asm rdtsc
}
void time_start() { TimeValue=time_RDTSC(); }
long long time_stop()
{ return time_RDTSC()-TimeValue; }
int main()
{
int i,j;
char namefile[50];
char buf[1000];
//char* buf = (char*)malloc(sizeof(char)*2048);
int N,len;
ofstream outfile;
ifstream infile;
cout << "Vvedite name of file\n";
cin >> namefile;
cout << "Vvedite kolvo strok\n";
cin >> N;
cout << "Vvedite max dliny stroki\n";
cin >> len;
// создание файла
outfile.open(namefile);
if (!outfile)
{
cout << "Oshibka pri chtenii faila\n";
return 0;
}
else
{
char * str = new char[len*100000];
for(i=0; i<N; i++)
{
for(j = 0;j<len;j++)
{
str[j] = rand()%('z'-'a'+1)+'a';
}
str[len] = '\0';
outfile << str << "\n";
}
delete []str;
outfile.close();
}
// заполнение обоих контейнеров
Container <Strings> cont1;
Container <copywrite> cont2;
infile.open(namefile);
if (!infile)
cout << "Oshibka\n";
else
{
while(!infile.eof())
{
infile.getline(buf,len+1);
if (N<20)
cout << buf << "\n";
Strings s1(buf);
copywrite s2(buf);
cont1.cont_add(s1);
cont2.cont_add(s2);
}
infile.close();
}
// сортировка классической строки
time_start();
sort(cont1,0,cont1.cont_size()-1);
cout << "Vremya sortirovki klassicheskoi stroki! " << time_stop() << "\n";
if (N<20)
{
for (i=0; i<cont1.cont_size(); i++)
cont1[i].print();
}
// сортировка строки copy on write
time_start();
sort(cont2,0,cont2.cont_size()-1);
cout << "Vremya sortirovki copy on write stroki! " << time_stop()/100 << "\n";
if (N<20)
{
for (i=0; i<cont2.cont_size(); i++)
cont2[i].print();
}
getchar();
getchar();
return (0);
}
________________________________________
string.h
#include <string.h>
class Strings
{
private:
char* str;
public:
Strings()
{
str = new char;
*str = '\0';
}
Strings(Strings &b)
{
int i=0;
while (b.str[i]!='\0')
i++;
str=new char[i+1];
i=0;
while (b.str[i]!='\0')
{
str[i]=b.str[i];
i++;
}
str[i]='\0';
}
Strings(const char* str1)
{
int i=0;
while(str1[i]!='\0')
i++;
str=new char[i+1];
i=0;
while (str1[i]!='\0')
{
str[i]=str1[i];
i++;
}
str[i]='\0';
}
int dlinstr() const; // длина строки
int sravstr(const Strings& str1); // функция сравнения: 0 - равны
//1- больше, -1 - меньше
bool operator<(const Strings& str1);
Strings& operator=(const Strings& str1); // оператор копирования
void catstr(const Strings& str1); // оператор конкатенации
void print(); // вывод строки
~Strings()
{
delete []str;
}
};
_______________________________________________________________________________
strin.cpp
#include <string.h>
#include <iostream>
#include "strin.h"
using namespace std;
int Strings:: dlinstr() const
{
int i=0;
int n=0;
while (str[i]!='\0')
{
n++;
i++;
}
return(n);
}
bool Strings:: operator<(const Strings& str1)
{
if (strcmp(str1.str,str)>0)
return (true);
else
return (false);
}
Strings& Strings:: operator=(const Strings & str1)
{
delete []str;
str = new char[str1.dlinstr()+1];
int i=0;
while (str1.str[i]!='\0')
{
str[i]=str1.str[i];
i++;
}
str[i]='\0';
return (*this);
}
void Strings:: catstr(const Strings & str1)
{
char * tmp = new char[dlinstr() + str1.dlinstr() + 1];
int i=0;
int j=0;
while (str[i]!='\0')
{
tmp[i]=str[i];
i++;
}
while (str1.str[j]!='\0')
{
tmp[i]=str1.str[j];
i++;
j++;
}
tmp[i]='\0';
delete []str;
str = tmp;
}
void Strings::print()
{
cout << str << "\n";
}
_________________________________________________________
copywrite.h
class copywrite;
class block
{
private:
char * str;
int usecount;
public:
block()
{
str=new char;
str='\0';
usecount=0;
}
block(const char * str1);
block (block &b)
{
int i=0;
while (b.str[i]!='\0')
i++;
str=new char[i+1];
i=0;
while (b.str[i]!='\0')
{
str[i]=b.str[i];
i++;
}
str[i]='\0';
usecount=b.usecount;
}
void add_count(); // добавляем указатель
void del_count(); // удаляем указатель
int bllen() const;
int blsrav(const block &str1);
block& operator=(const block& str1);
block operator+(const block& str1);
void prin();
~block();
friend class copywrite;
};
class copywrite
{
private:
block *s; // указатель на блок
copywrite(block * b); // просто конструктор
public:
copywrite()
{
s=new block("");
s->add_count();
}
copywrite(const char* );
copywrite(const copywrite& str1); // конструктор копирования
int cwlen(); // длина строки
int cwsrav(const copywrite& str1); // сравнение строк
bool operator<(const copywrite& str1);
copywrite& operator=(const copywrite& str1); // присваивание строк
copywrite& operator+=(const copywrite& str1); // конкатенация строк
void print();
~copywrite(); // деструктор
friend class block;
};
_____________________________________________________________
copywrite.cpp
#include "copywrite.h"
#include <iostream>
using namespace std;
// для работы с блоком
block::block(const char *str1)
{
int i=0;
while(str1[i]!='\0')
i++;
str=new char[i+1];
i=0;
while (str1[i]!='\0')
{
str[i]=str1[i];
i++;
}
str[i]='\0';
usecount=0;
}
block& block:: operator=(const block& str1)
{
str=str1.str;
usecount=str1.usecount;
return(*this);
}
void block:: add_count()
{
usecount++;
}
void block::del_count()
{
usecount--;
if (usecount==0)
{
delete []str;
}
}
int block:: bllen() const
{
int i=0;
while(str[i]!='\0')
i++;
return (i);
}
int block::blsrav(const block& str1)
{
return strcmp(str1.str,str);
}
block block:: operator+(const block& str1)
{
int i=0;
int j=0;
char* str2=new char[bllen()+str1.bllen()+1];
while (str[i]!='\0')
{
str2[i]=str[i];
i++;
}
while (str1.str[j]!='\0')
{
str2[i]=str1.str[j];
i++;
j++;
}
str2[i]='\0';
block bl(str2);
delete []str2;
return bl;
}
block::~block()
{
delete []str;
}
// для работы со строкой
copywrite::copywrite(block * b)
{
s=b;
s->add_count();
}
copywrite::copywrite(const char *str1)
{
s=new block(str1);
s->add_count();
}
copywrite::copywrite(const copywrite& str1)
{
s=str1.s;
s->add_count();
}
int copywrite::cwlen()
{
int i;
i=s->bllen();
return (i);
}
int copywrite:: cwsrav(const copywrite& str1)
{
int j;
j=s->blsrav(*(str1.s));
return (j);
}
bool copywrite:: operator<(const copywrite& str1)
{
if (s->blsrav((*str1.s))>0)
return (true);
else
return (false);
}
copywrite& copywrite:: operator=(const copywrite& str1) // присваивание строк
{
block *b=s;
s=str1.s;
s->add_count();
b->del_count();
return (*this);
}
copywrite& copywrite:: operator+=(const copywrite& str1) // конкатенация строк
{
block * b = new block(*s);
(*b)=(*s)+(*str1.s);
b->add_count();
s->del_count();
s=b;
return(*this);
}
copywrite::~copywrite()
{
s->del_count();
}
void block::prin()
{
cout << str << "\n";
}
void copywrite::print()
{
s->prin();
}
______________________________________________________________
cont.h
#include <memory.h>
#include <iostream>
#include <exception>
using namespace std;
template <class mytype>
class Container
{
private:
mytype *m;
int size;
public:
Container();
class Range {}; // класс исключений
void cont_add(mytype data); // добавляет элемент в конец контейнера
void cont_insert(mytype data, int pos); //вставляет элемент в позицию pos
int cont_size() const; // размер контейнера
mytype cont_get(int pos) const; //возвращает данные из позиции pos
mytype cont_replace(mytype data, int pos); // заменяет данные в позиции pos. возвращает старые данные
mytype cont_remove(int pos); // удаляет данные из позиции pos
mytype operator[](int pos) const; // что-то типа итератора
mytype & operator[](int pos); // что-то типа итератора
~Container()
{
delete []m;
}
};
template <class mytype>
Container <mytype>:: Container()
{
size=0;
}
template <class mytype>
void Container<mytype>:: cont_add(mytype data) // Добавляет элемент в конец контейнера
{
int i;
mytype *n;
n=m;
m=new mytype[sizeof(mytype)*(size+1)];
if(n!=NULL)
{
for (i=0; i<size; i++)
m[i]=n[i];
}
m[size]=data;
size++;
// delete []n;
}
template <class mytype>
void Container<mytype>:: cont_insert(mytype data, int pos){ // Вставляет злемент в позицию pos
mytype *n=m;
m=new mytype[sizeof(mytype)*(size+1)];
if(pos>size)
{
pos = size;
}
if(n!=NULL)
{
memcpy(m,n,sizeof(mytype)*pos);
}
m[pos]=data;
if (n!=NULL)
{
memcpy(&(m[pos+1]),&(n[pos]),sizeof(mytype)*(size-pos));
}
size++;
delete []n;
}
template <class mytype>
int Container<mytype>:: cont_size() const // Возвращает размер контейнера
{
return (size);
}
template <class mytype>
mytype Container<mytype>:: cont_get(int pos) const // Возвращает данные в позиции pos
{
if (pos>=size)
{
throw Range();
}
return (m[pos]);
}
template <class mytype>
mytype Container<mytype>:: cont_replace(mytype data, int pos) // Заменяет данные в позиции pos. Возвращает старые данные.
{
if(pos>=size)
{
pos = size-1;
}
mytype d = m[pos];
m[pos] = data;
return d;
}
template <class mytype>
mytype Container<mytype>:: cont_remove(int pos) // Удаляет данные из позиции pos. Возвращает удаленные данные.
{
if(pos>=size)
{
throw Range();
}
mytype *n=m;
mytype p=m[pos];
if (size<=0)
{
throw Range();
}
m=new mytype[sizeof(mytype)*(size-1)];
if (size>1)
{
memcpy(m,n,sizeof(mytype)*pos);
memcpy(&(m[pos]),&(n[pos+1]),sizeof(mytype)*(size-pos-1));
}
else{
m = NULL;
}
delete []n;
size--;
return p;
}
template <class mytype>
mytype Container<mytype>::operator[](int pos) const
{
if ((pos>=0) && (pos<size))
return (m[pos]);
else{throw std::out_of_range("Error position");}
}
template <class mytype>
mytype & Container<mytype>::operator[](int pos)
{
if ((pos>=0) && (pos<size))
return (m[pos]);
else{throw std::out_of_range("Error position");}
}
// сортировка
template <class mytype>
void sort(Container<mytype> &cont,int l, int r)
{
mytype x,w;
int i,j;
i=l; j=r;
x=cont[(l+r)/2];
do{
while(cont[i]<x) i++;
while (x<cont[j]) j--;
if(i<=j){
w=cont[i]; cont[i]=cont[j];
cont[j]=w; i++; j--;
}
}
while (i<j);
if(l<j)
sort(cont,l,j);
if(r>i)
sort(cont,i,r);
}
Сообщение отредактировано: Neonig -
