perl ~~~ 익명의 배열을 가진 해쉬를 정렬하는 방법?
해쉬는 얼래 스칼라값을 가진다고 하더군요 ....
근데 레퍼런스의 형태로 참조를 하게되면 익명의 배열을 생성해서 여러개의 리스트 값을 가질수가 있다고 하는데
예를 든다면 ...........
%food_color = (
"Apple" => "red",
"Banana" => "yellow",
"Lemon" => "yellow",
"Carrot" => "orange"
); #스칼라값으로 가진 해쉬 가장 일반적인 형태죠
%food_color = (
"Apple" => ["red","blue"],
"Banana" => ["yellow","green"],
"Lemon" => ["yellow","red"],
"Carrot" => ["orange","pink"]
); #각각의 키값에 익명의 배열을 활당한것입니다.
어떻게 하다 보니 이런식의 해쉬를 사용할수 밖에 없게 되었는데...
문제는 저 익명의 배열값을 가진 해쉬 값을 정렬을 하는것이 문제가 되었습니다.
보통의 경우였다면 sort { length($food_color{$a}) <=> length($food_color($b})} keys %food_color;
이렇게 햇다면 값의 크기에 따라서 잘 정리가 되었을것입니다. 스칼라 값을 가졌다는 전제로...
하지면 저의 경우는 익명의 배열 즉 비교가 되는 대상이 value가 아닌 리스트가 되어 버린것입니다...
이것을 처리 할려면 저는 다시 리스트의 형태로 다 저장을 해버린 다음에 비교를 할가도 생각을 햇는데 너무 비효율적인것같기도 해서 혹시 다른 분들의 생각을 듣고 싶습니다......
잘 기억은 안나지만
잘 기억은 안나지만 cookbook 2nd에서 다음과 비슷한 방법을 썼던 것 같습니다.
@sortedkey = map { $_[0] } sort { $a[1] <=> $b[1] } map { ["$_", length(join("",$food_color{$_}))] } keys %food_color결국 리스트를 새로 만드는 군요
해쉬검색시간을 고려하면 리스트를 만드는 것이 꽤 효율적일 것 같습니다.
map과 sort에서 $_[0],
map과 sort에서 $_[0], $a[1], $b[1] 이 아니라 $_->[0], $a->[1], $b->[1] 일 것 같습니다. :-)
pung96님의 코드를 읽기 쉽게 들여쓰기하면 다음과 같습니다 :-)
my @sortedkey = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [ "$_", length(join("",$food_color{$_})) ] } keys %food_color;pung96님께서 소개해주신 코드의 스타일의 경우 아래서부터 위로... 즉 keys -> map -> sort -> map 순서로 코드를 읽으시면 됩니다. perl에서는 자주 쓰는 perlish한 표현이니 익숙해지시면 매우 편합니다. 비슷한 예로는 Schwartzian Transform 이 있습니다.
my @output_data = map { $_->[0] } sort { SORT COMPARISON USING $a->[1] AND $b->[1] } map { [ $_, EXPENSIVE FUNCTION OF $_ ] } @input_data;lse0101님 께서는 다음과 같은 값으로 정렬을 하고자 하시는 것 같은데...
"Apple" => ["red","blue"] 일 경우, 3(red) + 4(blue) = 7
"Banana" => ["yellow","green"] 일 경우, 6(yellow) + 5(green) = 11
이미 저장을 그런식으로 하셨기 때문에(그렇지 않으면 각 key에 대해 소팅시 비교할 값을 value로 가져야겠지요...) 리스트 형태로 저장해서 비교하는 것이 비효율적인것이 아니라 제일 효율적인 방법이지 않을까 사료됩니다. :-)
---------------------------
Smashing Watermelons~!!
Whatever Nevermind~!!
Kim Do-Hyoung Keedi
----
use perl;
Keedi Kim
그렇군요!!
그렇군요!!
pung96님...
글의 내용을 정확하게 이해 하고 계신것 같은데..
좀더 자세히 설명좀 해주실수 있나요?
map의 정확한 사용법은 물론 map-sort-map이라는 기법의 정확한 의미를 잘 파악을 못하겠습니다.
my @sortedkey
= map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [ "$_", length(join("",$food_color{$_})) ] }
keys %food_color;
my @sortedkey = map
상기 코드의 경우 1 -> 2 -> 3 -> 4 의 순서로 읽어야 합니다.
my @sortedkey = map { $_->[0] } #4 sort { $a->[1] <=> $b->[1] } #3 map { [ "$_", length(join("",$food_color{$_})) ] } #2 keys %food_color; #11: 우선 %food_colors 의 key 배열을 얻어오고
2: 1에서 얻어온 key 배열 각각에 대해 배열을 생성하는데 이 배열의 각각의 아이템은 익명배열을 뜻합니다. 이 익명 배열의 첫번째 아이템은 key, 두번째 아이템은 $food_color{key}에 해당하는 익명 배열의 아이템의 글자 총 개수가 되겠습니다.
3: 2에서 만든 배열의 아이템(익명배열)의 두번째 항목으로 정렬을 하고,
4. 마지막으로 정렬한 배열에서 아이템(익명배열)의 첫번째 항목(key)을 추려냅니다.
map의 용법은 perldoc -f map 으로 참고하시면 됩니다. :-)
---------------------------
Smashing Watermelons~!!
Whatever Nevermind~!!
Kim Do-Hyoung Keedi
----
use perl;
Keedi Kim
keedi님께서 말씀하신
keedi님께서 말씀하신 것 처럼
@sortedkey = map { $_->[0] } sort { $a->[1]<=>$b->[1] } map { ["$_", length(join("",$food_color{$_}))] } keys %food_color가 맞구요.
grep과 map두가지 용법을 익혀두시면 여러가지 편리한 코딩을 할 수 있습니다.
my @result = grep { /test/ } @list # 는 다음 foreach문을 줄여쓸수 있습니다. my @result=(); foreach (@list){ /test/ and push(@result,$_); }my @result = map { $_*3 } @list #는 다음과 같습니다. my @result=(); foreach(@list){ push(@result,$_*3); }직접 루프를 돌리는 것 보다 map이나 grep이 속도도 더 빠른 것으로 알고 있습니다. 아무래도 push가 무겁겠죠.
위 예제의 경우 풀어쓰면
my @templist =(); foreach(keys %food_color){ push(@templist,[$_,join("",$food_color{$_})); } @templist2 = sort {$a->[1]<=>$b->[1]} @templist; my @sortedlist=(); foreach(@templist2){ push(@sortedlist,$_->[0]); } # 버그가 다수 존재할 수 있습니다^^ # 위 예제를 완전히 풀어쓰기 위한 것이고 물론 실제로는 이렇게 엉터리로 코딩하지는 않겠지요보시는 바와같이 map을 쓰면 더 읽기쉽고 빠른 코드를 만들 수 있습니다.
코드가... my @sortedkey
코드가...
my @sortedkey
= map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [ "$_", length(join("",@{$food_color{$_}})) ] }
keys %food_color;
이게 맞는 코드가 아닐지.. 싶은데요?
제 생각에는 그래도...
my @sortedkey = sort { length(join("",@{$food_color{$a}})) <=> length(join("",@{$food_color{$b}})) } keys %food_color;
이게 더 빠르지 않을까 싶은데 아닌가요?
익명사용자 씀:제
실제로 프로파일링을 해보아야 정확하게 논할 수 있겠습니다만, 분명한 것은 위의 코드 조각의 경우 length와 join의 쌍(x2)이 평균(퀵소트이므로...) nlogn 회수 만큼 실행될 것입니다. 즉 평균 (length + join) x 2 x nlogn 이겠지요. 하지만 앞의 경우처럼 추가적으로 메모리(리스트)를 더 사용할 경우는 (length + join ) x n 번 실행을 보장받겠지요... :-)
---------------------------
Smashing Watermelons~!!
Whatever Nevermind~!!
Kim Do-Hyoung Keedi
----
use perl;
Keedi Kim
이런 멍청한!!!
이런 멍청한!!! 당연히 @{$food_color{$_}}가 맞겠지요.
돌려보지 않은게 문제였군요 ^^.
해쉬에서 읽는데 시간이 걸리기 때문에 더 오래 걸릴 것 같습니다.
해쉬에서 읽는데 걸리는 시간이 O(logN) 아닌가요? length와 join을 계속 부르는 것도 그렇구요.
물론 perl이 충분히 머리가 좋아서 충분히 최적화한다면 얘기가 다르겠지만
최적화 한다고 하더라도 length(join"",@{$food_color{$a})를 캐쉬한다면 결국 리스트를 새로 만드는 셈이 되는거죠.
누군가 직접 벤치마크를....ㅎㅎ
제가 질문을 했던 내용인데 제가 벤치 마크를 해야 할려나-_-;
제가 벤치 마크를 해야 할까요-_-;;
다들 수행 시간 계산 하는 방식이 책에서 나왔던 내용들이랑 똑같이 말씀 하시내요;;
저는 책에서 그런 부분은 그냥 패스-_-;;
수학과는 거리가 멀어서인지 먼말인지 모르겟어요 ㅜㅜ
급조로 밴치마크를
급조로 밴치마크를 해봤습니다.
#!/usr/bin/perl $t1 = time; print "=== STEP1 ===\n"; for(1..1000000){ $src{$_}=$_; } $t2=time; print "=== Step2 ===\n"; my @sorted = sort { $src{$a} <=> $src{$b} } %src; $t3=time; print "time : ".($t3-$t2)."\n"; print "=== Step3 ===\n"; my @sorted = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [$_,$src{$_}] } keys %src; $t4=time; print "time : ".($t4-$t3)."\n";결과는
단순히 해쉬검색만으로도 속도가 현저히 떨어지는 것을 볼수 있습니다.
앞에서 하는 것처럼 length, join등까지 사용한다면 속도가 더 차이가 날것입니다.
역시 perl이란것은 처리가 희안하군요;;;
저또한 테스트를 해봤는데요
테스트 방법은 time 스크립트 명령어로 했으며
서버는 www2.freebsdcity.org의 차대협님의 서버입니다.
테스트 결론은 이랬습니다.
my @sortedkey
= map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [ "$_", length(join("",$food_color{$_})) ] }
keys %food_color;
-------------------------------------------------------------
real 6m40.464s
user 5m54.288s
sys 0m21.965s
--------------------------------------------------------------
my @sortedkey
= sort {
length(join("",@{$food_color{$a}})) <=> length(join("",@{$food_color{$b}}))
} keys %food_color;
------------------------------------------------------------------------------------
real 6m41.974s
user 5m53.411s
sys 0m22.289s
-------------------------------------------------------------------------------------
테스트 결론은 이랬습니다.;;;
제가 만들어 놓은 스크립트가 문제가 있는것인지는 모르겠으나;;
기본적으로 제가 짜놓은 것은 메모리 상으로 해쉬안에 리스트를 참조가 되어 있는 상태입니다.
하지만 실질적으로 메모리에서만 있을때는 테스트가 되지 못햇으며 모두 파일을 열고 쓰고 하는 시간또한 포함이 되어 있기때문에 차이가 있을수 있습니다만 .....
결론적으로 스크립트 자체의 수행시간에는 큰 차이가 없었습니다.
수고하셨습니다.^^
여러가지 이유가
여러가지 이유가 있겠지만 일단 length의 종류가 몇가지 없기 때문일 꺼라고 생각합니다.
값들이 반복이 많을 경우 sort알고리즘의 루프 회수자체가 매우 줄어들기 때문입니다.
위의 제 결과를 length에 관한 것으로 바꾸었을때
순서대로 둘다 5초로 차이가 없어졌습니다.
length join "" ,@{$food_color{$a}}<=>length join "" ,@{$food_color{$b}}대신
join "" ,@{$food_color{$a}} cmp join "" ,@{$food_color{$b}}를 사용하면 어떨지 궁금하군요.
#!/usr/bin/perluse
#!/usr/bin/perl use Benchmark; print "=== STEP1 ===\n"; for(1..10000){ $src{$_}= rand()*1000; } timethese ( 100, { Step2 => sub { my @sorted = sort { $src{$a} <=> $src{$b} } keys %src; }, Step3 => sub { my @sorted = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [$_,$src{$_}] } keys %src; } });그냥 %src를 쓰면 안될것같아서 keys %src; 이걸로 하도록 바꾼후에 벤치마크툴을 돌려보았습니다.
=== STEP1 === Benchmark: timing 100 iterations of Step2, Step3... Step2: 14 wallclock secs (14.42 usr + 0.00 sys = 14.42 CPU) @ 6.93/s (n=100) Step3: 17 wallclock secs (16.27 usr + 0.00 sys = 16.27 CPU) @ 6.15/s (n=100)크게 차이나진 않습니다...
음.. 정신을
음.. 정신을 차려야겠군요.. 이것저것 실수가 많았습니다 죄송합니다.
결국 차이가 안나는 거네요. 해시를 바로 쓰는게 오히려 빠르군요.. 역시 펄의 해시가 대단하긴 합니다.
words 파일을 이용해
words 파일을 이용해 키값을 좀더 다양화 시켜봤습니다.
#!/usr/bin/perl use Benchmark; print "=== STEP1 ===\n"; my (@words,%src);; $file="/etc/dictionaries-common/words"; open F,$file; @words = <F>; close F; foreach (@words){ $src{$_} = $words[int(rand()*$#words)]; } timethese ( 10, { Step2 => sub { my @sorted = sort { $src{$a} cmp $src{$b} } keys %src; }, Step3 => sub { my @sorted = map { $_->[0] } sort { $a->[1] cmp $b->[1] } map { [$_,$src{$_}] } keys %src; } });=== STEP1 === 98569 Benchmark: timing 1 iterations of Step2, Step3... Step2: 1 wallclock secs ( 1.27 usr + 0.02 sys = 1.29 CPU) @ 0.78/s (n=1) (warning: too few iterations for a reliable count) Step3: 1 wallclock secs ( 1.43 usr + 0.01 sys = 1.44 CPU) @ 0.69/s (n=1) (warning: too few iterations for a reliable count)조금 차이가 나긴 하는데.. 왠지 억지로 차이를 만든듯 한 기분이.
아 그리고 혹시나 해서 rand도 넣고 이것 저것 해봤는데 그냥 words파일을 앞에서 부터
키, 밸류로 차례로 넣어도 동일 한 결과가 나오는 군요.
Schwartzian Transform 에서
Schwartzian Transform(참고문헌: Learning Perl Objects, References & Modules, Chap 07. Practical Reference Tricks) 에서 언급 한것 같이, 다음의 코드조각은 EXPENSIVE FUNCTION을 sort 내부에서 처리해야할 때 유용합니다. 이미 해쉬접근의 경우 펄 내부적으로 최적화가 되어 있을테고(물론 배열보다는 느리겠죠...), 해쉬접근+join+length가 고비용을 지불해야 하는 함수라고 보기는 힘들겠지요. :-)
my @output_data = map { $_->[0] } sort { SORT COMPARISON USING $a->[1] AND $b->[1] } map { [ $_, EXPENSIVE FUNCTION OF $_ ] } @input_data;예를 들어 단순히 length와 join이 아니라, 해당 값이 단어이고 그 단어로 파일 안에서 출현한 횟수를 sort안에서 비교 대상으로 쓴다고 한다면 sort안에서 평균 nlogn 회수 만큼 파일에 접근해서 해당 단어의 출현 빈도를 점검하겠죠. 이런 경우 미리 이 방법을 쓰면 최악(이라기 보다는 언제나...)의 경우 n번만 파일에 접근해서 처리할테고 메리트가 있다고 봅니다.
물론 이러한 방법의 경우 엄청난 크기의 데이터를 처리하는 경우 메모리가 두배로 필요하니 문제가 될 수 도 있겠지요. :-)
---------------------------
Smashing Watermelons~!!
Whatever Nevermind~!!
Kim Do-Hyoung Keedi
----
use perl;
Keedi Kim
댓글 달기