Algorithm-Bucketizer

 view release on metacpan or  search on metacpan

Bucketizer.pm  view on Meta::CPAN

=head2 Prefilling Buckets

Sometimes you will have preexisting buckets, which you need to 
tell the algorithm 
about before it starts adding new items. The C<prefill_bucket()> method
does exactly that, simply putting an item into a specified bucket:

    $b->prefill_bucket($bucket_idx, $item, $itemsize);

C<$bucket_idx> is the index of the bucket, starting from 0. Non-existing buckets
are automatically created for you. Make sure you have a consecutive number
of buckets at the end of the prefill.

=head2 Optimize

Once you've inserted all items, you might choose to optimize the distribution
over the buckets, in order to I<minimize> the number of required buckets
to hold all the elements.

Optimally distributing a number discrete-sized items into a 
number of discrete-sized buckets, however, is a non-trivial task. 

Bucketizer.pm  view on Meta::CPAN

Currently, it implements C<"random"> and C<"brute_force">.

C<"random"> tries to randomly vary the distribution until a time
or round limit is reached.

        # Try randomly to improve distribution, 
        # timing out after 100 rounds
    $b->optimize(algorithm => "random", maxrounds => 100);

        # Try randomly to improve distribution, 
        # timing out after 60 secs
    $b->optimize(algorithm => "random", maxtime => 60);

        # Try to improve distribution by brute_force trying
        # all possible combinations (watch out: can take forever)
    $b->optimize(algorithm => "brute_force",
                 maxtime => ..., 
                 maxrounds => ...,
                );

I'm currently evaluating more sophisticated methods suggested by

Bucketizer.pm  view on Meta::CPAN

    $b->current_bucket_idx( $idx );

Set/retrieve the index of the bucket that the C<simple> algorithm will
use first in order to try to insert the next item.

=item *

    $b->optimize(
        algorithm  => $algorithm,
        maxtime    => $seconds,
        maxrounds  => $number_of_rounds 
       );

Optimize bucket distribution. Currently C<"random"> and C<"brute_force">
are implemented. Both can be (C<"random"> I<must> be) terminated
by either the maximum number of seconds (C<maxtime>) or 
iterations (C<maxrounds>).

=back

=head1 EXAMPLE

We've got buckets which hold a weight of 100 each, 
and we've got 10 items weighing 30, 31, 32, ... 39. Distribute 
them into buckets.

README  view on Meta::CPAN

  Prefilling Buckets
    Sometimes you will have preexisting buckets, which you need to tell the
    algorithm about before it starts adding new items. The
    "prefill_bucket()" method does exactly that, simply putting an item into
    a specified bucket:

        $b->prefill_bucket($bucket_idx, $item, $itemsize);

    $bucket_idx is the index of the bucket, starting from 0. Non-existing
    buckets are automatically created for you. Make sure you have a
    consecutive number of buckets at the end of the prefill.

  Optimize
    Once you've inserted all items, you might choose to optimize the
    distribution over the buckets, in order to *minimize* the number of
    required buckets to hold all the elements.

    Optimally distributing a number discrete-sized items into a number of
    discrete-sized buckets, however, is a non-trivial task. It's the
    "bin-packing problem", related to the "knapsack problem", which are both
    *NP-complete*.

README  view on Meta::CPAN

    Currently, it implements "random" and "brute_force".

    "random" tries to randomly vary the distribution until a time or round
    limit is reached.

            # Try randomly to improve distribution, 
            # timing out after 100 rounds
        $b->optimize(algorithm => "random", maxrounds => 100);

            # Try randomly to improve distribution, 
            # timing out after 60 secs
        $b->optimize(algorithm => "random", maxtime => 60);

            # Try to improve distribution by brute_force trying
            # all possible combinations (watch out: can take forever)
        $b->optimize(algorithm => "brute_force",
                     maxtime => ..., 
                     maxrounds => ...,
                    );

    I'm currently evaluating more sophisticated methods suggested by more

README  view on Meta::CPAN

    *
            $b->current_bucket_idx( $idx );

        Set/retrieve the index of the bucket that the "simple" algorithm
        will use first in order to try to insert the next item.

    *
            $b->optimize(
                algorithm  => $algorithm,
                maxtime    => $seconds,
                maxrounds  => $number_of_rounds 
               );

        Optimize bucket distribution. Currently "random" and "brute_force"
        are implemented. Both can be ("random" *must* be) terminated by
        either the maximum number of seconds ("maxtime") or iterations
        ("maxrounds").

EXAMPLE
    We've got buckets which hold a weight of 100 each, and we've got 10
    items weighing 30, 31, 32, ... 39. Distribute them into buckets.

        use Algorithm::Bucketizer;

        my $b = Algorithm::Bucketizer->new( bucketsize => 100 );
        for my $i (1..10) {

t/2multsize.t  view on Meta::CPAN

for my $item (@items) {
    $b->add_item($item, $item);
}

my @buckets = $b->buckets();

is(join('-', $buckets[0]->items()), "30-31-32",
   "first bucket");

is(join('-', $buckets[1]->items()), "33",
   "second bucket");

is(join('-', $buckets[2]->items()), "34-35-36-37-38",
   "third bucket");

is(join('-', $buckets[3]->items()), "39",
   "fourth bucket");