任意のネストされたjsonデータから任意のネストされたjsonデータをjqで抽出する

Question

主題として、all_keys関数を記述して、任意にネストしたjsonブロブからすべてのキーを抽出し、必要に応じて配列とオブジェクトをトラバースし、重複することなく、キーを含む。 all_keysのfuctionは、この出力を生成する必要があり

[ 
    {"name": "/", "children": [ 
     {"name": "/bin", "children": [ 
     {"name": "/bin/ls", "children": []}, 
     {"name": "/bin/sh", "children": []}]}, 
     {"name": "/home", "children": [ 
     {"name": "/home/stephen", "children": [ 
      {"name": "/home/stephen/jq", "children": []}]}]}]}, 
    {"name": "/", "children": [ 
     {"name": "/bin", "children": [ 
     {"name": "/bin/ls", "children": []}, 
     {"name": "/bin/sh", "children": []}]}, 
     {"name": "/home", "children": [ 
     {"name": "/home/stephen", "children": [ 
      {"name": "/home/stephen/jq", "children": []}]}]}]}  
] 

：以下の入力与え例えば

、この目的のために

[ 
    "children", 
    "name" 
] 

は、私は次の関数を考案し、それはそれと同じくらい遅いです畳み込まれているので、私は同じ結果を得るためのより簡潔で速い方法を考え出すことができるかどうか疑問に思っていました。参考のため

def all_keys: 
    . as $in | 
    if type == "object" then 
     reduce keys[] as $k (
      []; 
      . + [$k, ($in[$k] | all_keys)[]] 
     ) | unique 
    elif type == "array" then (
     reduce .[] as $i (
      []; 
      . + ($i | all_keys) 
     ) | unique 
    ) 
    else 
     empty 
    end 
; 

、this 53MB json fileにその機能を実行すると、（私が知っている、それは非常に古代のですが、まだ正常に動作します）私のインテルT9300@2.50GHz CPUにおよそ22秒かかります。

Answer 1

単純なアプローチでは、すべてのキーを収集して一意の値を取得するだけです。

[.. | objects | keys[]] | unique 

しかし、そのデータでは、キーを収集してソートする必要があるため、それは少し遅いです。

これで少し改善できました。すべての異なるキーを決定しようとしているので、より効率的になるように、ある種のハッシュマップを使用します。さて、私たちはそのように行動できるオブジェクトを持っています。

reduce (.. | objects | keys[]) as $k ({}; .[$k] = true) | keys 

私はこれで時間を測定しませんでしたが、それは他のバージョンよりも速いです。私は他の人が終了するのを待たずに、私の仕事用マシン（i5-2400@3.1GHz）で10秒以内でした。

Answer 2

私はOPのall_keysの次の亜種が実際には..を使ったバージョンより少し速いことがわかります。これは予想さおそらくある - のみ216930 JSONオブジェクトがあるのに対し、jeopardy.jsonため、..は完全1731807個のJSONエンティティを生成します。

def all_keys: 
    def uniquely(f): reduce f as $x ({}; .[$x] = true) | keys; 
    def rkeys: 
    if type == "object" then keys[] as $k | ($k, (.[$k]|rkeys)) 
    elif type == "array" then .[]|rkeys 
    else empty 
    end; 
    uniquely(rkeys);