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.
