go语言的set和python中的set比较

[roboter]

刚刚接触了go语言，写了一些测试例子，go没有内置set，所以用map来处理set的操作，但是测试下来发现go的效率比python差了10多倍。

具体测试方法如下：

两个set，长度分别为60000和1300，执行100次or和and操作，python用时0.16秒，go用时1.96秒。

我怀疑我的map实现set方式有问题，特贴代码上来，请各位大侠指正。

go代码：

package main

import (

    "fmt"

    "time"

)

type Empty struct{

}

func set(arr []int) map[int]Empty{

    mapret := make(map[int]Empty)

    

    for _, ele := range arr {

        mapret[ele] = Empty{}

    }

    return mapret

}

func set_or(set1 map[int]Empty,set2 map[int]Empty) map[int]Empty {

    mapret := make(map[int]Empty,len(set1) + 10)

    

    for k,_ := range set1{

        if _,ok := set2[k];ok{

            mapret[k] = Empty{};

        }

    }

    return mapret;

}

func set_and(set1 map[int]Empty,set2 map[int]Empty) map[int]Empty {

    mapret := make(map[int]Empty,len(set1)+len(set2) + 1)

    

    for k, _ := range set1 {

        mapret[k] = Empty{};

    }

    for k,_ := range set2{

        if _,ok := mapret[k];!ok {

            mapret[k] = Empty{};

        }

    }

    return mapret

}

func main() {

    xs := make([]int,60000)

    for i := 1; i < 60000; i++ {

        xs = append(xs,i)

    }

    ys := make([]int,2500)

    for i := 1200; i < 2500; i++ {

        ys = append(ys,i)

    }

    

    x := set(xs)

    y := set(ys)

    fmt.Println(len(x),len(y))

    

    start := time.Now()

    for i := 1; i < 100; i++ {

        set_or(x,y)

        set_and(x,y)

    }

    endd := time.Now()

    xx := endd.Sub(start)

    fmt.Println(xx)

}

python代码：

#encoding:utf-8

import time

xs = set(range(1,60000))

x2s = set(range(1200,2500))

start = time.time()

for i in range(100):

x = xs & x2s

x = xs | x2s

end = time.time()

print end - start

[vuleetu]

On Mon, Jan 21, 2013 at 4:52 PM, roboter <kind...@gmail.com> wrote:

xs := make([]int,60000)

    for i := 1; i < 60000; i++ {

        xs = append(xs,i)

    }

xs长度变成了120000-1 了

[roboter]

xs长度没有变啊，长度打印出来是60000的

修改成xs := []int{}，效率也是很差的

2013/1/21 vuleetu <vul...@gmail.com>

--
--
官网: http://golang-china.org/
IRC: irc.freenode.net #golang-china
@golangchina
 
 
 

[steve wang]

这个测试不对。

1.如果你是要对比数据结构的效率，应该是go中的map对比python中的dictionary。python中的set应该是经过排序的，而且允许的操作也不同。

2.如果你是要对比做一件事情的效率，你就应该用要对比的语言中最合适做这个事情的数据结构和算法来进行对比。例如如果这些数据经过排序再求交集和并集，效率会高很多。

[steve wang]

我假设你要测试不同语言求并集和交集的速度，

我的测试结果：

go: 11ms

python:757ms

go的测试代码如下：

package main

import (

"fmt"

"sort"

"time"

)

func set_or(s1 []int, s2 []int) []int {

r := make([]int, len(s1)+len(s2))

index, i, j := 0, 0, 0

for {

f1 := i < len(s1)

f2 := j < len(s2)

if f1 && f2 {

x, y := s1[i], s2[j]

switch {

case x == y:

r[index] = x

index++

i++

j++

case x < y:

r[index] = x

index++

i++

default:

r[index] = y

index++

j++

}

} else if f1 {

for _, v := range s1[i:] {

r[index] = v

index++

}

break

} else {

for _, v := range s2[j:] {

r[index] = v

index++

}

break

}

}

return r[:index]

}

func set_and(s1 []int, s2 []int) []int {

size := len(s1)

if size < len(s2) {

size = len(s2)

}

r := make([]int, size)

index, i, j := 0, 0, 0

for {

if i >= len(s1) || j >= len(s2) {

break

}

x, y := s1[i], s2[j]

switch {

case x == y:

r[index] = x

index++

i++

j++

case x < y:

i++

default:

j++

}

}

return r[:index]

}

func main() {

xs := make([]int, 60000)

for i := 0; i < len(xs); i++ {

xs[i] = i + 1

}

sort.Sort(sort.IntSlice(xs))

ys := make([]int, 1300)

for i := 0; i < len(ys); i++ {

ys[i] = i + 1200

}

sort.Sort(sort.IntSlice(ys))

start := time.Now()

for i := 1; i < 100; i++ {

set_or(xs, ys)

set_and(xs, ys)

}

fmt.Println(time.Since(start))

}

On Monday, January 21, 2013 4:52:17 PM UTC+8, roboter song wrote:

[steve wang]

