위키로그:2014/11/17 - 재귀를 사용하지 않고 해시 경로 탐색

From PGWiki

특정 참조를 탐색하는 코드가 필요했다.

물론 우리의 재귀법을 사용하는 방법이 있다지만 정말 쓰기가 싫었다.

그래서 재귀를 사용하지 않는 코드를 만들어봤다.

이런 작은 코드에 왜 이리 삽질을 길게한건지...

my $dummy =
{
    "A" =>
    {
        "AA" => "AAA",
        "AB" => "ABA",
    },
    "B" =>
    {
        "BA" => "BAA",
        "BB" => "BAB",
    },
    "C" =>
    {
        "CA" => ["CAA", "CAB"],
    },
    "D" =>
    {
        "DA" => ["DAA", {"DAB" => "DABA"}],
        "DB" => ["DBA", ["DBB", "DBC"]],
    }
};

my $out = undef;

my @branches =
(
    {
        branch => \$dummy,
        path   => "root"
    },
);

while (my $branch = pop(@branches))
{
    # 다른 가지가 없을 때 종료
    my $path = $branch->{path};
    my $ref = $branch->{branch};

    while (ref($$ref) ne "")
    {
        if (ref($$ref) eq "HASH")
        {
            my @keys = keys(%{$$ref});
            my $next = shift(@keys);

            foreach my $key (@keys)
            {
                printf "PUSH: %s{%s}\n", $path, $key;

                push (@branches,
                    {
                        branch => \$$ref->{$key},
                        path   => "$path.$key"
                    }
                );
            }

            $path .= ".$next";
            $ref   = \$$ref->{$next};
        }
        elsif (ref($$ref) eq "ARRAY")
        {
            for (my $i=1; $i<@{$$ref}; ++$i)
            {
                printf "PUSH: %s[%s]\n", $path, $i;

                push (@branches,
                    {
                        branch => \$$ref->[$i],
                        path   => "$path\[$i\]"
                    }
                );
            }

            $path .= "\[0\]";
            $ref   = \$$ref->[0];
        }
    }

    printf "LEAF: %s - %s\n", $path, $$ref;
}

1;

스택을 사용했으며, 실행 결과는 아래와 같다.

[root@Potato-Dev ~]$ perl test.pl
PUSH: root{D}
PUSH: root{C}
PUSH: root{B}
PUSH: root.A{AB}
LEAF: root.A.AA - AAA
LEAF: root.A.AB - ABA
PUSH: root.B{BB}
LEAF: root.B.BA - BAA
LEAF: root.B.BB - BAB
PUSH: root.C.CA[1]
LEAF: root.C.CA[0] - CAA
LEAF: root.C.CA[1] - CAB
PUSH: root.D{DA}
PUSH: root.D.DB[1]
LEAF: root.D.DB[0] - DBA
PUSH: root.D.DB[1][1]
LEAF: root.D.DB[1][0] - DBB
LEAF: root.D.DB[1][1] - DBC
PUSH: root.D.DA[1]
LEAF: root.D.DA[0] - DAA
LEAF: root.D.DA[1].DAB - DABA
[root@Potato-Dev ~]$ perl test.pl | grep LEAF
LEAF: root.A.AA - AAA
LEAF: root.A.AB - ABA
LEAF: root.B.BA - BAA
LEAF: root.B.BB - BAB
LEAF: root.C.CA[0] - CAA
LEAF: root.C.CA[1] - CAB
LEAF: root.D.DB[0] - DBA
LEAF: root.D.DB[1][0] - DBB
LEAF: root.D.DB[1][1] - DBC
LEAF: root.D.DA[0] - DAA
LEAF: root.D.DA[1].DAB - DABA

정렬이 필요하다면 다음 순서에 순회할 해시 키 집합을 @keys에 저장할 때 정렬해서 넣으면 땡...

Potatogim (토론) 2014년 11월 17일 (월) 15:57 (KST)



blog comments powered by Disqus