U E D R , A S I H C RSS
ZeroWiki

Summation Of Four Primes/1002

1. Approach

맨 μ²˜μŒμ— 문제λ₯Ό 읽고 λŒ€λž΅ μ—°μŠ΅μž₯에 λ¬Έμ œμ—μ˜ 각 λ³€μˆ˜λ“€μ΄ λ λ§Œν•œ 뢀뢄듀을 λ³΄μ•˜λ‹€. 일단 μ†Œμˆ˜λ“€μ˜ 합이라 ν•˜κ³ , 4자리의 합이라고 ν•œλ‹€. λŒ€λž΅ pseudo code λ₯Ό λ‹€μŒμ™€ 같이 μž‘μ„±ν•΄λ³΄μ•˜λ‹€.

~cpp 
for eachGenNumberFour in GenNumbersFour
  isAllPrimeNumber:
      print eachGenNumberFour
      return
print "impossible"

GenNumbersFour = 합이 x 인 수 μ‘°ν•©λ¦¬μŠ€νŠΈ

합이 x 인 수 μ‘°ν•©λ¦¬μŠ€νŠΈμ— λŒ€ν•΄ μ–΄λ–»κ²Œ κ΅¬ν• κΉŒ κΆλ¦¬ν•˜λ˜μ€‘, μ†Œμˆ˜λ¦¬μŠ€νŠΈλ₯Ό λ¨Όμ € λ§Œλ“€κ³  μ†Œμˆ˜λ¦¬μŠ€νŠΈμ—μ„œ 4개λ₯Ό κ³¨λΌμ„œ 합을 κ΅¬ν•œ κ²°κ³Όκ°€ n 인지λ₯Ό λΉ„κ΅ν•˜λŠ” 방법이 더 빨리 κ΅¬ν˜„ν•  수 μžˆκ² κ΅¬λ‚˜λΌλŠ” 생각이 λ“€μ—ˆλ‹€. 이에 λŒ€ν•΄μ„œ TDD둜 진행.
~cpp 
class PrimeNumberList:
    def __init__(self,aNum):
        self.size = aNum
        self.resultTable = []
        self.createList()

    def createList(self):
        for i in range(2,self.size+1):
            if self.isPrimeNumber(i):
                self.resultTable.append(i)

    def isPrimeNumber(self,aNum):
        for eachValue in self.resultTable:
            if aNum % eachValue == 0:
                return False
        return True

    def getList(self):
        return self.resultTable

class PrimeNumberTest(unittest.TestCase):
    def testPrimeNumber(self):
        self.assertEquals([2,], PrimeNumberList(2).getList())
        self.assertEquals([2,3], PrimeNumberList(3).getList())
        self.assertEquals([2,3,5], PrimeNumberList(5).getList())
        self.assertEquals([2,3,5,7,11], PrimeNumberList(12).getList())
        self.assertEquals([2,3,5,7,11,13,17,19], PrimeNumberList(20).getList())
그리고 μ†Œμˆ˜λ¦¬μŠ€νŠΈλ‘œλΆ€ν„° 4개λ₯Ό κ΅¬ν•˜λŠ” 방법에 λŒ€ν•΄ μƒκ°ν•˜λ‹€. 맨 μ²˜μŒμ— λŒ€ν•΄μ„œλŠ” 쀑볡을 ν—ˆμš©ν•˜λ©΄ μ•ˆλ˜λŠ” 쀄 μ•Œκ³  κ΅¬ν˜„ν•˜μ˜€λ‹€. κ·ΈλŸ¬λ‹€κ°€ λ¬Έμ œμ—μ„œ 쀑볡을 ν—ˆμš©ν•œλ‹€λŠ” 사싀을 μ•Œκ³  λ‹€μ‹œ κ΅¬ν˜„.
~cpp 
def selectionFour(aList):
    sizeOfList = len(aList)
    for i in range(sizeOfList):
        for j in range(sizeOfList):
            for k in range(sizeOfList):
                for l in range(sizeOfList):
                    yield [aList[i],aList[j],aList[k],aList[l]]

2. full source 

~cpp 
from __future__ import generators
import psyco

class PrimeNumberList:
    def __init__(self,aNum):
        self.size = aNum
        self.resultTable = []
        self.createList()

    def createList(self):
        for i in range(2,self.size+1):
            if self.isPrimeNumber(i):
                self.resultTable.append(i)

    def isPrimeNumber(self,aNum):
        for eachValue in self.resultTable:
            if aNum % eachValue == 0:
                return False
        return True

    def getList(self):
        return self.resultTable

def selectionFour(aList):
    sizeOfList = len(aList)
    for i in range(sizeOfList):
        for j in range(sizeOfList):
            for k in range(sizeOfList):
                for l in range(sizeOfList):
                    yield [aList[i],aList[j],aList[k],aList[l]]

