LINUX.ORG.RU

сложность удаления из вектора по значению

 ,


1

5

Есть код c++11:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> a{1,2,3,4,5,6,7,8,9};
    
    for(auto it=a.begin(); it!=a.end();)
    {
        if (*it % 2)
        {
            it=a.erase(it);
        }
        else
        {
            ++it;
        }
    }

    for(auto& i:a)std::cout<<i<<',';
}

Какая сложность алгоритма?)

Мой ответ O(N). Ответ интервьюера O(N*N), т.к. после каждого удаления вектор «перестраивается или что».


естессно при удалении элемента хвост сдвигается на одну позицию влево. ну да примерно N*N

alysnix ★★★
()

O(1), в коде нет размерности N.

snizovtsev ★★★★★
()

если каждый элемент будет чётным, то на каждой итерации будет сдвигаться N-1 элементов. N*N/2 получается

kaldeon
()

erase() имеет линейную сложность от размера, находится в цикле по всей длине, очевидно, что O(N*N).

unC0Rr ★★★★★
()

Что бы это работало за O(N) нужно на первом проходе отмечать элементы для удаления, на втором дефрагментировать то что осталось.

А так конечно O(N^2)

AntonI ★★★★★
()
Ответ на: комментарий от AntonI

Думается мне что интервьюер хотел услышать об remove_if() и почему не стОит изобретать собственные велосипеды.

bugfixer ★★★★★
()
Ответ на: комментарий от bugfixer

да. и erase_if.

насколько понимаю, это просто обертки над кодом на C++11 выше.

ИИ так пишет:

Временная сложность erase_if для vector составляет O(N + M), где N - количество удаленных элементов, а M - количество перемещенных элементов. Это связано с тем, что erase_if сначала итерируется по контейнеру, проверяя условие для каждого элемента (это часть сложности O(N)), а затем удаляет элементы, что может потребовать перемещения оставшихся элементов (сложность O(M))

т.е. вообще говоря если N=M -> O(N+M) ~ O(N) :D

zudwa
() автор топика
Последнее исправление: zudwa (всего исправлений: 1)

к алгоритмам это отношения не имеет. Иди в веб там они вообще не нужны. При поиске какого-то значения в массиве у тебя сложность будет в худшем случае O(N), где N - длина, когда что-то искомое в конце массива. При удалении каждого 2-го элемента (с индексами 1,3,5,7,… нечетного больше 0) там полное копирование же происходит, те внутри реализации вектора проход по вектору производится… Но рассматривается лишь худший случай. Нужен листик и бумага чтобы посчитать количество итераций, но скорее всего он прав.

rtxtxtrx ★★★
()
Последнее исправление: rtxtxtrx (всего исправлений: 2)

Мой ответ O(N). Ответ интервьюера O(N*N)

А что «думает» nanobench?

#define ANKERL_NANOBENCH_IMPLEMENT

#include <iostream>
#include <vector>
#include "nanobench.h"

int main() {

    ankerl::nanobench::Bench bench;

    std::vector<int> a;

    for (auto setSize : {10U, 20U, 50U, 100U, 200U, 500U, 1000U}) {
	a.resize(setSize);
	std::iota(a.begin(), a.end(), 0);

	bench.complexityN(setSize).minEpochIterations(10000).run("vector erase", [&] {
	    for(auto it = a.begin(); it != a.end();)
	    {
		if (*it % 2)
		{
		    it = a.erase(it);
		}
		else
		{
		    ++it;
		}
	    }
	    ankerl::nanobench::doNotOptimizeAway(a);
        });

    }
    std::cout << bench.complexityBigO() << std::endl;
}
complexityNns/opop/serr%totalbenchmark
10109.499,133,388.192.9%0.01vector erase
20178.885,590,452.071.2%0.02vector erase
50364.272,745,215.413.2%0.04vector erase
100676.741,477,672.731.4%0.08vector erase
2001,300.63768,855.510.2%0.16vector erase
5003,217.13310,835.770.6%0.39vector erase
1,0006,371.71156,943.720.2%0.76vector erase
coefficienterr%complexity
6.3936793e-092.1%O(n)
6.5817043e-1012.0%O(n log n)
6.7992260e-1243.7%O(n^2)
6.6801693e-1561.1%O(n^3)
3.1984146e-0792.1%O(log n)
1.7455504e-06122.4%O(1)

