4
무차별 대입 (Brute Force) 접근법은 문제를 풀기위한 것이 아니며 연구에 도움이되는 것은 아닙니다. 나는 Project Euler 문제로 X에서 숫자 하나 하나를 "substring"숫자의 자릿수로 나눌 수있는 Y보다 하나 작은 숫자를 찾는 문제가 있습니다.python/pypy에서 하나 자식 (one-child) 번호 찾기를위한 무차별 대입 프로세스 최적화
이러한 것을 하나의 하위 번호라고합니다. 104는 하나의 자식 번호입니다. 하위 문자열 중 [1, 0, 4, 10, 04, 104]는 0 만 3으로 나눌 수 있습니다.이 질문은 10 * 17보다 적은 one-child 숫자의 양을 찾습니다. 올바른 접근법이 아닙니다. 그러나 나는 1 * 11 이전에 발생하는 한 어린이 수의 양을 알 필요가있는 이론이 있습니다.
나는 랩톱을 반나절 동안두고도이 번호를 찾지 못했습니다. 나는 Cython을 시도했다. 나는 C에 대해 아무것도 모르는 초보 프로그래머이다. 결과는 정말 나빴다. 나는 심지어 클라우드 컴퓨팅을 시도했지만 프로세스가 완료되기 전에 내 ssh 파이프는 항상 중단됩니다. 누군가가 나 10 ** 11이 문제에 대한 폭력 방법을 예비 성형에 대한 몇 가지 다른 접근법 또는 최적화를 파악하는 데 도움 수 있다면
, 그것은 크게 감상 할 수있다. 나는 많은 시간을 위해 작업을 한 것처럼
은 ...
는 정수론 또는이 문제에 대한 답에 나에게 조언을 빌려하지 마십시오, 나는 정말 결론에 도달 할 혼자서.## a one child number has only one "substring" divisable by the
## number of digits in the number. Example: 104 is a one child number as 0
## is the only substring which 3 may divide, of the set [1,0,4,10,04,104]
## FYI one-child numbers are positive, so the number 0 is not one-child
from multiprocessing import Pool
import os.path
def OneChild(numRange): # hopefully(10*11,1)
OneChild = []
start = numRange[0]
number = numRange[1]
## top loop handles one number at a time
## loop ends when start become larger then end
while number >= start:
## preparing to analayze one number
## for exactly one divisableSubstrings
numberString = str(start)
numDigits = len(numberString)
divisableSubstrings = 0
ticker1,ticker2 = 0, numDigits
## ticker1 starts at 0 and ends at number of digits - 1
## ticker2 starts at number of digits and ends +1 from ticker1
## an example for a three digit number: (0,3) (0,2) (0,1) (1,3) (1,2) (2,3)
while ticker1 <= numDigits+1:
while ticker2 > ticker1:
if int(numberString[ticker1:ticker2]) % numDigits == 0:
divisableSubstrings += 1
if divisableSubstrings == 2:
ticker1 = numDigits+1
ticker2 = ticker1
##Counters
ticker2 -= 1
ticker1 += 1
ticker2 = numDigits
if divisableSubstrings == 1: ## One-Child Bouncer
OneChild.append(start) ## inefficient but I want the specifics
start += 1
return (OneChild)
## Speed seems improve with more pool arguments, labeled here as cores
## Im guessing this is due to pypy preforming best when task is neither
## to large nor small
def MultiProcList(numRange,start = 1,cores = 100): # multiprocessing
print "Asked to use %i cores between %i numbers: From %s to %s" % (cores,numRange-start, start,numRange)
cores = adjustCores(numRange,start,cores)
print "Using %i cores" % (cores)
chunk = (numRange+1-start)/cores
end = chunk+start -1
total, argsList= 0, []
for i in range(cores):
# print start,end-1
argsList.append((start,end-1))
start, end = end , end + chunk
pool = Pool(processes=cores)
data = pool.map(OneChild,argsList)
for d in data:
total += len(d)
print total
## f = open("Result.txt", "w+")
## f.write(str(total))
## f.close()
def adjustCores(numRange,start,cores):
if start == 1:
start = 0
else:
pass
while (numRange-start)%cores != 0:
cores -= 1
return cores
#MultiProcList(10**7)
from timeit import Timer
t = Timer(lambda: MultiProcList(10**6))
print t.timeit(number=1)
왜 브 루트 포스 방식을 사용하고 있습니까? – Blender
그는 단지 문제의 작은 부분에 무차별 대입을 사용하고 있습니다. 그 다음에 실제 솔루션에 대한 숫자 이론이 적용됩니다. –
PyPy를 사용해도 10 ** 7을 통과하는 데 15 초 밖에 걸리지 않습니다. 이 일에 무차별 한 방법이 있다는 것은 정말로 의심 스럽습니다. – Blender