当前位置：首页 > 文章列表 > Golang > Go问答 > 优化嵌套逻辑以提高性能并实现正常工作的方法

优化嵌套逻辑以提高性能并实现正常工作的方法

来源：stackoverflow 2024-02-15 14:48:22 0浏览收藏

哈喽！大家好，很高兴又见面了，我是golang学习网的一名作者，今天由我给大家带来一篇《优化嵌套逻辑以提高性能并实现正常工作的方法》，本文主要会讲到等等知识点，希望大家一起学习进步，也欢迎大家关注、点赞、收藏、转发! 下面就一起来看看吧！

问题内容

我有一个包含评论的数据库，每个评论都有一个 ID 和一个父 ID。目标只是以高效的方式将带有父 ID 的每个评论放在其父评论下。

我最初使用递归函数在 arranged 数组中搜索父注释，但性能很糟糕。我重构为使用指针来跟踪父母，这几乎完美地工作，但似乎最后要处理的评论总是被排除在输出之外。

在下面的示例中，“comment 1”应该是“comment 11”的子级，但它根本不包含在输出中。

package main

import (
  "encoding/json"
  "fmt"
)

// Comment from Database
type Comment struct {
  ID       string `json:"id""`
  ParentID string `json:"pid"`
  Text     string `json:"text"`
}

// NestedComment output
type NestedComment struct {
  Comment
  Children []NestedComment `json:"children,omitempty"`
}

func main() {
  // Some comment data from DB
  jsondata := `[{"id":"f1c3a838-f4b4-4ebd-bb1b-d3e4c0dce27d","pid":"6a162b3f-9341-46e9-95f7-dedc6cd06868","text":"comment 1"},{"id":"131cf4bb-1971-43a2-992f-2cbb042a4184","pid":"","text":"comment 2"},{"id":"4c93a789-ecab-4173-954c-b039cd3a9e17","pid":"131cf4bb-1971-43a2-992f-2cbb042a4184","text":"comment 3"},{"id":"c7974b6d-67e1-47d0-84fa-c78d51682df2","pid":"131cf4bb-1971-43a2-992f-2cbb042a4184","text":"comment 4"},{"id":"386c4439-4596-47c1-99bf-cb479055fe5a","pid":"","text":"comment 5"},{"id":"5ef0816e-ea13-4a7e-8009-e67ee08ef906","pid":"386c4439-4596-47c1-99bf-cb479055fe5a","text":"comment 6"},{"id":"96b0a536-602b-4f3f-a352-020f22cdfb18","pid":"","text":"comment 7"},{"id":"d0f11e98-deea-4fd5-becb-8f406ebcae83","pid":"96b0a536-602b-4f3f-a352-020f22cdfb18","text":"comment 8"},{"id":"bad87461-3cbf-4ecb-a8c7-36876b57d652","pid":"","text":"comment 9"},{"id":"e3ee6f90-495f-4348-9c29-bd6e15ec3b39","pid":"bad87461-3cbf-4ecb-a8c7-36876b57d652","text":"comment 10"},{"id":"6a162b3f-9341-46e9-95f7-dedc6cd06868","pid":"","text":"comment 11"},{"id":"041c7c2d-0688-491e-b6cd-899eac95bd3d","pid":"","text":"comment 12"},{"id":"5acdf3ff-345b-47a5-bd66-a6687a1441b7","pid":"041c7c2d-0688-491e-b6cd-899eac95bd3d","text":"comment 13"},{"id":"aaee2ae5-7e3a-4435-a094-83bf6b77abfb","pid":"","text":"comment 14"},{"id":"6108b28c-a7af-4c5a-a38c-c22db0d34b31","pid":"aaee2ae5-7e3a-4435-a094-83bf6b77abfb","text":"comment 15"},{"id":"1736393e-95b0-4f5d-a149-50fe52c28350","pid":"","text":"comment 16"},{"id":"b646f202-17aa-4af9-b8dc-c1d8ff3529ac","pid":"1736393e-95b0-4f5d-a149-50fe52c28350","text":"comment 17"},{"id":"a8827b1d-fdbc-41c2-bdb5-38e8b308dedc","pid":"b646f202-17aa-4af9-b8dc-c1d8ff3529ac","text":"comment 18"},{"id":"76e49597-6039-4cb5-a595-556ccc2e3c12","pid":"a8827b1d-fdbc-41c2-bdb5-38e8b308dedc","text":"comment 19"},{"id":"07dc4b90-65d3-4f75-8351-457305988235","pid":"76e49597-6039-4cb5-a595-556ccc2e3c12","text":"comment 20"},{"id":"2d4e838b-82df-4ca0-bf9b-f1dfb99d6763","pid":"07dc4b90-65d3-4f75-8351-457305988235","text":"comment 21"},{"id":"617c1760-0dca-409c-af2a-c614f0530e07","pid":"","text":"comment 22"},{"id":"712c0b7e-a9e4-40fd-ab78-c39b483b1435","pid":"617c1760-0dca-409c-af2a-c614f0530e07","text":"comment 23"},{"id":"e325094c-886e-42c9-bd59-fdd7a189b384","pid":"","text":"comment 24"},{"id":"f3b8b0f9-edef-4ee6-9555-42e8595f854c","pid":"e325094c-886e-42c9-bd59-fdd7a189b384","text":"comment 25"},{"id":"6e09a231-a2ee-4aa1-a898-57695e6fe153","pid":"","text":"comment 26"},{"id":"63e629d6-c0f9-4b36-ad96-e0c47cf8bb4e","pid":"6e09a231-a2ee-4aa1-a898-57695e6fe153","text":"comment 27"},{"id":"d7b698f1-8757-46db-a6e6-5141a481b42b","pid":"","text":"comment 28"},{"id":"a7e3d522-553c-44f1-befa-047bd94f0e59","pid":"","text":"comment 29"},{"id":"fe78ce24-c2c8-4d00-b96d-8b8be9ce0f06","pid":"","text":"comment 30"},{"id":"fabdccb5-a024-4476-bd51-7d55fb685c42","pid":"","text":"comment 31"},{"id":"608d0693-6e43-46a0-9e54-107da6adb109","pid":"fabdccb5-a024-4476-bd51-7d55fb685c42","text":"comment 32"}]`

  var comments []Comment

  err := json.Unmarshal([]byte(jsondata), &comments)
  if err != nil {
    panic(err)
  }

  arranged := ArrangeComments(comments, len(comments))

  arrangedjson, _ := json.MarshalIndent(arranged, "", "  ")

  fmt.Println(string(arrangedjson))
  fmt.Println("comments", len(comments), "arranged", recursiveCount(arranged))
}

