ACM - Псков

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.


Вы здесь » ACM - Псков » Структуры данных » Элементарные структуры данных


Элементарные структуры данных

Сообщений 1 страница 21 из 21

1

В этой теме вы вряд ли найдёте что-то нужное, но собрать уже известные вещи в одном месте - тоже полезно.
Речь пойдёт о стандартных контейнерах - например <vector>, <queue> и тд.
В большинстве задач не требуется извращаться, и реализовывать их вручную,
но бывают и задачи, где активное использование STL недопустимо.
(либо ТЛ очень мал, либо большой объём данных)
Поэтому приведу реализации, которые сам использую.

2

Начнём по порядку.

vector
Представляет собой ни что иное как банальный динамический массив.
Должен поддерживать следующие операции:
-  push - встака элемента в конец массива
-  size - возвращает количество элементов
-  clear - очищает вектор
-  pop - удаляет последний элемент

Очевидно, что для реализации этих операций потребуется
-  массив для хранения элементов
-  счётчик для реализации операций

Рассмотрим на примере вектора содержащего элементы типа int

Объявления:

int maxn = 100000  (максимальное количество элементов, столько сколько нужно для конкретной задачи)
int vector[maxn]  (собственно массив)
int vp = 0;  (счётчик, можно хранить в нулевом элементе массива, тогда не потребуется заводить новую переменную, но нумерация элементов в векторе будет не с 0, а с 1.  Я предпочитаю завести новую переменную.)

Реализация операций:
- push
{   
vector[vp] = element;
vp++;
}

- size
значение переменной vp =)

- clear
{
vp = 0;
}

- pop
{
vp--;
}

Данная реализация работает гораздо быстрее, чем STL vector  <int> в  C++ (примерно в 10 раз)
Можно это реализовать в виде отдельного класса,  но объект класса будет при создании выделять
память под все свои поля, и соответственно под весь массив, что неэффективно.

3

queue
Очередь.
Должна поддерживать следующие операции:
-  push - встака элемента в конец очереди
-  pop - удаляет первый элемент
-  empty - проверка на наличие элементов
-  clear - очищает очередь

Для реализации этих операций потребуется
-  массив для хранения элементов
-  счётчики для реализации операций

Рассмотрим на примере очереди содержащей элементы типа int

Объявления:

int maxn = 100000  (максимальное количество элементов, столько сколько нужно для конкретной задачи)
int queue[maxn]  (собственно массив)
int qs = 0; номер первого элемента 
int qf = 0; номер последнего элемента

Реализация операций:
- push
{   
queue[qf] = element;
qf++;
}

- pop
{
qs++;
}

- clear
{
qs=0;
qf=0;
}

- empty
пуста, если qs == qf

4

stack
Стек.
Должен поддерживать следующие операции:
-  push - встака элемента в конец стека
-  pop - удаляет последний элемент
-  empty - проверка на наличие элементов
-  clear - очищает стек

Для реализации этих операций потребуется
-  массив для хранения элементов
-  счётчики для реализации операций

Рассмотрим на примере очереди содержащей элементы типа int

Объявления:

int maxn = 100000  (максимальное количество элементов, столько сколько нужно для конкретной задачи)
int stack[maxn]  (собственно массив)
int sp = 0; номер последнего элемента

Реализация операций:
- push
{   
stack[sp] = element;
sp++;
}

- pop
{
sp--;
}

- clear
{
sp = 0;
}

- empty
пуст, если sp == 0

Реализация не отличается от реализации вектора.
Задачка на стек: http://acm.timus.ru/problem.aspx?space=1&num=1494

5

Ktulhu написал(а):

Данная реализация работает гораздо быстрее, чем STL vector  <int> в  C++ (примерно в 10 раз)

попробовал написать собственный вектор(требовалась вставка в конец, очистка)

Код:
    #define V_SIZE 32768
	template <class T> class vector{
public:
	vector():size(0){};
	
	T a[V_SIZE];
	int size;


	void push_back(T elem){
    a[size++]=elem;
	}
	void clear(){
    size=0;
	}
};

замер времени работы осуществлял при помощи следующей функции:

Код:
	vector<int> v;

int t1=GetTickCount();  

	for (int j=0; j<V_SIZE; ++j){
	for (int i=0; i<V_SIZE; ++i){
    v.push_back(i);
	}
	v.clear();

	}
t1=GetTickCount()-t1;  //время работы цикла

итого: 32768*32768 вставок +32768 очисток;

время на проведение данного количества операций:

Код:
//мой вектор
(размер     время (миллисекунды))
32768    5968	
32768    5969
32768    5937
32768    5937
32768    5953

среднее:	5952,8

//стл вектор
32768    5922	
32768    5704
32768    5719
32768    5735
32768    5734

среднее:	5762,8

тоетсь теряется 0,2 секунды при использовании самописного вектора;

а по сему факту вопрос: в чём заключается тот самый 10-кратный выйгрыш ?

