time complexity of map lookups?

[Mark Summerfield]

Hi,

Does anyone know what the time complexity for map lookups is?
(Or where it is documented?)

Thanks!

--
Mark Summerfield, Qtrac Ltd, www.qtrac.eu
C++, Python, Qt, PyQt - training and consultancy
"Rapid GUI Programming with Python and Qt" - ISBN 0132354187
http://www.qtrac.eu/pyqtbook.html

[Serge Hulne]

The underlying structure appears to be a hash table ( see
http://groups.google.com/group/golang-nuts/browse_thread/thread/9286f3bc294e7ca7
), so the complexity should be constant O(1).

This would make them much faster than the STL maps (red-black-trees).

Serge.

[John Asmuth]

On Mar 16, 10:12 am, Serge Hulne <serge.hu...@gmail.com> wrote:
> The underlying structure appears to be a hash table ( seehttp://groups.google.com/group/golang-nuts/browse_thread/thread/9286f...

> ), so the complexity should be constant O(1).
>
> This would make them much faster than the STL maps (red-black-trees).

Thing to keep in mind with hash tables is that when collisions occur
another system has to be used. I think that go's maps have a flat list
to collect collisions. This is made nice by the fact that only a few
types are allowed to be used as keys, and they give these types very
good hashing functions, making collisions unlikely.

I know that when I wanted to use a hash table (gohash.googlecode.com)
to store some stuff with custom keys, I ended up not being very good
at writing hashing functions. To fix it, I collected collisions with
"github.com/petar/GoLLRB/llrb".

[Dave Cheney]

Hi Mark,

I whipped up this little test https://gist.github.com/873990 and as
far as I can tell, the difference between the three methods, array,
slice and map is unmeasurable. However, not being an expert at the
Benchmark package, or micro benchmarking Go, I think some peer review
is called for.

main.BenchmarkArrayAccess 2000000000 0 ns/op
main.BenchmarkSliceAccess 2000000000 0 ns/op
main.BenchmarkMapAccess 1000000000 0 ns/op

Cheers

Dave

On Thu, Mar 17, 2011 at 6:23 PM, Mark Summerfield <li...@qtrac.plus.com> wrote:
> Hi Serge,

>
> On Wed, 16 Mar 2011 07:12:34 -0700 (PDT)
> Serge Hulne <serge...@gmail.com> wrote:
>>
>>
>> On Mar 16, 11:34 am, Mark Summerfield <m...@qtrac.eu> wrote:
>> > Hi,
>> >
>> > Does anyone know what the time complexity for map lookups is?

>> > (Or where it is documented?)Hi

>> >
>>
>> The underlying structure appears to be a hash table ( see
>> http://groups.google.com/group/golang-nuts/browse_thread/thread/9286f3bc294e7ca7
>> ), so the complexity should be constant O(1).
>>
>> This would make them much faster than the STL maps (red-black-trees).
>

> Some hash implementations work in flat constant time O(1) as you say,
> and others in some time proportional to the number of items.
>
> But what I really want to know is this:
>
>    item := slice[n] // O(1) slice lookup
>    value := m[k]    // Even if O(1) it will be slower than slice
>                     // lookup: on average 2x slower, 3x slower or what?
>                     // I just want to get a feel for the difference.
>
> Thanks!
>
> PS I looked at the hashmap.c file but it didn't say.

>
> --
> Mark Summerfield, Qtrac Ltd, www.qtrac.eu

>    C++, Python, Qt, PyQt - training and consultancy

>        "Programming in Python 3" - ISBN 0321680561
>            http://www.qtrac.eu/py3book.html

>
> --
> Mark Summerfield, Qtrac Ltd, www.qtrac.eu

>    C++, Python, Qt, PyQt - training and consultancy

>        "Programming in Go" - http://www.qtrac.eu/gobook.html
>

[Mark Summerfield]

Hi Serge,

On Wed, 16 Mar 2011 07:12:34 -0700 (PDT)
Serge Hulne <serge...@gmail.com> wrote:
>
>

> On Mar 16, 11:34 am, Mark Summerfield <m...@qtrac.eu> wrote:
> > Hi,
> >
> > Does anyone know what the time complexity for map lookups is?
> > (Or where it is documented?)
> >
>

> The underlying structure appears to be a hash table ( see
> http://groups.google.com/group/golang-nuts/browse_thread/thread/9286f3bc294e7ca7
> ), so the complexity should be constant O(1).
>
> This would make them much faster than the STL maps (red-black-trees).

Some hash implementations work in flat constant time O(1) as you say,

and others in some time proportional to the number of items.

