[cupidvogel]

Hi, a program requires one to enter a given number of strings, and for each string, the program has to output the number of permutations possible. We all know that if a string S of length l has a type of one letter, b type of another, c type of another, and so on, while the rest are present only once, then the answer will be (l!)/(a! * b! * c!). Line no. 8 calculates the denominator. Now the question is, can this be made more efficient in any possible way???

use bignum;
sub fact { $_[0] == 0 ? 1 : $_[0]*fact($_[0] - 1); }
chomp($count = <STDIN>);
for (1..$count) {
%hash = ();
$div = 1;
chomp($_ = <STDIN>);
$div *= 1+$hash{$_}++ for split //;
$init = fact(length($_))/$div;
print "$init\n"
}

This post has been edited by cupidvogel: 08 February 2012 - 09:14 AM

[dsherohman]

Assuming long strings with some high-frequency characters, you're effectively calculating all your factorials from scratch for each character, which means you're doing a lot of unnecessary multiplication, which can slow things down noticeably, especially when you're using bignum. (Or so I've heard. Never used bignum myself, but performance seems to be the standard complaint about it.)

It should be possible to speed this up a bit by revising your factorial code to cache previously-calculated results. I would expect this to be a bit slower for short strings, because of the overhead involved in the caching, but, when more and higher-order factorials are needed, it should produce massive improvements.

A small bit of hacking later...

Yes, the results are much as I'd expected. The code:

#!/usr/bin/env perl

use strict;
use warnings;
no warnings 'recursion'; # Otherwise we get "deep recursion" warnings on $long

use bignum;
use Benchmark ':all';

my $short = 'foo';
my $long  = <<EOLOREM;
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor
incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis
nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.
Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu
fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in
culpa qui officia deserunt mollit anim id est laborum.
EOLOREM

$long =~ s/\n//g;

# Original version
  
sub fact_orig { $_[0] == 0 ? 1 : $_[0] * fact_orig($_[0] - 1); }
  
sub loop_orig {
  my $text = $_[0];

  my %hash;
  my $div = 1;
  $div *= 1 + $hash{$_}++ for split //, $text;
  return fact_orig(length($text)) / $div;
} 


# Caching version
  
my %factorial;
sub fact_cache {
  my $num = shift;
  
  # ||= will only calculate the result if it's not already there
  $factorial{$num} ||= $num * fact_cache($num - 1);
  return $factorial{$num};
} 
  
sub loop_cache {
  my $text = $_[0];
  
  # In real code, you'd only want to initialize %factorial once at program
  # startup, but here we have to clean out the cache at the start of each
  # trial or else it won't be a fair comparison
  %factorial = (1 => 1);

  my %chars;
  $chars{$_}++ for split //, $text;
  my $div = 1;
  $div *= fact_cache($chars{$_}) for keys %chars;
  return fact_cache(length($text)) / $div;
}
  

# And now to compare the two...

# First make sure that both versions of the calculation get the same results
die "Bad result on short string - aborting\n"
  unless loop_orig($short) == loop_cache($short);
die "Bad result on long string - aborting\n"
  unless loop_orig($long) == loop_cache($long);

cmpthese(
  1000,
  { 'orig short'   => "loop_orig(q($short))",
    'cached short' => "loop_cache(q($long))",
  }
);

cmpthese(
  100,
  { 'orig long'   => "loop_orig(q($long))",
    'cached long' => "loop_cache(q($long))",
  }
);

produces the output:

               Rate cached short   orig short
cached short 18.5/s           --         -99%
orig short   1961/s       10500%           --
              Rate   orig long cached long
orig long   14.0/s          --        -25%
cached long 18.6/s         33%          --

The hash lookups make the caching version 100 times slower when looking at the single word "foo", but about a third faster for the 441 characters of lorem ipsum in the long string. But also note the comment in loop_cache - if you're going to be doing this sort of thing several times in a single run of the program and preserve the cached factorials between them, the cached version will be a huge win. (If I don't clean the cache between tests, the 'cached long' jumps from 18.6/s to 127/s and 'cached short' to 124/s.)

[cupidvogel]

