C ++ checks if any of the previous 5 or next 5 elements is equal to

Question

Is there an easy way to do this without a for loop or a lot of ifs and elses.

For example..

for (i=0;i<arr.size;i++) if (any of the values from i-5 to i+5, ignoring i = value) { // Do stuff ... } 

Do I need to set a nested loop from -5 to +5. Or I could use std::any_of maybe

Answer 1

Despite what the description looks like, the complexity is linear , because the inner loop (if any) is repeated with a constant number of times (and does not depend on the amount of data).

Since you suggest that your data be in the form of an array (continuous and random indexing) and the use of nested loops, in fact, this is the easiest and easiest way to use all the optimization options and caching of the processor. No matter which “dynamically sorted” container threshold works poorly, due to the distributed nature of the data.

I will most likely do

 for(size_t i=5; i<N-5-1; ++i) { int good=0; //will count the successful comparisons for(size_t j=i-5; j<=i+5; ++j) { if(i==j) continue; //skip the i on i case if(array[j]==value) ++good; } if(good==10) do_stuff(i); } 

The inner loop runs completely on cached data (and does not depend on N, so it does not contribute to complexity). Currently, the processor is probably faster than trying to somehow sort the data in a container with many (with non-contiguous storage).

Despite the elegance of many beginner / end approaches, the old KISS indexing wins.

You can parameterize the predicate array[j]==value , as well as 5 (and 10 == 2 * 5) at no cost (the template function will be built-in), which makes this even more general.

if you don't want to insert an inner loop, you can even do it faster with

 for(size_t i=5; i<N-5-1; ++i) { int good=0; //will count the successful comparisons for(size_t j=i-5; j<i; ++j) good+=(array[j]==value); for(size_t j=i+1; j<=i+5; ++j) good+=(array[j]==value); if(good==10) do_stuff(i); } 

If a loop of 11 elements is divided into two halves (avoiding the check j == i), and the increment on good "calculated" functionally, without branches. This will also lead to faster execution of predictive pipeline processors.

---

EDIT

It seems that I did not understand that one equal value (not all) is enough.

If this is the case, you can check good!=0 , but you can even shorten:

 for(size_t i=5; i<N-5-1; ++i) { bool good=false; //will count the successful comparisons for(size_t j=i-5; j<i && !good; ++j) good|=(array[j]==value); for(size_t j=i+1; j<=i+5 && !good; ++j) good|=(array[j]==value); if(good) do_stuff(i); } 

This will break the cycles as soon as a match is found, but makes the cycle more inconspicuous. Removing && !good will not trim the loops, but it can work to the end faster than checking for cropping or not.

If you shorten the loops, you can use = instead of |= , if you don't use the shortcut, using bool has no advantages: |= the compiler point is more complicated than +=

Answer 2

In terms of readability, I prefer double for loops.

In terms of performance, I would use the following, which runs iterations of the minimum n+5 (for scope = 5) without additional data structures .
In general, O(n) complexity and O(1) memory.

 void checkArray(int arr[], int n, int value) { const int scope = 5; int closestBeforeI = -1; int closestAfterI = -1; for (int i = 0; i < scope && i < n; ++i) { if (arr[i] == value) { closestAfterI = i; } } for (int i = 0; i < n; ++i) { if (closestAfterI == i) { // exclude self index closestAfterI = -1; } if (closestAfterI == -1 && i + scope < n // closest after not set & i + scope is within range && arr[i + scope] == value) { closestAfterI = i + scope; } if (closestBeforeI != -1 && closestBeforeI + scope >= i || closestAfterI != -1) { do_stuff(i); } if (arr[i] == value) { closestBeforeI = i; } } } 

perfectly coped with this task:

 int main() { const int n = 14; int arr[] = {1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2}; int value = 2; // should be true for indices: 0, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12 checkArray(arr, n, value); return 0; } 

Answer 3

Here is an efficient approach that uses the previous results to execute in O (n) time. It works with both stl containers and embedded arrays and is circular.

 #include <vector> #include <functional> #include <iterator> #include <iostream> #include <algorithm> template <class Indexable, class EQComparable> void for_each_if_value_in_neighbors(Indexable& container, const EQComparable& value, size_t offset, std::function<void(size_t)> callable) { size_t size = std::distance(std::begin(container), std::end(container)); size_t next_index = offset % size; size_t prev_index = size - (offset % size); size_t range_count = std::count(std::begin(container) + prev_index, std::end(container), value) + std::count(std::begin(container), std::begin(container) + next_index, value); for (size_t i = 0; i < size; ++i) { bool found_cur = (container[i] == value); bool found_next = (container[next_index] == value); range_count += found_next - found_cur; if (range_count) { callable(i); } bool found_prev = (container[prev_index] == value); range_count += found_cur - found_prev; next_index = (next_index + 1) % size; prev_index = (prev_index + 1) % size; } } int main() { std::vector<int> vec = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0}; for_each_if_value_in_neighbors(vec, 2, 5, [&](size_t i){ std::cout << i << " vector check\n"; }); // prints: 0 vector check // 1 vector check // 2 vector check // 8 vector check // 9 vector check // 10 vector check // 11 vector check // 12 vector check // 14 vector check // 15 vector check int arr[] = {2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2}; for_each_if_value_in_range(arr, 2, 5, [&](size_t i){ std::cout << i << " array check\n"; }); // prints: 0 array check // 1 array check // 2 array check // 3 array check // 4 array check // 5 array check // 10 array check // 11 array check // 12 array check // 13 array check // 14 array check // 15 array check return 0; } 

Answer 4

 template<class C, class V, class F> void customrunner(C&& c, V&& v, F&& f) { auto it = begin(c); unsigned viable = 0; for(int i = 0; i < 6; i++) { viable <<= 1; if(it != end(c)) { viable |= *it == v; ++it; } } for(auto i2 = begin(c); i2 != end(c); ++i2) { if(viable & 0x3bf) f(c, i2); viable = (viable<<1) & 0x7ff; if(it != end(c)) { viable |= *it == v; ++it; } } } 

Above would be, as you said, want to iterate the sequence exactly twice (once for testing, twice for providing an iterator for transmission).

If you really need an index instead of an iterator, this is left as an exercise for the reader.

Answer 5

You may be able to use std::any_of , but then you have to exclude the value you are in (or it will match), which probably requires two calls to std::any_of . I would probably just use std::count_if :

 if ( std::count_if( arr.cbegin() + std::max( 0, i - 5 ), arr.cbegin() + std::min( arr.size(), i + 5 ), [&]( int x ) { return x == arr[i] } ) > 1 ) { // ... } 

Using std::max and std::min is to ensure that you don't go beyond. Alternatively, you can start with begin() + 5 and end with end() - 5 (after at least 10 elements), and don't worry about that. In fact, if you do this:

 for ( auto it = arr.cbegin() + 5, end = arr.cend() - 5; it != end; ++ it ) { if ( std::count_if( it - 5, it + 5, []( int x ) { return x == *it; } ) > 1 ) { // ... } } 

Just make sure the array is big enough first.

Answer 6

This is more effective if the window size can change (and not just a fixed offset +/- 5).

For a fixed small window size in this question, it is probably much less efficient than a simple sequential scan, for example, using count_if , as in James & rsquo; Answer.

 int const array[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4}; multiset<int> numbers; for( int i = -5; i < count_of( array ); ++i ) { if( i > 5 ) { remove_one( array[i - 6], numbers ); } if( i + 5 < count_of( array ) ) { numbers.insert( array[i + 5] ); } if( i >= 0 ) { int const value = array[i]; if( numbers.count( value ) > 1 ) { cout << "a[" << i << "] = " << value << endl; } } } 

Secondary functions:

 template< class Item, Size n > auto count_of( Item (&)[n] ) -> Size { return n; } void remove_one( int const v, multiset<int>& s ) { auto const it = s.find( v ); if( it != s.end() ) { s.erase( it ); } } 

Answer 7

You can use the segment tree for this type of problem, and the complexity will be much less.