Member Avatar for swissknife007

I am implementing a program where I want to store only certain part of the input string.
for eg if the input string is
0123456789
I want to discard 4 AND 7
and store
01235689
Please my program requires an input string of 10000 characters so running time is very crucial for me.
Also while inputting the string I really don't know how many characters will be there.
Does anybody have any suggestions?
Any help will be greatly appreciated

Edited by swissknife007 because: n/a
  • 4 Contributors
  • 8 Replies
  • 214 Views
  • 9 Hours Discussion Span
  • Latest Post Latest Post by mhd_arif123

Dani AI

Generated

A single linear pass is the simplest, fastest and clearest solution: test each byte once and copy only the accepted bytes. That gives O(n) time and either O(1) extra space (in-place) or O(n) extra space if preservation of the original buffer is required. For a fixed set of discard characters (like '4' and '7') a 256-entry boolean lookup indexed by the unsigned byte value makes each test a single array lookup (branch-friendly and cache-friendly) instead of an expensive container search.

An in-place C-style compaction (no extra buffer) looks like this:

unsigned char discard[256] = {0};
discard['4'] = 1;
discard['7'] = 1;

/* buf is a NUL-terminated modifiable C string */
size_t wr = 0;
for (size_t rd = 0; buf[rd] != '\0'; ++rd) {
    unsigned char c = (unsigned char)buf[rd];
    if (!discard[c]) buf[wr++] = buf[rd];
}
buf[wr] = '\0';

For streaming input (unknown length or stdin/stdout), process large blocks: read a chunk (fread), copy non-discard bytes into an output chunk, then fwrite the output chunk. That avoids per-byte I/O overhead and repeated reallocations. In C++ the equivalent is either reserving capacity and push_back for non-discard bytes, or using std::remove_if + erase on a string (both are linear).

Notes and ties to existing replies: is correct that filtering while reading is natural; the buffered-block variant above is the higher-performance version for large inputs. mentioned memchr — it can help skip to matches in some patterns, but for multiple discard values a simple 256-byte lookup is usually clearer and faster. described the general match-and-copy idea; the examples above show an efficient, low-overhead implementation suitable for ~10k characters or much larger inputs. Care must be taken to cast to unsigned char for indexing and to NUL-terminate C strings when modifying in-place.

Recommended Answers

All 8 Replies

Member Avatar for gerard4143

Depends, what is the criteria for discarding characters.

Member Avatar for swissknife007

Depends, what is the criteria for discarding characters.

I already told you the criteria.
I dont want 4s and 7s in my answer

Member Avatar for swissknife007

I already told you the criteria.
I dont want 4s and 7s in my answer

I mean I don't want to store 4s and 7s present in the input.

Member Avatar for gerard4143

I would investigate a function like

void *memchr(const void *s, int c, size_t n);

The memchr() function scans the first n bytes of the memory area
pointed to by s for the character c. The first byte to match c
(interpreted as an unsigned character) stops the operation.

The memchr() and memrchr() functions return a pointer to the match‐
ing byte or NULL if the character does not occur in the given mem‐
ory area.

Copied from the manpages on GNU/Linux.

With this function you can leap through valid areas of data to store.

Edited by gerard4143 because: n/a
Member Avatar for swissknife007

I would investigate a function like

void *memchr(const void *s, int c, size_t n);

The memchr() function scans the first n bytes of the memory area
pointed to by s for the character c. The first byte to match c
(interpreted as an unsigned character) stops the operation.

The memchr() and memrchr() functions return a pointer to the match‐
ing byte or NULL if the character does not occur in the given mem‐
ory area.

Copied from the manpages on GNU/Linux.

With this function you can leap through valid areas of data to store.

Sorry but you didnt understand my question.i dont want to stop reading once i encounter 4 or 7.I want to continue reading the rest of the string

Member Avatar for gerard4143

Sorry but you didnt understand my question.i dont want to stop reading once i encounter 4 or 7.I want to continue reading the rest of the string

Yes I understood your question. You use the function memchr to find the occurrence of characters(or pointers to the occurrences) to find ranges(pointer ranges) of valid data.

Member Avatar for L7Sqr

How are you handling the input/output? Given that you can read from stdin and write to stdout why not just filter the input?

int main () {
   int c = 0;
   while (EOF != (c = fgetc (stdin))) {
      switch (c) {
         case '4': case '7': break;
         default: fputc (c, stdout);
      }
   }
   return 0;
}
Member Avatar for mhd_arif123

I am implementing a program where I want to store only certain part of the input string.
for eg if the input string is
0123456789
I want to discard 4 AND 7
and store
01235689
Please my program requires an input string of 10000 characters so running time is very crucial for me.
Also while inputting the string I really don't know how many characters will be there.
Does anybody have any suggestions?
Any help will be greatly appreciated

Step 1 : you have to store those characters (that you want to discard) in a data structure
Step 2 : extract a single character from the input string and match it with the list of discardable characters.
Step 3 : if match is not found , copy the extracted character to a new place(datastructure). else leave it.
continue above steps , till the end of input string.

Edited by mhd_arif123 because: n/a
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.