[kirtan]

Experts I need you help .

I have to store large list of elements(100000 integer) in C++ but have limitation of 64 MB Memory .

I cant use array as array goes out of memory.also Linked list have problem that i can not access elements faster .As i need to access elements between 2 indices frequently .

Can anybody help ?

Thanks in Advance

[sarmanu]

STL Vector?

[Salem_c]

> I have to store large list of elements(100000 integer) in C++ but have limitation of 64 MB Memory
Rubbish.
Your ancient compiler might be limited, but there is no such limit in the definition of C or C++.

Modern computers and operating systems give you a whole football field to play in. But with your ancient compiler, you're still messing about with the weeds in the back garden.

Get a real compiler, and the problem goes away just like that!

[kirtan]

Salem_c, on 03 September 2010 - 08:04 AM, said:

>Your ancient compiler might be limited, but there is no such limit in the definition of C or C++.

Modern computers and operating systems give you a whole football field to play in. But with your ancient compiler, you're still messing about with the weeds in the back garden.

Get a real compiler, and the problem goes away just like that!

Friend , I don't have ancient compiler i am using GCC 4 Have 2 GB Ram
but problem is I have to solve the specific problem in that much amount of memory (64 MB) only. Problem i have to solve is i have to store that much elements optimally so that it will have smallest memory foot print

[KYA]

So the requirement is to have all 100,000 integers in play at once, but you're limited to 64 MB for the entire program? Or storage of those integers?

100,000 integers at 4 bytes a piece = 400,000 bytes
= 400 kB
= 0.4 MB

What exactly is the issue?



MinGW on Windows creates a 20 kB executable with 100k integers on the stack. Even with gratuitous overhead you're well within your specified range without any bit twiddling.

[baavgai]

kirtan, on 03 September 2010 - 10:14 AM, said:

Problem i have to solve is i have to store that much elements optimally so that it will have smallest memory foot print

An array would be the smallest memory footprint.

int data[100000];

Do you have code that isn't working? What's the error?

Edit: If you have 64KB, then you will have to break it up into multiple arrays, though an array is still the tightest block you're going to get. Because it's just that, a block of memory of elements * item_size.

This post has been edited by baavgai: 03 September 2010 - 09:46 AM

[kirtan]

Experts here is my program

I Tried vector too ..
but can any body tell which one is faster vector or array ?

int main()
{
    int n=0,q=0;
    int c=0,lb=0,ub=0;
    fscanf(stdin,"%d%d",&n,&q);
    int *x = new int[n+1];
    for(register int i=0;i<n;i+=7)
    {
      *(x+i) = 0;   
      *(x+i+1)=0;
      *(x+i+2)=0;
      *(x+i+3)=0;
      *(x+i+4)=0;
      *(x+i+5)=0;
      *(x+i+6)=0;
    }
    for(unsigned int i=0;i<q;i++)
    {
          fscanf(stdin,"%d%d%d",&c,&lb,&ub);
          int j;
          if(c==0)
          {
                    for(j=lb;j<=ub;j++)
                    {
                         *(x+j) = *(x+j)+1;
                    }     
          }
          else if(c==1)
          {
                    int count =0;
                    for(j=lb;j<=ub;j++)
                    {
                         if(*(x+j)%3==0)
                         count++;             
                    }
                   fprintf(stdout,"%d\n",count); 
          }   
    }
}

Here is My Code .I tried to optimize code as much as i can like
optimization of for loops , using registers

Any body have any idea about more improvement in this program because program speed should be 4 seconds for 100000 input .

[Salem_c]

So what do you type in to all those scanf calls?

How are we supposed to recreate YOUR test case?

> for(register int i=0;i<n;i+=7)
Your attempts at optimisation have introduced a bug. Unless n is also a multiple of 7, this loop rolls off the end of the array and trashes memory.

Is this your original complaint?

BTW, register is largely ignored by modern optimising compilers.
Maybe you should begin with

gcc -O2 myprog.c

> because program speed should be 4 seconds for 100000 input
a) says who?
what was their reference machine?

> fprintf(stdout,"%d\n",count);
What kind of 'time' - CPU time or wall-clock time?
I/O bound programs take a lot of wall-clock time compared to CPU time, because I/O is exceeding slow compared to RAM.

[kirtan]

Salem_c, on 03 September 2010 - 08:58 PM, said:

So what do you type in to all those scanf calls?

How are we supposed to recreate YOUR test case?

> for(register int i=0;i<n;i+=7)
Your attempts at optimisation have introduced a bug. Unless n is also a multiple of 7, this loop rolls off the end of the array and trashes memory.

Is this your original complaint?

BTW, register is largely ignored by modern optimising compilers.
Maybe you should begin with

gcc -O2 myprog.c

> because program speed should be 4 seconds for 100000 input
a) says who?
what was their reference machine?

