Поделитесь опытом, наиболее быстрый способ найти подмножество M в множестве N упорядоченных целых чисел по условию "больше чем k и меньше чем q"?
Например дано множество N: set<int> array;
Пусть ~1 000 000 элементов, и требуется диапазон [100,8000) т.е.:
1. Итератор указывающий на первое число больше чем 99;
2. Итератор указывающий на первое число больше чем 7999.
(вроде правильно)
Вроде просто, но что-то ничего толкового в голову не приходит.
Специализированный "доморощенный" бинарный поиск aka велосипед?
Из algorithm подойдет что-нибудь?
K>Поделитесь опытом, наиболее быстрый способ найти подмножество M в множестве N упорядоченных целых чисел по условию "больше чем k и меньше чем q"?
K>Например дано множество N: set<int> array; K>Пусть ~1 000 000 элементов, и требуется диапазон [100,8000) т.е.: K>1. Итератор указывающий на первое число больше чем 99; K>2. Итератор указывающий на первое число больше чем 7999. K>(вроде правильно)
вызывать у сет'а метод lower_bound, от начала до конца, потом upper_bound от полученного итератора до конца
Здравствуйте, Sni4ok, Вы писали:
S>Здравствуйте, kvasya, Вы писали:
K>>Поделитесь опытом, наиболее быстрый способ найти подмножество M в множестве N упорядоченных целых чисел по условию "больше чем k и меньше чем q"?
K>>Например дано множество N: set<int> array; K>>Пусть ~1 000 000 элементов, и требуется диапазон [100,8000) т.е.: K>>1. Итератор указывающий на первое число больше чем 99; K>>2. Итератор указывающий на первое число больше чем 7999. K>>(вроде правильно)
S>вызывать у сет'а метод lower_bound, от начала до конца, потом upper_bound от полученного итератора до конца
Думается это именно то, что мне нужно по условию задачи. Буду учить матчасть.
Здравствуйте, kvasya, Вы писали:
K>Поделитесь опытом, наиболее быстрый способ найти подмножество M в множестве N упорядоченных целых чисел по условию "больше чем k и меньше чем q"?
K>Например дано множество N: set<int> array; K>Пусть ~1 000 000 элементов, и требуется диапазон [100,8000) т.е.: K>1. Итератор указывающий на первое число больше чем 99; K>2. Итератор указывающий на первое число больше чем 7999. K>(вроде правильно)
Это потребует 2*log(n) операций. Можно написать собственный алгоритм, который будет искать оба значения сразу, и «раздваиваться», только когда оба конца окажутся в разных половинах рассматриваемого интервала, но он будет эффективнее не более чем в два раза.
Здравствуйте, Sni4ok, Вы писали:
K>>Например дано множество N: set<int> array; K>>Пусть ~1 000 000 элементов, и требуется диапазон [100,8000) т.е.: K>>1. Итератор указывающий на первое число больше чем 99; K>>2. Итератор указывающий на первое число больше чем 7999. K>>(вроде правильно)
S>вызывать у сет'а метод lower_bound, от начала до конца, потом upper_bound от полученного итератора до конца
Есть мнение, что собственный метод set::lower_bound по всему множеству будет быстрее, чем общий алгоритм std::lower_bound по подмножеству. Из-за специфической организации std::set’а: собственный метод пойдёт в точности по узлам дерева, а общий алгоритм — как попало.