jjzjj

algorithm - 戈朗 : benchmark Radix Tree Lookup

coder 2024-07-10 原文

为了练习 Golang，我一直在尝试对我编写的 Radix Tree 实现进行基准测试。

但我遇到了“我应该如何对其进行基准测试？”的问题。在下面的代码中显示了两种情况，或者说我想对 LookUp 函数进行基准测试的不同方式。

  • 情况 1:使用存在于树上的单个 byte slice 段，这意味着它将通过所有子节点等成功查找...

  • 情况 2:使用函数从树中的现有数据生成随机 slice ，这意味着它也将成功查找...

我知道花费的时间将取决于树的深度...我认为案例 2 是否接近现实世界的实现？

问题:哪种情况对基准测试更有效或更有用？

基准:

func BenchmarkLookUp(b *testing.B) {
    radix := New()
    insertData(radix, sampleData2)

    textToLookUp := randomBytes()

    for i := 0; i < b.N; i++ {
        radix.LookUp(textToLookUp) // Case 1 
        //radix.LookUp(randomBytes()) // Case 2
    }
}

func randomBytes() []byte {
    strings := sampleData2()
    return []byte(strings[random(0, len(strings))])
}

func sampleData2() []string {
    return []string{
        "romane",
        "romanus",
        "romulus",
        ...
    }
}

结果案例 1:

PASS
BenchmarkLookUp-4       10000000               146 ns/op
ok      github.com/falmar/goradix       2.068s
PASS
BenchmarkLookUp-4       10000000               149 ns/op
ok      github.com/falmar/goradix       2.244s

结果案例 2:

PASS
BenchmarkLookUp-4        3000000               546 ns/op
ok      github.com/falmar/goradix       3.094s
PASS
BenchmarkLookUp-4        3000000               538 ns/op
ok      github.com/falmar/goradix       4.481s

没有匹配时的结果:

PASS
BenchmarkLookUp-4       10000000               194 ns/op
ok      github.com/falmar/goradix       3.189s
PASS
BenchmarkLookUp-4       10000000               191 ns/op
ok      github.com/falmar/goradix       3.243s

最佳答案

如果您的基准测试是随机的，那么将很难比较不同实现之间从一次运行到下一次运行的性能。

相反，静态实现几个不同的基准案例，强调算法的不同领域。这些案例应该代表不同的场景，例如没有匹配项的情况(因为您已经有)，源数据中有很多项目将在查找中返回的情况，有很多项目的情况和只有 1 件商品将被退回，等等。

关于algorithm - 戈朗 : benchmark Radix Tree Lookup，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37245579/

algorithmbenchmarkBenchmarkLookUpsectiongoradixdata-structuresgotreeradix-tree