def main():
    n = int(raw_input('input number : '))
    primeNumberList = PrimeNumberList(n)
    for eachPrimeNumberSeq in selectionFour(primeNumberList.getList()):
        if sum(eachPrimeNumberSeq) == n:
            print eachPrimeNumberSeq
            return
    print "Impossible"

if __name__=="__main__":
    #unittest.main(argv=('','-v'))
    psyco.full()
    main()

3. 문제점 - 4초 이내에 닡이 λ‚˜μ˜€μ§€ μ•ŠλŠ”λ‹€.

μŠ€νŽ™μƒ 10000000 κ°’ λ‚΄μ—μ„œ 4초 이내에 닡이 λ‚˜μ™€μ•Ό ν•œλ‹€. 이에 λŒ€ν•΄μ„œ ν˜„μž¬μ˜ 병λͺ©μ§€μ μ— λŒ€ν•΄ profiling 을 ν•΄ λ³΄μ•˜λ‹€.
~cpp 
C:\WINDOWS\system32\cmd.exe /c python SummationOfFourPrimes.py
input number : 10000
[2, 2, 23, 9973]
         21065 function calls in 6.387 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.075    0.075    1.201    1.201 summationoffourprimes.py:13(createList)
        0    0.000             0.000          profile:0(profiler)
        1    5.103    5.103    6.387    6.387 summationoffourprimes.py:88(main)
        1    0.000    0.000    1.201    1.201 summationoffourprimes.py:8(__init__)
     9999    1.126    0.000    1.126    0.000 summationoffourprimes.py:18(isPrimeNumber)
        1    0.000    0.000    0.000    0.000 summationoffourprimes.py:24(getList)
    11061    0.083    0.000    0.083    0.000 summationoffourprimes.py:79(selectionFour)
        1    0.000    0.000    6.387    6.387 <string>:1(?)

~cpp 
C:\WINDOWS\system32\cmd.exe /c python SummationOfFourPrimes.py
input number : 50000
[2, 2, 3, 49993]
         60269 function calls in 24.926 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.428    0.428   19.348   19.348 summationoffourprimes.py:13(createList)
        0    0.000             0.000          profile:0(profiler)
        1    5.492    5.492   24.923   24.923 summationoffourprimes.py:88(main)
        1    0.000    0.000   19.348   19.348 summationoffourprimes.py:8(__init__)
    49999   18.920    0.000   18.920    0.000 summationoffourprimes.py:18(isPrimeNumber)
        1    0.000    0.000    0.000    0.000 summationoffourprimes.py:24(getList)
    10265    0.083    0.000    0.083    0.000 summationoffourprimes.py:79(selectionFour)
        1    0.003    0.003   24.926   24.926 <string>:1(?)


Hit any key to close this window...
λŒ€λΆ€λΆ„μ˜ μ‹œκ°„μ€ μ†Œμˆ˜ν…Œμ΄λΈ”μ„ μž‘μ„±ν•˜λŠ” 뢀뢄이 λœλ‹€. κ·Έλž˜μ„œ 이 뢀뢄에 λŒ€ν•΄μ„œ Seminar:PrimeNumberλ₯Ό μ°Έκ³ , μ΅œμ ν™”λœ μ•Œκ³ λ¦¬μ¦˜μœΌλ‘œ μˆ˜μ •ν•˜μ˜€λ‹€. 그리고 μ—­μ‹œ psyco λ₯Ό μ΄μš©ν•˜μ˜€λ‹€. κ·Έ κ²°κ³Ό, 10000000 κΈ°μ€€ 10초. κΈ°μ‘΄ μ•Œκ³ λ¦¬μ¦˜μ˜ 경우 50000번 κΈ°μ€€ 24초 이상.
~cpp 
C:\WINDOWS\system32\cmd.exe /c python SummationOfFourPrimes.py
input number : 10000
[2, 2, 23, 9973]
         11067 function calls in 5.417 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.000    0.000 summationoffourprimes.py:48(getList)
        1    0.000    0.000    5.417    5.417 <string>:1(?)
        1    0.000    0.000    0.013    0.013 summationoffourprimes.py:36(createList)
        1    0.000    0.000    0.013    0.013 summationoffourprimes.py:31(__init__)
    11061    0.094    0.000    0.094    0.000 summationoffourprimes.py:103(selectionFour)
        1    5.309    5.309    5.416    5.416 summationoffourprimes.py:112(main)
        1    0.013    0.013    0.013    0.013 summationoffourprimes.py:8(prime2)


Hit any key to close this window...

