Re: [MacPerl] BigInt sluggishness.

[Jim Miner <jfm@winternet.com>]

This is a good application for Bit::Vector.  The MacPerl port is at <http://www.perl.com/CPAN/authors/id/A/AS/ASANDSTRM/Bit-Vector-5.6-bin-2-MacOS.tgz>

You'll have to adapt your algorithm, because "adding" bit vectors
won't work the same way you're using integers.  

You can think of bit vectors as sets of integers from 0 up to some
maximum.  In you application, the vector/set for a class would 
contain the integers representing the hours that the class meets.

You need to formulate the algorithms in terms of set operations.
The intersection of two sets contains the elements that are in both
of those sets.  The union of two sets contains the elements that are 
in either of the sets.

The following script has two main parts.  First, define the
hour bit-vectors for some classes.  Second, test for overlaps
between some of these classes.  The function that checks for
the overlap (is_overlap()) gets passed a list of bit-vectors. 
It loops through the list, checking whether each class has any
hour in common with the union of all prior classes in the list.
If it finds any, there is any overlap.

Hope this helps....

Jim


------- snip -------
#!/usr/local/bin/perl -w

use strict;

use Bit::Vector;

my $MAX = 70; # largest element, smallest is 0



### Define the hour-vectors for some classes.

my %class_hours;

sub class_hour_vector {
    my (@hours) = @_;
    my $bitvec = Bit::Vector->new($MAX);
    foreach my $hour (@hours) {
        $bitvec->Bit_On($hour)
    }
    $bitvec;
}

$class_hours{'basket weaving'} = class_hour_vector(0, 1, 2);
$class_hours{'water balloons'} = class_hour_vector(3, 4, 5);
$class_hours{'archery'} = class_hour_vector(5, 6);



### Check for overlaps

sub is_overlap {
    my @classes = @_;
    
    my $union = Bit::Vector->new($MAX); 
        # accumulate hours seen in any class

    my $intersection = Bit::Vector->new($MAX);
        # gets result of intersect operation in loop

    foreach my $c (@classes) {
        $intersection->Intersection($union, $c);
        return 1 # overlap found
            unless $intersection->is_empty();
        $union->Union($union, $c);
    }

    return 0; # no overlap found
}


my $overlap = is_overlap(
    $class_hours{'basket weaving'}, 
    $class_hours{'water balloons'}
);
  # should be 0
print "basket weaving and water balloons ", 
    ($overlap ? 'do' : "don't") , " overlap.\n";
  
$overlap = is_overlap(
    $class_hours{'basket weaving'}, 
    $class_hours{'water balloons'}, 
    $class_hours{'archery'});
  # should be 1
print "basket weaving, water balloons and archery ", 
    ($overlap ? 'do' : "don't") , " overlap.\n";
 ------- snip -------


At 4:49 PM -0500 12/2/00, bert wrote:
>Hello all, first off let me just say it's wonderful how friendly and helpful
>the folks on this list are...it is much appreciated. Having said that I hope
>this question is appropriate:
>
>I am trying to create a program that, when given a list of classes and their
>meeting time, will sort through and output every possible combination where
>no classes overlap. My problem is in how I'm trying to represent the class
>times. I have a 71 digit number, each digit representing an hour of the week
>during which classes can meet. It's a zero if there's no class at that hour,
>one if there is (plus a one at the beginning or else it thinks i'm trying an
>octal number?):
>
>Basketweaving 101: 1000000111000000000000000111000000000000000000000
>
>The example is shortened a bit, but Basketweaving would be a three hour
>class twice a week. In order to see if a schedule works i add together all
>the class's numbers and if there's nothing but ones and zeros in the sum
>('cept for the first number) then they didn't overlap.
>
>1000000111000000000000000111000000000000000000000
>1000000000000000111000000000000001110000000000000   <--Fine
>
>1000000111000000000000000111000000000000000000000
>1000000000001000000000000011100000000000000000000   <--No
>
>My problem is, quite simply, it's a 71 digit number, which gets chopped down
>to 15 digits without Math::BigInt, and Math::BigInt is far too slow. A large
>schedule can require 15,000+ iterations to check all the classes (I don't
>mind waiting myself, but this may end up on a server eventually). When I
>benchmarked BigInt vs. normal addition (with smaller numbers) it was over
>ten times slower. Is there a better alternative? Am I doing something wrong
>perhaps? I can't think of a better/simpler way to represent the classes, but
>I'm only a dumb Graphic Design major and I'm not too familiar with many data
>structures ;-)
>
>Thanks a lot for any help and suggestions,
>Brian Boucheron.
>
>
># ===== Want to unsubscribe from this list?
># ===== Send mail with body "unsubscribe" to macperl-request@macperl.org

-- 

Jim Miner          jfm@winternet.com

# ===== Want to unsubscribe from this list?
# ===== Send mail with body "unsubscribe" to macperl-request@macperl.org