IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> Структуры, heap, C++
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


Передо мной стоит следующая задача:

Есть (N<10^5) чисел, на каждом шаге алгоритма нужно находить 2 минимальных числа и заменять их на их сумму. Так делается до тех пор, пока не останется одно число. Сделать то я сделал, вот только работает это долго.

Знаю, что есть такая структура данных как куча, которая выдает минимальный элемент за O(1) и добавляет за O(log N). Но как это реализовывать не знаю, не нашел. А то, что находил, было совсем не понятно... возможно потому, что никогда не работал со структурами.

Может это можно реализовать на простом массиве?

Помогите, кто может. smile.gif

P.S.
Вот как я делал:


#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
int main()
{
ifstream in("input.txt");
ofstream out("output.txt");
out.setf(ios::fixed);
out.precision(2);
double sum=0,z;
int n,i,j,d=0;
vector <int> v;
in>>n;
for(i=0;i<n;i++)
{
in>>j;
v.push_back(j);
d++;
}
while (d>1)
{
sort(v.begin(),v.end());
z=v[0]+v[1];
sum+=z/100*5; //5% процентов от полученной суммы двух этих минимальных чисел
v.push_back(z);
v.erase(v.begin(),v.begin()+2);
d--;
}
out<<sum;
return 0;
}


Сообщение отредактировано: first_day -


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Цитата
Сделать то я сделал, вот только работает это долго
Можно посмотреть, как именно ты реализовал, и озвучить, что значит "долго", и насколько быстрее хочется?

Упс... Не успел. Но вторая часть вопроса - в силе...

Сообщение отредактировано: volvo -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


немного не то написал, через час покажу на примере.

в общем мой пример уже смысла не имеет smile.gif

Сообщение отредактировано: klem4 -


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


Цитата(volvo @ 2.05.2008 18:14) *

что значит "долго", и насколько быстрее хочется?


При моей реализации если N=5000 программа работает дольше секунды, а нужно, чтобы при N=100000 работало быстрее секунды


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Быстрее не быстрее, но 10-кратное ускорение на твоем же векторе можно получить не напрягаясь:
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
int main()
{
ifstream in("input.txt");
ofstream out("output.txt");

out.setf(ios::fixed);
out.precision(2);

int n, j;
vector<double> v;
in >> n;

for(int i = 0; i < n; i++) {
in >> j;
v.push_back((double)j);
}

double s = 0.0;
while (n > 1)
{
vector<double>::iterator i_min, i_max;
double mini_1 = *(i_min = min_element(v.begin(), v.end()));
v.erase(i_min);
double mini_2 = *(i_max = min_element(v.begin(), v.end()));
v.erase(i_max);

double sum_two = (mini_1 + mini_2);
s += sum_two / (double)100 * 5;
v.push_back(sum_two);
n -= 1;
}
out << s;
out.close();
return 0;
}

Откуда берется ускорение понимаешь? smile.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


Ну общий принцип вроде как да... Т.е. находим 2 минимальных элемента, а не соритруем, так?


vector<double>::iterator i_min, i_max;
double mini_1 = *(i_min = min_element(v.begin(), v.end())); //находится минимум?
v.erase(i_min);
double mini_2 = *(i_max = min_element(v.begin(), v.end())); //сново минимум?
v.erase(i_max);


Вот только про итераторы знаю я очень мало, это что-то вроде указателя?
А как быстро работает поиск минимума этим способом?

P.S.
Теперь считает при N=10000, еще бы раз в 10 ускорить... smile.gif


Сообщение отредактировано: first_day -


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






Цитата
Ну общий принцип вроде как да...
Как видно, не совсем понятно smile.gif У тебя огромное количество времени уходило на конвертацию int -> double, я это пресек, конвертация не нужна, время уменьшается...

Цитата
А как быстро работает поиск минимума этим способом?
Да уж быстрее, чем отсортировать, а потом брать первые 2 элемента. Но все равно, для того, чтобы показывать такие временнЫе характеристики, которые нужны тебе, vector-а недостаточно... Попробуй multiset, оно реализовано на деревьях, должно быть еще в несколько раз быстрее... Если уж и с multiset-ом не получится - тогда будем думать дальше...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


Знать бы что такое multiset... unsure.gif


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


интересное дело smile.gif Вот смотри: http://www.cplusplus.com/reference/stl/multiset/

надо попробовать, может будет быстрее.


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






