Nested Loops: A cautionary tale about exponential growth

A couple of days ago, I decided to write a script which would change the appearance of the font of some displayed text in HTML. To do that, I needed to nest some loops. So, I wrote the loops and everything was wonderful. I needed some help to make the script functional. After I got the help and a functioning script, I decided to add more loops to it. After I did that but before I ran it in my browser again and on a whim, I decided to do some math. The math made me stop and wonder what I had just done.

In the script, I am looping two hashes. Each hash value is an array. Well, multiplying the amounts of values in each array showed me just how many iterations there were going to be. Then I multiplied that by the approximate amount of text that would be generated, and I got a really really really really really big number. That big number made me sit back and realize I need to rethink the whole thing. I still need the loops, but do I really want to display all options when the script it first loaded? The answer of course is no.

The script below generates approximately 145 Mb of text when nothing is selected. Even if one item (with the least options) is selected, it would still generate approximately 50 Mb of text. That is a bit much, don't you think? :)

What was learned? Be careful when nesting loops since it grows exponentially.

#!/usr/bin/perl
use strict;
use warnings;

use CGI;
use HTML::Entities qw(encode_entities);
use Tie::IxHash;

print "content-type: text/html \n\n";

my @options = qw(text color background_color);

tie my %font, qw(Tie::IxHash);
tie my %text, qw(Tie::IxHash);

%font = (
  style       => [qw(normal italic oblique)],
  variant     => [qw(normal small-caps)],
  weight      => [qw(normal bold 100 200 300 400 500 600 700 800 900)]
+,
  size        => [qw(xx-small x-small small medium large x-large xx-la
+rge)],
  family      => [qw(serif sans-serif cursive fantasy monospace)],
);

%text = (
  align      => [qw(left right center justify)],
  decoration => [qw(none underline overline line-through blink)],
  transform  => [qw(none capitalize uppercase lowercase)],
);

my $cgi               = CGI->new();
my $text              = encode_entities($cgi->param('text')) || "The q
+uick brown fox jumps over the lazy dog.";
my $color             = encode_entities($cgi->param('color')) || "#000
+";
my $background_color  = encode_entities($cgi->param('background_color'
+)) || "transparent";
my $select_style      = $cgi->param('select_style');
my $select_variant    = $cgi->param('select_variant');
my $select_weight     = $cgi->param('select_weight');
my $select_size       = $cgi->param('select_size');
my $select_family     = $cgi->param('select_family');
my $select_align      = $cgi->param('select_align');
my $select_decoration = $cgi->param('select_decoration');
my $select_transform  = $cgi->param('select_transform');

sub select_group {
  my ($value, $hash) = @_;
  my $display_value = ucfirst $value;
  print qq{<div>\n<span>$display_value: </span>\n};
  for my $select (keys %$hash) {
    my $options = $$hash{$select};
    print qq{<select name="select_$select:">\n};
    my $label = $select;
    print qq{<option value="">$label</option>\n};
    for my $option (@$options) {
        print qq{<option value="$option">$option</option>\n};
    }
   print qq{</select>\n};
  }
  print qq{</div>\n};
}

print <<"sec1";
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/T
+R/html4/strict.dtd">
<html><head><title>Font, text, and color tests</title>
<style type="text/css">
h1 {font-size:14pt;}
</style>
</head>
<body>
<h1Font, text, and color tests</h1>
<form action="/fantasy/files/perl/font.pl" method="get">
sec1

for my $option (@options) {
  my $display_option = ucfirst $option;
     $display_option =~ tr/_/ /;
  print qq{<div>\n<label for="$option">$display_option: </label>\n<inp
+ut type="text" id="$option" name="$option">\n</div>};
}

select_group('font', \%font);
select_group('text', \%text);

print <<"sec2";
<div>
<input type="submit" value="submit">
<a href="font.pl">Start over</a>
</div>
</form>
sec2

