Мегабайты в квадрате это вам не биты. Удаление многих элементов из массива.

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

Имеется массив чисел. Надо удалить все отрицательные:

float *array; 
int size;


Часто люди её разбивают на два этапа:
1) пишут кусочек кода который удаляет один элемент из массива (или используют готовый метод динамического массива)
2) пишут цикл по массиву, который применяет первый кусочек если условие не выполнено.
3) исправляют баги с итераторами/индексами в связи с тем, что итерируемся по массиву меняющему свою длину.

i = 0 
пока (не дойдём до конца) 
  если условие: 
    удалить элемент i 
  иначе 
    ++i

Часто при развитии программы условие растягивается на много строчек, появляются вложенные if, ++i и удаление в нескольких местах. Где-то забытое, где-то по два раза.

1 – это что-то вроде

for (от места удаления до конца) 
  array[i] = array[i+1]; 
size -= 1;

Это ведёт к медленному исполнению алгоритма, он становится не O(N), а O(N2) (представьте, что все числа отрицательные, или половина из них, или только три из них).

Есть ещё вариант с удалением как

size -= 1; 
array[i] = array[size];

Но он порождает тот же ошибкоопасный код в пункте 2-3, и не сохраняет порядок элементов, что часто не то что нужно.

Теперь, о том как надо.

int j = 0; 
for (int i = 0; i < size; ++i) 
  if (не удалять) 
    array[j++] = array[i]; 
size = j;

Тут одна ветка if, а не две, поэтому при развитии этого кода будет меньше багов. Сложность – так же очевидно что не квадратичная.

Для std::vector (или вашего корпоративного динамического массива) код будет почти таким же (эффективный код – без operator[] и size() в теле цикла, чисто на указателях, это отдельная тема).
“size = j” пишется как resize(j) или erase(begin() + j, end()).

Замечу, что есть std::remove_if, который делает тоже самое. +оптимизация – отсутствие копирования пока i == j при помощи разбития на два цикла. Первый цикл ищет первый элемент который надо удалить, второй цикл уже делает перетаскивание элементов.

int j = 0; 
for (; j < size; ++j) 
  if (удалить) 
    break; 
if (j != size)  //проверка нужна, если заменяем индексы из этого псевдокода на итераторы. 
  for (int i = j + 1; i < size; ++i) 
    if (не удалять) 
      array[j++] = array[i]; 
size = j;

Поэтому если доступен STL и std::remove_if удобно применить – лучше применить std::remove_if (к сожалению, часто проще написать 5 строчек цикла чем перекинуть локальные переменные в предикат и дополнительные действия в ответ на (не)удаление).
Это был рассказ про индексируемые массивы, про списки рассказ был бы другим. Подробно про удаление из разных STL контейнеров рассказывает Меерс в Effective STL.

Если ещё не читали, то прочитайте сказку о маляре Шлемиэле: http://russian.joelonsoftware.com/Articles/BacktoBasics.html
Семён, вы уже исправили тормозящую “корзину”? ;)

  • murkt

    А что скажете насчёт того, чтоб создать новый массив, а в него записать всё, что не нужно удалять? Память жрёт побольше чем любой другой алгоритм, но простора для багов почти нет. А как со скоростью? O(N), если не ошибаюсь.

  • http://-winnie.livejournal.com _winnie

    Вполне решение, если не жалко память. Вот “создать” – точно не стоит, тратиться на malloc прямо перед циклом даже жальче чем на память (если её много). Если делается серия push_back без предварительного reserve – вообще зашибись.
    Можно создать где-то вне, что бы была заранее выделенная память, но это замусоривает код, когда у нас вдруг дополнительные члены в классе на такую не пойми то ли пессимизацию, то ли оптимизацию, причем в километре от точки использования (вообще в другом файле)
    У меня есть похожий remove_if в питоне, кстати. Не по соображениям оптимизации, а потому что иногда надо удалить inplace (os.walk).

  • VoidEx

    murkt, так проще не создавать, а ссылку на начало текущего массива. Будет как будто два, все равно читаются последовательно и мы не перезапишем то, что еще не прочлось. Код, собственно, будет отличаться лишь “синтаксически”, вместо array[j++] = array[i] будет что-то типа *new_array++ = *old_array;
    Если создавать новый, код не изменится, просто new_array будет не в тот же массив писать, а в новый.

  • Sergei_am

    Хорошая задачка для раннего теста Напида-Раса.

  • http://blog.murkt.org.ua/ Муркт

    to _winnie, VoidEx

    Да, это действительно просто – писать в тот же массив. Просто я не сишник, для меня создать список – очень простое действие: var = [] :)