Split Период-разделители Вершина Для JSON объекта

Question

У меня есть много записей строки (это пространства имена/класс дерева), которые выглядят следующим образом:

appsystem 
appsystem.applications 
appsystem.applications.APPactivities 
appsystem.applications.APPmanager 
appsystem.applications.APPmodels 
appsystem.applications.MAPmanager 
appsystem.applications.MAPmanager.maphub 
appsystem.applications.MAPmanager.mapmanager 
appsystem.applications.pagealertsmanager 
appsystem.authentication 
appsystem.authentication.manager 
appsystem.authentication.manager.encryptionmanager 
appsystem.authentication.manager.sso 
appsystem.authentication.manager.tokenmanager 

Но мне нужен конечный результат будет как:

{ 
    "name": "appsystem", 
    "children": [ 
     { 
     "name": "applications", 
     "children": [ 
      {"name": "APPactivities"}, 
      {"name": "APPmanager"}, 
      {"name": "APPmodels"}, 
      {"name": "MAPmanager", 
       "children": [ 
        {"name": "maphub"}, 
        {"name": "mapmanager"} 

       ]}, 
      {"name": "pagealertsmanager"} 
      ] 
     }, 
     { 
     "name": "authentication", 
     "children": [ 
      {"name": "manager", 
       "children": [ 
        {"name": "encryptionmanager"}, 
        {"name": "sso"}, 
        {"name": "tokenmanager"} 
       ]} 
      ] 
     } 
    ] 
} 

Всего узлов может быть любое число.

Я предполагаю, что мне понадобится рекурсия, но я в недоумении, где даже начать.

Answer 1

Это строит вложенные списки, PowerShell ConvertTo-JSON выравнивает внешний список.

Вы можете изменить $Line in $s на $line in (Get-Content input.txt).

Но я думаю, что это делает:

$s = @' 
appsystem 
appsystem.applications 
appsystem.applications.APPactivities 
appsystem.applications.APPmanager 
appsystem.applications.APPmodels 
appsystem.applications.MAPmanager 
appsystem.applications.MAPmanager.maphub 
appsystem.applications.MAPmanager.mapmanager 
appsystem.applications.pagealertsmanager 
appsystem.authentication 
appsystem.authentication.manager 
appsystem.authentication.manager.encryptionmanager 
appsystem.authentication.manager.sso 
appsystem.authentication.manager.tokenmanager 
'@ -split "`r`n" 

$TreeRoot = New-Object System.Collections.ArrayList 

foreach ($Line in $s) { 

    $CurrentDepth = $TreeRoot 

    $RemainingChunks = $Line.Split('.') 
    while ($RemainingChunks) 
    { 

     # If there is a dictionary at this depth then use it, otherwise create one. 
     $Item = $CurrentDepth | Where-Object {$_.name -eq $RemainingChunks[0]} 
     if (-not $Item) 
     { 
      $Item = @{name=$RemainingChunks[0]} 
      $null = $CurrentDepth.Add($Item) 
     } 

     # If there will be child nodes, look for a 'children' node, or create one. 
     if ($RemainingChunks.Count -gt 1) 
     { 
      if (-not $Item.ContainsKey('children')) 
      { 
       $Item['children'] = New-Object System.Collections.ArrayList 
      } 

      $CurrentDepth = $Item['children'] 
     } 

     $RemainingChunks = $RemainingChunks[1..$RemainingChunks.Count] 
    } 
} 

$TreeRoot | ConvertTo-Json -Depth 1000 

---

Edit: Это слишком медленно? Я пробовал профилирование random pausing и нашел (не удивительно), что это внутренний вложенный цикл, который ищет массивы children для соответствия дочерним узлам, которые попадают слишком много раз.

Это измененная версия, которая по-прежнему строит дерево, и на этот раз он также создает хеш-таблицу TreeMap ярлыков в дереве, ко всем ранее созданным узлам, поэтому они могут сразу перепрыгивать их, а не искать списки children для них.

Я сделал тестовый файл, некоторые 20k случайных строк. Исходный код обработал его за 108 секунд, это делается через 1,5 секунды, и результат соответствует.

$TreeRoot = New-Object System.Collections.ArrayList 
$TreeMap = @{} 