#Begin the OH MY GOD THIS IS HUGE! loop
for my $style ($select_style ? $select_style : @{$font{'style'}}) {
  for my $variant ($select_variant ? $select_variant: @{$font{'variant
+'}}) {
    for my $weight ($select_weight ? $select_weight : @{$font{'weight'
+}}) {
      for my $size ($select_size ? $select_size : @{$font{'size'}}) {
        for my $family ($select_family ? $select_family : @{$font{'fam
+ily'}}) {
          for my $align ($select_align ? $select_align : @{$text{'alig
+n'}}) {
            for my $decoration ($select_decoration ? $select_decoratio
+n : @{$text{'decoration'}}) {
              for my $transform ($select_transform ? $select_transform
+ : @{$text{'transform'}}) {
                print qq{
#Outdented for visibility and ease of editing
<dl>\n
<dt>font-<dt>\n
<dd>style: $style; variant: $variant; weight: $weight; size: $size; fa
+mily: $family;</dd>\n
<dt>text-</dt>\n
<dd>align: $align; decoration: $decoration; transform: $transform;<dd>
+\n
<dt>color<dt>\n
<dd>$color</dd>\n
<dt>background-color</dt>\n
<dd>$background_color</dd>\n
<dl>\n
                };
                print qq{
#Outdented for visibility and ease of editing
<p style="
font:$style $variant $weight $size $family;
text-align:$align;text-decoration:$decoration;text-transform:$transfor
+m;
color:$color;background-color:$background_color;
">$text</p>\n
                };
              }
            }
          }
        }
      }
    }
  }
}
#End the OH MY GOD THIS IS HUGE! loop

print "</body></html>";
[download]

PS. If you have any thoughts that might help me with the rethink, I will take them.

Have a nice day!

Lady Aleena

Comment on Nested Loops: A cautionary tale about exponential growth Download Code

Replies are listed 'Best First'.
Re: Nested Loops: A cautionary tale about exponential growth by graff (Chancellor) on Feb 26, 2010 at 04:53 UTC
I'm not understanding why you think it's necessary to create a full enumeration of all possible combination over a 3 x 2 x 11 x 7 x 5 x 4 x 5 x 4 parameter set. Isn't it really a matter of having 8 independent sets of parameters? For each parameter, you just hold the other 7 constant, and show the (2 or 3 or 4 or 5 or 7 or 11) different values available for the parameter in focus. Imagine just 8 rows of radio buttons (number of buttons per row = number of choices for that parameter), along with 8 rows of sample text (each text row demonstrates the appearance of the different options for that one parameter, given that all other parameters are held constant). When the user selects an option in each of the 8 rows and then submits, the next display shows the 8 lines of text based on the various selections -- e.g. the line that shows the different font weights will have its style, variant, size, family, etc all held constant, based on the user's selections for those other parameters. This approach means that the user can only see a subset of the possible variations on any one page, but at least the page isn't overwhelming.	[reply]
Re^2: Nested Loops: A cautionary tale about exponential growth by Jenda (Abbot) on Feb 26, 2010 at 10:23 UTC
With a little bit of JavaScript you do not even need the submit. The example text below the rows of radiobuttons may change as you click the radiobuttons. Jenda Enoch was right! Enjoy the last years of Rome.	[reply]
Re^3: Nested Loops: A cautionary tale about exponential growth by roboticus (Chancellor) on Feb 26, 2010 at 14:39 UTC
Update: After re-reading the text, my message doesn't make sense. I originally thought he meant that he was going to provide example text below, which wasn't in his post. Perhaps I need to get my eyes checked again... Jenda: That's a really terse example ... I don't follow. </big_grin> ...roboticus	[reply]
(Slightly) OT: Re: Nested Loops: A cautionary tale about exponential growth (long, rambly anecdote) by roboticus (Chancellor) on Feb 26, 2010 at 15:09 UTC
Lady Aleena: That reminds me of a problem we had to solve in a programming contest we had in High School. We were submitting the jobs in a time-share system, and the code had to (1) print the correct answer, and (2) execute within the CPU time limit. The problem was trivial: Find the cube root of some large number (say 13000) that happened to have an integer for a cube root. My code went roughly^[1] like this: `FOR I = 1 to 13000 FOR J = 1 TO 13000 FOR K = 1 TO 13000 IF 13000 = IJK THEN PRINT "CUBE ROOT IS ", I NEXT K NEXT J NEXT I` [download] (Obviously, this is when I was young and stupid.) They would only give us the error messages from the run, nothing else. This code kept blowing the CPU time limit. (We didn't know that until after the contest, because it didn't generate any output. They just told us "Your program didn't print anything".) After the contest, I thought to myself: "Oh, obviously I, J and K can't be any larger than the cube root of the number: We were blowing the time limit because we had 13000^3 or 2.197x10^12 loops^[2]. We should've looked up log(13000) from our CRC book^[4], divided by three and reverse-lookup to get 27.5. Then we would've had less than 22000 loops if we changed the code to^[3]: `FOR I = 1 to 28 FOR J = 1 TO 28 FOR K = 1 TO 28 IF 13000 = IJK THEN PRINT "CUBE ROOT IS ", I NEXT K NEXT J NEXT I` [download] ...roboticus NOTES: [1] As accurate as I can recall over several decades... [2] On the GE-635 processor we were using, a multiply was between 5 and 10 uS, so looking only at the multiplications, it would've taken 127+ days to complete... assuming the jumps, additions, and comparisons were free. Also assuming no-one else was using the computer. [3] It wasn't for several months before I realized the code should've been: `FOR I = 1 to 28 IF 13000 = III THEN PRINT "CUBE ROOT IS ", I NEXT I` [download] Oh, well, I was a wee cog back then. [4] I had just received a "four-banger" calculator (a calculator with addition, subtraction, multiplication and division) for Christmas -- rather expensive back then. I don't recall if scientific calculators were available at the time or not. I barely missed having to use a "slipstick" (slide rule).	[reply] [d/l] [select]