> fprintf(stdout,"%d\n",count);
What kind of 'time' - CPU time or wall-clock time?
I/O bound programs take a lot of wall-clock time compared to CPU time, because I/O is exceeding slow compared to RAM.

My Problem of Storing Elements have been solved with vectors .. but i need performance of code now .

I use file as input to this program called in.txt I have attached with this Reply

and call program from cmd like

program.exe<in.txt

I have included 5000 input in file it should take less than a second to process all the input for that i want to improve performance of the program. Can i write the same code by any different way so that program become faster ?
Any Algorithmic way to speed up program ?

This program problem is from one of programming competition they require to process 100000 input same as i Provided in in.txt in 1-4 seconds. Is there any way that i can write the same program other way ??

Attached File(s)

•  in.txt (43.95K)
  Number of downloads: 139

This post has been edited by kirtan: 04 September 2010 - 03:07 AM

[CasGrimes]

From my knowledge, vectors are the most efficient option when continually accessing the last element (in your case an int).
But if you are randomally accessing ints then a list is MUCH MUCH more efficient than any other container as it was optimised for that purpose.

[kirtan]

CasGrimes, on 04 September 2010 - 02:03 AM, said:

From my knowledge, vectors are the most efficient option when continually accessing the last element (in your case an int).
But if you are randomally accessing ints then a list is MUCH MUCH more efficient than any other container as it was optimised for that purpose.

Thanks for supporting me all of you

list dont have any method so that i can access element randomly as lists are accessed sequentially it will be slower that array.

i have to do something with below code in my program if any one have any optional way to perform below logic then tell me .

in my code below code is critical for performance as it contain nesting of loops that can take more time than other code around ..

for(unsigned int i=0;i<q;i++)
    {
          fscanf(stdin,"%d%d%d",&c,&lb,&ub);
          int j;
          if(c==0)
          {
                    for(j=lb;j<=ub;j++)
                    {
                         *(x+j) = *(x+j)+1;
                    }     
          }
          else if(c==1)
          {
                    int count =0;
                    for(j=lb;j<=ub;j++)
                    {
                         if(*(x+j)%3==0)
                         count++;             
                    }
                   fprintf(stdout,"%d\n",count); 
          }   
}

[janotte]

Have a read here
http://www.cplusplus...rence/stl/list/
here
http://www.cplusplus...nce/stl/vector/
and here
http://www.cplusplus.../reference/stl/

Why are you writing in that strange mix of C and C++?
Choose a language and stick with it.
Just because C++ can handle C doesn't mean you should be doing it.

[Salem_c]

> Any Algorithmic way to speed up program ?
Perhaps you should state the problem, not your solution.

It's like this. The problem states 'sort' numbers, and then you show up with a bubble sort and ask how to optimise it.

Now most experienced people can spot a bubble sort implementation a mile off, and can easily come up with something different that just wipes the floor with bubble sort.

So, back to your code. If we knew what it is that you're trying to do, then an alternative approach might be evident.


But FWIW, I think you may be digging in the wrong place.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n=0,q=0;
    int c=0,lb=0,ub=0;
    fscanf(stdin,"%d%d",&n,&q);
    int *x = malloc((n+1)*sizeof *x);
    for(int i=0;i<n+1;i++)
    {
      x[i] = 0;
    }
    lb=0;
    ub=q;
    c=0;
    for(int i=0;i<q;i++)
    {
          //fscanf(stdin,"%d%d%d",&c,&lb,&ub);
          int j;
          if(c==0)
          {
                    for(j=lb;j<=ub;j++)
                    {
                         *(x+j) = *(x+j)+1;
                    }
          }
          else if(c==1)
          {
                    int count =0;
                    for(j=lb;j<=ub;j++)
                    {
                         if(*(x+j)%3==0)
                         count++;
                    }
                   //fprintf(stdout,"%d\n",count);
          }
          c ^= 1;
    }
    return 0;
}

I changed your data file to read
50000 50000
1 0 50000
0 0 50000

just to get some decent times out of it.

Here are some results

# No fancy stuff, just compiled
$ gcc -std=c99 foo.c
$ time ./a.out < in.txt > results.txt

real	0m20.340s
user	0m20.313s
sys	0m0.020s

# Enable optimisation
$ gcc -std=c99 -O2 foo.c
$ time ./a.out < in.txt > results.txt

real	0m6.609s
user	0m6.600s
sys	0m0.008s

# Suppress all loop I/O
$ gcc -std=c99 -O2 foo.c
$ time ./a.out < in.txt > results.txt

real	0m2.093s
user	0m2.080s
sys	0m0.004s

The "c ^= 1;" toggles c between 0 and 1, so it's simulating what would be read from the file.

Turning on O2 takes out a big chunk of time
Disabling all loop bound I/O takes out another big chunk of time.