foreach ($line in (Get-Content d:\out.txt)) { 

    $_ = ".$line" # easier if the lines start with a dot 

    if ($TreeMap.ContainsKey($_)) # Skip duplicate lines 
    { 
     continue 
    } 

    # build a subtree from the right. a.b.c.d.e -> e then d->e then c->d->e 
    # keep going until base 'a.b' reduces to something already in the tree, connect new bit to that. 
    $LineSubTree = $null 
    $TreeConnectionPoint = $null 

    do { 
     $lastDotPos = $_.LastIndexOf('.') 
     $leaf = $_.Substring($lastDotPos + 1) 
     $_ = $_.Substring(0, $lastDotPos) 

     # push the leaf on top of the growing subtree 
     $LineSubTree = if ($LineSubTree) { 
          @{"name"=$leaf; "children"=([System.Collections.ArrayList]@($LineSubTree))} 
         } else { 
          @{"name"=$leaf} 
         } 

     $TreeMap["$_.$leaf"] = $LineSubTree 

    } while (!($TreeConnectionPoint = $TreeMap[$_]) -and $_) 


    # Now we have a branch built to connect in to the existing tree 
    # but is there somewhere to put it? 
    if ($TreeConnectionPoint) 
    { 
     if ($TreeConnectionPoint.ContainsKey('children')) 
     { 
      $null = $TreeConnectionPoint['children'].Add($LineSubTree) 
     } else { 
      $TreeConnectionPoint['children'] = [System.Collections.ArrayList]@($LineSubTree) 
     } 
    } else 
    {   # nowhere to put it, this is a new root level connection 
     $null = $TreeRoot.Add($LineSubTree) 
    } 
} 

$TreeRoot | ConvertTo-Json -Depth 100 

(@ код mklement0 занимает 103 секунд, и производит дико другой вывод - 5.4m символы JSON вместо 10.1M символов JSON [Edit: потому что мой код позволяет использовать несколько корневых узлов в списке, который мой тест. файл имеет, и их код не позволяет, что])

---

Auto сгенерированные PS помогают ссылки из моего кодоблок (если таковые имеются):

• New-Object (в модуле Microsoft.PowerShell.Utility)
• Get-Content (в модуле Microsoft.PowerShell.Management)
• ConvertTo-Json (в модуле Microsoft.PowerShell.Utility)

Answer 2

В дополнение к TessellatingHeckler's great answer с альтернативной реализацией, которая использует рекурсивную функцию.

Акцент делается на модульность и терпение, а не на производительность.^[1]

# Outer function that loops over all paths and builds up a one or more nested 
# hashtables reflecting the path hierarchy, which are converted to JSON on output. 
# Note that only a single JSON object is output if all paths share the same root 
# component; otherwise, a JSON *array* is output. 
function convert-PathsToNestedJsonObject([string[]] $paths) { 
    $hts = New-Object Collections.ArrayList 
    $paths.ForEach({ 
    $rootName = $_.split('.')[0] 
    $ht = $hts.Where({ $_.name -eq $rootName }, 'First')[0] 
    if (-not $ht) { [void] $hts.Add(($ht = @{})) } 
    convert-PathToNestedHashtable $ht $_ 
    }) 
    $hts | ConvertTo-Json -Depth 100 
} 

# Recursive helper function that takes a path such as "appsystem.applications" 
# and converts it into a nested hashtable with keys "name" and "children" to 
# reflect the path hierarchy. 
function convert-PathToNestedHashtable([hashtable] $ht, [string] $path) { 
    $name, $childName, $rest = $path -split '\.', 3 
    $ht.name = $name 
    if ($childName) { 
    if ($ht.children) { 
     $htChild = $ht.children.Where({ $_.name -eq $childName }, 'First')[0] 
    } else { 
     $ht.children = New-Object Collections.ArrayList 
     $htChild = $null 
    } 
    if (-not $htChild) {  
     [void] $ht.children.Add(($htChild = @{})) 
    } 
    convert-PathToNestedHashtable $htChild "$childName.$rest" 
    } 
} 

# Call the outer function with the input paths (assumed to be stored in $paths). 
convert-PathsToNestedJsonObject $paths 

---

^[1]Один преднамеренным тип оптимизации применяется, которая, однако, до сих пор хранит код лаконичный:

PSv4 + предлагает (малоизвестные) методы расширения.ForEach() and .Where(), которые не только заметно быстрее, чем их сопоставления командлетов ForEach-Object и Where-Object, но также предлагают дополнительные функции.

В частности:

• $paths.ForEach({ ... }) используется вместо
  $paths | ForEach-Object { ... }

• $ht.children.Where({ $_.name -eq $childName }, 'First')[0] используется вместо
  $ht.children | Where-Object { $_.name -eq $childName } | Select-Object -First 1