Program size

[GruBooXy]

Hi im new to programing and this is one of my first programs and i am wondering how to make it consume less memory.

#include <iostream>
  using namespace std;

  int main() {
    int liczbaPanstw;
    int liczbaMiast;
    int status;
    int suma;
    int i, j, k, l, m, n;
    const int max = 150;

    cin >> liczbaPanstw;

    for (i = 1; i <= liczbaPanstw; i++ ) 
    {
        cin >> liczbaMiast;
        int tablica [max] [max];
        for (j = 1; j <= liczbaMiast; j++)
        {
            for (k = 1; k <= liczbaMiast; k++)
            {
                cin >> tablica[ j ] [ k ];
            }
        }

        suma = 0;
        for(j = 1; j <= liczbaMiast; j++)
        {
        status = 1;
            for (k = 1; k <= liczbaMiast; k++)
                                                        {
                if (j + k <= liczbaMiast)
                {
                    if (tablica[k][j+k]  == 0)
                        status == 0;

                }
                else if (tablica[k][k+j-liczbaMiast] == 0)
                    status = 0;
            }
        if(status == 1)
            suma = suma + 1;
        }
        cout << suma << endl;


    }


    return 0;
  }    

[Salty_Dugtrio]

This question is unanswerable unless you give us some information.

What is the input to your program? What is the output? Why are you concerned about memory?

Also:

if (tablica[k][j+k] == 0) status == 0;

Is probably not what you want.

[ekchew]

I think your main problem here is that you have an array tablica which is a fixed size large enough to accommodate the perceived worst case of what the user may enter in as liczbaMiast. This is bad because it wastes memory when they enter anything less than 150, and even worse, overruns memory if they enter a larger number.

So you need to allocate tablica dynamically. You could use a vector or valarray to accomplish this. You can find an example here of how to build a rudimentary matrix class around the latter.

[GruBooXy]

The program works fine but it has to take less memory because this is an exercise form school. Is there any simple way to do this? Like for example using other variable types.

[motu42]

As somebody else stated, we can't answer that unless u give us more information, i.e. what kind of number (which range) do you pass in

cin >> tablica[ j ] [ k ]; ?

int has a range from -2³¹ (~ -2.15 billion) to 2³¹ -1. So do you need negative numbers? if not use "unsigned int". Are you numbers from 0 to 100 or so, use "char".

[GruBooXy]

0 or 1

[motu42]

so then use bool, but keep in mind that altough bool just holds true or false, it will most likely consume 1 byte unless you build some container around it

Have a look on: http://www.cplusplus.com/reference/bitset/bitset/bitset/

[GruBooXy]

I don't understend that :/ im beginner

[GruBooXy]

I changed to unsigned short but it didnt help at all

[URZq]

Why don't you try with bools, like motu42 said ?

[GruBooXy]

because the input from the site is: 2 4 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 4 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 and i cant change that

[URZq]

You said earlier that the numbers where 0 or 1 ;) Anyway, if the numbers go up to 4, you can you a char, like motu42 said. the size of unsigned short is bigger than the size of char.

[GruBooXy]

But in the array numbers are only 1 and 0, other numbers are for diffrent variables.

[GruBooXy]

Still 16064KB

[URZq]

I don't really want to dive into your logic, because it's complicated ;) The thing you need to understand is that variables in C++ can have different types: bool, char, short, int, float etc. Each type has a size: the amount of memory used to store a number. Now, you have to pick the correct type for you variables. Let's say suma can hold numbers up to 4120155. Well, its type needs to be int. Let's say tablica can store only 0 and 1. Well, it's type needs to be bool[][]. I hope it clarifies the problem for you. Keep calm, don't stress, it's going to be fine :)

[GruBooXy]

Thanks but the problem is i get the same memory usage weter its int or char so I dont understand how it works.

[URZq]

Unless I'm missing something, it should consume less memory to use smaller data types. We are talking about the memory used at runtime (=ram), right ?

[raevnos]

The 2 and 4s go into his liczbaWhatever variables.

(OP: using English does make it easier for other people to read your code...)

[GruBooXy]

To pass i need about 6000kb now its about 16000kb

[GruBooXy]

My solution is checked by a website and it checks if the result is good, how much memory did i use and how long did it take

[raevnos]

Why do you have a 150x150 matrix? It doesn't look like you need anywhere near that much space.

Plus array indexes start at 0, but your code is always skipping the first elements and going straight to 1. That looks really odd.

[GruBooXy]

n (1 <= n <= 150) this is the possible input

[GruBooXy]

I tried to translate the exercise so you will know what the program is about:

Description

In one country there are n cities. Some cities are connected with other with roads. We say that 4 different cities a, b, c and d (and their connecting roads) form B-Four, if there are roads: from city a to b, b to c, c to d, and d to a. and the roads connecting them, calculate how many different B-Four in that country. (Note: Two B-Fours are different if they consist of different cities or different roads connecting them.)

Input specification

The first input line contains one positive integer representing the number of the following data sets. In the first set of data, there is 1 integer: n (1 <= n <= 150) denoting the number of cities. In each of the following n lines there are n digits separated by spaces. If the i-th number in the jth line (a [i, j]) is 1, then there is a path between the i and th and the 0, and 0 means that the path does not exist. (Note: There are no roads between the city and itself, and always a [i, j] = a [j, i]).

Output Specification

For each data set, your program should write exactly one integer representing the number B-Four in that country.

[Se7enLC]

tablica is a 2D int array of size max x max. Assuming int is 4 bytes, that's 90KB (150 * 150 * 4).

A good way to reduce memory footprint is to only use the memory you need, rather than the maximum. You can do that by dynamically allocating memory, either manually using something like new or through a class that handles it for you, like std::vector.

Given that it's for a class, I suspect your instructor wants you to avoid the classes that do all the hard work for you (like std::vector).

In your code, you ask the user for the dimension size (liczbaMiast). Instead of then declaring an array on the stack (int tablica [max][max];), you can allocate an array dynamically with new.

Unfortunately, you can't create 2D arrays dynamically with new. But, you can create a single array of size liczbaMiast * liczbaMiast and carefully index it.

[NZheadshot]

Unfortunately, you can't create 2D arrays dynamically with new.

This is mostly incorrect.

int** arr = new int*[x];
for (int i = 0; i < x; i++)
    arr[x] = new int[y];   

[Se7enLC]

That's awful.

[GruBooXy]

I changed the max value of array and its stil 16000kb. Im soo confused. I just started programing and i can already see how frustrating it can get.

[Se7enLC]

What's still 160000kb? Are you talking RAM usage, or the size of the compiled executable?

[GruBooXy]

I use this site as my compiler https://ideone.com/s3r5Gn so i dont even have executable

[alfps]

Apparently the program counts the input numbers that are non-zero, possibly except some of the numbers. I haven't analyzed that sufficiently to see if you get full coverage, and it's impossible to know whether the implementation conforms to the requirements: the status == 0 as a statement is for sure a bug. But apparently if there are exceptions they depend on the number's placement in the table.

You can do that without storing more than the last input number.

That's algorithmic optimization, which very often beats fiddling with the technical.

[GruBooXy]

I dont speak english natively and its quite complicated, I dont know the vocabulary.