有关algorithm - 戈朗 : benchmark Radix Tree Lookup的更多相关文章

  1. javascript - 动态规划 : Code Wars: twice linear: algorithm times out - 2

    我在CodeWars中遇到了卡塔:https://www.codewars.com/kata/5672682212c8ecf83e000050/train/javascript这个想法是创建一个数字序列，其中每个数字都是按照以下两个公式隐式创建的:y=2x+1z=3x+1x是序列中的当前数字。从1开始，序列会像这样增长:sequence=[1]x=1y=2*1+1=3z=3*1+1=4leadingtosequence=[1,3,4]将它应用到下一个数字会导致:x=3y=2*3+1=7z=3*3+1=10leadingtosequence=[1,3,4,7,10]x=4y=2*4+1=

  2. 戈朗 "Log in to the site and download the xls file"？ - 2

    关闭。这个问题需要更多focused.它目前不接受答案。想改进这个问题吗？更新问题，使其只关注一个问题editingthispost.关闭3年前。Improvethisquestion告诉我如何使用Golang登录网站。下载xls文件是得到了，但是为了在Excel表格中有数据，需要登录网站。该站点位于公司的服务器上。如果你能告诉你怎么做。例如，我用来执行此操作的VBA代码。SetoFields=CreateObject("Scripting.Dictionary")WithoFields.Add"login","sdiscor".Add"password","sdiscor"EndWi

  3. arrays - 戈朗 : Could not understand how below code is executing - 2

    下面是我查询的代码:我有一个单维数组a当我打印a[0][0]时，我不明白为什么它返回字符a的ascii值:packagemainimport("fmt")funcmain(){a:=[3]string{"a","b","c"}fmt.Println(a[0][0])}输出:97 最佳答案 下面是如何打印ascii的代码示例a:=[3]string{"a","b","c"}for_,rune:=rangea{fmt.Println(rune)//Itwillprinta,b,c}因为你在你的代码中使用了[0][0]，所以它是等价的fo

  4. 戈朗 :which way is more efficient about using "for range" - 2

    typepath[]bytefunc(ppath)ToUpper(){fori,b:=rangep{if'a'在上面(这个例子是从“TheGoBlog”复制过来的)，如果ToUpper变成这样:func(ppath)ToUpper(){fori,_:=rangep{if'a'哪个会更有效率为什么？“TheGoBlog”对前一个说:“这里的ToUpper方法在forrange构造中使用两个变量来捕获索引和slice元素。这种形式的循环避免了在主体中多次写入p[i]。”什么意思？ 最佳答案 前者有更多的内存操作，即在b上:它在循环的第一

  5. 戈朗 : go command inside script? - 2

    我有一个用Golang编写的脚本，我不太明白。我想知道他为什么要在脚本里面写goserver.Start()？为什么不简单地编写server.Start？packagemainimport("github.com/miekg/dns""testing""time")constTEST_ADDR="127.0.0.1:9953"funcTestDNSResponse(t*testing.T){server:=NewDNSServer(&Config{dnsAddr:TEST_ADDR,})goserver.Start()//Allowsometimeforservertostarttim

  6. algorithm - 根据需要转移值(value)的算法[保留] - 2

    我需要一个算法，以最佳转移价值的基础上，需要的数额到其他帐户。例如，考虑到下面的帐户，什么是算法/psuedocode，可以在不导致正帐户不足的情况下，将有多余帐户的值转移到有不足帐户？Account1Balance:0Needed:.17853Account2Balance:0Needed:.1789524Account3Balance:0.296Needed:.4278Account4Balance:0Needed:.50231Account5Balance:0.1Needed:.17853Account6Balance:0Needed:.89Account7Balance:4.0

  7. 戈朗 : Is there a way to modify one of the multi-value return parameters in one line? - 2

    我正在尝试在Go中做一些相对简单的事情——将字符串转换为整数，然后将其加倍:myInt,_:=strconv.Atoi(args[1])doubleArg:=myInt*2由于Atoi()返回两个参数(整数和err)，我使用myInt,_:=来检索值的整数。我想将它加倍(因此是第二行)但不能在一行中完成所有操作:myInt,_:=strconv.Atoi(args[1])*2给我:multiple-valuestrconv.Atoi()insingle-valuecontext但是，根据我使用大多数其他语言的经验，必须在两行中执行此操作似乎有很多样板。这只是我必须处理的一个限制，还是有

  8. elasticsearch - 戈朗错误 "not enough arguments in call" - 2

    我刚接触golang。尝试通过golang实现批量上传到Elasticsearch。我正在使用golang库->https://github.com/olivere/elastic用于与Elasticsearch通信。此外，我正在尝试一段示例代码，但出现以下错误...suresh@BLR-245:~/Desktop/tools/golang/src$goinstallgithub.com/crazyheart/elastic-bulk-upload#github.com/crazyheart/elastic-bulk-uploadgithub.com/crazyheart/elasti

  9. multithreading - 戈朗 : can WaitGroup leak with go-routines - 2

    我计划实现一个go-routine并有一个sync.WaitGroup同步创建的go-routine的结尾。我基本上使用go创建了一个线程.所以它是这样的:main(){varwgsync.WaitGroupfor{gomyThread(wg)wg.Add(1)}wg.wait()}myThread(wgsync.WaitGroup){deferwg.Done()}我之前曾与pthread_create合作过在某些情况下确实无法创建线程。在这种情况下，是否可能针对上述gomyThread(wg)无法启动和/或运行wg.Done()例程的其余部分是否正常运行？如果是这样，将报告什么以及如

  10. 戈朗 : appending slices with or w/o allocation - 2

    Go的append()函数仅在给定slice的容量不足时分配新的slice数据(另请参见:https://stackoverflow.com/a/28143457/802833)。这可能会导致意外行为(至少对我这个golang新手来说):packagemainimport("fmt")funcmain(){a1:=make([][]int,3)a2:=make([][]int,3)b:=[][]int{{1,1,1},{2,2,2},{3,3,3}}common1:=make([]int,0)common2:=make([]int,0,12)//providesufficientcap

随机推荐