func recursiveCount(arranged []NestedComment) int {
    count := len(arranged)
    for _, item := range arranged {
        count += recursiveCount(item.Children)
    }
    return count
}

// Nesting function -------------------------------------------------------------------------

func ArrangeComments(queue []Comment, count int) []NestedComment {
  var arranged []NestedComment

  // using pointers over a recursive search
  var refs []*NestedComment

  // some comments are orphaned, se we need a bail out
  tries := 0
  maxTries := 5
  prevPlacedLen := 0

  // IDs of placed comments
  var placed []string

  // while count is greater then length of placed
countloop:
  for count > len(placed) {
    // loop through queue
  queueloop:
    for _, item := range queue {

      // skip if already placed
      if len(placed) > 0 {
        for _, id := range placed {
          if id == item.ID {
            continue queueloop
          }
        }
      }

      // if parent is nil, add to arranged
      if item.ParentID == "" {
        arranged = append(arranged, NestedComment{
          Comment: item,
        })
        refs = append(refs, &arranged[len(arranged)-1])
        placed = append(placed, item.ID)
      } else {
        // if parent is not nil, loop through refs and add to children
      refloop:
        for _, ref := range refs {
          if ref.ID == item.ParentID {
            ref.Children = append(ref.Children, NestedComment{Comment: item})
            refs = append(refs, &ref.Children[len(ref.Children)-1])
            placed = append(placed, item.ID)
            break refloop
          }
        }
      }
    }

    // if no comments were placed, bail out after x tries
    if len(placed) == prevPlacedLen {
      if tries >= maxTries {
        break countloop
      }
      tries++
      break
    }

    prevPlacedLen = len(placed)
  }

  return arranged
}

更新；这让我更接近，但无法嵌套一些更深层次的嵌套评论。奇怪的是，它每次运行时都会产生不同的输出：

func ArrangeComments(comments []Comment) []NestedComment {
    // Map to hold references to NestedComment by their ID
    queue := make(map[string]*NestedComment)

    // Result slice
    var result []NestedComment

    // First, create all NestedComments and store references in the map
    for _, comment := range comments {
        nc := &NestedComment{Comment: comment}
        queue[comment.ID] = nc
    }

    // Second, loop through the map and add children to their parents
    for _, comment := range queue {
        if comment.ParentID != "" {
            parent := queue[comment.Comment.ParentID]
            if parent != nil {
                parent.Children = append(parent.Children, *comment)
            }
        }
    }

    // Third, loop through the map and add all root comments to the result slice
    for _, comment := range queue {
        if comment.ParentID == "" {
            result = append(result, *comment)
        }
    }

    return result
}

