std: sort vs inserting into std :: set

Question

Я читаю некоторые сегменты линии из cin. Каждый сегмент линии представлен начальной и конечной точкой. 2D. X и Y.

Вход не отсортирован. Это в случайном порядке. (Обновление: но мне они сначала отсортированы по X, а затем по Y)

Я могу читать во всех сегментах, хранить их в векторе, а затем вызывать std :: sort. С другой стороны, я могу создать пустой std :: set и вставить каждый сегмент по мере его поступления. Набор автоматически сохранит отсортированный порядок. Какой из двух подходов более эффективен?

Обновление: общий размер ввода (количество сегментов) известен заранее.

Answer 1

Вы должны измерить производительность обоих подходов, чтобы быть уверенным, но это безопасная ставка, чтобы предположить, что std::sort на std::vector является способ быстрее, чем вставка в std::set из-за локальности эффектов и больших констант, скрывающихся в дереве алгоритм вставки. Кроме того, последующие запросы и итерация будут выполняться быстрее.

(Тем не менее, std::set лучше подходит для поддержки смешанного ряда вставок и делеции/выборок/итераций. Поддержание порядка в векторе является дорогостоящим, поскольку каждая вставка будет принимать линейное время в среднем.)

Answer 2

Используй контейнер который имеет соответствующую семантику для ваших нужд. Эффективность обычно следует автоматически с этого выбора.

Если вы затем испытываете узкие места в производительности, выполните некоторые бенчмаркинга.

Answer 3

Это действительно зависит, но он уверен, что std::set предназначен для случайных вставок и стираний. В этом случае вы только вставляете. Идите с std::vector. Кроме того, возможно, что более важно, если вы заранее знаете, сколько сегментов есть, вам нужно всего лишь выделить вектор только один раз, он не будет перераспределять память каждый раз, когда он удваивается по размеру.

Answer 4

Как хорошее эмпирическое правило, предлагаются более строгие гарантии, тем хуже производительность.

Вставка в std::set гарантирует, что последовательность сортируется после каждой вставки.

Вставка в std::vector, и призывая std::sortраз после все вставки были сделаны гарантии, что последовательность сортируется раз все манипуляции на vector были сделаны. Это не требует, чтобы вектор был отсортирован во время всех промежуточных вставок.

A std::vector также обладает лучшей пространственной локальностью и требует меньшего выделения памяти. Таким образом, я бы предположил, что подход vector будет быстрее, но если для вас важна производительность, то это имеет значение, чтобы быть измеряется.

Если вы не заботитесь, чтобы измерить то, что быстрее в вашем случае для ваших наборов данных с вашего кода в вашего приложения, то вам не все равно, что быстрее.