И Оскар отправляется 6.3936793e-09 2.1% O(n).

dataman ★★★★★
()
Последнее исправление: dataman (всего исправлений: 1)
Ответ на: комментарий от dataman

А что «думает» nanobench?

А пофиг, что он там думает. N*N и все тут. Анализ работы кешей, особенностей работы алгоритма, пороков nanobench и проч. билиберды к оценкам O(…) не относится.

alysnix ★★★
()
Ответ на: комментарий от bugfixer

Понапридумывают методов на каждый чих, а программисту их все помни:-)

AntonI ★★★★★
()

Правильный ответ: логарифмическая сложность, те между линейной и квадратичной.

Из-за того что вектор перестраивается с убывающим количеством элементов то получаем сложность меньше чем квадратичная (N*M), где M<N.

Также понятно что сложность больше линейной N. Отсюда выбираем сложность между линейной и квадратичной, а это логарифмическая.

Obezyan
()
Ответ на: комментарий от alysnix

nanobench не мытьмой, я просто разместил объяву.

dataman ★★★★★
()
Ответ на: комментарий от Obezyan

Из-за того что вектор перестраивается с убывающим количеством элементов то получаем сложность меньше чем квадратичная (N*M), где M<N.

нет. а если б начали с конца - и «вектор» возрастал бы?

«убывающий вектор» просто дает некий неубывающий вектор средней длины (порядка N/2). и сложность остается «теоретически квадратичной».

просто пересылка данных пачкой намного быстрей пересылки поэлементно - (которая и дает лишнее N), потому теоретический N*N тут близок к N, в силу высокой скорости пересылки пачкой.

а нанобенч лишь показывает насколько эффективно современный процессор выполняет некоторые алгоритмы с теоретической сложностью N*N.

alysnix ★★★
()
Ответ на: комментарий от alysnix

нет. а если б начали с конца - и «вектор» возрастал бы?

возрастал бы до M<N.

сложность остается «теоретически квадратичной».

теоретически.

Тут все дело в том что и N и N квадрат - чёткие границы до которых не дойдёт сложность. Те в обоих случаях нужно поднатянуть сову на глобус чтобы заявить что это линейная или что это квадратичная сложность, понимаете? Реальная сложность между ними.

теоретический N*N тут близок к N

Вы только что подтвердили своими словами мой ответ. Близок к N, но не N, причём теоретически может быть почти до N*N. Это и есть логарифмическая сложность.

Obezyan
()
Ответ на: комментарий от Obezyan

Из-за того что вектор перестраивается с убывающим количеством элементов

Сложность становится O(N * (N-1)/2), что эквивалентно O(N*N). Нельзя так лихо оценивать больше-меньше.

unC0Rr ★★★★★
()
Последнее исправление: unC0Rr (всего исправлений: 1)
Ответ на: комментарий от Obezyan

на абстрактном теоретическом проце, где нет кешей, и пересылка это просто пословный цикл, и будет сложность уровня N*N.

просто суперскалярные процы с хитровыделанными кешами давно не есть абстрактно-теоретический проц, что и показывают бенчмарки.

И дело тут вовсе не в «уменьшении длины пересылки», что никак не может дать логарифм, а даст N/2 (опять же на абстрактном проце, для которого и строятся такие рассуждения.).

alysnix ★★★
()
Ответ на: комментарий от unC0Rr

Нельзя так лихо оценивать больше-меньше.

Смотрите, если вектор содержит вершины пирамиды (линеаризованный объект такой), то в этом случае, если мы удаляем, например, определённый элемент, то сложность будет равна логарифмической. Ну нет там квадрата.

Obezyan
()
Ответ на: комментарий от alysnix

Почитайте более внимательно когда возникает логарифмическая сложность. Спойлер, не только при бинарном поиске. Но и вполне себе в операциях над деревьями и пирамидами, которые в свою очередь имеют отображение в виде векторов.

