ethico's blog

a simple mistake every beginner usually do.
By ethico, history, 5 years ago, In English

usually when i started coding and started learning about string array or normal array ,i used to work with string array or array by typing strlen() or size() in the for loop condition.

for(int i=0;i<strlen();i++)
{
    statement;
}

but its a totally wrong way to set up the condition.because normally if my algorithms complexity is O(n),and i use strlen() it,my time complexity will become O(n^2). **** this happens because every time for loop come to check the condition it will start checking what is the string length is,so total complexity will become n*n = n^2 **** so to avoid this kind of situation ,declare integer variable n= strlen(),and then put the code like this

int n= strlen();
for(int i=0;i<n;i++)
{
    statement;
}

i hope this will be helpful :).

  • Vote: I like it
  • +35
  • Vote: I do not like it

Comments Comments (17)
| Write comment?
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I use .size() yet no problem when the string size is constant

also yes you should put a lim for example for sqrt n

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +89 Vote: I do not like it

thanks for writing everything in bold ,it makes the whole thing easy to read

Yes, strlen is linear so for(int i = 0; i < strlen(...); i++) is quadratic. It's better to create and use a variable n.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    That is to give more emphasis and strength to the statement.

    → Reply
»
5 years ago, # |
  Vote: I like it +63 Vote: I do not like it

If the compiler is able to prove that the const char * argument to strlen doesn't change in the loop, it may hoist the strlen call out of the loop.

Try this with G++ in custom invocation, with or without s[i] = '0' and observe the time.

#include <cstdio>
#include <cstring>

using namespace std;

int main() {
    char s[1000000];
    scanf ("%s",s);
    int ret = 0;
    for (int i = 0; i < strlen(s); ++i) {
        s[i] = '0'; //< comment this line to reduce the running time
        ret += s[i];
    }
    printf("%d", ret);
}

So it's not always lost. However, it is a good practice not to do this.

→ Reply
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Your way of storing string data is C style. I use C++ way, the std::string. I would say it's beneficial to use std::string. It is easy to work with (like you are working with char array). you can add another string to the end of that with += operator and you can get it's length with size member function in constant time (which means you just have to type .size() and it won't affect your program's time complexity the way you described). If you wanted a C string (which is const char*) you can have it by .c_str(). You can lexicographically compare two std::string s by </>. You can sort an array of them by std::sort "easily" (By that I mean you don't have to write a comparator). It has handy pop_back and substr member functions. For further reading, check out basic_string. std::string may have some overhead but I'd say its negligible. BTW you don't have to type std:: all the time :).

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    std::string is as far as I know quite slower than char*. And yes it has a lot of useful functions but when your write them on your own you know exactly how they are implemented and can optimise them but it doesn't take a lot of time. It is different with std::set or std::map which have a complicated implementation.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +75 Vote: I do not like it

      C++ is as far as I know quite slower than Assembler. And yes it has a lot of useful functions but when your write them on your own you know exactly how they are implemented and can optimise them but it doesn't take a lot of time. It is different with Haskell or Postgres which have a complicated implementation.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        C++ is on a lot of cases faster than (naively-written) assembly code. In general what you would say that makes std::string and other containers slow is heap allocations. As long as you make the same number of allocations for std::string as you would make with char*, you shouldn't see much difference.

        A std::string probably makes a logarithmic (in the number of elements) number of heap allocations, just as std::vector, which is totally fine. What might not be as fine is allocating a std::string at every iteration of a loop, where for char* you might preallocate straight away (mainly because coding in a rudimentary C-style fashion goes implicitly hand-in-hand with making everything global). The allocation might or might not be optimized away by the compiler, but if you strive performance, just try to limit the number of allocations (stl or non-stl).

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'd rather stick to STL as long as it provides the functionalities I want. I prefer to get used to that because time limits, most of the time, aren't that tight that small changes will be necessary and help you pass the tests. Another reason (at least for me) is that in an onsite contest when you are not allowed to copy/paste codes from web or your own library, and you have to type anything you want (at least once!), you can use language features and buy yourself some amount of time. Plus, C++ library is well written and you won't face an issue if you use it right.

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

There is no harm in doing strlen operation in a loop, unless you are modifying the string in the loop again and again. Length of the string gets stored in the memory and the value is accessed by the Hit, which is constant time. In case the string is modified, the modify flag becomes True, hence the program takes O(length of string) complexity to run the operation.
Also, string.size() works in constant time complexity.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    thanks <3

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it +16 Vote: I do not like it

    What you described is a possible optimization which the compiler may make if it can prove that the string length isn't modified in the loop. It is not required by the C++ standard and you shouldn't rely on it because it's very possible that the compiler isn't able to make such a proof. For example, the compiler might not perform this optimization if you called a function that has access to the string, even if that function doesn't actually modify the string. A real-world example from ShapC shows the compiler not performing the optimization even though the string is const and never modified resulting in much slower code. Don't take such an unnecessary risk in contests.

    → Reply
»
5 years ago, # |
  Vote: I like it +36 Vote: I do not like it

https://sourceforge.net/p/notepad-plus/patches/473/

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

some coders use this trick 

char s[100];
for (int i = 0; s[i]; ++i) { ... }
→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Do you have to do this with vectors as well?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    .size() works ok, so you should not worry about it. When you use strlen() it iterates through the whole char[] to find null-termination character

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think .size() is constant and doesn't take linear time;

due to this link: http://www.cplusplus.com/reference/string/string/size/

→ Reply