map key, where key is an slice of interface{}

[Alfonso Vega]

Hi,

I couldn't find an efficient workaround for using a slice as a map key other than converting it to string as shown below. Any suggestions or ideas are welcome.

package main

import "fmt"

func main() {

s := []interface{}{"the end", 1969}

k := fmt.Sprintf("%#v", s)

m := map[string]int{k: 3}

fmt.Printf("%#v", m)

}

map[string]int{"[]interface {}{\"the end\", 1969}":3}

[rogerjd]

Explain what the slice key represents, how it will be used.

Roger

[Alfonso Vega]

The slice represents a cell of a sparse multi-dimensional table. The number of dimensions is unknown at compile time, and the type for each dimension could be string, int, float64 and even a struct.

Ideally, the conversion from key to the original slice should be easy to do.

[Dan Kortschak]

On Wed, 2014-06-04 at 22:27 -0700, Alfonso Vega wrote:
> The slice represents a cell of a sparse multi-dimensional table. The
> number of dimensions is unknown at compile time, and the type for each
> dimension could be string, int, float64 and even a struct.
> Ideally, the conversion from key to the original slice should be easy
> to do.

Brad gave an example that works for this kind of case using a linked
list key thus type Key struct { Val int; Rest interface{} }. If list is
only filled with other Keys (or nil), it can be used as a hashable key.

[Alfonso Vega]

Although I search for such answer from Brad, I didn't find anything relevant.

I would appreciate a working example.

[Dan Kortschak]

Here you go.

http://play.golang.org/p/HLPCw0vM27

[Alfonso Vega]

Thank you, that gave the necessary hints to answer the original question (a key can contain int, string, float64)

Here it is:

http://play.golang.org/p/BHyyVO7VWw

[Dan Kortschak]

That approach to slice reversal is rather expensive; I should not have been lazy and used an explicit fo loop on construction.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Dan Kortschak]

More parsimonious with allocations and loops.

http://play.golang.org/p/2pWWwa_UCj

[Steven Blenkinsop]

I wonder if it would be more efficient to have `type Key struct { Len int; Head List }; type List struct { Val interface{}; Rest interface{} }`. That way, if you have a length mismatch, it gets caught right away, and you can allocate up front for printing.

On Sat, Jun 7, 2014 at 2:44 AM, Dan Kortschak <dan.ko...@adelaide.edu.au> wrote:

More parsimonious with allocations and loops.

http://play.golang.org/p/2pWWwa_UCj

[David DENG]

I think in the map, hashcode works for similar things to Len, but for comparison itself, Len may help.

[Steven Blenkinsop]

Yeah, I guess if you have to traverse the structure in order to generate a meaningful hash code, doing it again for the comparison is likely of marginal benefit as long as you don't have too many collisions.

[Alfonso Vega]

Thanks all for your replies,

Benchmark time: http://play.golang.org/p/qNCFsM3wWo

go test -bench=.

BenchmarkKey0 1000000      1177 ns/op   // struct, not flexible

BenchmarkKey1  200000     13164 ns/op   // fmt.Sprintf

BenchmarkKey2  500000      5208 ns/op   // linked list, reversed

BenchmarkKey3  500000      5241 ns/op   // linked list

my conclusions:

* fmt.Sprintf is 11.18x slower than the most efficient (but not flexible) solution

* linked list is 4.4x slower than the most efficient (but not flexible) solution

* It turns out that the reversed linked list doesn't impact its performance

I didn't include Steven's suggestion as I didn't know how to implement MakeKey4 based on his idea.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.

[egon]

Is the table sparse or dense?

What would be an example content it can contain?

How often will the index be added to / removed from?

Is it for offline/online algorithms?

How does it need to be iterated?

How will it be processed?

+ egon

[Dan Kortschak]

No significant difference is  when the length of the key is short since hashing and map lookup would dominate bounds checks on the key slice. The reverse should be faster if you want to print the key members in the prder given since there is no reverse (again likely dominated by fmt calls).