help me to optimizing speed

**Artie Gold** · Jul 19 '05, 08:08 PM

Re: help me to optimizing speed

ArShAm wrote:[color=blue]
> Hi there
> Please help me to optimize this code for speed[/color]

OK.

The following information is off-topic here:
<OT>[color=blue]
> I added /O2 to compiler settings
> I added /Oe to compiler settings for accepting register type request , but
> it seems that is not allowed and if I remove register type for "l" , time of
> generating codes doesn't change
>
> the original code makes some files , but I removed that section to make it
> simple for you to read
> please help me to optimize it for faster running
> my system is Windows XP , 512 Mb ram , 1.6 Intel[/color]
<OT>
[color=blue]
> Code is here :
>
>
> #include "stdio.h"[/color]
#include <stdio.h>
[color=blue]
> #include "stdlib.h"[/color]
#include <stdlib.h>
[color=blue]
> #include "string.h"[/color]
#include <string.h>
[color=blue]
>
> const int NUM=7;//number of characters in each word
> const int total=20000000;//total generation
> char q[total][NUM+1];// the table
>
> void main(void)[/color]
int main(void) // main() returns int...main() returns int...
[color=blue]
> {
> int NUMBERS=26;//size of al array
> char al[]="abcdefghijklm nopqrstuvwxyz"; //array to generate a random code
> register int l;//my windows XP doesn't respect this request
>
> for(int i=1;i<total;i++ )
> {
> for(int j=0;j<NUM;j++)
> {
> q[i][j]=al[rand()%NUMBERS];//generating each password
> }
>
> for(l=0;l<i;l++ )//comparing if it is unique or not
> {
> if(!strcmp(q[i],q[l]))
> {
> printf(" %d was equal to %d with %s:%s value\n",i,l,q[i],q[l]);
> i--;
> break;
> }
> }
> if(i%10000==0)p rintf("%d\n",i/10000);//each 10,000 times shows that the
> program is runing
> //printf("%s\n",q[i]);
> }
> printf("\r\nDON E");
> getchar();
> }
>
>[/color]
Micro-optimization -- or even compiler optimization -- is *not*
going to help you here. You've got an O(n-squared) algorithm where
an O(n log n) algorithm would be more appropriate.

Consider using a std::set.

HTH,
--ag

--
Artie Gold -- Austin, Texas
Oh, for the good old days of regular old SPAM.

**Victor Bazarov** · Jul 19 '05, 08:08 PM

Re: help me to optimizing speed

"ArShAm" <arshamshirvani @hotmail.com> wrote...[color=blue]
> Hi there
> Please help me to optimize this code for speed
> I added /O2 to compiler settings
> I added /Oe to compiler settings for accepting register type request , but
> it seems that is not allowed and if I remove register type for "l" , time[/color]
of[color=blue]
> generating codes doesn't change
>
> the original code makes some files , but I removed that section to make it
> simple for you to read
> please help me to optimize it for faster running
> my system is Windows XP , 512 Mb ram , 1.6 Intel
> Regards
> ArShAm
>
> Code is here :
> [...][/color]

Instead of comparing each word with all others, sort them and then
run through the sorted array and see if any neighbours are equal.

Victor

**Jerry Coffin** · Jul 19 '05, 08:08 PM

Re: help me to optimizing speed

In article <bomtf7$1evmsk$ 1@ID-89294.news.uni-berlin.de>,
arshamshirvani@ hotmail.com says...[color=blue]
> Hi there
> Please help me to optimize this code for speed
> I added /O2 to compiler settings
> I added /Oe to compiler settings for accepting register type request , but
> it seems that is not allowed and if I remove register type for "l" , time of
> generating codes doesn't change[/color]

That almost certainly means that the compiler is putting your variable
in a register automatically -- in fact, for most practical purposes, the
register keyword is obsolete.
[color=blue]
> please help me to optimize it for faster running[/color]

As usual, the key to optimizing the code is not microscopic details like
whether a variable ends up in a register, but in improving the
algorithms and/or data structures involved.
[color=blue]
> #include "stdio.h"
> #include "stdlib.h"
> #include "string.h"[/color]