测试结果写错了，更正如下：

go: 11ms

python:76ms

[steve wang]

测试结果写错了，更正如下：

go: 11ms

python:76ms

On Monday, January 21, 2013 7:06:42 PM UTC+8, steve wang wrote:

[Ruiqi Hong]

Python的set也是用哈希表实现的

算法不一样，所以效率有区别

并且，Python的set操作实际是由C语言实现的

简单的Python脚本和Go效率对比，实际对比的是C语言和Go的效率

2013/1/21 steve wang <steve....@gmail.com>

--

[steve wang]

谢谢指正。

不过C语言和Go语言的哈希表实现性能会有这么大的差异？

[Ruiqi Hong]

PS: 插入0-60000的数据，Python和Go的插入时间相当（几十毫秒）。

差距可能发生在这60000个数据在union时生成新的Hash表时的消耗。

Python的Hash表中，记录了key的hash值，在遍历并插入新的Hash表时，不需要重新计算

而遍历Go的map并把key插入新的map时，需要重新计算key的hash值

不知是否因为这个影响的性能

2013/1/21 Ruiqi Hong <hong...@gmail.com>

[lihui]

应该是算法不同，针对不同的场景优化策略不同所致。

如果仅仅是hash重复计算的问题，差异应该在1倍之内。

而且我怀疑python的set不是像java一样用map模拟的，因为python的set版本明显比map版本快很多。

2013/1/21 Ruiqi Hong <hong...@gmail.com>

[lihui]

哦，后一个猜测我可能弄错了，因为我测试map版本的时候，用python迭代了。这就增加了python与C的代码运行时比重。

2013/1/21 lihui <ustc....@gmail.com>

[王新]

问一个愚笨的问题，既然python可以用c实现集合类的算法，那么go为什么不用呢？

[Ruiqi Hong]

我把map的hint值省略了以后，时间没有大的变化

而省略之后，插入60000个数据时，会把哈希表复制多次。但由于是内部复制，不会重新计算哈希。

以下是go的int哈希函数实现

void

runtime·memhash(uintptr *h, uintptr s, void *a)

{

byte *b;

uintptr hash;

b = a;

hash = M0 ^ *h;

while(s > 0) {

hash = (hash ^ *b) * M1;

b++;

s--;

}

*h = hash;

}

python的int哈希函数就是返回int自身

可以看出，go的要复杂的多。

[Ruiqi Hong]

问一个愚笨的问题，既然python可以用c实现集合类的算法，那么go为什么不用呢？

go和c一样都是编译语言。要做的应该是优化编译器和运行时，争取接近c的性能吧。

用c写的话，额。。。

[lihui]

go 的map就是C实现的吧

2013/1/21 王新 <wangxin...@gmail.com>

[Leo Jay]

2013/1/21 Ruiqi Hong <hong...@gmail.com>:

> 问一个愚笨的问题，既然python可以用c实现集合类的算法，那么go为什么不用呢？
>
> go和c一样都是编译语言。要做的应该是优化编译器和运行时，争取接近c的性能吧。
>
> 用c写的话，额。。。
>
>

我个人的感觉来说，go虽然是编译型的语言，但现在速度上并不及c/c++和java，在某些计算密集型的应用中，甚至不如python
（因为python的这部分代码是c实现的）。

我认为，这得从 go 的源头来找原因。go 是 google 那些人提出来的，对于 google 这种公司来说，代码的运行速度并不是非常重要的一件事。
最重要的是高并发和web开发的支持，所以在 go 语言里内建了 coroutine 的支持，而且你能在标准库里看到 template,
http 等的支持。最奇葩的是居然还有内建的 suffixarray。
至于运行速度嘛，差不多就行了。他们目前的主要精力并不在这。

--
Best Regards,
Leo Jay

[steve wang]

建议从技术角度讨论。

那些没有必要没有根据的臆测，对讨论技术问题并没有帮助。

 

[steve wang]

On Monday, January 21, 2013 10:33:06 PM UTC+8, Leo Jay wrote:

建议从技术角度讨论。

那些没有必要没有根据的臆测，对讨论技术问题并没有帮助。

 

[Linker]

其实是因为现在go并没有杀手级应用。故发展的重点还在于功能而不是可用性。可用性太细节，大牛现在还顾不上那个。增加功能呢，则更容易吸引观众。

在 13-1-21，Leo Jay<python...@gmail.com> 写道：

> --
> --
> 官网: http://golang-china.org/
> IRC: irc.freenode.net #golang-china
> @golangchina
>
>
>
>

--
从我的移动设备发送

*Regards,
Linker Lin
linker...@gmail.com*

[roboter]

谢谢各位大侠，了解了一点原因。

谢谢steve wang的思路代码，排序之后交集并集计算快了很多。但是如果把排序代码放到计算循环中，执行100次，这个效率就很差了。

[Monnand]

On 01/21/2013 04:21 AM, roboter wrote:
> xs长度没有变啊，长度打印出来是60000的