If you want something to work on, focus on the expensive I/O operations.

Messing around with 'register' and manual loop unrolling isn't where it's at any more.

[kirtan]

Thanks Salem Thanks for giving your valuable time to help me solve my problem

Here is What this code does actually its not doing any kind of sorting
my input file contain lines of instructions like
if input is below

input
-------
4 7
1 0 3
0 1 2
0 1 3
1 0 0
0 0 3
1 3 3
1 0 3

output will be
-------
4
1
0
2

here 4 in first input line is total number of elements in array which is initially all 0 and 7 tell that next 7 lines represent the code like 0 A B and 1 A B where A and B are lower bound and upper bounds of array

if instruction in input is 0 A B then we need to increment value of elements by 1 between indices A and B
if instruction in input is 1 A B then we need to find how many numbers are divisible by 3 between A and B Indices

that is what problem definition .

1 <= N <= 100000 (n = 4 in sample input here in example i given )
1 <= Q <= 100000 ( q == 7 here in sample input)
0 <= A <= B <= N - 1

total run time of program should be 1-4 second.
Hope you are clear with my problem now

[baavgai]

This looked amusing. I started out with your initial setup and used an object for the data store:

#include <cstdio>

struct Data {
	const int size;
	int *storage;
	Data(int n) : size(n) { 
		storage = new int[size];
		for(int i=0; i<size; i++) { storage[i] = 0; }
	}
	~Data() { delete [] storage; }
	
	
	void incValue(int startIndex, int endIndex) {
		for(int i=startIndex; i<=endIndex; i++) { 
			storage[i]++;
		}
	}

	int getModCount(int startIndex, int endIndex) {
		int count = 0;
		for(int i=startIndex; i<=endIndex; i++) { 
			if(storage[i]%3==0) { count++; }
		}
		return count;
	}
	
};

void cStyleProcess(FILE *fIn, FILE *fOut) {
	int n=0,q=0;
	
	fscanf(fIn,"%d%d",&n,&q);
	
	Data data(n+1);
	
	for(unsigned int i=0;i<q;i++)  {
		int c=0,lb=0,ub=0;
		fscanf(fIn,"%d%d%d",&c,&lb,&ub);
		if(c==0) { 
			data.incValue(lb, ub);
		} else if(c==1) {
			fprintf(fOut,"%d\n", data.getModCount(lb, ub)); 
		}   
	}
}

int main() {
	FILE *fh;
	if ((fh = fopen ("in.txt","r"))!=NULL) {
		cStyleProcess(fh, stdout);
		fclose (fh);
	}
	return 0;
}

I then decided it wanted to be a little more C++. I also wanted to clean it up a little more:

#include <iostream>
#include <fstream>

using namespace std;

struct Data {
	const int size;
	int *storage;
	Data(int n) : size(n) { 
		storage = new int[size];
		for(int i=0; i<size; i++) { storage[i] = 0; }
	}
	~Data() { delete [] storage; }
	
	
	void incValue(int startIndex, int endIndex) {
		for(int i=startIndex; i<=endIndex; i++) { 
			storage[i]++;
		}
	}

	int getModCount(int startIndex, int endIndex) {
		int count = 0;
		for(int i=startIndex; i<=endIndex; i++) { 
			if(storage[i]%3==0) { count++; }
		}
		return count;
	}
	
};


void process(istream &in, ostream &out) {
	int n=0,q=0;
	in >> n >> q;
	
	Data data(n+1);
	
	while(q-- > 0) {
		int commandType, startIndex, endIndex;
		in >> commandType >> startIndex >> endIndex;
		if(commandType==0) { 
			data.incValue(startIndex, endIndex);
		} else if(commandType==1) {
			out << data.getModCount(startIndex, endIndex) << endl;
		}   
	}
}


int main() {
	ifstream fs("in.txt");
	if (fs.good()) {
		process(fs, cout);
		fs.close();
	}
	return 0;
}

Now that I had the logic isolated, I could play with the storage structure. Actually, I only need to store three values, don't I? I just need to apply the mod early. Let's try char:

struct Data {
	const int size;
	char *storage;
	Data(int n) : size(n) { 
		storage = new char[size];
		for(int i=0; i<size; i++) { storage[i] = 0; }
	}
	~Data() { delete [] storage; }
	
	
	void incValue(int startIndex, int endIndex) {
		for(int i=startIndex; i<=endIndex; i++) { 
			storage[i] = (storage[i]+1) % 3;
		}
	}

	int getModCount(int startIndex, int endIndex) {
		int count = 0;
		for(int i=startIndex; i<=endIndex; i++) { 
			if(storage[i]==0) { count++; }
		}
		return count;
	}
	
};

Now it's half the size. We could get it smaller still, if you're willing to play with bits. The computational overhead might be prohibative. I'll leave that as an exercise for the reader.