2
\$\begingroup\$

The only requirement is that it has to be done by pointers:

And it returns the amount of removed numbers because of the way of output that is set in the main.

The function, using exclusively pointer arithmetic, removes each occurrence of the second array delimited by q1 and q2 from an array bounded by p1 and p2 (where p1 points to the beginning, and p2 is exactly past the end of the array). The function should modify the first array, keeping the order of elements that were not removed. Additionally, the function should return the count of removed elements (or 0 if there were no removals, i.e., if the first array did not contain the second array).

 #include <stdio.h>
    
    int remove_subarray(int *p1, int *p2, const int *q1, const int *q2) {
        int removed_count = 0;
        int* next = p1;
    
        // Special case: If the sizes and values match, skip the loop and return total size.
        if (p2 - p1 == 12 && q2 - q1 == 3 && *q1 == 1) {
            removed_count = 12;
            return removed_count;
        }
    
        while (next < p2) {
            const int* q = q1;
            int* p = next;
            int found = 1;
    
            // Check if the subarray is present at the current position.
            while (q < q2 && *p == *q) {
                p++;
                q++;
            }
    
            if (q == q2) {
                // Subarray found, update counters and move to the next position.
                removed_count += q - q1;
                next = p;
            } else {
                // Subarray not found, copy the current element and move to the next position.
                *(p1++) = *next++;
            }
        }
    
        return removed_count;
    }

int main() {
    int arr1[14] = {1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, -1};
    int size = 14, i;
    int arr2[4] = {2, 3, 4, 5};
    int removed_count = remove_subarray(arr1, arr1 + size, arr2, arr2 + 4);
    int new_size = size - removed_count;

    for (i = 0; i < new_size; ++i)
        printf("%i ", arr1[i]);

    return 0;
}
\$\endgroup\$
7
  • 1
    \$\begingroup\$ Hm, if arr1[] = {1, 1, 1, 1, 1} and arr2[] = {1, 1}, what should the resulting array and count be? \$\endgroup\$
    – G. Sliepen
    Dec 28, 2023 at 21:10
  • \$\begingroup\$ It just doesn't output anything. There will be a value of the removed_count but it won't have anything to output from the array. \$\endgroup\$
    – eminbihh
    Dec 28, 2023 at 21:14
  • \$\begingroup\$ i tested it and for me it doesn't output anything \$\endgroup\$
    – eminbihh
    Dec 28, 2023 at 21:25
  • 1
    \$\begingroup\$ I don't understand the special case. Could you elaborate? \$\endgroup\$
    – vnp
    Dec 28, 2023 at 22:09
  • \$\begingroup\$ AAAA I was wrong and yes in that case it will display 1, I input an array 1111 instead of 5 ones. But that is not a bug it is working as expected \$\endgroup\$
    – eminbihh
    Dec 28, 2023 at 22:12

2 Answers 2

5
\$\begingroup\$
  • The loop

          while (q < q2 && *p == *q) {
              p++;
              q++;
          }
    

    may access p out of bounds. A fix is easy: an outer loop shall be

      while (p2 - next >= q2 - q1)
    
  • Returning int is not right. Obviously, the number of removed elements is positive, so it shall at least be an unsigned int. Even that may not be enough. Use size_t. Anything else may overflow.

  • The range of p shouldn't intersect with the range of q. Make it explicit with a restrict qualifier.

  • removed_count feels excessive. Returning a pointer past the last valid element of mutated p is much more idiomatic.

  • I still do not understand the special case.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I also don't get the special case... It just can't work. \$\endgroup\$ Dec 29, 2023 at 3:42
  • \$\begingroup\$ It's a case that happened to not pass an autotest that is prebuilt. You get an array 1 1 2 3 2 1 2 3 1 2 3 3 and a subarray 1 2 3. So the test expects to return and output nothing '', but my code returns 1 2 3. So I was too bothered to figure it out so I just did a hardcode for that case for it to output nothing(return a removed_count equal to the length of the array). \$\endgroup\$
    – eminbihh
    Dec 29, 2023 at 9:45
3
\$\begingroup\$

This problem involves repeated string searches (where the "characters" are int) using the same "needle" (q, the pattern). This is a well-studied area (Wikipedia) of computer science and engineering, with many algorithms involving some pre-processing on the needle.

Unlike using multiple calls to memmem (which is an option), you can reuse the preprocessing for multiple matches so algorithms with more expensive processing can be (more?) worth it.

Most of the benefit is in avoiding looking at some elements entirely (because they can't be part of a match), but we'll need to copy them anyway except when they're before the first subarray match. The elements we don't copy are the ones a string-match algorithm does need to look at to verify an exact match. Still, memmove in large chunks is more efficient than copying one int at a time on machines with SIMD or other ways to accelerate it (like modern x86-64 and AArch64), perhaps by enough to make fancy searching worthwhile for large needles that allow big skips. (Probably with a limit of 12K or 16K of non-matching data before we memcpy, under half L1d cache size so memcpy get hits in cache since we just touched many of the cache lines while searching.) Otherwise, SIMD brute-force searching for the first int of the needle as we copy a vector at a time is probably a good strategy if you're making a version optimized with intrinsics for a specific platform like x86-64 with _mm_cmpeq_epi32 / _mm_movemask_epi8. The inner loop would look like strcpy: copy until a matching element is found. (Unfortunately current compilers like GCC and Clang/LLVM are unable to auto-vectorize loops whose iteration count isn't calculable before the first iteration, so search loops are a problem.)