Obezyan
()
Ответ на: комментарий от Obezyan

Почитайте более внимательно когда возникает логарифмическая сложность.

вернитесь из фантазий на землю, топикстартер вам код нарисовал, где удаляется каждый второй! элемент. по нему и задан вопрос.

если б удалялось ln N элементов, сложность была бы N*ln N. Но это не наш случай.

Скажем по секрету, что если б не удалялся ни один элемент, сложность была бы N.

alysnix ★★★
()
Ответ на: комментарий от alysnix

топикстартер вам код нарисовал, где удаляется каждый второй! элемент. по нему и задан вопрос.

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

Obezyan
()
Ответ на: комментарий от Obezyan

и при этом вы заявляете что сложность квадратичная.

а какая еще??? N/2 раз(нечетные) надо переписать N/2 элементов(средняя сдвигаемая длина) на один элемент влево.

N/2 * N/2 дает сложность N*N. :))))

alysnix ★★★
()
Последнее исправление: alysnix (всего исправлений: 2)
Ответ на: комментарий от alysnix

а какая еще??? N/2 раз(нечетные) надо переписать N/2 элементов(средняя сдвигаемая длина) на один элемент влево.

последний элемент - нечетный, удаляем нечетные числа, т.е. (N-1)/2.

итоговая сложность N*(N-1)/2 => N^2 - N что явно меньше квадратичной, но больше линейной. Отбрасывать N позволительно мидлам которые про биг О на хабре читали.

тимлид, вы не можете это понять, и занимаетесь балабольством на самом деле

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

Obezyan
()
Ответ на: комментарий от Obezyan

С каких это пор логарифмическая сложность расположилась между линейной и квадратичной?

Вообще-то O(log n) < O(n) < O(n²)

Gordon
()
Ответ на: комментарий от Obezyan

итоговая сложность N*(N-1)/2 => N^2 - N что явно меньше квадратичной, но больше линейной. Отбрасывать N позволительно мидлам которые про биг О на хабре читали.

посмотрите уже как оценивается сложность и не порите чушь. N^2-N…такой просто не бывает :) сложность оценивается асимптотически. и N^2 забивает N.

начните отсюда, сеньор.

https://ru.wikipedia.org/wiki/%D0%92%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0

alysnix ★★★
()
Ответ на: комментарий от Gordon

Ну вот зачем?!! Зачем вы мешаете Обезьяну выводить всех этих знатоков на чистую воду? Никто из них даже не заметил, видите как тужатся доказывая.

Obezyan
()
Ответ на: комментарий от Gordon

у обезяна речь идет о n*ln n. а не чисто логарифме. и то, он ее приплел сюда от непонимания самого термина, и как его оценивают.

alysnix ★★★
()
Ответ на: комментарий от Obezyan

Вы даже не заметили то о чем написал @Gordon, миддл ;)

этот вообще в ваших потемках заблудился. а O(N^2 - N) - это надо отлить в граните, сеньор :)

alysnix ★★★
()
Ответ на: комментарий от Obezyan

При оч малых N можно считать что n*ln N ~ n, это как раз наш случай

никого не интересует сложность при малых. интересуют асимптотические оценки на больших(лучше бесконечных). поскольку это используется для оценки вычислимости и сравнения алгоритмов промеж собой, где сложность - мера эффективности.

alysnix ★★★
()
Ответ на: комментарий от alysnix

сложность оценивается асимптотически. и N^2 забивает N.

на больших N. У нас N какое, большое? Пример же дан чётко с небольшим количеством значений.

Obezyan
()
Ответ на: комментарий от alysnix

никого не интересует сложность при малых.

Дан пример где чётко определено небольшое N. Если бы это было не так написали бы

std::vector<int> a{1,2,3,4,5,6,7,8,9,.., n};

Тогда ваши рассуждения были бы верны.

Вы отбрасываете явное условие в задаче.

Obezyan
()
Ответ на: комментарий от Obezyan

Какая сложность алгоритма?)

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

