[ProfessorChill]

I did this challenge, because I like learning by doing challenges.
http://i.imgur.com/SZzrXSp.png

But it can clearly go faster, but I'm not sure how I'd do that.

Code:

class Solution { public: int lengthOfLongestSubstring(std::string s) { size_t x; int y, result; int index[128]; std::memset(index, 0, sizeof(index)); result = y = 0; for (x = 0; x < s.length(); x++) { y = std::max(index[static_cast<int>(s[x])], y); result = std::max(result, static_cast<int>(x - y + 1)); index[static_cast<int>(s[x])] = x + 1; } return result; } };

Any tips?

[phyrrus9]

1. don't use a class for that, you don't need it. The initialization and destruction of the class rob a lot. If you insist on using a class, make the method static.
2. wtf are you doing with that array and cast nonsense.

How are you defining substrings?

[ProfessorChill]

1. don't use a class for that, you don't need it. The initialization and destruction of the class rob a lot. If you insist on using a class, make the method static.
2. wtf are you doing with that array and cast nonsense.

How are you defining substrings?

Um... I'm just going to ignore this because I answer most of that up top in one single picture and exclamation.

EDIT: And this response doesn't give me any resources to learn from, it's just complaints.

[Skullmeat]

1. don't use a class for that, you don't need it. The initialization and destruction of the class rob a lot. If you insist on using a class, make the method static.
2. wtf are you doing with that array and cast nonsense.

How are you defining substrings?

Um... I'm just going to ignore this because I answer most of that up top in one single picture and exclamation.

EDIT: And this response doesn't give me any resources to learn from, it's just complaints.

Ignore him, hes complaining without giving any real constructive criticism. Anyway, I'm not much of a coder, can you explain what it is you are trying to do?

[Blink]

@ProfessorChill
If you aren't changing the length of the array in the loop, you shouldn't do this:

Code:

