U E D R , A S I H C RSS

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.0218 sec