These should really be enclosed in angle brackets instead of quotes
(though changing that is extremely unlikely to change the speed at all
-- and if it does, you're doing other things you really shouldn't (like
creating headers of your own with the same names as those supplied by
the system).
[color=blue]
> const int NUM=7;//number of characters in each word
> const int total=20000000;//total generation
> char q[total][NUM+1];// the table
>
> void main(void)[/color]

main always returns an int. Again, this won't really affect the speed,
but it's something you should do anyway.
[color=blue]
> register int l;//my windows XP doesn't respect this request[/color]

XP, as such, has nothing to do with it one way or the other -- it's the
compiler, not the OS, that decides what goes into registers. In any
case, you probably have things backwards -- it isn't that it's ignoring
your request to put this in a register. Rather, it's putting it in a
register automatically, whether you ask for it or not.
[color=blue]
> for(int i=1;i<total;i++ )
> {
> for(int j=0;j<NUM;j++)
> {
> q[i][j]=al[rand()%NUMBERS];//generating each password
> }
>
> for(l=0;l<i;l++ )//comparing if it is unique or not[/color]

Here's where your real problem arises -- verifying uniqueness with a
linear search renders your overall algorithm O(N^2). Keeping the
strings sorted and doing a binary search will reduce this to O(N lg N)
instead -- a massive improvement when you're dealing with 20 million
items (see below for just how massive it really is).

In this case (creating 20 million _small_ strings) it's probably worth
using our own little string-like class instead of the full-blown
std::string, if only to save memory. Using std::map and my own pwd
class, I came up with this:

#include <set>
#include <string>
#include <cstdlib>
#include <iostream>
#include <ctime>

const int total = 20000000;

class pwd {
const static int NUM = 7;
const static int NUMBERS = 26;
char data[NUM];

public:
// generate a random string.
pwd() {
static char letters[] = "abcdefghijklmn opqrstuvwxyz";

for (int i=0; i< NUM; i++)
data[i] = letters[std::rand() % NUMBERS];
}

// std::set requires ability to compare items.
bool operator<(pwd const &other) const {
return -1 == strncmp(data, other.data, NUM);
}

// support writing a pwd to a stream.
friend std::ostream &operator<<(std ::ostream &os, pwd const &p) {
return os.write(p.data , pwd::NUM);
}
};

int main() {
std::set<pwd> passwords;

std::srand(std: :time(NULL));

std::clock_t start = clock();
for (unsigned long size=0; size<total; size++) {
if ( passwords.inser t(pwd()).second )
size++;
if ( size % 10000 == 0)
std::cout << '\r' << size << std::flush;
}

std::clock_t end = clock();

std::cout << "\nTime: " << double(end-start)/CLOCKS_PER_SEC
<< "seconds\n" ;

// show first and last passwords, so the optimizer won't eliminate
// the loop above.
std::cout << *passwords.begi n() << std::endl;
std::cout << *--passwords.end() << std::endl;

#if 0
std::copy(passw ords.begin(),
passwords.end() ,
std::ostream_it erator<pwd>(std ::cout, "\n"));
#endif
return 0;
}

I modified your program slightly, so it would only produce 90 thousand
strings. I compiled that program with MS VC++ 7.1, using:
cl /Oxb2 /G6ry pwds1.cpp
and it ran in 56.4 seconds on my machine. Extrapolating from that, based
on an O(N^2) complexity, I estimate it would take around a month for
your program to produce all 20 million passwords.

Compiled the same way and run on the same machine, the code above
produces 20 million strings in about 58 seconds (i.e. 20 million strings
_almost_ as fast as you were getting 90 thousand).

A micro-optimization (like register) will rarely give an improvement
more than a few percent. If the compiler really screws up and you
manage to enregister something inside of a really tight loop, you might,
concievably get an improvement of, say, 50:1, but that's _extremely_
rare (I don't think I've ever seen it). By contrast, this algorithmic
improvement gave an improvement of around fifty _thousand_ to 1, with
only minimal investment... :-)

--
Later,
Jerry.

The universe is a figment of its own imagination.

**ArShAm** · Jul 19 '05, 08:08 PM

Re: help me to optimizing speed

Thanks Dear Jerry,
It was gr8
before I recieve your answer I tried to change my generation code , and I
think that will be much better
but there is a problem , and that is the program crashes with a huge number
for total

here is the code:

#include "stdio.h"
#include "time.h"
#include "stdlib.h"
#include "string.h"
#include "myqueue.h"
#include <sys/timeb.h>

const int NUM=10;
char element[NUM];
int a[NUM]={0};
char al[]="ABCDEFGHIJKLM NOPQRSTUVWXYZ";
int size;

void main(void)
{
const int total=1000000;
size=sizeof(al)-2;
void gen(void);

myQueue* table[total];

for(int r=0;r<NUM;r++)
element[r]='A';
for(int l=0;l<total;l++ )
{
gen();
table[l]=new myQueue();
strcpy(table[l]->element,elemen t);
}

srand( (unsigned)time( NULL ) );
int tot=total;

FILE *file;
file=fopen("rep ort.pin","w");

int Sorted[total],shuffled[total];
int i3, j3;

for ( i3 = 0; i3 < total; i3++ ) Sorted[i3] = i3;

for ( i3 = 0; i3 < total; i3++ )
{
j3 = rand() % (total-i3);
shuffled[i3] = Sorted[j3];

Sorted[j3] = Sorted [ total-1-i3 ];
}

for(register int i=0;i<total;i++ )
{
fprintf(file,"% 06d:%s\n",i,tab le[shuffled[i]]->element);
}

fclose(file);

printf("Done\n" );
exit(0);
}

void gen(void)
{
a[0]++;
for(int k=0;k<NUM;k++)
{
if(a[k]>size)
{
a[k]=0;
a[k+1]++;
}
}

for(int y=0;y<NUM;y++)
{
element[y]=al[a[y]];
}
}

//and the myQueue class :
const int NUM1=10;
class myQueue
{
public:
char element[NUM1];
myQueue();
virtual ~myQueue();

myQueue(){
strcpy(element, "");}
~myQueue(){}

};

Thank you for your help
Regards
ArShAm

**Thomas Matthews** · Jul 19 '05, 08:09 PM

Re: help me to optimizing speed

ArShAm wrote:
[color=blue]
> Thanks Dear Jerry,
> It was gr8
> before I recieve your answer I tried to change my generation code , and I
> think that will be much better
> but there is a problem , and that is the program crashes with a huge number
> for total
>
> here is the code:
>
> #include "stdio.h"
> #include "time.h"
> #include "stdlib.h"
> #include "string.h"
> #include "myqueue.h"
> #include <sys/timeb.h>[/color]

I really don't understand.
Why are the standard header files using '"'
excepth the last one? Be consistent and use
angle brackets '<' and '>' instead of quotes (").

[color=blue]
> const int NUM=10;
> char element[NUM];
> int a[NUM]={0};
> char al[]="ABCDEFGHIJKLM NOPQRSTUVWXYZ";
> int size;
>
> void main(void)[/color]

Hmmm. How many people have told you that main()
returns int?
Make the change.
[color=blue]
> {
> const int total=1000000;
> size=sizeof(al)-2;[/color]
Why the "-2"?
I could understand a "-1" because of the terminating
nul character, but why "-2". some comments would
really help.

[color=blue]
> void gen(void);[/color]
Better naming would help too.
What does this function do?

[color=blue]
> myQueue* table[total];[/color]
The declaration for this class should be before
its usage.
Why do you need 10,000,000 pointers to queues?
So far, this is a memory hog program. See below.

[color=blue]
> for(int r=0;r<NUM;r++)
> element[r]='A';[/color]
Prefer library routines:
memset(element, 'A', sizeof(element) );
or
std::fill(eleme nt, element + num, 'A');
they may be optimized for your processor, where
a simple "for" loop isn't.

[color=blue]
> for(int l=0;l<total;l++ )
> {
> gen();
> table[l]=new myQueue();
> strcpy(table[l]->element,elemen t);[/color]
In order for strcpy to work, there must be a
terminating nul ('\0') character within the
string.
I didn't see any terminating null placed in the
"element" array. The strcpy() function is probably
the cause of your crash. It will copy until it
_finds_ a nul character or it accesses undefined or
protected memory.
I think you want:
memcpy(table[l]->element, element, sizeof(element) );
or
std::copy(eleme nt, element + NUM, table[i]->element);
[color=blue]
> }[/color]

At this point, you have allocated:
10,000,000 pointers to myQueue objects
10,000,000 myQueue objects.
Insert these statements into your code:
cout << "current memory allocation: "
<< total * (sizeof (myQueue *) + sizeof(myQueue) )
<< "\n";

[color=blue]
> srand( (unsigned)time( NULL ) );[/color]
Search the C FAQ and the C++ FAQ and the C language
newsgroup (news:comp.lang .c) about random numbers.
You'll find some interesting information.

[color=blue]
> int tot=total;
>
> FILE *file;
> file=fopen("rep ort.pin","w");[/color]
Are you programming in C or C++?
ostream file("report.pi n");

[color=blue]
>
> int Sorted[total],shuffled[total];[/color]
Memory Hog!
At this point, you have asked the compiler to allocate
20,000,000 integers in the "automatic" area (a.k.a stack).

Add these lines to your code:
cout << "Automatic variable allocation: "
<< 2 * total * sizeof(int)
<< "\n";

[color=blue]
> int i3, j3;
>
> for ( i3 = 0; i3 < total; i3++ ) Sorted[i3] = i3;
>
> for ( i3 = 0; i3 < total; i3++ )
> {
> j3 = rand() % (total-i3);
> shuffled[i3] = Sorted[j3];
>
> Sorted[j3] = Sorted [ total-1-i3 ];
> }[/color]
I believe you would do better to use the shuffle algorithm
of the STL.

[color=blue]
> for(register int i=0;i<total;i++ )
> {
> fprintf(file,"% 06d:%s\n",i,tab le[shuffled[i]]->element);
> }[/color]
Here is a big waste of time. Don't bother with register
variables. Formatted output requires a lot of time, so
making the index variable as a register will not save any
significant time.

[color=blue]
> fclose(file);
>
> printf("Done\n" );
> exit(0);
> }
>
> void gen(void)
> {
> a[0]++;
> for(int k=0;k<NUM;k++)
> {
> if(a[k]>size)
> {
> a[k]=0;
> a[k+1]++;
> }
> }
>
> for(int y=0;y<NUM;y++)
> {
> element[y]=al[a[y]];
> }
> }[/color]
The above should not modify global variables. This poses
a hindrance when reading the code. Pass pointers to the
variables that will be modified. Also, use comments to
explain what this function is doing.

[color=blue]
> //and the myQueue class :
> const int NUM1=10;
> class myQueue
> {
> public:
> char element[NUM1];
> myQueue();
> virtual ~myQueue();
>
> myQueue(){
> strcpy(element, "");}
> ~myQueue(){}
>
> };[/color]
What is the purpose of this class?
It doesn't look like a queue container.

[color=blue]
> Thank you for your help
> Regards
> ArShAm
>
>[/color]

You could gain a lot of speed by replacing the "myQueue"
class with a fixed size vector or array. The class
provides no useful functionality, so remove it.

Also, why do you need to store 10,000,000 random strings
of 10 characters in length to a file. Your file will be
a minimum of 10,000,000 * 10 bytes long or 100MB.

If you're looking to write a program that generates
possible passwords, a more successful approach is to
use common names, then common words. After those fail,
then generate the random list.

--
Thomas Matthews

C++ newsgroup welcome message:

404 Not Found

http://www.slack.net/~shiva/welcome.txt

C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.l earn.c-c++ faq:

http://www.raos.demon.uk/acllc-c++/faq.html

Other sites:
http://www.josuttis.com -- C++ STL Library book