any suggestion to improve the following code?

[Fei Liu]

Hello, the following code is an implementation computing the 3n+1
problem, specifically maximum number of steps to complete for any
integer range. The algorithm aims to be as efficient/fast as possible.

One thing I am unsatisfied of is the use of hash_map (deprecated but
supported by most C++ vendors). Is there a portable hash map
implementation? I am tempted to use unordered_map with boost::hash. I
didn't use std::map because std::map lookup/insertion is O(lgN) while
hash map is O(1). What's your opinion? Comments about style etc are
welcome as well regarding other aspects of my implementation.

Fei

#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

#include <ext/hash_map>
using namespace __gnu_cxx;

#include <boost/filesystem/convenience.hpp>

hash_map<unsigned int, unsigned int, hash<unsigned int> > steps;

// Computes number of steps for number n according
// to Collatz Conjecture (3n+1 problem)
// http://en.wikipedia.org/wiki/Collatz_conjecture
//
// To speed things up, results are book kept, saved/restored
// when program starts/finishes.
//
// In the recursively computing function, the steps to finish a
// a number is always memorized and retrieved on demand.
unsigned int compute_steps(int n){
// shortcut to retrieve memorized steps[n]
if(steps[n])
return steps[n];
if(n == 1) return 1;
if(n%2)
n = 3*n+1;
else
n = n/2;
cout << ' ' << n;
// shortcut to memorize steps[n]
steps[n] = compute_steps(n);
return steps[n] + 1;
}

int main(){
boost::filesystem:ath file("record_h.txt");

unsigned int two[2];
if(exists(file)){
ifstream inf("record_h.txt", ios::binary);
while(inf.read((char *)two, 2*sizeof(unsigned int)))
steps[two[0]] = two[1];
inf.close();
}

int i, j;
// It's not as easy as it seems to safely read integers from cin
// The following trick makes sure a pair of integers are read in safely
while(!(cin >> i >> j)) {
cout << i << ' ' << j << endl;
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
}
assert(i != 0 && j >= i);

// compute steps for each l between i and l and prints its value
for(int l = i; l <= j; l ++){
cout << l << ": ";
steps[l] = compute_steps(l);
cout << '\n';
}

// compute some statitics of the result, the largest number n
steps[n] is computed
// the number of 0s from steps to steps+rbegin

unsigned int max_step = 0;
ofstream ofs("record_h.txt", ios::binary);

::const_iterator it = steps.begin();

while(it != steps.end()){
two[0] = it->first;
two[1] = it->second;
max_step = (max_step > it->second) ? max_step : it->second;
ofs.write((const char *)two, 2*sizeof(unsigned int));
++it;
}
ofs.close();
cout << "maximum step: " << i << ' ' << j << ' ' << max_step << '\n';
}

 

[Barry]

#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

#include <ext/hash_map>
using namespace __gnu_cxx;

#include <boost/filesystem/convenience.hpp>

hash_map<unsigned int, unsigned int, hash<unsigned int> > steps;

// Computes number of steps for number n according
// to Collatz Conjecture (3n+1 problem)
// http://en.wikipedia.org/wiki/Collatz_conjecture
//
// To speed things up, results are book kept, saved/restored
// when program starts/finishes.
//
// In the recursively computing function, the steps to finish a
// a number is always memorized and retrieved on demand.
unsigned int compute_steps(int n){
// shortcut to retrieve memorized steps[n]
if(steps[n])
return steps[n];
if(n == 1) return 1;
if(n%2)
n = 3*n+1;
else
n = n/2;
cout << ' ' << n;
// shortcut to memorize steps[n]
steps[n] = compute_steps(n);
return steps[n] + 1;
}

