В этой теме вы вряд ли найдёте что-то нужное, но собрать уже известные вещи в одном месте - тоже полезно.
Речь пойдёт о стандартных контейнерах - например <vector>, <queue> и тд.
В большинстве задач не требуется извращаться, и реализовывать их вручную,
но бывают и задачи, где активное использование STL недопустимо.
(либо ТЛ очень мал, либо большой объём данных)
Поэтому приведу реализации, которые сам использую.
Элементарные структуры данных
Сообщений 1 страница 21 из 21
Поделиться12009-01-08 14:54:27
Поделиться22009-01-08 15:14:05
Начнём по порядку.
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 раз)
Можно это реализовать в виде отдельного класса, но объект класса будет при создании выделять
память под все свои поля, и соответственно под весь массив, что неэффективно.
Поделиться32009-01-08 15:27:01
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
Поделиться42009-01-08 15:41:50
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
Поделиться52009-02-04 21:30:48
Данная реализация работает гораздо быстрее, чем 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-кратный выйгрыш ?
ззы: продолжаю писать нерабочие велосипеды
Поделиться62009-02-04 22:27:20
ну ты бы ещё написал свой класс вектор в котором бы использовался STL вектор...
Поделиться72009-02-04 22:47:50
я не понял, зачем мне это делать?
как мне написать вектор чтобы получить выйгрышь по времени ?
Поделиться82009-02-05 01:24:16
забей писать класс. =)
Поделиться92009-02-05 02:10:22
ты предлагаешь прямо в главной функции , не обьявляя класса, хранить голый массив?
Отредактировано trc (2009-02-05 02:10:41)
Поделиться102009-02-05 10:19:05
Я думаю, template <typename T> - и вся производительность летит к черту. А по поводу увеличения производительности - речь же идет о спортивных задачах и кусках кода, максимально критичных по времени. В них можно и нужно использовать голые массивы и всякие другие неприглядные вещи.
Поделиться112009-02-05 13:29:14
Ога. Именно так.
Хруст, выкладываешь копипаст кода из студии - замени табуляции на пробелы. =)
Отредактировано Ktulhu (2009-02-05 13:31:42)
Поделиться122009-02-05 16:13:40
Я думаю, 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 раза быстрее чем зашитые в класс или стл...
(но в моём случае это не подходит )
...пойду
Поделиться132009-02-05 17:01:01
провёл написание / исследование листа
#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)
Поделиться142009-02-05 19:09:45
Напиши мапу.
Поделиться152009-02-06 01:10:36
скажите как она работает и я напишу мапу!
Поделиться162009-02-06 01:20:17
А ты в дебаге или релизе проверяешь, разные результаты будут
Дебаг память отслеживает и разные там проверки делает, а релиз оптимизирует.
пишите письма
Поделиться172009-02-06 01:57:04
Написал письмо... не компилируется
Поделиться182009-02-06 09:59:03
Gubarev Valentin
в релизе естественно
Поделиться192009-02-08 00:32:53
Мапу проще всего реализовать декартовым деревом
Поделиться202009-02-08 17:18:10
Это наверное надо было во флуд добавить . Но меня взволновал вопрос, тут уже 3 e-maxx . Вы размножаетесь ?
Поделиться212009-02-09 15:15:49
Это наверное надо было во флуд добавить . Но меня взволновал вопрос, тут уже 3 e-maxx . Вы размножаетесь ?
не, просто с мобилы зайти какие-то баги (вероятно, из-за особенностей использования JS), поэтому каждый раз приходилось регить нового юзера. Теперь я вернулся из ПЗ, поэтому могу писать с компа под нормальным аккаунтом