json - 恒定时间搜索深度嵌套的 JSON 数据

Question

我有一个嵌套 JSON 的深层嵌套结构，如下所示。

{"object": 
    {
       "buffer_size": 10,
       "Databases":
       [
               {
                       "host": "localhost",
                       "user": "root",
                       "pass": "",
                       "type": "mysql",
                       "name": "go",
                       "Tables":
                       [
                               {
                                       "name": "testing",
                                       "statment": "teststring",
                                       "regex": "teststring ([0-9]+) ([A-z]+)",
                                       "Types": 
                                        [
                                           {
                                               "id": "1",
                                               "value": "string"
                                           },
                                           {
                                               "id": "2",
                                               "value": "string"
                                           },
                                           {
                                               "id": "3",
                                               "value": "string"
                                           }
                                        ]
                               }
                       ]
               }
       ]
    }
}

有没有一种方法可以使用恒定时间查找来搜索 Types 的 id 并仅针对那些具有扁平化 JSON 的结果获取过滤结果，以便输出:

{
  "Types": [
     {"id": 1, "value": "string"}
     {"id": 2, "value": "string"}
     {"id": 3, "value": "string"}
  ]
}

我知道我可以通过使用 for 循环来实现，但这需要很长时间。

Answer 1

这是我的做法:

type Id int

func (i *Id) UnmarshalJSON(b []byte) error {
    s := strings.Trim(string(b), `"`)
    id, err := strconv.Atoi(s)
    *i = Id(id)
    return err
}

type Type struct {
    Id    Id     `json:"id"`
    Value string `json:"value"`
}

func getTypes(b []byte) ([]Type, error) {
    var types = []Type{}
    var obj struct {
        Object struct {
            Databases []struct {
                Tables []struct {
                    Types []Type `json:"Types"`
                } `json:"Tables"`
            } `json:"Databases"`
        } `json:"object"`
    }
    if err := json.Unmarshal(b, &obj); err != nil {
        return nil, err
    }
    for _, d := range obj.Object.Databases {
        for _, t := range d.Tables {
            types = append(types, t.Types...)
        }
    }
    return types, nil
}

func showTypes(types []Type) error {
    return json.NewEncoder(os.Stdout).Encode(struct {
        Types []Type `json:"Types"`
    }{types})
}

func main() {
    types, err := getTypes([]byte(data))
    if err != nil {
        log.Fatal(err)
    }
    if err := showTypes(types); err != nil {
        log.Fatal(err)
    }
}

就恒定时间而言，这是不可能的。