MD5-Ring その３

関連する過去の記事

MD5-Ring - peanutsjamjamの日記

http://d.hatena.ne.jp/peanutsjamjam/20060218/p2

MD5-Ring その２ - peanutsjamjamの日記

http://d.hatena.ne.jp/peanutsjamjam/20080122/p1

MD5-Ring って幾つくらい存在するのだろうか？って考えてもわからないので、もっと小さなノード数で Ring の数を数えてみよう、というプログラムです。
どのノードがどのノードを指すか、っていう部分は、ランダムで。

ノード数を 10 万個に設定して、100 回実験してみたら、リングの数は平均で 6.19 個だそうな。思ったより少ない。

simulate(20, 1);

っていう部分を、

simulate(100000, 100);

に書き換えると、「ノード数を 10 万個に設定して、100 回実験」っていう意味になります。

ソースコード

#! /usr/bin/perl

use strict;
use warnings;
use integer;

##
## GLOBAL VARIABLES.
##

my @NODES;
my $PRINT_ALL_NODES_FLAG = 1; #  0:disable  1:enable
my $PRINT_RINGS_FLAG     = 1; #  0:disable  1:enable

##
## usage:
##  simulate( node count, repeat count);
##

simulate(20, 1);

exit(1);

sub simulate {
    my $node_cnt = shift;
    my $repeat_cnt = shift;

    my $total_ring = 0;
    for my $repeat (1 .. $repeat_cnt) {
        my $ring_cnt = 0;

        push @NODES, [int(rand($node_cnt)), 0] for (1 .. $node_cnt);
        print_all_nodes() if ($PRINT_ALL_NODES_FLAG);

        for my $i (0 .. $#NODES) {
            if ($NODES[$i][1] == 0) {
                $ring_cnt += walk($i);
            }
            set_two_if_one($i);
        }

        print "node count = $node_cnt\n";
        print "ring count = $ring_cnt\n";
        $total_ring += $ring_cnt;
        @NODES = ();
    }

    print "\n";
    print "\$repeat = $repeat_cnt\n";
    {
        no integer;
        print "average ring count ($total_ring/$repeat_cnt) = ",
         $total_ring/$repeat_cnt, "\n";
    }

}

sub walk {
    my $i = shift;
    my @ring;

    while (1) {
        if ($NODES[$i][1]==0) {
            $NODES[$i][1]++;
        } elsif ($NODES[$i][1]==1) {
            $NODES[$i][1]++;
            push @ring, $i;
        } else {
            if (scalar @ring) {
                print "(", join(' ', @ring), ")\n"
                    if ($PRINT_RINGS_FLAG);
                return 1;
            }
            last;
        }
        $i = $NODES[$i][0];
    }
    return 0;
}

sub set_two_if_one {
    my $i = shift;

    while ($NODES[$i][1] == 1) {
        $NODES[$i][1] = 2;
        $i = $NODES[$i][0];
    }
}


sub print_all_nodes {
    for my $i (0 .. $#NODES) {
        printf "%2d -> %2d\n", $i, $NODES[$i][0];
    }
}

TODO

• リングの長さやそのバラつき具合も報告するように。
• ノード数と繰り返し回数はコマンドラインからオプション指定できるように。
• もっと速く。(Perlじゃなく Cで)
• リングに含まれるノードと、含まれないノードの割合。