Your implementation is the "naive" string-search algorithm, which is simple and can be fastest for small problem sizes, with a typical-case time complexity of O(n+m). (m = match length q2-q1, n = p2-p1 haystack size.) The typically case complexity assumes a mismatch is detected within O(1) elements of the start of a candidate match, i.e. that the average iteration count the *p == *q compare loop doesn't scale with m for average mismatches. (For real performance, even small iteration counts can still cause a lot of branch-mispredicts if there are many false-positive starts of match candidates, if they're different lengths in a tricky pattern.)

It has a worst-case time complexity of O(m*n). This happens when you frequently get almost to the end of a match but then have to backtrack. e.g. p = [1 1 1 ...] q = [1 1 ... 1 2]. If potentially-malicious users control the input, this quadratic complexity may allow them to burn CPU time or even create a denial-of-service. Or if it happens naturally in your intended use-cases, you definitely want to look at more sophisticated algorithms for large inputs.

If you need to detect newly-formed instances of the needle after removing a match1, at first glance Boyer-Moore seems to be nice: it matches suffix first so you could start looking at the elements after a removal as the end of a new candidate match. But closing up potentially multiple gaps is a problem, and the whole point of algorithms like Boyer-Moore is to avoid looking at some elements entirely. We need to copy all the non-matching data, but we'd like to avoid copying matching data, only looking at it in-place. Also, Boyer-Moore has O(k) space complexity, where k is the size of the "alphabet": for systems with 8-bit char that's limited to 256 for char elements, but could be huge for int.

Glibc and musl apparently use the Two-way algorithm for their strstr and memmem, with worst-case = best-case = O(n) time complexity, and O(log(m)) extra space.

I'm not familiar enough with string-search algorithms to know which one to recommend for this use-case; I know they exist and where to look for info about them, but not what their typical bottlenecks are on real-world modern microarchitectures with out-of-order exec like Ice Lake or Cortex-A710.


The search part of the problem is a lot like memmem (an explicit-length version of strstr, found in GNU and *BSD C libraries) but with int instead of char elements. You could literally use memmem if you check for and reject unaligned matches. The implementation should be well optimized with hand-written asm using SIMD instructions.

For systems where wchar_t is the same as int, there's C11 wmemchr and wmemcmp as possible building-blocks, but no wmemmem for wide-char.

You can always use regular memcmp(p, q1, len_in_bytes) instead of the while (q < q2 && *p == *q) loop, to get access to platform-specific optimize code (usually hand-written in asm) that compares bytes in memory in a range. (Where size_t len_in_bytes = (const char*)q2-(const char*)q1; or (q2-q1) * sizeof(int), or actually min of that and (p2-p)*sizeof(int) to avoid going past the end of p.) This typically uses SIMD on platforms like x86-64 and AArch64 to compare in chunks of 32 or 16 bytes. (Related: Why does glibc's strlen need to be so complicated to run quickly?).

If you were vectorizing manually, e.g. with x86 intrinsics like __m128i first_16bytes_of_needle = _mm_loadu_i128((const __m128*)q1), a useful special-case would be a needle length of 4 int elements, exactly one 16-byte vector. (SSE4.2 string-search instructions like pcmpestri are slower with explicit-length than implicit-length (0-terminated), and only work with 8-bit or 16-bit elements, but int is 32-bit on x86, so I don't think they'd be easy to use even though strstr or memmem does make them potentially useful, unlike memchr where plain SSE2 or AVX2 instructions like pcmpeqb / pmovmskb are faster.)


Miscellaneous minor points.

            int found = 1;

Your compiler should warn you about an unused variable, set but not read.

Also, agreed with @vnp that returning a pointer to the new end of p would be the most useful and natural API for this function. Or a new length, of elements you kept, not elements removed. If the caller wants elements removed, they can easily calculate it from the old and new ranges, like p2 - remove_subarrays(p1,p2, q1,q2) to do old_end - new_end.


        // Special case: If the sizes and values match, skip the loop and return total size.
        if (p2 - p1 == 12 && q2 - q1 == 3 && *q1 == 1) {
            removed_count = 12;
            return removed_count;
        }

Why is this code in your function? Some kind of easter-egg, or signalling mechanism to behave differently than specified? It's not just an optimization for a specific case, it removes all the elements without checking if they actually match the pattern.

Clearly this is only appropriate for specific use-cases, because it makes the function fail if these circumstances happen "by accident" when you did want removals only when data matched. A comment should do a better job of explaining which callers want this behaviour, or something like that.

Usually in code we have special cases either as an optimization or implementing the same general rule in two different ways, e.g. for size 0 or 1 vs. >= 1. This isn't like that, the behaviour doesn't follow the general rule any more.

This is super weird and requires a more detailed comment to justify its existence. Or it doesn't belong in a code-review post about implementing the described problem of matching sub-array removal at all.


Footnote 1: discovering new matches after removing all initially-visible

Do we need to backtrack to consider newly formed matches involving earlier elements? That's possible:

 array = [1 2 1 2 1 1 2 1 2 1]
needle = [1 2 1]

      2 1 1 2 1 2 1    After first subarray remove (at start)
      2 1       2 1    After second subarray removal
2 1 2 1                After compaction (which hopefully happened on the fly as we copied)
 This contains another copy of the subarray starting at an element passed by earlier
2                     After removing the final instance of the subarray
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.