int main(){
boost::filesystem:ath file("record_h.txt");

unsigned int two[2];
if(exists(file)){
ifstream inf("record_h.txt", ios::binary);
while(inf.read((char *)two, 2*sizeof(unsigned int)))
steps[two[0]] = two[1];
inf.close();

no need to call fstream::close explictly.
the destructor will handle this well.

}

using Boost.FileSystem here just to detect a file exists or not may be
overkill, and after knowing that the file does exist, you can't
guarantee that th opening of the file will be successful.

so just

std::string const file_path = "record_h.txt";
std::ifstream inf(file_path, ios_base::binary);
if (!inf)
{
// report fail
return EXIT_FAILURE;
}
else
{
// read the file
}

 

[Daniel T.]

Hello, the following code is an implementation computing the 3n+1
problem, specifically maximum number of steps to complete for any
integer range. The algorithm aims to be as efficient/fast as possible.

It would probably be faster if it wasn't recursive.

One thing I am unsatisfied of is the use of hash_map (deprecated but
supported by most C++ vendors). Is there a portable hash map
implementation? I am tempted to use unordered_map with boost::hash. I
didn't use std::map because std::map lookup/insertion is O(lgN) while
hash map is O(1). What's your opinion?

Comments about style etc are
welcome as well regarding other aspects of my implementation.

Fei

#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

#include <ext/hash_map>
using namespace __gnu_cxx;

#include <boost/filesystem/convenience.hpp>

hash_map<unsigned int, unsigned int, hash<unsigned int> > steps;

// Computes number of steps for number n according
// to Collatz Conjecture (3n+1 problem)
// http://en.wikipedia.org/wiki/Collatz_conjecture
//
// To speed things up, results are book kept, saved/restored
// when program starts/finishes.
//
// In the recursively computing function, the steps to finish a
// a number is always memorized and retrieved on demand.
unsigned int compute_steps(int n){
// shortcut to retrieve memorized steps[n]
if(steps[n])
return steps[n];

The above forces an insert even if the value doesn't currently exist in
the map. Instead use find.

if(n == 1) return 1;
if(n%2)
n = 3*n+1;
else
n = n/2;
cout << ' ' << n;
// shortcut to memorize steps[n]
steps[n] = compute_steps(n);
return steps[n] + 1;
}

int main(){
boost::filesystem:ath file("record_h.txt");

unsigned int two[2];
if(exists(file)){
ifstream inf("record_h.txt", ios::binary);
while(inf.read((char *)two, 2*sizeof(unsigned int)))
steps[two[0]] = two[1];
inf.close();
}

int i, j;
// It's not as easy as it seems to safely read integers from cin
// The following trick makes sure a pair of integers are read in safely
while(!(cin >> i >> j)) {
cout << i << ' ' << j << endl;
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
}
assert(i != 0 && j >= i);

// compute steps for each l between i and l and prints its value
for(int l = i; l <= j; l ++){
cout << l << ": ";
steps[l] = compute_steps(l);
cout << '\n';
}

// compute some statitics of the result, the largest number n
steps[n] is computed
// the number of 0s from steps to steps+rbegin

unsigned int max_step = 0;
ofstream ofs("record_h.txt", ios::binary);

::const_iterator it = steps.begin();

while(it != steps.end()){
two[0] = it->first;
two[1] = it->second;
max_step = (max_step > it->second) ? max_step : it->second;
ofs.write((const char *)two, 2*sizeof(unsigned int));
++it;
}
ofs.close();
cout << "maximum step: " << i << ' ' << j << ' ' << max_step << '\n';
}

 

[James Kanze]

Hello, the following code is an implementation computing the 3n+1
problem, specifically maximum number of steps to complete for any
integer range. The algorithm aims to be as efficient/fast as possible.

One thing I am unsatisfied of is the use of hash_map (deprecated but
supported by most C++ vendors).

Not deprecated; there was never a "standard" hash_map. And
while most C++ compilers do support some sort of hash table,
there are subtle differences between them.

The next version of the standard will contain an
std::unsorded_map, but until then, you're on your own, at least
if you want to be portable.

Is there a portable hash map implementation?

It's not hard to write. (There's one at my site, for example.)

I am tempted to use unordered_map with boost::hash.

unordered_map is presumably an implementation of the draft
standard, and definitly to be preferred if it is available.

I didn't use std::map because std::map lookup/insertion is
O(lgN) while hash map is O(1). What's your opinion?

How many elements? I've found that for up to a thousand or so,
it really doesn't matter.

Note too that the complexity of a hash map depends on the
quality of the hashing function. Use a bad hashing function,
and it rapidly becomes O(n).

Comments about style etc are welcome as well regarding other
aspects of my implementation.

#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

#include <ext/hash_map>
using namespace __gnu_cxx;