Nice solution, but when I submitted this version in Codechef (you may register there and try it out by submitting solutions for the problem at http://www.codechef....problems/WCOUNT), it showed the same message as my solution, that is, time limit exceeded. I have thought of a better solution. Your one calculates the factorial of a number if it is not present in the cache, else it calculates. That is, if the cache has got the factorial of 51, and you want it for 55, you have to calculate it anew. I am planning to improve it by finding out the greatest number less than equal to the number in question, then multiplying the factorial of that number (51 in this case, whose factorial is stored in the dictionary corresponding to a key value of 51) with numbers upto the number in question. So in this case, the moment I come across 55!, the algo will take the value of 51! from the dictionary (unless it has factorials of 52, 53, 54 stored also, in which case I will consider the maximum), multiply it with 52,53, 54 and 55, and use it, before storing it in the dictionary. Sounds exciting, I will start right away.

[cupidvogel]

Although, I still have no idea that why my (not to speak of yours, which is way more efficient) solution didn't work. The optimization will come handy when calculation of big factorials, like say 60, 70, etc is required. But if you read the question at the link, you will find that we won't require to calculate factorials of numbers higher than 10. So how much further optimization for factorial of 10 can be achieved by using these techniques?

[cupidvogel]

There, here is the code I mentioned above. Although still it is showing time limit exceeded at Codechef, I think this is a significant betterment. Please modify the code to output the running time for each case along-with the required output, i.e if the number of test cases is 5, for each case, along with the number of permutations, it should also display the time that case took to give the result. So for 5 test cases with the appropriate inputs suited to the testing, the time gain can be seen. (For example, if in one test case, factorial of 21 is calculated for the first time, the previous highest being 10 only, the time it takes should be more than a factorial 21 in the next case, since this time it will readily find the factorial value of 21 from the hash without the need to compute it).

use bignum;
use integer;
sub facto { $_[0] == 0 ? 1 : $_[0]*facto($_[0] - 1); }
sub factoo { $_[0] == $_[1] ? $_[0] : $_[0]*factoo($_[0]+1,$_[1]); }
%fact = (2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,10,3628800);
@temp = sort keys %fact;
sub fsp {
$target = pop @_;
my $low = 0;
my $high = @_ - 1;
while ($low <= $high) {
$mid = ($high+$low)/2;
return $mid if $_[$mid] == $target;
$high = $mid - 1 if $target < $_[$mid];
$low = $mid + 1 if $target > $_[$mid];
}
$low-1;
}
sub sorted {
$num = shift;
$index = shift;
if ($index == -1) {
unshift @temp,$num;
$fact{$num} = facto($num);
}
elsif ($index == 0) {
return $fact{$num} if $temp[0] == $num;
splice @temp,1,0,$num;
$fact{$num} = $fact{$temp[0]}*factoo($temp[0]+1,$num);
}
else {
return $fact{$temp[$index]} if $temp[$index] == $num;
$newindex = $index + 1;
splice @temp,$newindex,0,$num;
$fact{$num} = $fact{$temp[$index]}*factoo($temp[$index]+1,$num);
}
$fact{$num};
}
sub prepare {
$num = shift;
$index = fsp(@temp,$num);
sorted($num,$index);
}
chomp($count = <STDIN>);
for (1..$count) {
$div = 1;
%ref = ();
chomp($_ = <STDIN>);
$ref{$_}++ for split //;
@divs = grep $_ > 1, values %ref;
$div *= prepare($_) for @divs;
$init = prepare(length($_))/$div;
$init %= 10**9+7;
print "$init\n";
}

The fsp subroutine finds the index of an incoming element into a sorted array, and is used twice, once to find the number after which the factorial of the last greatest integer from the hash should be started multiplied until the desired factorial is found (refer to the factoo function), and then to insert the new number into the sorted array at the index.

[dsherohman]

cupidvogel, on 09 February 2012 - 12:51 PM, said:

Your one calculates the factorial of a number if it is not present in the cache, else it calculates. That is, if the cache has got the factorial of 51, and you want it for 55, you have to calculate it anew. I am planning to improve it by finding out the greatest number less than equal to the number in question, then multiplying the factorial of that number (51 in this case, whose factorial is stored in the dictionary corresponding to a key value of 51) with numbers upto the number in question.

Look more closely... That's what my code does. It calculates 55! as 55*54!, which is 54*53!, which is 53*52!, which is 52*51! and it already knows 51! from calculating it previously. That's why it's faster for longer strings even when the cache is reset at the start of each run.

Given the actual constraints from CodeChef, I suspect it may not be possible to meet their time limit in Perl. Note that pretty much all of the successful submissions are in C, C99, or C++ - languages which are compiled fully to native machine instructions prior to execution and which are known for being very fast with numerical computation. Perl, on the other hand, has the overhead of compiling the program at startup, then running it through a bytecode interpreter during execution, as well as chaining every access to a variable through a couple levels of indirection in order to decide whether it's a number or not before returning a value to work with. Although Perl is generally more than fast enough in real-world situations, it's not a high-performance language. It's optimized for flexibility, not raw speed.

If you only need to deal with factorials up to 10!, then pre-calculating them and just doing an array lookup at runtime is definitely the way to go, but, even there, an array lookup is much, much faster in C than in Perl.

[cupidvogel]

In this case, an array lookup will not suffice, because the maximum times one letter occurs in a string is 10, but the string may be of any length less than 500, in which case the lookup won't suffice and I have to use the cache. Plus I am going to add another level of optimization. Currently, if the cache contains factorials of 57 and then 76, and I require the factorial of 72, it will start by multiplying 72 with 71, then 70, until 58, and multiply the final result with 57! But 76 is much nearer to 72 than 57, so it would be better if I multiply 76 with 75, then 74, upto...73, before dividing 76! by that product to get 72! So the new algo will find the position where the new number is gonna enter the cache, search forward and backward to decide which one is nearer, and go in that direction.

And as to the speed thing, yes, I was feeling the same way too. Is Python also slower in this regard compared to those languages like Perl?

[cupidvogel]

Here, it's the final one I have come out with, although it's still not good enough for Codechef:

use bignum;
sub factoo { $_[0] == $_[1] ? $_[0] : $_[0]*factoo($_[0]+1,$_[1]); }
%fact = (0,0,1,1,2,2,3,6,4,24,5,120,6,720,7,5040,8,40320,9,362880,10,3628800);
@temp = sort {$a <=> $b} keys %fact;
sub fsp {
$target = pop @_;
my $low = 0;
my $high = @_ - 1;
while ($low <= $high) {
$mid = sprintf "%d", ($high+$low)/2;
return $mid if $_[$mid] == $target;
$high = $mid - 1 if $target < $_[$mid];
$low = $mid + 1 if $target > $_[$mid];
}
$low;
}
sub sorted {
if ($index > $#temp) {
push @temp,$num;
$fact{$num} = $fact{$temp[-2]}*factoo($temp[-2]+1,$num);
}
else {
return $fact{$num} if $temp[$index] == $num;
($fir,$sec) = @temp[$index-1,$index];
$fact{$num} = $fact{$fir}*factoo($fir+1,$num) if $num-$fir <= $sec-$num;
$fact{$num} = $fact{$sec}/factoo($num+1,$sec) if $num-$fir > $sec-$num;
splice @temp,$index,0,$num;
}
$fact{$num};
}
sub prepare {
$num = shift;
$index = fsp(@temp,$num);
sorted();
}
chomp($count = <STDIN>);
for (1..$count) {
$div = 1;
%ref = ();
chomp($_ = <STDIN>);
$ref{$_}++ for split //;
@divs = grep $_ > 1, values %ref;
$div *= prepare($_) for @divs;
$init = prepare(length($_))/$div;
$init %= 10**9+7;
print "$init\n";
}

This post has been edited by cupidvogel: 11 February 2012 - 03:47 AM

[dsherohman]

cupidvogel, on 10 February 2012 - 01:24 PM, said:

In this case, an array lookup will not suffice, because the maximum times one letter occurs in a string is 10, but the string may be of any length less than 500, in which case the lookup won't suffice and I have to use the cache.

I think you misunderstood... I meant an array lookup (instead of a hash or any on-the-fly calculation) to find the factorials. In Perl, the performance of arrays and hashes is basically identical (I've benchmarked it on this problem and they're within 1-2% of each other), but array lookups in C are very fast. Much faster than any other kind of data structure.

cupidvogel, on 10 February 2012 - 01:24 PM, said:

And as to the speed thing, yes, I was feeling the same way too. Is Python also slower in this regard compared to those languages like Perl?

I don't know offhand whether Python would be faster or slower than Perl for this specific type of calculation, but I can definitely say that Python is structurally in the same class of loosely-typed dynamic languages as Perl, so it will still be way slower than a strictly-typed, statically-compiled language like C.

[cupidvogel]

Got it.