What is the best way to map slices or arrays?

[a.m...@abdn.ac.uk]

Hi,

I want to use Go's in-built map to define a mapping from a series of
integers to an integer.
Conceptually, this would be something like {5,2,12} -> 8, or
map[[]int]int. But since arrays
or slices cannot be used as keys to maps, I ended up using the string
representation of
the slice as the key to a map[string]int. This works, but probably it
is inefficient since one
needs to convert every slice to a string for any map lookup, and there
must be a better way
of doing this. Is there anything obvious I am missing?

Many thanks,

Alessandro.

[Sverre Rabbelier]

Heya,

On Fri, Apr 2, 2010 at 21:36, <a.m...@abdn.ac.uk> wrote:
> I want to use Go's in-built map to define a mapping from a series of
> integers to an integer.
> Conceptually, this would be something like {5,2,12} -> 8,

Why can you not map each of those individually? Something like:

keys := {5,2,12}
value := 8
for i in range(keys) {
mymap[i] = value
}

--
Cheers,

Sverre Rabbelier

[Steven]

(ignores non-Go code)

I think the point is to make map an ordered set of integers to get an integer, not to map each integer independently.  One thing you could do is something like:

http://ideone.com/bJIWjD8d

Something tells me this might not be any more efficient (likely less, but I don't know enough about it to say for sure).

[Steven]

However, I don't see why

key := []int{5, 3, 7}

m[string(key)]int

would be particularly inefficient, though it doesn't accept negative numbers.

[Corey Thomasson]

Perhaps you could do this with a multidimensional map. Some thing like
mymap[5][2][12]=8

> --
> To unsubscribe, reply using "remove me" as the subject.
>

[Steven]

Doesn't work when one of the intermediate maps is uninitialized, hence why my code has to do that explicitly.

Here's an example of an N number sequence key (again efficiency not considered):

http://ideone.com/qHLNlxm6

Apparently, the problem with arrays is that == is not defined, the reason being that it is uncertain whether to do shallow or deep equals.

[peterGo]

Alessandro,

You didn't provide sample code and weren't precise enough for me to
determine exactly what you mean by "string representation" e.g.
string([]int{5,2,12}), fmt.Sprintf([]int{5,2,12}), etc.

The Go string type is a UTF-8 variable-length encoding of a set of
Unicode code points. Unicode code point values, called runes in Go,
range from 0x0 to 0x10FFFF; however, not all code points in the range
are valid. The current implementation of Go accepts invalid code point
values within the range and maps all code points outside the range to
the Unicode replacement character 0xFFFD; implementation defined
behaviour can't always be relied upon.

Conversions of the form string([]int{5,2,12}) are not valid for all
int values, may be implementation dependent, and are time consuming.

Using fmt.Sprintf([]int{5,2,12}) is very time consuming.

A Go string type is represented internally as a UTF-8 encoded array of
bytes. You could take advantage of that to convert an int slice key to
something acceptable as a string key. For example,

func mapkey(k []int) string {
mk := make([]byte, len(k)*4)
for i := 0; i < len(k); i++ {
e := k[i]
for j := 0; j < 4; j++ {
mk[i*4+j] = byte(e >> uint((j * 8)))
}
}
return string(mk)
}

Peter

[Steven]

I'm assuming that should either be int32, or would require using unsafe.Sizeof(k[i])/8 or reflect.Typeof(k[i]).Size()/8, since there's no guarantee that int will be int32, even if it always will in the current implementation.

[peterGo]

Alessandro and Steven,

The example in Alessandro's message used []int{5,2,12} as a key.
Therefore, the mapkey function parameter k is also []int.

The int, int32, and int64 types are distinct. The int type is
guaranteed to be at least 32 bits. In all current implementations,
it's 32 bits.

The mapkey function could be written in a more portable fashion.

var sizeofInt = unsafe.Sizeof(int(0))

func mapkey(k []int) string {
mk := make([]byte, len(k)*sizeofInt)

for i := 0; i < len(k); i++ {
e := k[i]

for j := 0; j < sizeofInt; j++ {

mk[i*4+j] = byte(e >> uint((j * 8)))
}
}
return string(mk)
}

Peter

On Apr 3, 12:30 pm, Steven <steven...@gmail.com> wrote:

[a.m...@abdn.ac.uk]

Dear Peter and Steven,

Thanks for your replies. I am just using fmt.Sprintf for the
conversion right now. I will try Peter's mapkey function instead and
see how that goes as regards efficiency, and let you know. On another
note, my guess is that many people will have met with the same
problem, especially in scientific computing, and perhaps there should
be a way in go to define an Equality interface for the purposes of map
comparison. It would make maps much more useful.

Cheers,

Alessandro.

[a.m...@abdn.ac.uk]

Hi,

I wrote a simple benchmark to compare the performances of Peter's
mapkey function with a Sprint implementation. The results were (I am
running a Toshiba Portege laptop with a dua-core Intel 2.0 GHz
processor, Ubuntu 9.10 and the latest release of Go):

rwalk_test.BenchmarkMapkey 100 10104680 ns/op
rwalk_test.BenchmarkSprintkey 100 91562820 ns/op

So mapkey is 9 times faster than using Sprintf!

Here is the code for the benchmark:

package rwalk_test

import (
"testing"
"unsafe"
"fmt"
)

var sizeofInt = unsafe.Sizeof(int(0))
func mapkey(k []int) string {
mk := make([]byte, len(k)*sizeofInt)
for i := 0; i < len(k); i++ {
e := k[i]
for j := 0; j < sizeofInt; j++ {
mk[i*4+j] = byte(e >> uint((j * 8)))
}
}
return string(mk)
}

/* Return the string representation of a grid coordinate */
func strPos (pos []int) string {
return fmt.Sprint(pos)
}

func BenchmarkMapkey(b *testing.B) {
// var s string
a := []int{0,0,0}
for i := 0; i < b.N; i++ {
for j := 0; j < b.N; j++ {
for k := 0; k < b.N; k++ {
a[0] = i
a[1] = j
a[2] = k
mapkey(a)
}
}
}
}

func BenchmarkSprintkey(b *testing.B) {
// var s string
a := []int{0,0,0}
for i := 0; i < b.N; i++ {
for j := 0; j < b.N; j++ {
for k := 0; k < b.N; k++ {
a[0] = i
a[1] = j
a[2] = k
strPos(a)
}
}
}
}

Cheers,

Alessandro.

[a.m...@abdn.ac.uk]

Hi,

I wrote a simple benchmark to compare the performance of Peter's
mapkey function with that of an equivalent function using Sprint. Here
are the results,
in a Toshiba Portege laptop with Intel Duo Core 2.0GHz running Ubuntu
9.10, and the latest release of Go:

rwalk_test.BenchmarkMapkey 100 10104680 ns/op
rwalk_test.BenchmarkSprintkey 100 91562820 ns/op

So Peter's implementation is 9 times faster than using Sprint!

Here is the benchmark code:

---------------------------------
package rwalk_test

import (
"testing"
"unsafe"
"fmt"
)

var sizeofInt = unsafe.Sizeof(int(0))

func mapkey(k []int) string {
mk := make([]byte, len(k)*sizeofInt)
for i := 0; i < len(k); i++ {
e := k[i]
for j := 0; j < sizeofInt; j++ {
mk[i*4+j] = byte(e >> uint((j * 8)))
}
}
return string(mk)
}

/* Return the string representation of a grid coordinate */

func strPos (pos []int) string {
return fmt.Sprint(pos)
}

func BenchmarkMapkey(b *testing.B) {
// var s string
a := []int{0,0,0}
for i := 0; i < b.N; i++ {
for j := 0; j < b.N; j++ {
for k := 0; k < b.N; k++ {
a[0] = i
a[1] = j
a[2] = k
mapkey(a)
}
}
}
}

func BenchmarkSprintkey(b *testing.B) {
// var s string
a := []int{0,0,0}
for i := 0; i < b.N; i++ {
for j := 0; j < b.N; j++ {
for k := 0; k < b.N; k++ {
a[0] = i
a[1] = j
a[2] = k
strPos(a)
}
}
}
}

--------------------------------------------

Many thanks,

Alessandro.

On Apr 3, 9:02 pm, a.mo...@abdn.ac.uk wrote:

[peterGo]

Alessandro,

On an Intel Q8300, where Go used one core, running Ubuntu 9.10, my
tests had a similar 10-fold speed improvement.

I did notice that, for portability, mk[i*4+j] should have been
mk[i*sizeofInt+j], plus I made some other minor speed and style
improvements. My final test version is:

var sizeofInt = unsafe.Sizeof(int(0)) // import unsafe

func mapkey(k []int) string {
mk := make([]byte, len(k)*sizeofInt)

for i, n := range k {
i *= sizeofInt

for j := 0; j < sizeofInt; j++ {

mk[i+j] = byte(n >> uint((j * 8)))
}
}
return string(mk)
}

Peter