Personally, I don't like the "using namespace". I'd generally
write std:: wherever needed (and alias __gnu_cxx to something
like gcc). And I definitly wouldn't use a "using namespace"
until after all of the include files have been processed.

#include <boost/filesystem/convenience.hpp>

I'm not familiar with the algorithm, so I'll skip that part.
[...]

int main(){
boost::filesystem:ath file("record_h.txt");

unsigned int two[2];
if(exists(file)){
ifstream inf("record_h.txt", ios::binary);
while(inf.read((char *)two, 2*sizeof(unsigned int)))
steps[two[0]] = two[1];
inf.close();
}

The above seems a bit heavy. What's wrong with just:

std::ifstream inf( "record_h.txt" ) ;
if ( inf ) {
// read file...
}

Note that the way you read the file in your loop is a recepe for
problems---recompile the code with different options or a
different version of the compiler, and you may read different
values than you wrote. The simplest solution would be to define
a text format for the data, and read and write it as text. This
will also simplify debugging enormously. If you do want to use
a raw memory image (which is probably acceptable since you
haven't lost anything critical if you can't read it), then
prefix it with some sort of signature, which is regenerated
(differently) every time you relink your code.

And of course, you really want this part in a separate function.
Or even a separate class, which encapsulates all of your file
cache management. (If you read and write in the same class,
then it's easy to modify the file format.)

int i, j;
// It's not as easy as it seems to safely read integers from cin
// The following trick makes sure a pair of integers are read in safely
while(!(cin >> i >> j)) {
cout << i << ' ' << j << endl;
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
}
assert(i != 0 && j >= i);

I'm not sure what your trying to do here. If you only need two
integers, and you always need two integers, wouldn't it be more
appropriate to pick them up from the command line. Something
like:

int
asInt( char const* arg )
{
int result ;
std::istringstream tmp( arg ) ;
tmp >> result >> std::ws ;
return tmp && tmp.get() == EOF
? result
: 0 ;
}

int
main( int argc, char** argv )
{
if ( argc != 3 ) {
std::cerr << argv[ 0 ] << ": syntax is: "
<< argv[ 0 ] << " i j" << std::endl ;
return EXIT_FAILURE ;
}
int i = asInt( argv[ 1 ] ) ;
int j = asInt( argv[ 2 ] ) ;
if ( i == 0 || j < i ) {
std::cerr << argv[ 0 ] << ": illegal values" <<
std::endl ;
return EXIT_FAILURE ;
}
// ...

Note that it's probably best to do this before trying to read
the file with the cached values. No point in reading the file
if all you're going to do is terminate with an error.

Also, of course, if you're doing any amount of programming,
you'll quickly write some generic code to handle the command
line arguments, and use it here.

If you really have to read the two values from std::cin, then
I'd define a somewhat stricter format, say both in one line,
use std::getline() to read the data, and std::istringstream to
parse it. This avoids all problems with handling an error state
in the input or resynchronizing. Something like:

int i = 0 ;
int j = 0 ;
while ( i == 0 ) {
std::string s ;
std::getline( std::cin, s ) ;
if ( ! std::cin ) {
std::cerr << argv[ 0 ]
<< ": fatal error on standard in"
<< std::endl ;
return EXIT_FAILURE ;
}
std::istringstream tmp( s ) ;
tmp >> i >> j >> std::ws ;
if ( ! tmp || tmp.get() != EOF || i == 0 || j < i ) {
std::cerr << argv[ 0 ]
<< ": illegal input, try again"
<< std::endl ;
i = j = 0 ;
}
}

[...]

ofstream ofs("record_h.txt", ios::binary);
hash_map<unsigned int, unsigned int, hash<unsigned int>>::const_iterator it = steps.begin();

Are you sure you didn't want to use a typedef for the type of
the map?

while(it != steps.end()){
two[0] = it->first;
two[1] = it->second;
max_step = (max_step > it->second) ? max_step : it->second;
ofs.write((const char *)two, 2*sizeof(unsigned int));

Again, this more or less guarantees that you won't be able to
reliably read the data later, if you recompile the program for
any reasons.

++it;
}
ofs.close();

if ( ! ofs ) {
std::cerr << argv[ 0 ]
<< ": fatal error writing cache file"
<< std::endl ;
remove( "record_h.txt" ) ;
return EXIT_FAILURE ;
}

I'm not sure about the return here---since it's only a cache
file, you might want to just note the error, without aborting
because of it.

The remove, on the other hand, is important; we've only written
part of the file, so it may be corrupt.

cout << "maximum step: " << i << ' ' << j << ' ' << max_step << '\n';

More of a style issue, but it's a lot cleaner if you add the
explicit return here:

return EXIT_SUCCESS ;

}

You still have way too much in the function main. I'd probably
end up with something like:

int
main( int argc, char** argv )
{
int i = 0 ;
int j = 0 ;
DataMap map ;
if ( parseArgs( argc, argv, i, j )
|| inputArgs( std::cin, i, j ) ) {
CacheFileManager cache( filename, map ) ;
process( dataStructure, i, j ) ;
outputResults( i, j ) ;
}
return exitStatus ;
}

Note the use of the destructor of CacheFileManager to output the
table.

 

[Phil Endecott]

unsigned int compute_steps(int n){
// shortcut to retrieve memorized steps[n]
if(steps[n])
return steps[n];
if(n == 1) return 1;
if(n%2)
n = 3*n+1;
else
n = n/2;
cout << ' ' << n;
// shortcut to memorize steps[n]
steps[n] = compute_steps(n);
return steps[n] + 1;
}

I presume that the "cout <<" is only there for debug / testing; it will
probably be slower than the rest of the code, so remove it.

Hopefully your compiler will do tail recursion optimisation. But maybe
it won't, for some reason. You might prefer to use explicit iteration
rather than recursion to be on the safe side.

You have two calls to hashmap:perator[] for each value of n. Maybe
the compiler can optimise the second away (CSE), but I would not rely on
that.

Most of the time will be spent in the hash-map operations. You might
try to re-design the algorithm so that there are fewer of them. For
example, you might choose to do the hash-map lookup only once every x
iterations. This means that you will do a few more cycles of the 3n+1
arithmetic than are necessary, but that is balanced against the smaller
number of hash-map lookups. Adjust x until you find a good value.

If n is odd, then 3*n+1 will be even (I think!). So after a 3*n+1 step
you will always do an n/2 step. By doing this explicitly you avoid one
odd-even test:

while (...) {
if (n%2) {
n = 3*n+1;
steps++;
}
n = n/2;
steps++;
...
}

I have a feeling that the algorithm can be unrolled to do more than one
step at a time as follows:

switch (n%4) {
case 0: n = n/4; break;
case 1: n = (3*n+1)/2; break;
case 2: n = 3*(n/2)+1; break;
case 3: n = (3*n+1)/2; break;
}
steps += 2;

I think that you can extend this to process many bits, but it's not
certain that it will actually be any faster. It's worth trying though;
I wrote some code to reverse the bits in a word and used an
8-bits-per-iteration lookup table, which was a lot faster than the naive
code.

Most of your hash-map lookups are actually just to test for the presence
of a value. For this some sort of bit-set or bit-vector might be
preferable. Consider using an int or int64 or larger to store 32 or 64
"steps known" flags, and store these ints in some sort of map.

You might also like to look inside your hashmap implementation and see
how it could be improved.

The performance will be influenced greatly by how the code is used,
especially how high the hit rate is in your hashmap.

Don't forget to use all of your compiler's optimisation settings,
including profile-driven optimisation, and to use profiling to see where
the time is actually spent.

Do let us know how you get on.


Phil.

 

[Fei Liu]

unsigned int compute_steps(int n){
// shortcut to retrieve memorized steps[n]
if(steps[n])
return steps[n];
if(n == 1) return 1;
if(n%2)
n = 3*n+1;
else
n = n/2;
cout << ' ' << n;
// shortcut to memorize steps[n]
steps[n] = compute_steps(n);
return steps[n] + 1;
}

I presume that the "cout <<" is only there for debug / testing; it will
probably be slower than the rest of the code, so remove it.

Hopefully your compiler will do tail recursion optimisation. But maybe
it won't, for some reason. You might prefer to use explicit iteration
rather than recursion to be on the safe side.

You have two calls to hashmap:perator[] for each value of n. Maybe
the compiler can optimise the second away (CSE), but I would not rely on
that.

Most of the time will be spent in the hash-map operations. You might
try to re-design the algorithm so that there are fewer of them. For
example, you might choose to do the hash-map lookup only once every x
iterations. This means that you will do a few more cycles of the 3n+1
arithmetic than are necessary, but that is balanced against the smaller
number of hash-map lookups. Adjust x until you find a good value.

If n is odd, then 3*n+1 will be even (I think!). So after a 3*n+1 step
you will always do an n/2 step. By doing this explicitly you avoid one
odd-even test:

while (...) {
if (n%2) {
n = 3*n+1;
steps++;
}
n = n/2;
steps++;
...
}

I have a feeling that the algorithm can be unrolled to do more than one
step at a time as follows:

switch (n%4) {
case 0: n = n/4; break;
case 1: n = (3*n+1)/2; break;
case 2: n = 3*(n/2)+1; break;
case 3: n = (3*n+1)/2; break;
}
steps += 2;

I think that you can extend this to process many bits, but it's not
certain that it will actually be any faster. It's worth trying though;
I wrote some code to reverse the bits in a word and used an
8-bits-per-iteration lookup table, which was a lot faster than the naive
code.

Most of your hash-map lookups are actually just to test for the presence
of a value. For this some sort of bit-set or bit-vector might be
preferable. Consider using an int or int64 or larger to store 32 or 64
"steps known" flags, and store these ints in some sort of map.

You might also like to look inside your hashmap implementation and see
how it could be improved.

The performance will be influenced greatly by how the code is used,
especially how high the hit rate is in your hashmap.

Don't forget to use all of your compiler's optimisation settings,
including profile-driven optimisation, and to use profiling to see where
the time is actually spent.

Do let us know how you get on.


Phil.

To summarize,
1. Use iteration instead of recursion to avoid function call
2. Drop boost::filesystem, use simpler fstream interface
3. I like the idea of using an bitarray to represent known/unknown result
4. Prefer unordered_map to hash_map
5. Body of main is too long, split up to smaller pieces
6. Optimize the algorithm

Thank you!

Fei

 

[Mirco Wahab]

To summarize,
1. Use iteration instead of recursion to avoid function call
2. Drop boost::filesystem, use simpler fstream interface
3. I like the idea of using an bitarray to represent known/unknown result
4. Prefer unordered_map to hash_map
5. Body of main is too long, split up to smaller pieces
6. Optimize the algorithm

7. Expect numerical problems and solve them


Why? I wrote a simple prototype (in Perl) to check
my hypothesis (see below). Already at low numbers
(below 10,000,000), you'll run into very large
temporary numbers, which means, your code part:

unsigned int compute_steps(int n){
...
if(steps[n])
return steps[n];
if(n == 1) return 1;
if(n%2)
n = 3*n+1; // <=== here be dragons
else
n = n/2;
...

will fail dependent of your integer representation.

Already a number like (e.g.) 7,006,663 will iterate/recurse
478 times in your algorithm, leading to a fancy temporary
"n" of 9,586,432,619 - which requires proper 64-bit int handling.

You won't notice because there is "something" in
your number hash (which is garbage) ...

Regards

M.

Addendum:

naíve collatz algorithm prototype, Perl
version (uses gmp)
usage: $> perl collatz.pl 1000 1000000

==>

use strict;
use warnings;
use Math::BigInt lib => 'GMP';

my ($fr, $to, $fn) = @ARGV;

printf "lmin:%d(n:%d,b:%s), lmax:%d(n:%d,b:%s)\n",
map @$_, chk_collatz_range($fr .. $to);

sub chk_collatz_range
{
my @stepcache;
while( my $nextnum = shift ) {
my ($lstr, $nstep, $bnum) = (0, 0, Math::BigInt->new($nextnum));
while( not $bnum->is_one() ) {
my $tmp = $bnum->bstr();
$lstr = $tmp if length $lstr < length $tmp && $lstr lt $tmp;
$bnum->is_odd() ? $bnum->bmuladd(3, 1) : $bnum->brsft(1);
++$nstep
}
push @stepcache, [$nstep, $nextnum, $lstr]
}
return ( sort { $a->[0] <=> $b->[0] } @stepcache )[0, -1]
}

<==