다른 값의 4 개의 숫자 목록이 있습니다. 그 지점까지 모든 숫자의 합계를 설명하는 두 번째 목록이 있습니다 (list1 = [1,3,2,5], list2 = [1,4,6,11] 인 경우). 수십만 개의 목록을 얻는 방법으로 모든 번호를 추가 할 필요가 없습니다. 정보가 이미 저장되어 있습니다.끊임없이 변화하는 목록을 가장 효율적으로 분할하여 합계를 계산하는 방법은 무엇입니까?
list1의 인덱스 0에 새 번호를 삽입하고 숫자 2라고 말하면 list2의 다음 값을 모두 업데이트해야합니다. 매우 큰 목록의 경우, 이것은 (두 번째 목록의 목적을 무너 뜨리는) 매우 많은 시간을 필요로합니다.
그러나 목록의 처음 절반의 합계를 기록하면 해당 합계 (list2 = [1,4,2,7])를 기준으로 list2를 계속할 수 있습니다. 이제 index = 0에 숫자 2를 삽입하면 처음 두 값과 기록 된 중간 값만 업데이트하면됩니다. 100,000 개의 숫자 목록을 보려면 이렇게하면 50,000 개의 값만 업데이트하면됩니다.
또한 목록의 3 분의 1 또는 10,000 개의 숫자마다 값을 기록 할 수 있습니다. 또는 중간에서 절반을 기록 할 수 있습니다 (이진 정렬과 비슷합니다. 이제는 내가 속한 하위 목록 만 업데이트하거나보아야합니다. 영향을 미침).
질문 :이 목록을 관리하는 가장 효율적인 방법은 무엇이며 어떻게 결정합니까? 반 은요? 3 분의 1? 세 단계, 이전 단계를 반으로 줄인 단계?
[이것은 이론적 인 질문이 아니라 실용적인 질문입니다. List2는 텍스트/그래픽을 레이아웃하고 렌더링하기위한 오프셋을 제공합니다. 나무는 내가 작업하고있는 맥락에서 실용적이지 않을 것이다. 나는 하나의 목록을 다뤄야 만한다. 주어진 합계/오프셋에 대한 액세스가 필요합니다. 또한, 나는 그것을 명확하게 제시하는 데 어려움을 겪고있다. 질문을 명확하게하거나 설명을 요청하십시오.]
어떤 종류의 나무 *를 원할 수도 있습니다. –
감사합니다. 그러나 내가 왜 내 접근 방식을 선택했는지 분명하지 않을 수도 있다는 것을 이해하는 동안 '왜'는 내 질문에 거의 한계를 두지 않습니다. 문맥을 고려할 때 나무는 실행 가능한 옵션이 아닙니다. – Jeff
목록에서 숫자를 삭제 하시겠습니까? 목록에 어떻게 접근합니까? 순서대로 트래버스하거나 인덱싱합니까? 목록에 얼마나 자주 새 번호를 삽입합니까? 얼마나 자주 목록에 액세스합니까? 목록의 숫자는 얼마나 큽니까? 목록은 얼마 동안 될 수 있습니까? – amdn