1. 没有细看你的代码从之前的几行来看，长度是会加倍的。参见以下代码：

package main

import (
"fmt"

)

func main() {
xs := make([]int, 100)
for i := 1; i< 100; i++ {
xs = append(xs, i)
}
fmt.Printf("len(xs) = %v\n", len(xs))
}

打印结果：

len(xs) = 199

具体参见append和make的文档

2. map本来就不是用来作为集合使用的。参见Profilling Go Programs:
http://blog.golang.org/2011/06/profiling-go-programs.html

That's reasonable when a map is being used to hold key-value pairs, but
not when a map is being used as a stand-in for a simple set.

3. map本身是哈西表，对应的python数据结构是dict。这两个数据结构的性能对比
参见这篇文章：

http://monnand.me/p/hashtable-bench/zhCN/

> 修改成xs := []int{}，效率也是很差的
>
> 2013/1/21 vuleetu <vul...@gmail.com <mailto:vul...@gmail.com>>

>
>
> On Mon, Jan 21, 2013 at 4:52 PM, roboter <kind...@gmail.com
> <mailto:kind...@gmail.com>> wrote:
>
> xs := make([]int,60000)
> for i := 1; i < 60000; i++ {
> xs = append(xs,i)
> }
>
>
>
> xs长度变成了120000-1 了
>
> --
> --
> 官网: http://golang-china.org/

> IRC: irc.freenode.net <http://irc.freenode.net> #golang-china
> @golangchina

[Risingv]

深表赞同，不仅毫无裨益，还误导人 

--
--
官网: http://golang-china.org/
IRC: irc.freenode.net #golang-china
@golangchina
 
 
 

--
Life is in chaos, keep struggling.

Personal blog: risingv.in

[Ruiqi Hong]

在 2013年1月21日下午8:48，Ruiqi Hong <hong...@gmail.com>写道：

PS: 插入0-60000的数据，Python和Go的插入时间相当（几十毫秒）。

差距可能发生在这60000个数据在union时生成新的Hash表时的消耗。

Python的Hash表中，记录了key的hash值，在遍历并插入新的Hash表时，不需要重新计算

而遍历Go的map并把key插入新的map时，需要重新计算key的hash值

不知是否因为这个影响的性能

抱歉，第一行弄错了。Python顺序插入60000个数据100次的时间是几十毫秒，Go插入60000个数据1次的时间是几十毫秒

Python乱序插入的时间约是顺序插入的2倍。可能与返回整数本身的哈希算法有关，顺序插入连续数字，几乎就是遍历数组。

如果key是字符串，go用的时间约是python的2.5倍。

[roboter]

哦，是的，长度会加倍的，我打印的长度是set之后的长度了。

我是想在go中找一下类似set的功能，go目前似乎支持不够好。

[Ruiqi Hong]

Python顺序插入60000个数据100次的时间约是1秒 ==！

[lihui]

你是手工迭代还是用数组来构造set？ 好像python的手工迭代很慢，一次迭代与一次coroutine调用的速度差不多，很坑爹。python只有用高层视角去写的时候才会高效。

import time

tmp=[]

for x in range(0,60000):

tmp.append(x)

s=time.time()

a=set()

k=True

for i in range(0,100):

#   a=set(tmp)

    a=set(xrange(0,60000))

    k=k and (99 in a)

t=time.time()-s

print t,k

结果：0.230999946594 True

我觉得应该不是我的机器比你强大这么多。

2013/1/22 Ruiqi Hong <hong...@gmail.com>

[minux]

2013/1/21 Leo Jay <python...@gmail.com>

我个人的感觉来说，go虽然是编译型的语言，但现在速度上并不及c/c++和java，在某些计算密集型的应用中，甚至不如python
（因为python的这部分代码是c实现的）。

如果你做计算密集型的程序，可以用gccgo，那个用gcc的后端，对于计算密集型的代码

很有效； llgo实现用LLVM，以后没准还可以用它。LLVM后端和gcc后端各有千秋。

我认为，这得从 go 的源头来找原因。go 是 google 那些人提出来的，对于 google 这种公司来说，代码的运行速度并不是非常重要的一件事。

后半句 不对。要是运行速度不重要，也没必要弄一个编译型语言了。

最重要的是高并发和web开发的支持，所以在 go 语言里内建了 coroutine 的支持，而且你能在标准库里看到 template,

goroutine != coroutine 

http 等的支持。最奇葩的是居然还有内建的 suffixarray。

因为godoc里的搜索功能用到了它。godoc不能依赖第三方包，所以就加入标准库了。

另外 我发现很奇怪啊，一方面批评Go的标准库太小，一方面它有可能用不到东西就说奇葩。

至于运行速度嘛，差不多就行了。他们目前的主要精力并不在这。

不是这样的。如果你提交一个CL说，2x faster map implementation，他们会很感兴趣的。

（当然，Go的map是为scalability优化的）

[Chen Yufei]

2013/1/23 minux <minu...@gmail.com>

这里的 scalability 指的是 map 中元素数量增加不会有性能下降么？