V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member  Sign In
The Go Programming Language
http://golang.org/
Go Playground
Go Projects
Revel Web Framework
moonheart

请教一个 leetcode 上 Go 的内存消耗的问题

  •  
  •   moonheart ·
    moonheart · Jun 25, 2022 · 2398 views
    This topic created in 1405 days ago, the information mentioned may be changed or developed.

    https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array

    给你一个含 n 个整数的数组 nums ,其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字,并以数组的形式返回结果。

    这道题两种解法, 第一种使用额外的数组来保存, 第二种直接在原始数组上存储:

    func findDisappearedNumbers1(nums []int) (res []int) {
    	x := make([]int, len(nums))
    	for _, num := range nums {
    		x[num-1] = num
    	}
    	for i, n := range x {
    		if n == 0 {
    			res = append(res, i+1)
    		}
    	}
    	return
    }
    
    
    func findDisappearedNumbers2(nums []int) (res []int) {
    	l := len(nums)
    	for _, num := range nums {
    		nums[(num-1)%l] += l
    	}
    	for i, n := range nums {
    		if n <= l {
    			res = append(res, i+1)
    		}
    	}
    	return
    }
    

    按理说, 第二种使用的内存会低一些, 使用 go benchmem 也可以看到 第一种 3 allocs/op, 第二种 2 allocs/op:

    goos: windows
    goarch: amd64
    cpu: AMD Ryzen 5 5600X 6-Core Processor
    Benchmark1-12           20885110                57.44 ns/op           88 B/op          3 allocs/op
    Benchmark2-12           21033442                58.17 ns/op           24 B/op          2 allocs/op
    

    但是在 leetcode 上提交的结果却是第一种消耗的内存更低些, 这是为什么呢?

    image image

    3 replies    2022-06-25 15:30:47 +08:00
    midasplus
        1
    midasplus  
       Jun 25, 2022 via Android
    看 leetcode 的耗时和内存没意义,时间空间复杂度是对的就行吧
    moonheart
        2
    moonheart  
    OP
       Jun 25, 2022
    @111qqz #1 懂了,谢谢大佬
    Itoktsnhc
        3
    Itoktsnhc  
       Jun 25, 2022
    leetcode 的耗时和内存仅在对比的时候有点用,有些时候题目还会加强数据集或者升级版本,都会导致性能有差距
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Solana   ·   2651 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 36ms · UTC 03:14 · PVG 11:14 · LAX 20:14 · JFK 23:14
    ♥ Do have faith in what you're doing.