ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Быстрый способ сгруппировать значения std::map
11 сообщений из 11, страница 1 из 1
Быстрый способ сгруппировать значения std::map
    #39626332
13th
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
13th
Гость
Добрый день.

Есть такие структурка и map:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
	struct CSomeStruct
	{
		int nLeftValue;
		int nRightValue;
	};

	std::map<double, CSomeStruct> mapValues;


значения double могут быть со знаками после запятой. Надо сгруппировать по значениям от 0 до 1, от 1 до 2, от 2 до 3 и т.д., результат сложить в вектор:
Код: plaintext
1.
	std::map<double, CSomeStruct> mapSummedStruct;


под группировкой я подразумеваю SUM: в векторе будет лежать CSomeStruct, в котором будет сумма nLeftValue и nRightValue по всем структурам мапы, которые попадают в диапазон;

Есть один ньюанс: Разряжённой может быть как шкала, так и данные. Что я имею ввиду:
1. Разряжённая шкала: шкала от 0 до 10 с шагом 1. В мапе 10М струтктур, в каждую единицу шкалы попадает в среднем по 1М структур;
2. Разряжённые данные: шкала от 0.0 до 1.0 с шагом 0.000 000 01 (10М), В мапе 200 единиц структур (именно поэтому результат складывается в map а не vector);
Причём разряженность достаточно большая (десятки, сотни миллионов единиц), т.о. полный перебор только по одной из сущностей может привести к ступору. А алгоритм должен работать быстро - это часть UI.

Можно, конечно, и самому написать два алгоритма и переключать их в зависимости от того, чего больше, но может есть более красивое решение?
...
Рейтинг: 0 / 0
05.04.2018, 18:54
| Ответить | Цитировать | Написать  
Быстрый способ сгруппировать значения std::map
    #39626350
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
std::map отсортирован по ключу, поэтому задача в один проход решается. Быстрее невозможно.
Последовательно суммируешь то что попадает в один диапазон, как только появился элемент за диапазоном - сохраняешь результат и т.д.
...
Рейтинг: 0 / 0
05.04.2018, 19:42
| Ответить | Цитировать | Написать  
Быстрый способ сгруппировать значения std::map
    #39626371
