草庐IT

去映射大量键的性能不佳

coder 2024-07-13 原文

我最近发现 go maps 有非常奇怪的行为。用例是创建一组整数并让 O(1) 检查 IsMember(id int)。

当前的实现是:

func convertToMap(v []int64) map[int64]void {
    out := make(map[int64]void, len(v))
    for _, i := range v {
        out[i] = void{}
    }
   return out
}

type Group struct {
    members map[int64]void
}

type void struct{}

func (g *Group) IsMember(input string) (ok bool) {
    memberID, _ := strconv.ParseInt(input, 10, 64)      
    _, ok = g.members[memberID]
    return
}

当我对 IsMember 方法进行基准测试时，直到 600 万成员为止，一切看起来都很好。但除此之外， map 查找每次查找需要 1 秒!!

基准测试:

func BenchmarkIsMember(b *testing.B) {
    b.ReportAllocs()
    b.ResetTimer()
    g := &Group{}
    g.members = convertToMap(benchmarkV)

    for N := 0; N < b.N && N < sizeOfGroup; N++ {
        g.IsMember(benchmarkKVString[N])
    }
}

var benchmarkV, benchmarkKVString = func(size int) ([]int64, []string{
    v := make([]int64, size)
    s := make([]string, size)
    for i := range v {
        val := rand.Int63()
        v[i] = val
        s[i] = strconv.FormatInt(val, 10)
    }
return v, s
}(sizeOfGroup)

基准数字:

const sizeOfGroup  = 6000000
BenchmarkIsMember-8      2000000           568 ns/op          50 B/op          0 allocs/op

const sizeOfGroup  = 6830000
BenchmarkIsMember-8            1    1051725455 ns/op    178767208 B/op        25 allocs/op

任何超过 680 万的群体规模都会产生相同的结果。

有人可以帮我解释为什么会这样吗，在仍然使用 map 的同时可以做些什么来提高性能？

另外，我不明白为什么要分配这么多内存？即使耗时是因为碰撞然后遍历链表，也不应该有mem分配，我的思路是不是错了？

最佳答案

无需测量将 slice 转换为 map 的额外分配，因为我们只想测量查找操作。

我稍微修改了基准:

func BenchmarkIsMember(b *testing.B) {
    fn := func(size int) ([]int64, []string) {
        v := make([]int64, size)
        s := make([]string, size)

        for i := range v {
            val := rand.Int63()
            v[i] = val
            s[i] = strconv.FormatInt(val, 10)
        }

        return v, s
    }

    for _, size := range []int{
        6000000,
        6800000,
        6830000,
        60000000,
    } {
        b.Run(fmt.Sprintf("size=%d", size), func(b *testing.B) {
            var benchmarkV, benchmarkKVString = fn(size)

            g := &deltaGroup{}
            g.members = convertToMap(benchmarkV)

            b.ReportAllocs()
            b.ResetTimer()

            for N := 0; N < b.N && N < size; N++ {
                g.IsMember(benchmarkKVString[N])
            }
        })
    }
}

得到如下结果:

go test ./... -bench=. -benchtime=10s -cpu=1
goos: linux
goarch: amd64
pkg: trash
BenchmarkIsMember/size=6000000          2000000000               0.55 ns/op            0 B/op          0 allocs/op
BenchmarkIsMember/size=6800000          1000000000               1.27 ns/op            0 B/op          0 allocs/op
BenchmarkIsMember/size=6830000          1000000000               1.23 ns/op            0 B/op          0 allocs/op
BenchmarkIsMember/size=60000000         100000000                136 ns/op               0 B/op          0 allocs/op
PASS
ok      trash   167.578s

降级并不像您的示例中那么显着。

关于去映射大量键的性能不佳，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53423553/

去不sizeBenchmarkIsMembersectiongohashmapmapshash-collision

有关去映射大量键的性能不佳的更多相关文章

  1. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

  2. ruby - 检查字符串是否包含散列中的任何键并返回它包含的键的值 - 2

    我有一个包含多个键的散列和一个字符串，该字符串不包含散列中的任何键或包含一个键。h={"k1"=>"v1","k2"=>"v2","k3"=>"v3"}s="thisisanexamplestringthatmightoccurwithakeysomewhereinthestringk1(withspecialcharacterslike(^&*$#@!^&&*))"检查s是否包含h中的任何键的最佳方法是什么，如果包含，则返回它包含的键的值？例如，对于上面的h和s的例子，输出应该是v1。编辑:只有字符串是用户定义的。哈希将始终相同。 最佳答案

  3. ruby-on-rails - 只有当不是 nil 时才执行映射？ - 2

    如果names为nil，则以下中断。我怎样才能让这个map只有在它不是nil时才执行？self.topics=names.split(",").mapdo|n|Topic.where(name:n.strip).first_or_create!end 最佳答案 其他几个选项:选项1(在其上执行map时检查split的结果):names_list=names.try(:split,",")self.topics=names_list.mapdo|n|Topic.where(name:n.strip).first_or_create!e

  4. Ruby 的数字方法性能 - 2

    我正在使用Ruby解决一些ProjectEuler问题，特别是这里我要讨论的问题25(Fibonacci数列中包含1000位数字的第一项的索引是多少？)。起初，我使用的是Ruby2.2.3，我将问题编码为:number=3a=1b=2whileb.to_s.length但后来我发现2.4.2版本有一个名为digits的方法，这正是我需要的。我转换为代码:whileb.digits.length当我比较这两种方法时，digits慢得多。时间./025/problem025.rb0.13s用户0.02s系统80%cpu0.190总计./025/problem025.rb2.19s用户0.0

  5. ruby - Ruby 性能中的计时器 - 2

    我正在寻找一个用ruby​​演示计时器的在线示例，并发现了下面的代码。它按预期工作，但这个简单的程序使用30Mo内存(如Windows任务管理器中所示)和太多CPU有意义吗？非常感谢deftime_blockstart_time=Time.nowThread.new{yield}Time.now-start_timeenddefrepeat_every(seconds)whiletruedotime_spent=time_block{yield}#Tohandle-vesleepinteravalsleep(seconds-time_spent)iftime_spent

  6. ruby-on-rails - 如果条件与 &&，是否有任何性能提升 - 2

    如果用户是所有者，我有一个条件来检查说删除和文章。delete_articleifuser.owner?另一种方式是user.owner?&&delete_article选择它有什么好处还是它只是一种写作风格 最佳答案 性能不太可能成为该声明的问题。第一个要好得多-它更容易阅读。您future的自己和其他将开始编写代码的人会为此感谢您。 关于ruby-on-rails-如果条件与&&，是否有任何性能提升，我们在StackOverflow上找到一个类似的问题：

  7. ruby - 使用 jbuilder 创建具有动态哈希键的 JSON - 2

    这里我想输出带有动态组名的json而不是单词组@tickets.eachdo|group,v|json.group{json.array!vdo|ticket|json.partial!'tickets/ticket',ticket:ticketend}end@ticket是这样的散列{a:[....],b:[.....]}我想要这样的输出{a:[.....],b:[....]} 最佳答案 感谢@AntarrByrd，这个问题有类似的答案:JBuilderdynamickeysformodelattributes使用上面的逻辑我已经

  8. ruby - 如何找到我的 Ruby 应用程序中的性能瓶颈？ - 2

    我编写了一个Ruby应用程序，它可以解析来自不同格式html、xml和csv文件的源中的大量数据。我如何找出代码的哪些区域花费的时间最长？有没有关于如何提高Ruby应用程序性能的好资源？或者您是否有任何始终遵循的性能编码标准？例如，你总是用加入你的字符串吗？output=String.newoutput或者你会使用output="#{part_one}#{part_two}\n" 最佳答案 好吧，有一些众所周知的做法，例如字符串连接比“#{value}”慢得多，但是为了找出您的脚本在哪里消耗了大部分时间或比所需时间更多，您需要进行分

  9. STM32的HAL和LL库区别和性能对比 - 2

    LL库和HAL库简介LL：Low-Layer，底层库HAL：HardwareAbstractionLayer，硬件抽象层库LL库和hal库对比，很精简，这实际上是一个精简的库。LL库的配置选择如下：在STM32CUBEMX中，点击菜单的“ProjectManager”–>“AdvancedSettings”，在下面的界面中选择“AdvancedSettings”，然后在每个模块后面选择使用的库总结：1、如果使用的MCU是小容量的，那么STM32CubeLL将是最佳选择；2、如果结合可移植性和优化，使用STM32CubeHAL并使用特定的优化实现替换一些调用，可保持最大的可移植性。另外HAL和L

  10. Ruby:映射和注入(inject)之间的区别 - 2

    在此处阅读有关SO的各种解释，它们是这样描述的:map:Themapmethodtakesanenumerableobjectandablock,andrunstheblockforeachelement注入(inject):Injecttakesavalueandablock,anditrunsthatblockonceforeachelementofthelist.希望你明白为什么我觉得它们表面上看起来很相似。我什么时候会选择一个而不是另一个，它们之间有什么明显的区别吗？ 最佳答案 如果您认为inject也别名为reduce，这

随机推荐