단어들을 anagram 으로 분류하는 문제.

입력 자료는 일반적인 사전의 등재 단어 전체. 230,000 단어 정도가 보통이다. 이 정도의 입력 자료에 대해 존재하는 모든 Anagram을 "현실적인 시간 내"에 전부 출력해야 한다. 계산 방법에 따라 수십년이 걸릴 수도 있다.

Anagram

  • 같은 수의 같은 글자들로 이루어진 단어들의 집합.
  • abc, acb, cba, bac 는 모두 같은 anagram 에 있는 단어들.
  • aabb, abab, bbaa, baab 는 모두 같은 anagram 에 있는 단어들.

요구사항

  • 표준 입력으로 단어의 목록을 입력받는다. (따라서 키보드로 직접 입력할 수도 있다)
  • 입력 받은 단어의 목록을 anagram 으로 분류하여 표준 출력으로 출력한다. (따라서 화면을 통해 볼 수도 있다)
  • 출력시 같은 anagram에 속하는 단어끼리의 순서와 anagram 집합끼리의 순서는 의미가 없다.
  • 실행을 할 때에는 OS에서 지원되는 리디렉션을 통해(예컨대, ~cpp anagram.exe < in.txt > out.txt) 화일 입출력으로 할 수 있다.

Example

  • 입력

~cpp 
abc
aabb
acb
cdd
cba
baab
bac
dcd
xds

  • 출력

~cpp 
abc acb cba bac
aabb baab
cdd dcd
xds


입력 데이터

