허용 한계 내에서 숫자의 가장 큰 문자열을 찾기 나는 다음과 같은 입력 한

Question

:

과제가

• 허용 오차 레벨 T
• 번호 N 수
• N 번호입니다 그 N 개의 숫자 내에서 가장 긴 기간을 찾아서 허용차 수준 내에있게하십시오. 보다 정확하게는 하위 문자열 l과 r의 왼쪽과 오른쪽 바운드와 두 경계 사이의 두 개의 별개 요소 a1과 a2이 주어지면 그 문자는 |a1 - a1| <= T이어야합니다. 어떻게 효율적으로이 작업을 수행 할 수 있습니까? 내 접근 방식은 다음과 같습니다.

  def getLength(T, N, numbers): 
  
      max_length = 1 
  
      for i in range(0, N-1): 
       start = numbers[i] 
       numlist = [start] 
  
       for j in range(i+1, N): 
        end = numbers[j] 
        numlist.append(end) 
  
        if (max(numlist) - min(numlist)) > T: 
         break 
  
        if (j-i+1) > max_length: 
         max_length = j-i+1 
  
      return max_length 
  

  편집 : 명확하게 말하십시오. 코드는 예상대로 작동합니다. 그러나, 그것은 충분히 효율적이지 않습니다. 더 효율적으로하고 싶습니다.

Answer 1

우선, 귀하의 코드가 귀하의 질문에 설명하는대로 작동하는지 확실하지 않습니다. 둘째, 12,000 개의 난수를 처리하는 데 걸리는 시간이 2 분 미만입니다.

관계없이, 그것은 새로운 요소가 추가 될 때마다 시간 numlist에 min() 및 max() 호출 하지 의해 가속화 될 수있다. 대신에 현재문을 사용하여 현재 최소값과 최대 값을 업데이트 할 수 있습니다. 여기

I 타이밍 성능을 위해 쓴 간단한 프레임 워크와 함께 수행되고 있음을 보여주는 코드 :

def getLength(T, N, numbers): 
    max_length = 1 

    for i in range(N-1): 
     start = numbers[i] 
     numlist = [start] 
     min_numlist = max_numlist = start # Added variables. 

     for j in range(i+1, N): 
      end = numbers[j] 
      numlist.append(end) 

# Inefficient - replaced. 
#   if (max(numlist) - min(numlist)) > T: 
#    break 

      # Update extremities. 
      if end > max_numlist: 
       max_numlist = end 
      if end < min_numlist: 
       min_numlist = end 

      if max_numlist-min_numlist > T: 
       break 

      if j-i+1 > max_length: 
       max_length = j-i+1 

    return max_length 


if __name__ == '__main__': 
    import random 
    import time 

    random.seed(42) # Use hardcoded seed to get same numbers each time run. 
    T = 100 
    N = 12000 
    numbers = [random.randrange(1000) for _ in range(N)] 
    starttime = time.time() 
    max_length = getLength(T, N, numbers) 
    stoptime = time.time() 
    print('max length: {}'.format(max_length)) 
    print('processing {:,d} elements took {:.5f} secs'.format(N, stoptime-starttime))