~cpp 
C:\WINDOWS\system32\cmd.exe /c python SummationOfFourPrimes.py
input number : 50000
[2, 2, 3, 49993]
         10271 function calls in 7.878 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.000    0.000 summationoffourprimes.py:48(getList)
        1    0.002    0.002    7.878    7.878 <string>:1(?)
        1    0.002    0.002    0.090    0.090 summationoffourprimes.py:36(createList)
        1    0.000    0.000    0.090    0.090 summationoffourprimes.py:31(__init__)
    10265    0.098    0.000    0.098    0.000 summationoffourprimes.py:103(selectionFour)
        1    7.688    7.688    7.876    7.876 summationoffourprimes.py:112(main)
        1    0.088    0.088    0.088    0.088 summationoffourprimes.py:8(prime2)


Hit any key to close this window...
μ΅œμ ν™” 이후 50000번 κΈ°μ€€μœΌλ‘œλŠ” 병λͺ©μ— λŒ€ν•œ 변별λ ₯이 μ—†λ‹€.

~cpp 
C:\WINDOWS\system32\cmd.exe /c python SummationOfFourPrimes.py
input number : 1000000
[2, 2, 13, 999983]
         470994 function calls in 26.768 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.000    0.000 summationoffourprimes.py:48(getList)
        1    0.040    0.040   26.768   26.768 <string>:1(?)
        1    0.062    0.062    2.708    2.708 summationoffourprimes.py:36(createList)
        1    0.000    0.000    2.708    2.708 summationoffourprimes.py:31(__init__)
   470988    5.244    0.000    5.244    0.000 summationoffourprimes.py:103(selectionFour)
        1   18.777   18.777   26.728   26.728 summationoffourprimes.py:112(main)
        1    2.646    2.646    2.646    2.646 summationoffourprimes.py:8(prime2)


Hit any key to close this window...
μ—¬κΈ°μ„œ selectionFour 의 κ²½μš°λŠ” percall 에 κ±Έλ¦¬λŠ” μ‹œκ°„μ€ 적닀. ν•˜μ§€λ§Œ, call 횟수 μžμ²΄κ°€ 470988 번으둜 λ§Žλ‹€. 이 뢀뢄에 λŒ€ν•΄μ„œ μΌμ’…μ˜ inlining 을 ν•˜μ˜€λ‹€.
~cpp 
C:\WINDOWS\system32\cmd.exe /c python SummationOfFourPrimes.py
input number : 1000000
(2, 2, 13, 999983)
         6 function calls in 16.671 CPU seconds

   Random listing order was used

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.000    0.000 summationoffourprimes.py:48(getList)
        1   13.736   13.736   16.540   16.540 summationoffourprimes.py:121(main2)
        1    0.067    0.067    2.804    2.804 summationoffourprimes.py:36(createList)
        1    2.738    2.738    2.738    2.738 summationoffourprimes.py:8(prime2)
        1    0.131    0.131   16.671   16.671 <string>:1(?)
        1    0.000    0.000    2.804    2.804 summationoffourprimes.py:31(__init__)


Hit any key to close this window...
10000000 건에 λŒ€ν•΄μ„œλŠ” 7.49 초 기둝 (profiler λ₯Ό μ΄μš©ν•  경우 μ†λ„μ €ν•˜κ°€ 있기 λ•Œλ¬Έμ— profiler λ₯Ό 끄고 psyco 만으둜 μ‹€ν–‰)


4. μ΅œμ ν™” 2μ°¨ : 문제 μ˜μ—­μ„ 쀄이기

비둝 inlining 을 μ‹œμΌ°μ§€λ§Œ μ—¬μ „ν•œ 것은 selectionFour 뢀뢄이닀. selectionFour κ°€ μ‹€ν–‰λ˜λŠ” 경우의 μ΅œμ•…μ˜ κ²½μš°λŠ” (n κΉŒμ§€μ˜ μ†Œμˆ˜κ°―μˆ˜)^4 κ°€ λœλ‹€. 이λ₯Ό μ’€ 더 smart ν•˜κ²Œ ν•  방법이 μ—†μ„κΉŒ.
μ†Œμˆ˜μ™€ κ΄€λ ¨ν•˜μ—¬ μ’€ 더 λ˜‘λ˜‘ν•˜κ²Œ 검색할 방법이 μ‘΄μž¬ν•˜λ¦¬λΌ μƒκ°ν•œλ‹€.
κ°€μž₯ κ°„λ‹¨ν•œ μ•„μ΄λ””μ–΄λ‘œ, 4번째 값에 λŒ€ν•΄μ„œλŠ” λ°”λ‘œ 계산을 ν•  μˆ˜κ°€ μžˆκ² λ‹€.

