Chef and Digits

Question

I am looking for a review on the following code which is for this question. I am looking for a general review of the code. I am specifically also looking for advice on how to make this code run more efficiently.

#include<iostream>
#include<stdlib.h>
using namespace std;
long int b[100001]={0},x,n,m,i;
char num[100001]; 
int main() 
{ 
 cin>>n>>m;
 for(i=1;i<=n;i++)
 cin>>num[i];
 while(m--)
 {
 b[100001]={0};
 cin>>x;
 for(i=1;i<x;i++)
 {
 b[i]=b[i-1]+abs(num[x]-num[i]);
 }
 cout<<b[x-1]<<"\n";
 }
 return 0;
}

• BenVlodgi: Getting something to run in under a second could just be you getting a better computer. It would be better instead to ask for a review, as that is what this site is for, and perhaps you will also get some efficiency tips.
• user40239: i'm quite new to this forum. any kind of help would be appreciated.
• Jerry Coffin: Start by making the code actually correct. I'm not sure what you think b[100001]={0}; does, but what it actually does is cause undefined behavior (it's writing past the end of b).
• user40239: it assigns the value '0' to each cell in the array b[]. for example in this code ideone.com/VHoTg1
• Loki Astari: NO: long int b[100001]={0}; sets all members to zero. But b[100001]={0}; access one past the end of the array pretends it a long a sets this single value to zero. So whatever was one past the end of your array is now corrupt. Also its undefined behavior this means your program is broken.

Answer 1

• Try not to get into the habit of using using namespace std. It may be okay for small programs, but it can cause problems for larder ones.

• Use <cstdlib> instead of <stdlib.h>; the latter is a C library.

  Moreover, you don't need this library at all; <cmath> is where std::abs() is defined.

• Even in a small program, do not use global variables:

  long int b[100001]={0},x,n,m,i;
  char num[100001];
  

  The problem with this is that these variables can be changed anywhere in the program. If you have a large program, this will be even worse as it won't be easy to determine where a certain variable is being modified. I'd strongly recommend that you don't let this become a habit.

  If you're going to keep everything in main() (could be permissible for this small program), then move those variables into the function. If you were to expand this to multiple functions, then pass those variables to the functions from main().

• Avoid single-character variable names unless they're simple loop counters. This makes it harder for others to understand your code. It will also make maintenance a lot harder, especially if you decide to grow this program. Use more distinctive names that will also not require comments.

• Use whitespace between operators for readability. There's no need to cram characters together if you're trying to have shorter lines. Just find ways to use less code on each line.

  This, for instance:

  b[i]=b[i-1]+abs(num[x]-num[i]);
  

  will become

  b[i] = b[i-1] + abs(num[x] - num[i]);
  

• Declaring the loop counter outside the loop statement is from C, not C++. Declare it inside.

  for (int i = 0; i < n; i++)
  

• You don't need the explicit return 0 at the end of main(). Reaching this point already implies successful termination, so the compiler will insert it for you.

• Although it may not make a great difference here, I'd recommend considering std::vector over C-style arrays in general. This is a common C++ storage container and is more usable than static arrays as it's a dynamic container.

  Your C-style arrays:

  long int b[100001]={0};
  

  char num[100001];
  

  would look like these respectively:

  std::vector<long int> b(100001, 0);
  

  std::vector<char> num(100001);
  

  This container overloads operator[], so the syntax for accessing C-style array elements is the same. But you also get iterators, which directly point to the elements and will help prevent accessing the container out of bounds.

• SAFAD: I am really surprised that you didn't recommend using C++ vectors rather than Arrays in C-style. Good answer, well organised!
• Jamal: @SAFAD: Very true. :-) I tend to still miss some obvious things. I may add this later. Thanks!

Answer 2

The advice from @Jamal's answer is sound regarding general programming issues. This is a supplemental answer specifically addressing performance and design issues.

b doesn't need to be an array

'b' in your code need only be a single long int rather than an array. Your inner loop then becomes

b += abs(num[x] - num[i]);

make only one loop through num[]

You need only iterate through num[] at most one time. Instead of reading in each x and calculating each in a loop, you could instead read all x values into an array and then calculate all answers in parallel.

It may seem contradictory, but then that means you could make b[] back into an array, but one which need only hold m answers rather than having the dimension n.

pull loop invariants out of the loop

The chances are good that your compiler will do this for you, but instead of this:

for(i=1; i<x; i++)
{
 b[i]=b[i-1]+abs(num[x]-num[i]);
}

You could instead write this:

for(long int i=1, lim=num[x]; i<x; i++)
{
 b+=abs(lim-num[i]);
}

This assumes that you've also made the change that b is now a single answers.

generate all answers and then print them

Instead of emitting each answer within your loop, create them all in an array and then emit them all at once at the end of the program. This makes little difference with small amounts of data, but as your data grows larger, this allows more of the relevant pieces to stay in the cache during calculation.

You might even consider creating the output string in memory and then send it to std::cout, but this only saves very little until the output strings get very large.