如何有效地展平地图？

Question

我的应用程序需要获取 map[string]interface{} 的大量嵌套实例并将它们变成扁平化地图。

例如：

{
                "foo": {
                    "jim":"bean"
                },
                "fee": "bar",
                "n1": {
                    "alist": [
                        "a",
                        "b",
                        "c",
                        {
                            "d": "other",
                            "e": "another"
                        }
                    ]
                },
                "number": 1.4567,
                "bool":   true
}

之后：

json.Unmarshal([]byte(input), &out)
result = Flatten(m.(map[string]interface{}))

变为：

{
                "foo.jim":      "bean",
                "fee":          "bar",
                "n1.alist.0":   "a",
                "n1.alist.1":   "b",
                "n1.alist.2":   "c",
                "n1.alist.3.d": "other",
                "n1.alist.3.e": "another",
                "number":       1.4567,
                "bool":         true,
}

目前我正在使用以下代码：

func Flatten(m map[string]interface{}) map[string]interface{} {
    o := map[string]interface{}{}
    for k, v := range m {
        switch child := v.(type) {
        case map[string]interface{}:
            nm := Flatten(child)
            for nk, nv := range nm {
                o[k+"."+nk] = nv
            }
        case []interface{}:
            for i := 0; i < len(child); i++ {
                o[k+"."+strconv.Itoa(i)] = child[i]
            }
        default:
            o[k] = v
        }
    }
    return o
}

此代码的内存效率非常低，当展开 ~800 张地图时，使用了 ~8 GiB 内存。我试过传递指针而不是副本，但这不会改变内存使用情况。我是否必须进行某种类型的手动内存管理？ Go 应该垃圾收集任何未使用的内存，但可能是我没有以某种方式释放它。

Answer 1

正如 Andy Schweig 在评论中建议的那样，传递一个在您遍历数据时更新的地图应该会显着减少内存使用量（注意：尚未测试）。类似于：

func Flatten2(prefix string, src map[string]interface{}, dest map[string]interface{}) {
    if len(prefix) > 0 {
        prefix += "."
    }
    for k, v := range src {
        switch child := v.(type) {
        case map[string]interface{}:
            Flatten2(prefix+k, child, dest)
        case []interface{}:
            for i := 0; i < len(child); i++ {
                dest[prefix+k+"."+strconv.Itoa(i)] = child[i]
            }
        default:
            dest[prefix+k] = v
        }
    }
}

在 the playground 试试这个。

Do I have to do some type of manual memory management?

Go 运行时旨在为您处理内存管理（请参阅 garbage collection 上的常见问题解答文章）。虽然垃圾收集器非常好，但它只能释放未使用的内存，并且您的原始例程在运行时创建了很多映射，这些映射在处理该级别的映射之前无法释放。

您可以通过 environmental variables or using the debug package 设置一些标志，但很少需要这些标志（并且它们可能会产生意想不到的后果）。

Any suggestions on where to further optimize this function?

如果不访问您的数据集以及了解您的要求和有关如何测量内存使用情况的信息，很难发表评论（这可能比看起来更复杂）。 Profiling 您的申请可能会为您提供一些改进方面的建议。一种可能的改进是使用 pre-allocated 切片而不是 dest 的映射（但我不知道你对结果做了什么，所以这可能不合适）。

Answer 2

我刚刚编写了一些代码来做到这一点，享受吧！

import (
    "container/list"
    "fmt"
    "strings"
)

type pair struct {
    key    []string
    isRoot bool
    value  interface{}
}

// FlattenMap flattens a given Map.
func FlattenMap(input map[string]interface{}) map[string]interface{} {
    var returnValue = make(map[string]interface{})

    var stack = list.New()
    stack.PushBack(pair{key: []string{}, isRoot: true, value: input})

    for {
        element := stack.Back()
        if element == nil {
            break
        }
        stack.Remove(element)

        thePair, ok := element.Value.(pair)
        if !ok {
            panic("can't cast element to pair")
        }

        switch v := thePair.value.(type) {
        // Handle generic maps.
        case map[string]interface{}:
            for key, val := range v {
                if thePair.isRoot {
                    stack.PushBack(pair{key: []string{key}, value: val})
                } else {
                    newKeys := append(thePair.key, key)
                    stack.PushBack(pair{key: newKeys, value: val})
                }
            }
        // Handle arrays.
        case []interface{}:
            lastKey := thePair.key[len(thePair.key)-1]
            for index, val := range v {
                newKeys := make([]string, len(thePair.key))
                itemsCopied := copy(newKeys, thePair.key)
                newKeys[itemsCopied-1] = fmt.Sprintf("%s[%d]", lastKey, index)
                stack.PushBack(pair{key: newKeys, value: val})
            }
        // Handle simple values.
        default:
            returnValue[strings.Join(thePair.key, ".")] = v
        }
    }

    return returnValue
}

如何有效地展平地图？

How to efficiently flatten a map?

garbage-collection

memory-leaks

pass-by-reference

go

flatten