размер входных данных мал настолько, что про асимптотику и говорить грешно. видимо там еще тот «интервьюер», типа сеньора из вашего «клуба сеньоров». :))

посоветуйте ему там написать хотя бы 10^ элементов, чтобы не позориться.

alysnix ★★★
()
Ответ на: комментарий от alysnix

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

Нет, нельзя, надо задать уточняющий вопрос, но у нас такой возможности нет.

Вы хорошо держитесь, но это вам не поможет ;)

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

Obezyan
()
Ответ на: комментарий от zudwa

насколько понимаю, это просто обертки над кодом на C++11 выше.

Вообще говоря std::remove_if() вполне себе полновесный самостоятельный алгоритм которому «100 лет в обед»: в 98ых плюсах уже был. std::erase_if() - да, относительно молодая (cxx-20) обёртка над ним прибивающая хвост (что раньше приходилось делать «ручками»).

bugfixer ★★★★★
()
Ответ на: комментарий от Obezyan

Вы хорошо держитесь, но это вам не поможет ;)

Мне не надо помогать, я даже не напрягаюсь :) Удивительно детские вопросы приходится обсуждать с сеньорами.

alysnix ★★★
()

выше отметили что для этой задачи есть более лучшие методы в stl

а конкретно по коду(ибо std::vector<int>.erase обычно двигает хвост ) O(n*n) то бишь квадрат  — «чютка» уменьшить «константу» можно если делать обход с конца :)

но на таком (n=10) не важно

любая реализация (нужного фильтра) очевидно не ниже O(n) ибо требуется проход по массиву

qulinxao3 ★☆
()
Последнее исправление: qulinxao3 (всего исправлений: 1)
Ответ на: комментарий от Obezyan

Никакого смысла нет обсуждать сложность на фиксированном наборе данных, для такого случая сложность всегда O(1). Это вы тут демагогией занимаетесь.

unC0Rr ★★★★★
()
Ответ на: комментарий от dataman

А что «думает» nanobench?

Поправь меня, если я где-то ошибся (не пишу на C++):

  1. Ты выполняешь бенчмарк для разных размеров вектора в цикле.
  2. В каждой итерации цикла ты ресайзишь и заполняешь вектор с нуля.
  3. Далее ты запускаешь бенчмарк, который замеряет скорость выполнения замыкания; вектор при этом в замыкание передаётся по ссылке. Замеры выполняются дохрениллиард раз (нам не особо важно, сколько именно, главное, что больше 1).
  4. В каждой итерации бенчмарка ты удаляешь из вектора чётные элементы.

Если я всё правильно понял, у тебя в первой итерации бенчмарка (не путать с итерацией цикла!) удаляются все чётные элементы вектора, при этом все последующие итерации бенчмарка будут выполняться уже на изменённом векторе, в котором чётных элементов не осталось (т.е. в последующих итерациях бенчмарка будет просто линейный проход по вектору без вызовов erase).

Что тогда ты хотел этим бенчмарком показать-то?

theNamelessOne ★★★★★
()
Последнее исправление: theNamelessOne (всего исправлений: 1)
Ответ на: комментарий от Obezyan

Правильный ответ: логарифмическая сложность

Мдя… впрочем чего ещё можно ожидать от ковидиссидента и сторонника теории заговора большой фармы, не асилившего понятие размерности?

AntonI ★★★★★
()
Ответ на: комментарий от dataman

В бенче критическая ошибка.

9999 итераций бенча, кроме первой исполняются на уже отфильтрованной коллекции с нечётными числами, поскольку vector не восстанаваливается между итерациями.

Ошибка прикольная, без отладочной печати не нашёл, вам светят большие перспективы на ниве внедрения незаметных бэкдоров))

Вот такое даёт n^2

#define ANKERL_NANOBENCH_IMPLEMENT

#include <iostream>
#include <vector>
#include "nanobench.h"