for (x = 0; x < s.length(); x++) {

It checks the length with each loop, wasting some cycles each time. Instead, just put the length in a variable ahead of time.

You also do this twice:

Code:

index[static_cast<int>(s[x])]

If you want ideal speed, you should just store that in a variable. It's not the most memory efficient, but it's better for CPU efficiency, especially when you're casting each time. Also, I don't think it's necessary to convert from char to int, just use char. Although interestingly, int variables are faster to deal with on some architectures, like ARM.

---

1. don't use a class for that, you don't need it. The initialization and destruction of the class rob a lot. If you insist on using a class, make the method static.
2. wtf are you doing with that array and cast nonsense.

How are you defining substrings?

Um... I'm just going to ignore this because I answer most of that up top in one single picture and exclamation.

EDIT: And this response doesn't give me any resources to learn from, it's just complaints.

Ignore him, hes complaining without giving any real constructive criticism. Anyway, I'm not much of a coder, can you explain what it is you are trying to do?

Actually he is trying to help; classes are unnecessary there, and nothing obvious in the top explains why he's using them.

[ProfessorChill]

@ProfessorChill
If you aren't changing the length of the array in the loop, you shouldn't do this:

Code:

for (x = 0; x < s.length(); x++) {

It checks the length with each loop, wasting some cycles each time.  Instead, just put the length in a variable ahead of time.

You also do this twice:

Code:

index[static_cast<int>(s[x])]

If you want ideal speed, you should just store that in a variable.  It's not the most memory efficient, but it's better for CPU efficiency, especially when you're casting each time.  Also, I don't think it's necessary to convert from char to int, just use char.  Although interestingly, int variables are faster to deal with on some architectures, like ARM.

---

Um... I'm just going to ignore this because I answer most of that up top in one single picture and exclamation.

EDIT: And this response doesn't give me any resources to learn from, it's just complaints.

Ignore him, hes complaining without giving any real constructive criticism. Anyway, I'm not much of a coder, can you explain what it is you are trying to do?

Actually he is trying to help; classes are unnecessary there, and nothing obvious in the top explains why he's using them.

Thanks for the actual hints, I'll probably integrate that.
Especially the for loop re-checking the length every loop, I didn't think about that at all.

I did explain above, I am doing a challenge on a website, they have a required format.
Actually, all challenge websites have some form of whack ass required format, but I suppose I could have pointed it out a bit better.

Also, I don't 100% understand this, but it seems to speed it up.
I think it's to do with buffering the cin and cout??? No clue though. I'll probably research it tomorrow when I actually wake up.

Code:

static auto x = [](){ std::ios::sync_with_stdio(false); std::cin.tie(NULL); return 0; }();

[Blink]

@ProfessorChill
If you aren't changing the length of the array in the loop, you shouldn't do this:

Code:

for (x = 0; x < s.length(); x++) {

It checks the length with each loop, wasting some cycles each time.  Instead, just put the length in a variable ahead of time.

You also do this twice:

Code:

index[static_cast<int>(s[x])]

If you want ideal speed, you should just store that in a variable.  It's not the most memory efficient, but it's better for CPU efficiency, especially when you're casting each time.  Also, I don't think it's necessary to convert from char to int, just use char.  Although interestingly, int variables are faster to deal with on some architectures, like ARM.

---

Ignore him, hes complaining without giving any real constructive criticism. Anyway, I'm not much of a coder, can you explain what it is you are trying to do?

Actually he is trying to help; classes are unnecessary there, and nothing obvious in the top explains why he's using them.

Thanks for the actual hints, I'll probably integrate that.
Especially the for loop re-checking the length every loop, I didn't think about that at all.

I did explain above, I am doing a challenge on a website, they have a required format.
Actually, all challenge websites have some form of whack ass required format, but I suppose I could have pointed it out a bit better.

Also, I don't 100% understand this, but it seems to speed it up.
I think it's to do with buffering the cin and cout??? No clue though. I'll probably research it tomorrow when I actually wake up.

Code:

static auto x = [](){    std::ios::sync_with_stdio(false);    std::cin.tie(NULL);    return 0; }();

Well here's that exact question on SO: https://stackoverflow.com/questions/3116...in-tienull

Spoiler:

This is a great use of StackOverflow. Too many people use code from SO, which causes their code to be terrible in the end. This is especially true when they don't understand what they're copying. However, it is good for questions like this. (more theory than implementation)

Also, I didn't realize that the site had a required format. I guess that makes sense, but it's definitely not an obvious thing.

[reGEN]

@ProfessorChill
If you aren't changing the length of the array in the loop, you shouldn't do this:

Code:

for (x = 0; x < s.length(); x++) {

It checks the length with each loop, wasting some cycles each time.  Instead, just put the length in a variable ahead of time.

You also do this twice:

Code:

index[static_cast<int>(s[x])]

If you want ideal speed, you should just store that in a variable.  It's not the most memory efficient, but it's better for CPU efficiency, especially when you're casting each time.  Also, I don't think it's necessary to convert from char to int, just use char.  Although interestingly, int variables are faster to deal with on some architectures, like ARM.

I just wanted to point out that though this might be true, it doesn't apply in every case. Compilers include optimizations to the code to make it more efficient. String lengths or data sizes are usually optimized into a local variable or register so something like this:

Code:

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

may be compiled down such that the loop operates on a static value.

Another classic example that creates optimizations is:

Code:

int num = 0; for (int i = 0; i < ONE_MILLION; i++) {    num++; }

may destroy the loop entirely and just statically initialize the num variable directly to its resulting value. This can create scenarios where higher level languages such as Java give the illusion that it is faster than a language such as C which preserved the loop.

So it depends on how your code is compiled. I'm assuming you submit your source and the server compiles the code for you using predefined optimizations so your binary does not get optimized as much.

Some things I've noticed when I compiled your code using no optimization flags:

• Yes, your code does constantly call string::length every time it iterates the loop,
  
• Since you are operating on the std:tring data type, every time you use the bracket operators, you are calling the class's string::operator[] member,
  
• As above, every time you are using max or memset, it is calling std::max or std::memset,
  

To optimize the above, you can try:

• As Ender stated, you may store the string::length value into a variable to remove the string::length call every iteration,
  
• For the string::operator[], you may store the string into an array so that it can direct access without the need for the function call overhead,
  
• For the std::memset and std::max, you may also remove the call overheads by inlining them (I'm not 100% sure if this is recommended since the compiler should normally determine how to optimize this but do NOT create your own by using some basic data assignment to 0 using a byte-by-byte loop or something like that, there is actually proper optimization in the memset function call),
  
• Perhaps there is a way to initialize your index array without using std::memset such that when it is compiled, it will be initialized to 0 in the actual binary itself, thus removing any need to initialize it (for more info, read about the BSS segment),
  
• Multithreading for overall optimization.