Осторожно удалять N элементов из «кругового» вектора (или, возможно, только NSMutableArray)

Question

Представьте себе вектор std: скажем, со 100 вещами на нем (от 0 до 99). Вы рассматриваете его как петлю. Итак, 105-й пункт - это индекс 4; вперед 7 из индекса 98 5.

Вы хотите удалить N элементов после позиции индекса P.

Таким образом, удаление 5 пунктов после индекса 50; легко.

Или 5 предметов после индекса 99: когда вы удаляете 0 пять раз или от 4 до 0, отмечая, что позиция на 99 будет стерта от существования.

Худший, 5 предметов после индекса 97 - вам нужно иметь дело с обоими способами удаления.

Какой элегантный и прочный подход?

Вот скучный рутинный я написал

-(void)knotRemovalHelper:(NSMutableArray*)original 
     after:(NSInteger)nn howManyToDelete:(NSInteger)desired 
    { 

#define ORCO ((NSInteger)[original count]) 

    static NSInteger kount, howManyUntilLoop, howManyExtraAferLoop; 

    if (... our array is NOT a loop ...) 
      // trivial, if messy... 
     { 
     for (kount = 1; kount<=desired; ++kount ) 
      { 
      if ((nn+1) >= ORCO) 
       return; 
      [original removeObjectAtIndex:(nn+1)]; 
      } 

     return; 
     } 
    else // our array is a loop 
      // messy, confusing and inelegant. how to improve? 
      // here we go... 
     { 
     howManyUntilLoop = (ORCO-1) - nn; 

     if (howManyUntilLoop > desired) 
      { 
      for (kount = 1; kount<=desired; ++kount ) 
       [original removeObjectAtIndex:(nn+1)]; 
      return; 
      } 

     howManyExtraAferLoop = desired - howManyUntilLoop; 

     for (kount = 1; kount<=howManyUntilLoop; ++kount ) 
      [original removeObjectAtIndex:(nn+1)]; 

     for (kount = 1; kount<=howManyExtraAferLoop; ++kount) 
      [original removeObjectAtIndex:0]; 

     return; 
     } 

#undef ORCO 
    } 

Update!

Второй ответ InVariant приводит к следующему превосходному решению. «Начиная с» намного лучше, чем «начиная с». Поэтому в рутине теперь используется «начать с». второй ответ Инвариантный приводит к этому очень простому решению ...

N раз делать, если P < currentsize удалить P еще удалить 0

-(void)removeLoopilyFrom:(NSMutableArray*)ra 
    startingWithThisOne:(NSInteger)removeThisOneFirst 
    howManyToDelete:(NSInteger)countToDelete 
{ 
// exception if removeThisOneFirst > ra highestIndex 
// exception if countToDelete is > ra size 

// so easy thanks to Invariant: 

for (do this countToDelete times) 
    { 
    if (removeThisOneFirst < [ra count]) 
      [ra removeObjectAtIndex:removeThisOneFirst]; 
    else 
      [ra removeObjectAtIndex:0]; 
    } 
} 

обновления!

Toolbox указал отличную идею работы с новым массивом - супер KISS.

Answer 1

Другой метод:

N times do {remove entry at index P mod max(ArraySize, P)}

Пример:

N=5, P=97, ArraySize=100 

1: max(100, 97)=100 so remove at 97%100 = 97 
2: max(99, 97)=99 so remove at 97%99 = 97 // array size is now 99 
3: max(98, 97)=98 so remove at 97%98 = 97 
4: max(97, 97)=97 so remove at 97%97 = 0 
5: max(96, 97)=97 so remove at 97%97 = 0 

Answer 2

Вот идея с головы.

Сначала сгенерируйте массив целых чисел, представляющих индексы для удаления. Таким образом, «удалить 5 из индекса 97» будет генерировать [97,98,99,0,1]. Это можно сделать с помощью простого модуля модуля.

Затем отсортируйте этот массив по убыванию, предоставив [99,98,97,1,0], а затем удалите записи в этом порядке.

Должен работать во всех случаях.

Answer 3

Я не программа iphone для знают, поэтому я станд изображение :: вектор, это довольно легко, просто и достаточно элегантный :

#include <iostream> 
using std::cout; 
#include <vector> 
using std::vector; 
#include <cassert> //no need for using, assert is macro 

template<typename T> 
void eraseCircularVector(vector<T> & vec, size_t position, size_t count) 
{ 
    assert(count <= vec.size()); 
    if (count > 0) 
    { 
     position %= vec.size(); //normalize position 
     size_t positionEnd = (position + count) % vec.size(); 
     if (positionEnd < position) 
     { 
      vec.erase(vec.begin() + position, vec.end()); 
      vec.erase(vec.begin(), vec.begin() + positionEnd); 
     } 
     else 
      vec.erase(vec.begin() + position, vec.begin() + positionEnd); 
    } 
} 

int main() 
{ 
    vector<int> values; 
    for (int i = 0; i < 10; ++i) 
     values.push_back(i); 

    cout << "Values: "; 
    for (vector<int>::const_iterator cit = values.begin(); cit != values.end(); cit++) 
     cout << *cit << ' '; 
    cout << '\n'; 

    eraseCircularVector(values, 5, 1); //remains 9: 0,1,2,3,4,6,7,8,9 
    eraseCircularVector(values, 16, 5); //remains 4: 3,4,6,7 

    cout << "Values: "; 
    for (vector<int>::const_iterator cit = values.begin(); cit != values.end(); cit++) 
     cout << *cit << ' '; 
    cout << '\n'; 

    return 0; 
} 

Однако, вы можете подумать:

