Optimizing performance of hashing array algorithm's implementation

Question

I wrote the following C++ code and since I am a novice in C++ and do not really have anybody who can give me advice, I think this site would be a good place to ask.

The algorithm takes the first two elements a1 and a2 of an array, calculate the difference a2 - a1. Then the first two elements a1 and a2 will be removed from the array and the calculated difference will be inserted in front of the array. This will be repeated until there is only one element left. The last element of the array will be the hash value of the array.

The initial array will be mutated q times with the following formula: increase all elements in the segment [lj,rj] by vj, after each mutation the hash value should be printed.

The input will look something like following

7
4 2 -5 10 4 -2 6
4
2 4 -8
5 7 2
3 3 -1
3 7 3

where the first line indicates the length of the array. The next line will be the content of the array, the third line would be q and every following line is lj, rj, vj.

This is how my code looks like at the moment. I would appreciate every critic.

#include <vector>
#include <iostream>
#define ll long long
ll __hash__(const std::vector<int> &arr) {
 ll front = arr[0];
 for(ll i = 1; i < arr.size(); i++){
 front = arr[i] - front;
 }
 return front;
}
int main() {
 std::vector<int> arr;
 ll size;
 std::cin >> size;
 for (ll i = 0; i < size; ++i) {
 ll c;
 std::cin >> c;
 arr.push_back(c);
 }
 ll q;
 std::cin >> q;
 for (ll i = 0; i < q; ++i) {
 ll l, r, v;
 std::cin >> l >> r >> v;
 for(ll j = l - 1; j < r; ++j){
 arr[j] += v;
 }
 std::cout << __hash__(arr) << std::endl;
 }
 return 0;
}

• vnp: You are briteforcing. Once the initial hash is computed, the subsequent queries shall be answered in constant time. Hint: pay attention to the parities of rj - lj and n - rj.
• curiouscupcake: @vnp well that is a great hint.
• Ted Lyngmo: Do I understand it correctly if I say that [1,2,3] will have the same hash value as [2,4]?

Answer 1

The Good

The code is fairly readable, horizontal spacing is good.

The variables are declared as they are needed.

You didn't use using namespace std; which is very good for a beginner.

Macros in C++

Macros are included in C++ to support some backward compatibility with the C programming language that it grew out of, but they generally aren't used in C++ because they aren't type safe. Replacements for macros are inline functions, and lambda expressions or closures.

An alternate to what is in the code is to use typedef. A second alternative is to use using ll = long long;.

The best thing might be to find what types C++ supports and use that instead. You can find a list of the types provided by the cstdint header file here.

Another alternative is to just use long long rather than shortening it. C++ is not a scripting language and C++ coders are used to things like this.

Beginning a Variable or Function with Double Underscore.

Function names and variables should start with letters rather than underscores, double underscore is reserved for special usage.

Variable Names

Single letter variable names make the code very hard to understand, I don't even have a clue what c, q, l, r or v are or I would try to guess at their meanings.

Variables i and j are used as indexes into the vector, it would be better if these variables were of type size_t rather than long long because size_t is defined as unsigned and can't be negitive. It would very rare to have an array or vector that would require the address space of a long long.

One Variable Declaration Per Line

The code contains this line

 ll l, r, v;

To make the code more maintainable each variable should be declared and initialized on it's own line.

 ll l = 0;
 ll r = 0;
 ll v = 0;

Vertical Spacing

To make the code more readable it needs some vertical spacing, one line between logical blocks:

#include <vector>
#include <iostream>
using ll = long long;
ll __hash__(const std::vector<int> &arr) {
 ll front = arr[0];
 for(ll i = 1; i < arr.size(); i++){
 front = arr[i] - front;
 }
 return front;
}
int main() {
 std::vector<int> arr;
 ll size;
 std::cin >> size;
 for (ll i = 0; i < size; ++i) {
 ll c;
 std::cin >> c;
 arr.push_back(c);
 }
 ll q;
 std::cin >> q;
 for (size_t i = 0; i < q; ++i) {
 ll l, r, v;
 std::cin >> l >> r >> v;
 for(size_t j = l - 1; j < r; ++j){
 arr[j] += v;
 }
 std::cout << __hash__(arr) << std::endl;
 }
 return 0;
}

• curiouscupcake: Thank you, those are some tips I could really need
• Mannoj: 1. It will be good if every "{" goes to next or new line. 2. using intList = std::vector<int>
• pacmaninbw: @Mannoj Yes, but that is a style issue generally covered in a style guide.
• Mannoj: Ok, but it's also help readability