更新；我快速编写了一个 JavaScript 实现，它可以在给定相同示例数据的情况下生成正确的结果，但我无法弄清楚为什么此 JS 代码可以工作而 Go 代码不起作用。

const datajson = `[{"id":"f1c3a838-f4b4-4ebd-bb1b-d3e4c0dce27d","pid":"6a162b3f-9341-46e9-95f7-dedc6cd06868","text":"comment 1"},{"id":"131cf4bb-1971-43a2-992f-2cbb042a4184","pid":"","text":"comment 2"},{"id":"4c93a789-ecab-4173-954c-b039cd3a9e17","pid":"131cf4bb-1971-43a2-992f-2cbb042a4184","text":"comment 3"},{"id":"c7974b6d-67e1-47d0-84fa-c78d51682df2","pid":"131cf4bb-1971-43a2-992f-2cbb042a4184","text":"comment 4"},{"id":"386c4439-4596-47c1-99bf-cb479055fe5a","pid":"","text":"comment 5"},{"id":"5ef0816e-ea13-4a7e-8009-e67ee08ef906","pid":"386c4439-4596-47c1-99bf-cb479055fe5a","text":"comment 6"},{"id":"96b0a536-602b-4f3f-a352-020f22cdfb18","pid":"","text":"comment 7"},{"id":"d0f11e98-deea-4fd5-becb-8f406ebcae83","pid":"96b0a536-602b-4f3f-a352-020f22cdfb18","text":"comment 8"},{"id":"bad87461-3cbf-4ecb-a8c7-36876b57d652","pid":"","text":"comment 9"},{"id":"e3ee6f90-495f-4348-9c29-bd6e15ec3b39","pid":"bad87461-3cbf-4ecb-a8c7-36876b57d652","text":"comment 10"},{"id":"6a162b3f-9341-46e9-95f7-dedc6cd06868","pid":"","text":"comment 11"},{"id":"041c7c2d-0688-491e-b6cd-899eac95bd3d","pid":"","text":"comment 12"},{"id":"5acdf3ff-345b-47a5-bd66-a6687a1441b7","pid":"041c7c2d-0688-491e-b6cd-899eac95bd3d","text":"comment 13"},{"id":"aaee2ae5-7e3a-4435-a094-83bf6b77abfb","pid":"","text":"comment 14"},{"id":"6108b28c-a7af-4c5a-a38c-c22db0d34b31","pid":"aaee2ae5-7e3a-4435-a094-83bf6b77abfb","text":"comment 15"},{"id":"1736393e-95b0-4f5d-a149-50fe52c28350","pid":"","text":"comment 16"},{"id":"b646f202-17aa-4af9-b8dc-c1d8ff3529ac","pid":"1736393e-95b0-4f5d-a149-50fe52c28350","text":"comment 17"},{"id":"a8827b1d-fdbc-41c2-bdb5-38e8b308dedc","pid":"b646f202-17aa-4af9-b8dc-c1d8ff3529ac","text":"comment 18"},{"id":"76e49597-6039-4cb5-a595-556ccc2e3c12","pid":"a8827b1d-fdbc-41c2-bdb5-38e8b308dedc","text":"comment 19"},{"id":"07dc4b90-65d3-4f75-8351-457305988235","pid":"76e49597-6039-4cb5-a595-556ccc2e3c12","text":"comment 20"},{"id":"2d4e838b-82df-4ca0-bf9b-f1dfb99d6763","pid":"07dc4b90-65d3-4f75-8351-457305988235","text":"comment 21"},{"id":"617c1760-0dca-409c-af2a-c614f0530e07","pid":"","text":"comment 22"},{"id":"712c0b7e-a9e4-40fd-ab78-c39b483b1435","pid":"617c1760-0dca-409c-af2a-c614f0530e07","text":"comment 23"},{"id":"e325094c-886e-42c9-bd59-fdd7a189b384","pid":"","text":"comment 24"},{"id":"f3b8b0f9-edef-4ee6-9555-42e8595f854c","pid":"e325094c-886e-42c9-bd59-fdd7a189b384","text":"comment 25"},{"id":"6e09a231-a2ee-4aa1-a898-57695e6fe153","pid":"","text":"comment 26"},{"id":"63e629d6-c0f9-4b36-ad96-e0c47cf8bb4e","pid":"6e09a231-a2ee-4aa1-a898-57695e6fe153","text":"comment 27"},{"id":"d7b698f1-8757-46db-a6e6-5141a481b42b","pid":"","text":"comment 28"},{"id":"a7e3d522-553c-44f1-befa-047bd94f0e59","pid":"","text":"comment 29"},{"id":"fe78ce24-c2c8-4d00-b96d-8b8be9ce0f06","pid":"","text":"comment 30"},{"id":"fabdccb5-a024-4476-bd51-7d55fb685c42","pid":"","text":"comment 31"},{"id":"608d0693-6e43-46a0-9e54-107da6adb109","pid":"fabdccb5-a024-4476-bd51-7d55fb685c42","text":"comment 32"}]`

