473,403 Members | 2,284 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,403 software developers and data experts.

help me to optimizing speed

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

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 :
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

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)
{
int NUMBERS=26;//size of al array
char al[]="abcdefghijklmnopqrstuvwxyz"; //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)printf("%d\n",i/10000);//each 10,000 times shows that the
program is runing
//printf("%s\n",q[i]);
}
printf("\r\nDONE");
getchar();
}
Jul 19 '05 #1
5 3508
ArShAm wrote:
Hi there
Please help me to optimize this code for speed
OK.
The following information is off-topic here:
<OT> 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 <OT>
Code is here :
#include "stdio.h" #include <stdio.h>
#include "stdlib.h" #include <stdlib.h>
#include "string.h" #include <string.h>

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) int main(void) // main() returns int...main() returns int...
{
int NUMBERS=26;//size of al array
char al[]="abcdefghijklmnopqrstuvwxyz"; //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)printf("%d\n",i/10000);//each 10,000 times shows that the
program is runing
//printf("%s\n",q[i]);
}
printf("\r\nDONE");
getchar();
}

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.

Jul 19 '05 #2
"ArShAm" <ar************@hotmail.com> wrote...
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

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 :
[...]


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
Jul 19 '05 #3
In article <bo*************@ID-89294.news.uni-berlin.de>,
ar************@hotmail.com says...
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
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.
please help me to optimize it for faster running
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.
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
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).
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)
main always returns an int. Again, this won't really affect the speed,
but it's something you should do anyway.
register int l;//my windows XP doesn't respect this request
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.
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


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[] = "abcdefghijklmnopqrstuvwxyz";

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.insert(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.begin() << std::endl;
std::cout << *--passwords.end() << std::endl;

#if 0
std::copy(passwords.begin(),
passwords.end(),
std::ostream_iterator<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.
Jul 19 '05 #4
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[]="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
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,element);
}

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

FILE *file;
file=fopen("report.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,table[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
Jul 19 '05 #5
ArShAm wrote:
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>
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 (").

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

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

void gen(void); Better naming would help too.
What does this function do?

myQueue* table[total]; 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.

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

for(int l=0;l<total;l++)
{
gen();
table[l]=new myQueue();
strcpy(table[l]->element,element); 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(element, element + NUM, table[i]->element);
}
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";
srand( (unsigned)time( NULL ) ); 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.

int tot=total;

FILE *file;
file=fopen("report.pin","w"); Are you programming in C or C++?
ostream file("report.pin");


int Sorted[total],shuffled[total]; 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";

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 ];
} I believe you would do better to use the shuffle algorithm
of the STL.

for(register int i=0;i<total;i++)
{
fprintf(file,"%06d:%s\n",i,table[shuffled[i]]->element);
} 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.
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]];
}
} 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.

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

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

}; What is the purpose of this class?
It doesn't look like a queue container.

Thank you for your help
Regards
ArShAm


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:
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.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

Jul 19 '05 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

6
by: A Future Computer Scientist | last post by:
A question: Is it really important to think about optimizing the native code or optimizing it for P Code? Or does the code you write make a difference?
13
by: Nickolay Kolev | last post by:
Hi all, I am currently writing some simple functions in the process of learning Python. I have a task where the program has to read in a text file and display some statistics about the tokens in...
2
by: m3ckon | last post by:
Hi there, had to rush some sql and am now going back to it due to a slow db performance. I have a db for sales leads and have created 3 views based on the data I need to produce. However one...
7
by: Arnold | last post by:
I need to read a binary file and store it into a buffer in memory (system has large amount of RAM, 2GB+) then pass it to a function. The function accepts input as 32 bit unsigned longs (DWORD). I...
4
by: J. Campbell | last post by:
From reading this forum, it is my understanding that C++ doesn't require the compiler to keep code that does not manifest itself in any way to the user. For example, in the following: { for(int...
3
by: PWalker | last post by:
Hi, I have written code that I would like to optimize. I need to push it to the limit interms of speed as the accuracy of results are proportional to runtime. First off, would anyone know any...
31
by: mark | last post by:
Hello- i am trying to make the function addbitwise more efficient. the code below takes an array of binary numbers (of size 5) and performs bitwise addition. it looks ugly and it is not elegant...
24
by: Richard G. Riley | last post by:
Without resorting to asm chunks I'm working on a few small routines which manipulate bitmasks. I'm looking for any guidance on writing C in a manner which tilts the compilers hand in, if possible,...
4
by: RS | last post by:
Hi all, I was told that using unsigned int instead of int can speed up the code. Is this true? If so, why? Are there are any other rules one should follow to optimize the code for speed (i.e....
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: emmanuelkatto | last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud. Please let me know. Thanks! Emmanuel
1
by: Sonnysonu | last post by:
This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
0
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
0
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers,...
0
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
0
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.