ззы: продолжаю писать нерабочие велосипеды :)

6

ну ты бы ещё написал свой класс вектор в котором бы использовался STL вектор...

7

я не понял, зачем мне это делать?
как мне написать вектор чтобы получить выйгрышь по времени ?

8

забей писать класс. =)

9

ты предлагаешь прямо в главной функции , не обьявляя класса, хранить голый массив?

Отредактировано trc (2009-02-05 02:10:41)

10

Я думаю, template <typename T> - и вся производительность летит к черту. А по поводу увеличения производительности - речь же идет о спортивных задачах и кусках кода, максимально критичных по времени. В них можно и нужно использовать голые массивы и всякие другие неприглядные вещи.

11

Ога. Именно так.
Хруст, выкладываешь копипаст кода из студии - замени табуляции на пробелы. =)

Отредактировано Ktulhu (2009-02-05 13:31:42)

12

Ikari написал(а):

Я думаю, template <typename T> - и вся производительность летит к черту.

изменил:

Код:
#define V_SIZE 32768
class _vector{

#ifndef V_SIZE
#define V_SIZE 1024
#endif

public:

#define T int
     _vector():size(0){};

     T a[V_SIZE];
     int size;


     void push_back(T elem){
          a[size++]=elem;
     }
     void clear(){
          size=0;
     }
};

результат работы :

Код:
32768	5656
32768	5688
32768	5813

теперь выйгрыш 0,1 секунды

сделал голые массивы

Код:
32768	1281
32768	1281
32768	1281

работает в 4 раза быстрее чем зашитые в класс или стл...
(но в моём случае это не подходит :( )
...пойду

13

провёл написание / исследование листа

Код:
#define L_SIZE 1024
     template <class T> class _list{

#ifndef L_SIZE
#define L_SIZE 1024
#endif

public:

     _list():size(1),senter(0){
     next[senter]=&a[senter]; prev[senter]=&a[senter];
     };

     stack<int> store;     //сейчас используется стл. позже следует написать свой !
     T a[L_SIZE],*next[L_SIZE],*prev[L_SIZE];



     typedef T* iterator;

     int size,senter;
     int get_size(){
          return size;
     }
//     T operator[]( int index ){
//          return *(a+index);
//     }

     void push_back(T elem){
          int cur;
          if (store.empty()) {cur=size;     ++size;} else {cur=store.top(); store.pop();++size;}
          a[cur]=elem;

          prev[cur] =prev[senter];
          next[cur] =&a[senter];
          next[prev[senter]-a]=&a[cur];
          prev[senter]=&a[cur];
     }

     T* begin(){
          return next[senter];
     }
     T* end(){
          return &a[senter];
     }

     void erase(iterator it){
          int t=it-a;
          store.push(t);
          --size;
          next[prev[t]-a]=next[t];
          prev[next[t]-a]=prev[t];
          *it=999;
     }

     void clear(){
          size=0;
          prev[0]=a;
          next[0]=a;
     }

};

дабы не заморачиваться на директиве new юзал стэк

функция для замера:

Код:
for (int k=1;k<10;++k){
     for (int i=0; i<L_SIZE-1;++i){
          l.push_back(i);
     };
     it=l.begin();
     while (it!=l.end()){
          l.erase(it);
          it=l.begin();
     }
}

результаты временных тестов:

Код:
100000 109  //моя
100000 109


100000 30359 //стл
100000 30969

ускорение в 300 раз (прикольно :) )
собственно это итак было известно...

если сделать голые массивы:

100000 734    //без класса
100000 719
100000 718
100000 735

100000 719   //с классом
100000 734
100000 734
выйгрыша нет (тоже прикольно, так как в векторе был 4верной выйгрышь, а тут... :) )

продолжаю писать велосипеды... на очереди - разбор стэков  :)

Отредактировано trc (2009-02-05 17:02:36)

14

Напиши мапу.   :D

15

скажите как она работает и я напишу мапу!

16

А ты в дебаге или релизе проверяешь, разные результаты будут :)
Дебаг память отслеживает и разные там проверки делает, а релиз оптимизирует.

пишите письма

17

Написал письмо... не компилируется  :crazy:

18

Gubarev Valentin
в релизе естественно

19

Мапу проще всего реализовать декартовым деревом

20

Это наверное надо было во флуд добавить :). Но меня взволновал вопрос, тут уже 3 e-maxx :). Вы размножаетесь :)?

21

atimofeyev написал(а):

Это наверное надо было во флуд добавить . Но меня взволновал вопрос, тут уже 3 e-maxx . Вы размножаетесь ?

:) не, просто с мобилы зайти какие-то баги (вероятно, из-за особенностей использования JS), поэтому каждый раз приходилось регить нового юзера. Теперь я вернулся из ПЗ, поэтому могу писать с компа под нормальным аккаунтом :)


Вы здесь » ACM - Псков » Структуры данных » Элементарные структуры данных