const queue = JSON.parse(datajson)

const result = []

const queueMap = new Map(queue.map(item => [item.id, item]))

for (const item of queue) {
  if (item.pid !== '') {
    const parent = queueMap.get(item.pid)
    if (parent) {
      if (!parent.children) {
        parent.children = []
      }
      parent.children.push(item)
    }
  }
}

for (const [_, value] of queueMap) {
  if (value.pid === '') {
    result.push(value)
  }
}

function recursiveCount(res) {
  let count = res.length
  res.forEach(item => {
    if (item.children) {
      count += recursiveCount(item.children)
    }
  });
  return count
}


console.log(JSON.stringify(result, null, 2))
console.log("comments", queue.length, "arranged", recursiveCount(result))

可运行的 Go 示例：https://gist.github.com/dlford/9e66069cfc7fb9afc649c5e3dc650083

可运行的 JS 示例：https://gist.github.com/dlford/f6f4a383a99f65659895ed51d1a4b651

Go 代码输出（参见底部的计数）：https://gist.github.com/dlford/302c4db939c21d15132848368caa01ec

JS 代码输出（参见底部的计数）：https://gist.github.com/dlford/60ab49d0466c957c7745059022e27e09

正确答案

问题是 NestedComment 中的 Children 也需要存储为指针。

工作示例：

package main

import (
    "encoding/json"
    "fmt"
)

// Comment from Database
type Comment struct {
    ID       string `json:"id"`
    ParentID string `json:"pid"`
    Text     string `json:"text"`
}

// NestedComment output
type NestedComment struct {
    Comment
    Children []*NestedComment `json:"children,omitempty"`
}

