All geek questions in one place

Gently removing N elements from a "circular" vector (or, possibly, only NSMutableArray)

Imagine a std vector: say, with 100 things on it (from 0 to 99). You see it as a loop. So, the 105th point is index 4; forward 7 of index 98 is 5.

You want to remove N elements after the position of index P.

So, remove 5 elements after index 50; easy.

Or 5 points after index 99: if you delete 0 five times or from 4 to 0, noting that a position at 99 will be erased from existence.

Worst of all, 5 points after index 97 - you need to deal with both removal methods.

What is an elegant and durable approach?

Here is the boring routine I wrote

-(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 else 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.

+3
5

:

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
+1

.

, . , " 5 97" [97,98,99,0,1]. .

, [99,98,97,1,0], .

.

+5

, ( ).

, 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 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);
+2

, . 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 . , , .

+2

iphone , , std::vector, , :

#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 - ) , vector (.. ), , (, std::vector erase (begin, end )

: , , , , : (, 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

Note that it is very easy to get inefficiency, see for example. at http://www.cplusplus.com/reference/stl/vector/erase/

+1
source

Source: https://habr.com/ru/post/1785148/

More articles:


All Articles