По-моему я уже давал тебе ссылку на этот сайт: std::multiset
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


Цитата(klem4 @ 2.05.2008 19:44) *

интересное дело smile.gif Вот смотри: http://www.cplusplus.com/reference/stl/multiset/

надо попробовать, может будет быстрее.



Цитата(volvo @ 2.05.2008 19:44) *

По-моему я уже давал тебе ссылку на этот сайт: std::multiset

Да, нашел...
А еще нашел <priority_queue>
Но стандартные функции связаны с макимальным элементов(удаление, возвращение), можно ли как то изменить их на минимальные?

P.S. сейчас попробую c multiset

Сообщение отредактировано: first_day -


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






Цитата
можно ли как то изменить их на минимальные?

Запросто, меняем функцию сравнения:

priority_queue< double, vector<double>, greater<double> > q;



Добавлено через 10 мин.
Ааааа !!!! blink.gif blink.gif Держите меня... priority_queue обработала 10000 элементов за 0.156 секунды. Результат совпал с тем, который получен vector-ом...

#include <fstream>
#include <queue>
#include <algorithm>
#include <iomanip>
using namespace std;
int main()
{
ifstream in("input6.txt");
ofstream out("output6.txt");

out.setf(ios::fixed);
out.precision(2);

int n, j;
in >> n;
priority_queue< double, vector<double>, greater<double> > q;
for(int i = 0; i < n; i++) {
in >> j;
q.push((double)j);
}

double s = 0.0;
while (n > 1)
{
double min_1 = q.top(); q.pop();
double min_2 = q.top(); q.pop();

double sum_two = (min_1 + min_2);
s += sum_two / (double)100 * 5;
q.push(sum_two);
n -= 1;
}
out << s;
out.close();
return 0;
}

 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


Все получилось с multiset'ом Спасибо smile.gif
Вот что я написал: (за 0.5 секунды прошло)

#include <fstream>
#include <set>
#include <algorithm>
#include <iomanip>
using namespace std;
int main()
{
ifstream in("input.txt");
ofstream out("output.txt");

out.setf(ios::fixed);
out.precision(2);

int n, j;
multiset<double> m;
in >> n;

for(int i = 0; i < n; i++)
{
in >> j;
m.insert((double)j);
}

double s = 0.0;
while (n > 1)
{
multiset<double>::iterator i_min, i_max;
double mini_1 = *(i_min = m.begin());
m.erase(i_min);
double mini_2 = *(i_max = m.begin());
m.erase(i_max);

double sum_two = (mini_1 + mini_2);
s += sum_two / (double)100 * 5;
m.insert(sum_two);
n -= 1;
}

out << s;
out.close();
return 0;
}


Все ли нормально?
Т.е. в multiset'е данне всегда хранятся по неубыванию? Можно ли как-то сделать чтобы по неубыванию?

А про замену функции не понял, можно поподробнее?

P.S. Ой, не увидел, сейчас почитаю

Добавлено через 6 мин.
Непонятна лишь одна строчка:
priority_queue< double, vector<double>, greater<double> > q;
А конкретно: как вектор внутри кучи? И что значит greater? После этого все функции действуют наоборот(т.е. min вместо max)?

Сообщение отредактировано: first_day -


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Гость






Цитата
Непонятна лишь одна строчка:
Смотри... В файле queue приоритетная очередь определяется вот так:
   namespace std {
template <class T,
class Container = vector<T>,
class Compare = less<typename Container::value_type> >
class priority_queue;
}

, то есть, первый параметр - это тип элементов, с которым будет работать priority_queue, второй - тип контейнера, в котором все данные будут храниться внутри priority_queue (по умолчанию - vector<того_же_типа>), а третий - критерий сортировки. По умолчанию используется less<тип_элемента_контейнера>, тебе понадобилось "обратное" поведение, значит, меняем на greater<double>.

Цитата
После этого все функции действуют наоборот(т.е. min вместо max)?
Не все... Это будет заметно только при работе с priority_queue, и будет выражаться в том, что выдаваться результаты будут не по убыванию (сначала - бОльшие, потом - меньшие), а по возрастанию значений...

Сообщение отредактировано: volvo -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


Класс, и памяти в 3 раза меньше потратилось. good.gif


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской
Реальное имя: Илья

Репутация: -  1  +


Понятней стало, спасибо smile.gif


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 14:21
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name