Optimizing system calls and nested loops

I'm writing a Perl program to take a set of clauses and a conclusion literal and produce a resolution-refutation proof (if possible) using a breadth-first set of support (SOS) search algorithm.

The actual searching part of the program runs extremely slow, because I have many nested loops. I imagine it may also have to do with the system calls for the I/O taking place, but I'm not sure.

Here is the code for the searching part of the program.

@clauses and @SOS are both 2D arrays. The @clauses contain all of the clauses including the negated conclusion. In the beginning of the algorithm you see @SOS gets initialized with the negated conclusion as its only value. It then grows with clauses as resolutions are found.

```
#Begin breadth-first/SOS search/add algorithm
$SOS[0][0]=$conclusion2;
my $cSize=@clauses;
say "\nworking......";
my $dots=0;
SOSROW:
for(my $a; $anew->sort(@tmp);
my $s1= join(undef, @a1);
for(my $i=0; $inew->sort(@{@clauses[$i]});
my $s2= join(undef,@a2);
if($s1 eq $s2 )
{
$dupl ='did';
}
}
if($dupl eq 'not')
{
my $s=$cSize+$cAdd;
$res++;
$sAdd++;
$cAdd++;
push @{$SOS[$sAdd]}, @tmp;
push @{$clauses[$s]}, @tmp;

#Print out the new clauses.
print RESULTS"clause $s: ";
my $clause = $cSize+$a-1;
if($SOS[$sAdd][0])
{
print RESULTS "{";
for(my $j=0; $j<$#{@clauses[$s]}+1; $j++)
{
if($clauses[$s][$j])
{
print RESULTS "$clauses[$s][$j]";

}
if($j!=$#{@clauses[$s]})
{
print RESULTS ",";
}
}
print RESULTS "} ($i,$clause)\n";
}
#If you found a new res, but there was nothing to push, you f

You seem to have taken away little from my efforts to help you write good Perl code. In particular you must add

use warnings

to the top of every Perl program, which in this case would have resulted in line after line of errors like

Scalar value @clauses[$s] better written as $clauses[$s]

You also should use Perl's range iterator. The C-style for loop is a clumsy tool, and you are also mixing together $#array, $#array + 1, @array, and @array - 1 in your loop limits.

To iterate over the indices of a Perl array you should write

for my $i (0 .. $#array) {
  ...
}

unless you have a strange and unusual requirement. It is also best to keep to $i, $j, $k etc. for array indices as everyone knows what they mean. $s is usually a string, and $a and $b are fobidden because they are used by the Perl sort engine.

So your loops

for (my $i = 0; $i < @clauses; $i++) { ... }

for (my $j = 0; $j < $#{ @clauses[$s] } + 1; $j++) { ... }

should be

for my $i (0 .. $#clauses) { ... }

for my $j (0 .. $#{ $clauses[$i] }) { ... }

which I hope you will agree is much more readable.

If you make at least these changes then you will get a lot more help from people who will then be able to understand your code better.

StackExchange Code Review Q#48358, answer score: 7