But what I really want to know is this:

item := slice[n] // O(1) slice lookup
value := m[k] // Even if O(1) it will be slower than slice
// lookup: on average 2x slower, 3x slower or what?
// I just want to get a feel for the difference.

Thanks!

PS I looked at the hashmap.c file but it didn't say.

--

Mark Summerfield, Qtrac Ltd, www.qtrac.eu

C++, Python, Qt, PyQt - training and consultancy

"Programming in Python 3" - ISBN 0321680561
http://www.qtrac.eu/py3book.html

--

Mark Summerfield, Qtrac Ltd, www.qtrac.eu

C++, Python, Qt, PyQt - training and consultancy

[Mark Summerfield]

Hi Dave,

On Thu, 17 Mar 2011 19:07:57 +1100
Dave Cheney <da...@cheney.net> wrote:
> Hi Mark,
>
> I whipped up this little test https://gist.github.com/873990 and as
> far as I can tell, the difference between the three methods, array,
> slice and map is unmeasurable. However, not being an expert at the
> Benchmark package, or micro benchmarking Go, I think some peer review
> is called for.
>
> main.BenchmarkArrayAccess 2000000000 0 ns/op
> main.BenchmarkSliceAccess 2000000000 0 ns/op
> main.BenchmarkMapAccess 1000000000 0 ns/op

I haven't looked into the benchmark package myself yet.

One thing your benchmark doesn't seem to account for is misses.

The code below _might_ do it assuming that the cost of setting up two
loops is outweighed. But it makes the assumption that the hit rate is
99%---for some use cases it might be 1% or 50% or anything. That's why
I'd rather have time complexity figures for the average and worst cases
than rely on benchmarks.

func BenchmarkMapAccess(b *testing.B) {
for i := 0; i < 990000; i++ {
r = Map[i]
}
for i := 0; i < 10000; i++ {
r = Map[-i]

[roger peppe]

On 17 March 2011 08:07, Dave Cheney <da...@cheney.net> wrote:
> Hi Mark,
>
> I whipped up this little test https://gist.github.com/873990 and as
> far as I can tell, the difference between the three methods, array,
> slice and map is unmeasurable. However, not being an expert at the
> Benchmark package, or micro benchmarking Go, I think some peer review
> is called for.

you have to iterate for b.N iterations (i'm slightly surprised that the
benchmarks terminated at all).

here's a version of your code that shows some more interesting
results: https://gist.github.com/874010

i get these results (divide the ns/op by 1e6 for the actual value):

array slice range 2000 1090022 ns/op
slice range 2000 1075931 ns/op
array 1000 1444934 ns/op
slice 1000 1466266 ns/op
array range 500 3493606 ns/op
map range 50 49293920 ns/op
map 5 289861600 ns/op

relative to the cheapest (slice range), they look like this:

slice range 1
array slice range 1.01
array 1.34
slice 1.36
array range 3.25
map range 45.8
map 269

that is, slice range is the cheapest (it doesn't have to
do the bounds checks); array range is expensive if
you don't slice it first because it copies the whole array.

map is much more expensive.

[Jan Mercl]

On Thursday, March 17, 2011 9:07:57 AM UTC+1, Dave Cheney wrote:

Hi Mark,

I whipped up this little test https://gist.github.com/873990 and as
far as I can tell, the difference between the three methods, array,
slice and map is unmeasurable. However, not being an expert at the
Benchmark package, or micro benchmarking Go, I think some peer review
is called for.

main.BenchmarkArrayAccess 2000000000         0 ns/op
main.BenchmarkSliceAccess 2000000000         0 ns/op
main.BenchmarkMapAccess 1000000000         0 ns/op

The benchmarks are broken (the 0 ns/op are absurd for the billion cycle numbers). Instead of e.g.:

func BenchmarkArrayAccess(b *testing.B) {

    for i := 0; i < 1000000; i++ {

        r = array[i]

    }

}

one has to write:

func BenchmarkArrayAccess(b *testing.B) {

    for i := 0; i < b.N; i++ {

        r = array[i]

    }

}

as is documented here:

http://golang.org/pkg/testing/

 

[Dave Cheney]

Thanks Roger and Jan for setting me straight.

[pww19...@gmail.com]

 The core of the core of the big data solutions -- Map
Download:
https://sourceforge.net/projects/pwwhashmap/files

在 2011年3月16日星期三 UTC+8下午6:34:06，Mark Summerfield写道：

[wenwei peng]

i am form china 
here is lots of people knows

 and documented is chinese

 the time comllexity is need you test youself

and  you will find it

--
You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/VUtUmxm2ubU/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.