selectionFour λ₯Ό λ‹€μŒκ³Ό 같이 μˆ˜μ •ν•˜μ˜€λ‹€.
~cpp 
def selectionFour(aList,aNum):
    sizeOfList = len(aList)
    for i in range(sizeOfList):
        for j in range(sizeOfList):
            for k in range(sizeOfList):
                for l in range(sizeOfList):
                    expectedLastValue = aNum-(aList[i]+aList[j]+aList[k])
                    if expectedLastValue in aList:
                        yield [aList[i],aList[j],aList[k],expectedLastValue]
                    else:
                        break
inlining 을 ν•˜μ§€ μ•Šμ•˜μŒμ—λ„ 6.4μ΄ˆλŒ€λ₯Ό κΈ°λ‘ν•˜μ˜€λ‹€. inlining 을 ν•˜λ©΄ 5.7μ΄ˆλŒ€λ₯Ό κΈ°λ‘ν•œλ‹€.

5. μ΅œμ ν™” 3μ°¨ : PyRex

PyRex λŠ” Python μ½”λ“œλ₯Ό C μ½”λ“œλ‘œ μ „ν™˜ν•΄μ€€λ‹€. 이λ₯Ό 이용, C λͺ¨λ“ˆλ‘œ λ§Œλ“€μ–΄ μ»΄νŒŒμΌν•˜κ³  κ²°κ³Όλ₯Ό μ‹€ν–‰. μ˜μ™Έλ‘œ 7.x λŒ€λ‘œ, PsyCo λ₯Ό μΌμ„λ•Œλ³΄λ‹€ 였히렀 μ„±λŠ₯이 λ–¨μ–΄μ‘Œλ‹€. C μ½”λ“œλ₯Ό λ³΄λ‹ˆ 웬걸. μ „ν˜€ μ•Œμ•„λ³Όμˆ˜κ°€ μ—†λŠ” μ½”λ“œλ‹€. 차라리 κΉ¨λ—ν•˜κ²Œ 직접 μž‘μ„±ν•΄μ£ΌλŠ”κ²Œ μ„±λŠ₯ν–₯상 μƒμœΌλ‘œλŠ” μœ λ¦¬ν•˜κ² λ‹€λŠ” 생각.

6. ν•œ 일 λŒ€λΉ„ λŠλ‚€μ 

  • 이전에도 λŠλ‚€ μ μ΄μ§€λ§Œ, ν•œκ°€μ§€ 문제λ₯Ό μ•„μ£Ό 깊게 풀어보렀고 ν•˜λŠ” 것도 μ—¬λŸ¬κ°€μ§€λ‘œ ν•™μŠ΅μ΄ λœλ‹€.
  • 과정에 λŒ€ν•œ 기둝. 무언가 잘 관리가 μ•ˆλ˜λŠ” 상황이 μ˜€λž˜λ λ•Œ, ν•œ 일듀과 사싀듀을 κΈ°λ‘ν•΄λ³΄λŠ” 것은 μƒλ‹Ήνžˆ 도움이 λœλ‹€.

7. 더 ν–ˆμ—ˆμœΌλ©΄ ν•˜λŠ” 점. 보완

  • PrimeNumber 의 μ΅œμ ν™”μ— λŒ€ν•΄μ„œ. 기쑴에 μžˆλŠ” μ•Œκ³ λ¦¬μ¦˜μ΄ μ•„λ‹Œ, 직접 μ΅œμ ν™”λ₯Ό μ‹œλ„ν•΄λ³΄λŠ” κ²ƒμœΌλ‘œ 더 λ§Žμ€ 것을 ν•™μŠ΅ν•  수 있으리라. 이번의 κ²½μš°λŠ” 2μ‹œκ°„ μž‘μ—…μœΌλ‘œ κ³„νšμ„ μž‘μ•˜λ˜ κ΄€κ³„λ‘œ.
  • μ΄λŸ¬ν•œ 문제의 경우 νŠΉμ • μ•Œκ³ λ¦¬μ¦˜μ˜ μ•„μ£Ό μ΅œμ ν™” 된 결과물이 닡이기 λ³΄λ‹€λŠ”, 무언가 λ‹€λ₯Έ μ°¨μ›μ—μ„œ λ΄€μ„λ•Œ λ„ˆλ¬΄λ‚˜ 빨리 닡이 λ‚˜μ˜€κ²Œ λ˜λŠ” κ²½μš°μΌκ²ƒμ΄λΌ μΆ”μΈ‘. μ „ν˜€ λ‹€λ₯Έ λ°©λ²•μ˜ μ–΄ν”„λ‘œμΉ˜λ„ 생각해보고 μ‹Άλ‹€.
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:28:09
Processing time 0.0200 sec