• создания нового класса loop_vector, если вы используете этот вид функциональности достаточно
• , используя список, если вы выполняете много удалений (или несколько удалений (не с конца, это просто pop_back), но большой массив)

Если ваш контейнер (NSMutableArray или что-то еще) не является списком, а вектор (т.е. изменяемый массив), вы определенно не хотите, чтобы удалить пункты один за другим, но весь диапазон (например, станд :: Стирание вектора (начало, конец)

Редактировать: реагировать на комментарии, чтобы в полной мере реализовать то, что должен быть выполнен с помощью вектора, если вы удалите элемент, отличный от последнего: он должен скопировать все значения после этого элемента (например, 1000 элементов в массиве, вы сначала удаляете, 999x копирование (перемещение) элемента, что очень дорого). Пример:

#include <iostream> 
#include <vector> 
#include <ctime> 
using namespace std; 

int main() 
{ 
    clock_t start, end; 

    vector<int> vec; 
    const int items = 64 * 1024; 
    cout << "using " << items << " items in vector\n"; 

    for (size_t i = 0; i < items; ++i) vec.push_back(i);  

    start = clock(); 
    while (!vec.empty()) vec.erase(vec.begin()); 
    end = clock(); 

    cout << "Inefficient method took: " 
     << (end - start) * 1.0/CLOCKS_PER_SEC << " ms\n"; 

    for (size_t i = 0; i < items; ++i) vec.push_back(i);  

    start = clock(); 
    vec.erase(vec.begin(), vec.end()); 
    end = clock(); 

    cout << "Efficient method took: " 
     << (end - start) * 1.0/CLOCKS_PER_SEC << " ms\n"; 

    return 0; 
} 

Производит вывод:

using 65536 items in vector 
Inefficient method took: 1.705 ms 
Efficient method took: 0 ms

Обратите внимание, что очень легко получить неэффективность, например, например. имеют на http://www.cplusplus.com/reference/stl/vector/erase/

Answer 4

Это решение работает, и оно копирует все оставшиеся элементы в векторе только один раз (до конечного пункта назначения).

Предполагается, что kNumElements, kStartIndex и kNumToRemove определены как значения const size_t.

vector<int> my_vec(kNumElements); 
for (size_t i = 0; i < my_vec.size(); ++i) { 
    my_vec[i] = i; 
} 

for (size_t i = 0, cur = 0; i < my_vec.size(); ++i) { 
    // What is the "distance" from the current index to the start, taking 
    // into account the wrapping behavior? 
    size_t distance = (i + kNumElements - kStartIndex) % kNumElements; 

    // If it's not one of the ones to remove, then we keep it by copying it 
    // into its proper place. 
    if (distance >= kNumToRemove) { 
     my_vec[cur++] = my_vec[i]; 
    } 
} 

my_vec.resize(kNumElements - kNumToRemove); 

Answer 5

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

endIdx = after + howManyToDelete 
if (Len <= after + howManyToDelete) //will have a second loop 
    firstloop = Len - after; //handle end in the first loop, beginning in second 
else 
    firstpass = howManyToDelete; //the first loop will get them all 

for (kount = 0; kount < firstpass; kount++) 
    remove after+1 
for (; kount < howManyToDelete; kount++) //if firstpass < howManyToDelete, clean up leftovers 
    remove 0 

Это решение не использует mod, делает вычисление предела вне цикла, и затрагивает соответствующие образцы один раз , Второй цикл for не будет выполняться, если все образцы были обработаны в первом цикле.

Обычный способ сделать это в DSP с круговым буфером. Это просто фиксированная длина буфера с двумя соответствующими счетчиками:

//make sure BUFSIZE is a power of 2 for quick mod trick 
#define BUFSIZE 1024 
int CircBuf[BUFSIZE]; 
int InCtr, OutCtr; 

void PutData(int *Buf, int count) { 
    int srcCtr; 
    int destCtr = InCtr & (BUFSIZE - 1); // if BUFSIZE is a power of 2, equivalent to and faster than destCtr = InCtr % BUFSIZE 

    for (srcCtr = 0; (srcCtr < count) && (destCtr < BUFSIZE); srcCtr++, destCtr++) 
     CircBuf[destCtr] = Buf[srcCtr]; 
    for (destCtr = 0; srcCtr < count; srcCtr++, destCtr++) 
     CircBuf[destCtr] = Buf[srcCtr]; 
    InCtr += count; 
} 

void GetData(int *Buf, int count) { 
    int srcCtr = OutCtr & (BUFSIZE - 1); 
    int destCtr = 0; 

    for (destCtr = 0; (srcCtr < BUFSIZE) && (destCtr < count); srcCtr++, destCtr++) 
     Buf[destCtr] = CircBuf[srcCtr]; 
    for (srcCtr = 0; srcCtr < count; srcCtr++, destCtr++) 
     Buf[destCtr] = CircBuf[srcCtr]; 
    OutCtr += count; 
} 

int BufferOverflow() { 
    return ((InCtr - OutCtr) > BUFSIZE); 
} 

Это очень легкий, но эффективный. И помимо материала ctr = BigCtr & (SIZE-1), я бы сказал, что он очень читабельен.Единственная причина для трюка & в старых DSP-средах, mod была дорогостоящей операцией, поэтому для чего-то, что часто выполнялось, как и каждый раз, когда буфер готов к обработке, вы найдете способы удалить такие вещи. И если вы делали FFT, ваши буферы, вероятно, были бы в 2 раза в любом случае.

В эти дни, конечно, у вас есть 1 ГГц процессоры и магически изменяющиеся размеры массивов. Вы, дети, сошли с газона.