func main() {
    // Some comment data from DB
    jsondata := `[{"id":"f1c3a838-f4b4-4ebd-bb1b-d3e4c0dce27d","pid":"6a162b3f-9341-46e9-95f7-dedc6cd06868","text":"comment 1"},{"id":"131cf4bb-1971-43a2-992f-2cbb042a4184","pid":"","text":"comment 2"},{"id":"4c93a789-ecab-4173-954c-b039cd3a9e17","pid":"131cf4bb-1971-43a2-992f-2cbb042a4184","text":"comment 3"},{"id":"c7974b6d-67e1-47d0-84fa-c78d51682df2","pid":"131cf4bb-1971-43a2-992f-2cbb042a4184","text":"comment 4"},{"id":"386c4439-4596-47c1-99bf-cb479055fe5a","pid":"","text":"comment 5"},{"id":"5ef0816e-ea13-4a7e-8009-e67ee08ef906","pid":"386c4439-4596-47c1-99bf-cb479055fe5a","text":"comment 6"},{"id":"96b0a536-602b-4f3f-a352-020f22cdfb18","pid":"","text":"comment 7"},{"id":"d0f11e98-deea-4fd5-becb-8f406ebcae83","pid":"96b0a536-602b-4f3f-a352-020f22cdfb18","text":"comment 8"},{"id":"bad87461-3cbf-4ecb-a8c7-36876b57d652","pid":"","text":"comment 9"},{"id":"e3ee6f90-495f-4348-9c29-bd6e15ec3b39","pid":"bad87461-3cbf-4ecb-a8c7-36876b57d652","text":"comment 10"},{"id":"6a162b3f-9341-46e9-95f7-dedc6cd06868","pid":"","text":"comment 11"},{"id":"041c7c2d-0688-491e-b6cd-899eac95bd3d","pid":"","text":"comment 12"},{"id":"5acdf3ff-345b-47a5-bd66-a6687a1441b7","pid":"041c7c2d-0688-491e-b6cd-899eac95bd3d","text":"comment 13"},{"id":"aaee2ae5-7e3a-4435-a094-83bf6b77abfb","pid":"","text":"comment 14"},{"id":"6108b28c-a7af-4c5a-a38c-c22db0d34b31","pid":"aaee2ae5-7e3a-4435-a094-83bf6b77abfb","text":"comment 15"},{"id":"1736393e-95b0-4f5d-a149-50fe52c28350","pid":"","text":"comment 16"},{"id":"b646f202-17aa-4af9-b8dc-c1d8ff3529ac","pid":"1736393e-95b0-4f5d-a149-50fe52c28350","text":"comment 17"},{"id":"a8827b1d-fdbc-41c2-bdb5-38e8b308dedc","pid":"b646f202-17aa-4af9-b8dc-c1d8ff3529ac","text":"comment 18"},{"id":"76e49597-6039-4cb5-a595-556ccc2e3c12","pid":"a8827b1d-fdbc-41c2-bdb5-38e8b308dedc","text":"comment 19"},{"id":"07dc4b90-65d3-4f75-8351-457305988235","pid":"76e49597-6039-4cb5-a595-556ccc2e3c12","text":"comment 20"},{"id":"2d4e838b-82df-4ca0-bf9b-f1dfb99d6763","pid":"07dc4b90-65d3-4f75-8351-457305988235","text":"comment 21"},{"id":"617c1760-0dca-409c-af2a-c614f0530e07","pid":"","text":"comment 22"},{"id":"712c0b7e-a9e4-40fd-ab78-c39b483b1435","pid":"617c1760-0dca-409c-af2a-c614f0530e07","text":"comment 23"},{"id":"e325094c-886e-42c9-bd59-fdd7a189b384","pid":"","text":"comment 24"},{"id":"f3b8b0f9-edef-4ee6-9555-42e8595f854c","pid":"e325094c-886e-42c9-bd59-fdd7a189b384","text":"comment 25"},{"id":"6e09a231-a2ee-4aa1-a898-57695e6fe153","pid":"","text":"comment 26"},{"id":"63e629d6-c0f9-4b36-ad96-e0c47cf8bb4e","pid":"6e09a231-a2ee-4aa1-a898-57695e6fe153","text":"comment 27"},{"id":"d7b698f1-8757-46db-a6e6-5141a481b42b","pid":"","text":"comment 28"},{"id":"a7e3d522-553c-44f1-befa-047bd94f0e59","pid":"","text":"comment 29"},{"id":"fe78ce24-c2c8-4d00-b96d-8b8be9ce0f06","pid":"","text":"comment 30"},{"id":"fabdccb5-a024-4476-bd51-7d55fb685c42","pid":"","text":"comment 31"},{"id":"608d0693-6e43-46a0-9e54-107da6adb109","pid":"fabdccb5-a024-4476-bd51-7d55fb685c42","text":"comment 32"}]`

    var comments []Comment

    err := json.Unmarshal([]byte(jsondata), &comments)
    if err != nil {
        panic(err)
    }

    arranged := ArrangeComments(comments)

    arrangedjson, _ := json.MarshalIndent(arranged, "", "  ")

    fmt.Println(string(arrangedjson))
    fmt.Println("comments", len(comments), "arranged", recursiveCount(arranged))
}

func recursiveCount(arranged []*NestedComment) int {
    count := len(arranged)
    for _, item := range arranged {
        count += recursiveCount(item.Children)
    }
    return count
}

// Nesting function -------------------------------------------------------------------------

func ArrangeComments(comments []Comment) []*NestedComment {
    // Map to hold references to NestedComment by their ID
    queue := make(map[string]*NestedComment)

    // Result slice
    var result []*NestedComment

    // First, create all NestedComments and store references in the map
    for _, comment := range comments {
        nc := &NestedComment{Comment: comment}
        queue[comment.ID] = nc
    }

    // Second, loop through the map and add children to their parents
    for _, comment := range queue {
        if comment.ParentID != "" {
            parent := queue[comment.Comment.ParentID]
            if parent != nil {
                parent.Children = append(parent.Children, comment)
            }
        }
    }

    // Third, loop through the map and add all root comments to the result slice
    for _, comment := range queue {
        if comment.ParentID == "" {
            result = append(result, comment)
        }
    }

    return result
}

今天关于《优化嵌套逻辑以提高性能并实现正常工作的方法》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！

版本声明

本文转载于：stackoverflow 如有侵犯，请联系study_golang@163.com删除