13th
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
13th
Гость
Dima T, а может какой-нибудь итератор есть, который ключи по порядку перебирает?
...
Рейтинг: 0 / 0
05.04.2018, 20:17
| Ответить | Цитировать | Написать  
Быстрый способ сгруппировать значения std::map
    #39626374
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
13thDima T, а может какой-нибудь итератор есть, который ключи по порядку перебирает?
Обычный итератор перебирает
Код: plaintext
1.
2.
3.
 // show content:
  for (std::map<char,int>::iterator it=mymap.begin(); it!=mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';


пример отсюда http://www.cplusplus.com/reference/map/map/begin/
...
Рейтинг: 0 / 0
05.04.2018, 20:26
| Ответить | Цитировать | Написать  
Быстрый способ сгруппировать значения std::map
    #39626494
AlekseySQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AlekseySQL
Гость
Честно говоря, использовать в качестве ключа double- не очень хорошее решение. Ведь идея заключается в том, чтобы по ключу получать значения, а вы не можете точно повторить double: он вечно будет в милитысячных отличаться. Поэтому получить по ключу что- либо становится просто невозможно.

Думаю лучше было переменную типа double положить в структуру CSomeStruct, которые хранить:
1. В контейнере set с функцией сравнения
Код: plaintext
1.
2.
3.
4.
        static bool Sort_vDouble(const CSomeStruct& a, const CSomeStruct& b)
        {
            return a.vDouble < b.vDouble;
        }



2. В контейнере vector и перед накоплением итоговых значений его отсортировать той же самой функцией.
...
Рейтинг: 0 / 0
06.04.2018, 08:20
| Ответить | Цитировать | Написать  
Быстрый способ сгруппировать значения std::map
    #39626512
13th
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
13th
Гость
AlekseySQLЧестно говоря, использовать в качестве ключа double- не очень хорошее решение. Ведь идея заключается в том, чтобы по ключу получать значения, а вы не можете точно повторить double: он вечно будет в милитысячных отличаться.
Да, я знаю. Но спасибо за напоминание. У меня, конечно же, не double, а нормальная обёртка со всеми операторами сравнения, преобразования и т.д. Double я написал для простоты.
...
Рейтинг: 0 / 0
06.04.2018, 08:52
| Ответить | Цитировать | Написать  
Быстрый способ сгруппировать значения std::map
    #39626685
13th
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
13th
Гость
Вот так сделал. Если где-то можно ещё подтюнить, буду благодарен за совет:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
	for (map<CLevel, SData>::const_reverse_iterator i = mapSrcData.rbegin(); i != mapSrcData.rend(); i++)
	{
		CLevel dIndex = i->first;
		SData data = i->second;
		dLevel = _priceMax - (CLevel(floor(((_priceMax - dIndex) / _priceDelta).to_double())) * _priceDelta);
		if (dIndex > _priceMax || dIndex < (_priceMin - _priceDelta))
			continue;
		if (mapResult.find(dLevel) == mapResult.end())
		{
			mapResult[dLevel] = data;
		}
		else
		{
			mapResult[dLevel].nUpVolume += data.nUpVolume;
			mapResult[dLevel].nDownVolume += data.nDownVolume;
		}
	}
...
Рейтинг: 0 / 0
06.04.2018, 11:45
| Ответить | Цитировать | Написать  
Быстрый способ сгруппировать значения std::map
    #39626732
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
13thЕсли где-то можно ещё подтюнить, буду благодарен за совет

Как уже сказали: накапливай агрегат в переменной, а в результирующий список его сбрасывай
только при изменении dLevel. Сейчас ты тратишь туеву хучу времени на обращение к mapResult
на каждом цикле.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
06.04.2018, 12:31
| Ответить | Цитировать | Написать  
Быстрый способ сгруппировать значения std::map
    #39626771
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
13th
значения double могут быть со знаками после запятой.


double ВСЕГДА со знаками после запятой.
Правда, ты, видимо, об этом не знаешь...

13th
Код: plaintext
1.
	std::map<double, CSomeStruct> mapSummedStruct;




MAP с ключём типа double ?
Парень, ты хорошо подумал, прежде чем это делать?
...
Рейтинг: 0 / 0
06.04.2018, 13:20
| Ответить | Цитировать | Написать  
Быстрый способ сгруппировать значения std::map
    #39626772
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
13th Надо сгруппировать по значениям от 0 до 1, от 1 до 2, от 2 до 3 и т.д., результат сложить в вектор:


Тут нет ничего сложного.
Бежишь по записям map-а, и суммируешь.
Хочешь -- в вектор, хочешь -- в другой map складывай.
Зависит от констрейнтов на алгоритм.
Про то, что map отсортирован по ключу, тебе уже сказали.
Итого O(N), один пробег.
...
Рейтинг: 0 / 0
06.04.2018, 13:22
| Ответить | Цитировать | Написать  
Быстрый способ сгруппировать значения std::map
    #39626774
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
AlekseySQLЧестно говоря, использовать в качестве ключа double- не очень хорошее решение.


Не не очень хорошее, а очень плохое решение.
Но для данной задачи пофиг, главное, что записи там лежат, и отсортированы.
А задачи поиска в map по ключу тут и не стоит.

Подозреваю, задача и возникла изза того, что были проблемы с поиском по иррациональным числам.
...
Рейтинг: 0 / 0
06.04.2018, 13:24
| Ответить | Цитировать | Написать  
11 сообщений из 11, страница 1 из 1
Форумы / C++ [игнор отключен] [закрыт для гостей] / Быстрый способ сгруппировать значения std::map
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]