왜 GO 테이블과 슬라이스 성능이 10 배 차이가 나는지

Question

방금 ​​Project Euler에서 23 번 문제를 해결했지만 map [int] bool과 [] bool의 성능면에서 큰 차이가 있음을 확인했습니다. 메인에서 다음

func divisorsSum(n int) int { 
    sum := 1 
    for i := 2; i*i <= n; i++ { 
     if n%i == 0 { 
      sum += i 
      if n/i != i { 
       sum += n/i 
      } 
     } 
    } 
    return sum 
} 

그리고는 다음과 같이 수행하십시오 :

func main() { 
    start := time.Now() 
    defer func() { 
     elapsed := time.Since(start) 
     fmt.Printf("%s\n", elapsed) 
    }() 

    n := 28123 
    abundant := []int{} 
    for i := 12; i <= n; i++ { 
     if divisorsSum(i) > i { 
      abundant = append(abundant, i) 
     } 
    } 

    sums := map[int]bool{} 
    for i := 0; i < len(abundant); i++ { 
     for j := i; j < len(abundant); j++ { 
      if abundant[i]+abundant[j] > n { 
       break 
      } 
      sums[abundant[i]+abundant[j]] = true 
     } 
    } 

    sum := 0 
    for i := 1; i <= 28123; i++ { 
     if _, ok := sums[i]; !ok { 
      sum += i 
     } 
    } 
    fmt.Println(sum) 
} 

이 코드는 내 컴퓨터에 450ms 소요

나는 숫자의 적절한 약수를 요약하는 기능이있다. 나는이 같은 부울의 조각 대신의지도 아래 메인 코드를 변경한다면 :

func main() { 
    start := time.Now() 
    defer func() { 
     elapsed := time.Since(start) 
     fmt.Printf("%s\n", elapsed) 
    }() 

    n := 28123 
    abundant := []int{} 
    for i := 12; i <= n; i++ { 
     if divisorsSum(i) > i { 
      abundant = append(abundant, i) 
     } 
    } 
    sums := make([]bool, n) 
    for i := 0; i < len(abundant); i++ { 
     for j := i; j < len(abundant); j++ { 
      if abundant[i]+abundant[j] < n { 
       sums[abundant[i]+abundant[j]] = true 
      } else { 
       break 
      } 
     } 
    } 
    sum := 0 
    for i := 0; i < len(sums); i++ { 
     if !sums[i] { 
      sum += i 
     } 
    } 
    fmt.Println(sum) 
} 

을 지금은 이전부터 속도의 1/10 이하 만 40ms가 소요됩니다. 나는지도가보다 빠른 룩업을해야한다고 생각했다. 여기서 성능 차이는 무엇입니까?

Answer 1

당신은 당신의 코드를 프로파일 링하고 볼 수 있지만, 일반적으로 두 가지 이유가 있습니다 : 당신이 원하는 크기로 두 번째 예에서는 sums을 미리 할당

1. 은. 이것은 결코 성장할 필요가 없다는 것을 의미하며,이 모든 것이 매우 효율적입니다. GC 압력이나 재 할당 등은 없습니다. 미리 원하는 크기로 맵을 생성하고 맵핑이 얼마나 개선되는지보십시오.

2. Go의 해시 맵의 내부 구현을 알지 못하지만 일반적으로 정수 인덱스를 사용하는 배열/슬라이스의 임의 액세스는 매우 효율적이며 해시 테이블은 오버 헤드를 추가합니다. 정수를 해시합니다 (더 나은 배포를 위해 그렇게 할 수도 있음).