anagram words 건수
2284(http://zeropage.org/~mulli2/gsl-edit.txt)
20159(http://zeropage.org/~nuburizzang/input.dat)
172823(http://zeropage.org/pds/2002104113433/word.lst)

기타 해 볼 수 있는 것들

  • DTSTTCPW를 지키면서 완전한 TDD로 개발을 해본다. (마소 2002년 10월호 TDD기사 참조) 그 프로그램의 퍼포먼스는 어떠한가? TDD가 퍼포먼스가 낮은 프로그램을 만들어 내는가? 그렇다면 그걸 최적화 하는 것이 어려운가, 쉬운가? M. Feathers의 논문(http://www.xp2002.org/atti/MichaelFeathers--EmergentOptimizationinTestDrivenDesign.pdf)을 참고한다.
  • 개발시간은 얼마나 걸렸는가? 다른 언어로 그 언어적 특징을 살려서 개발해 보라. 그리고 이를 비교해 보라. 어느 것이 더 간단한가? 어느 것이 더 퍼포먼스가 좋은가?
  • 정보은닉이 얼마나 되었는가? David Parnas의 SeparationOfConcerns 논문을 읽어보라. 자신이 만든 프로그램을 좀 더 정보은닉도가 높게 만들 수 있겠는가? 어떤 모듈들로 나눌 수 있겠는가?
  • 발음이 비슷한 단어를 모으는 프로그램(이 알고리즘을 Soundex라고 한다)을 만들어 보라. Anagram 프로그램을 만들 때 사용했던 알고리즘을 얼마나 그대로 사용하는가? 재사용을 하는가? 뭐가 달라지는가?
  • 이런 과정을 통해 무엇을 배웠는가? 여기서 얻은 교훈을 앞으로 다른 프로그래밍을 할 때에 어떻게 적용할 수 있을까? 나에게 어떤 도움이 될까?

소스

만든 사람 소스 사용언어 수행시간 상대시간
["Lovelyboy^_^"] ClassifyByAnagram/인수 C++ 6.2초(17만단어) 1.77
신재동 ClassifyByAnagram/재동 Python . .
sun ClassifyByAnagram/sun Java 3.0초 (17만 단어) 1.38 (17만 단어)
상규 ClassifyByAnagram/상규 C++ 4.1초 (17만 단어) 0.95 (17만 단어)
JuNe ClassifyByAnagram/JuNe Python 3.4초 (17만 단어) 1.2 (17만 단어)
김재우 ClassifyByAnagram/김재우 Python, C#, Java 7초, 8.6초, 5.5초(17만단어) .
박응주 ClassifyByAnagram/박응주 Python 8.8초 (17만 단어) 1.35 (17만 단어)
1002 ClassifyByAnagram/1002 Python 7.09초 (17만 단어) .
zennith ClassifyByAnagram/zennith c . .
구근 ClassifyByAnagram/Passion Java 5초(17만 단어)

현재의 수행시각은 각기의 머신이 다르기 때문에 비교가 어렵습니다. 이에 간단한 자바 애플릿을 만들어 봤습니다. 자신이 측정한 시각을 애플릿에서 측정한 시각으로 나누면 어느정도는 상대적인 수치가 나올겁니다. 물론 각자의 브라우져에 내장된 혹은 연결된 JVM이 다르겠지만, 큰 범위에서 서로를 비교하는데엔 무리가 없으리라 생각됩니다. Test(http://zeropage.org/~sun/PowerTest.html), 소스(http://zeropage.org/moin/moin.cgi/ClassifyByAnagram_2fsun#head-219f097b78ba73a69e8b406ff09371cd97cdff63) (단위는 ms입니다) --sun
가장 교육적인 방법은 알고리즘의 컴플렉시티(Big-O-Notation?)를 비교하는 것이겠죠. 아마도 10초 이내인 이상 대부분 비슷하리라 생각합니다. --JuNe

어찌된 일인가..? 내 컴퓨터는 JVM이 느린가...?ㅡ.ㅡ --상규
몇번 reload 해서 적당한 값을 고르면 될텐데.. 하지만, 내가 해보기에도 상규 소스 빨랐음. :) --sun

파이썬에서 수행시간 체크는 어떻게 해야 하나요? 찾아 봤는 데 잘 못찾겠네요...ㅠ,ㅠ --재동
win32라면 ~cpp time.clock을 사용하면 좋다. 이 함수는 win32에서 ~cpp QueryPerformanceCounter를 사용한다. 해당 코드를 호출하기 전에 시각을 기록하고 반환됐을 때의 시각을 기록해서 그 차이를 구하면 수행시간이 나오겠지. 만약 전체 수행시간이 너무 짧다면 같은 코드를 1000번, 10000번 정도 실행하고 전체 걸린 시간을 횟수만큼 나누면 된다. 입력값에 따라 전체 시간의 증가 추이를 보려면 입력량을 10, 100, 1000 등으로 늘려가면서 얼마씩 시간이 더 걸리는가를 그래프로 그려보면 좋다(O of n, n^2, nlogn 등을 눈으로 볼 수 있다). 그리고 사양이 다른 컴퓨터 간에서 수행시간 비교는 lib/test/pystone.py를 실행시켜서 몇 pystone/sec가 나오는지 계산해서 상대비교를 하면 근사치가 나온다. 예를 들어, 내 컴퓨터는 20500 pystone/sec 정도 나오는데, 여기서 3초 걸린 작업이, 10000 pystone/sec 컴퓨터에서는 아마 6초 정도 걸릴 것이다. --JuNe
일단 작동하는 프로그램을 만들고, 이것이 제대로 작동하도록 만든 다음, 빠르게 만들라.

문제를 다 풀었고, 자신이 사용하는 알고리즘에 만족하는(출력까지 10초 이내에 가능하다면 어느 정도 만족해도 된다) 사람은 도서관에서 Jon Bentley의 Moa:ProgrammingPearls를 빌린다. 그리고 거기에 나온 알고리즘과 자신의 것을 비교해 본다. 만약 아직 직접 풀지 않았다면 그 책을 보지 말것을 권한다.
Retrieved from http://wiki.zeropage.org/wiki.php/ClassifyByAnagram
last modified 2021-02-07 05:22:53