int main() {

    ankerl::nanobench::Bench bench;

    std::vector<int> a;

    for (auto setSize : {10U, 20U, 50U, 100U, 200U, 500U, 1000U}) {

        bench.complexityN(setSize).minEpochIterations(10000).run("vector erase", [&] {
            a.resize(setSize);
            std::iota(a.begin(), a.end(), 0);
            for(auto it = a.begin(); it != a.end();)
            {
                if (*it % 2)
                {
                    it = a.erase(it);
                }
                else
                {
                    ++it;
                }
            }
            ankerl::nanobench::doNotOptimizeAway(a);
        });

    }
    std::cout << bench.complexityBigO() << std::endl;
}

Собрано c -O3

| complexityN |               ns/op |                op/s |    err% |          ins/op |          cyc/op |    IPC |         bra/op |   miss% |     total | benchmark
|------------:|--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:----------
|          10 |               30.91 |       32,347,322.02 |    1.2% |          272.00 |           87.54 |  3.107 |          69.00 |    0.0% |      0.01 | `vector erase`
|          20 |               63.68 |       15,702,760.61 |    1.4% |          516.00 |          178.88 |  2.885 |         137.00 |    0.0% |      0.01 | `vector erase`
|          50 |              217.43 |        4,599,177.12 |    2.0% |        1,632.00 |          607.51 |  2.686 |         373.00 |    0.0% |      0.03 | `vector erase`
|         100 |              560.53 |        1,784,031.31 |    2.0% |        4,431.00 |        1,568.49 |  2.825 |         855.00 |    0.0% |      0.07 | `vector erase`
|         200 |            1,656.03 |          603,854.27 |    0.9% |       13,141.00 |        4,675.86 |  2.810 |       2,080.00 |    0.4% |      0.20 | `vector erase`
|         500 |            8,085.70 |          123,675.13 |    0.8% |       60,715.01 |       23,157.82 |  2.622 |       7,542.01 |    0.7% |      0.97 | `vector erase`
|       1,000 |           31,408.96 |           31,838.05 |    0.5% |      216,916.03 |       89,517.07 |  2.423 |      23,055.03 |    1.3% |      3.77 | `vector erase`

|   coefficient |   err% | complexity
|--------------:|-------:|------------
| 3.1481492e-11 |   3.4% | O(n^2)
| 3.1932491e-14 |  27.7% | O(n^3)
| 2.8805564e-09 |  40.0% | O(n log n)
| 2.7514601e-08 |  52.1% | O(n)
| 1.1735065e-06 | 151.8% | O(log n)
| 6.0033211e-06 | 178.4% | O(1)

По-хорошему чуть тяжёлую подготовку в виде вызова iota надо вынести в функцию setup, вызываемую на каждом цикле, но nanobench пока не придумал подход к этому и она является линейной, не создавая квадратичную сложность.

GPFault ★★★
()
Ответ на: комментарий от Obezyan

К алгоритму ТС это вообще никак не относится. Заканчивайте уже позориться, прям стыдно за Вас…:-(

AntonI ★★★★★
()
Ответ на: комментарий от theNamelessOne

Да всё так, критическая ошибка в бенче. Тоже увидел, но пока разбирался как же грамотно сделать инциализацию в nanobench - опоздал )

GPFault ★★★
()
Ответ на: комментарий от AntonI

сорян ща историю переписывают именно как заг овор

зы. вера не коррелирует с разумом

все «4» комбинации возможны

qulinxao3 ★☆
()
Ответ на: комментарий от GPFault

По-хорошему чуть тяжёлую подготовку в виде вызова iota надо вынести в функцию setup, вызываемую на каждом цикле, но nanobench пока не придумал подход к этому и она является линейной, не создавая квадратичную сложность.

Автор пока предлагает запускать два бенча: один с сетапом и собсно замеряемым кодом, второй — только с сетапом, и потом отнимать от первого результат второго xD

theNamelessOne ★★★★★
()
Последнее исправление: theNamelessOne (всего исправлений: 1)
Ответ на: комментарий от bugfixer

Думается мне что интервьюер хотел услышать об remove_if() и почему не стОит изобретать собственные велосипеды

О remove, если уж по значению

annulen ★★★★★
()
Для того чтобы оставить комментарий войдите или зарегистрируйтесь.