获取jq中对象数组的索引

24
我有一个类似这样的JSON对象(由i3-msg -t get_workspaces生成):
[
  {
    "name": "1",
    "urgent": false
  },
  {
    "name": "2",
    "urgent": false
  },
  {
    "name": "something",
    "urgent": false
  }
]

我正在尝试使用jq查找基于select查询的列表中的索引号。 jq有一个叫做index()的东西,但它似乎只支持字符串?

像这样使用i3-msg -t get_workspaces | jq '.[] | select(.name=="something")'将给我想要的对象。但我想知道它的索引。在这种情况下是2(从0开始计数)

仅使用jq是否可以实现此目的?

4个回答

24
我提供了一个解决方案给OP,OP迅速接受了。随后@peak和@Jeff Mercado提供了更好、更完整的解决方案。因此我将其转化为社区wiki。如果你能改进这个答案,请尽管去做。
一个简单的解决方案(由@peak指出)是使用内置函数index
map(.name == "something") | index(true)

jq的文档令人困惑地建议index操作字符串,但它也可以操作数组。因此,index(true)返回由map产生的布尔数组中第一个true的索引。如果没有符合条件的项,则结果为null。

jq表达式以"惰性"方式评估,但map将遍历整个输入数组。我们可以通过重写上面的代码并引入一些调试语句来验证这一点:

[ .[] | debug | .name == "something" ] | index(true)

如@peak所建议的,做得更好的关键是使用jq 1.5中引入的break语句:

label $out | 
foreach .[] as $item (
  -1; 
  .+1; 
  if $item.name == "something" then 
    ., 
    break $out 
  else 
    empty
  end
) // null

请注意,//不是注释,它是替代运算符。如果找不到名称,则foreach将返回empty,该运算符将其转换为null。
另一种方法是递归处理数组:
def get_index(name): 
  name as $name | 
  if (. == []) then
    null
  elif (.[0].name == $name) then 
    0 
  else 
    (.[1:] | get_index($name)) as $result |
    if ($result == null) then null else $result+1 end      
end;
get_index("something")

然而,正如@Jeff Mercado所指出的那样,这种递归实现在最坏情况下将使用与数组长度成比例的堆栈空间。在1.5版本中,jq引入了尾递归优化(TCO),它将允许我们使用本地辅助函数进行优化(请注意,这是对@Jeff Mercado提供的解决方案进行的微小调整,以便与上面的示例保持一致)。
def get_index(name): 
  name as $name | 
  def _get_index:
    if (.i >= .len) then
      null
    elif (.array[.i].name == $name) then
      .i
    else
      .i += 1 | _get_index
    end;
  { array: ., i: 0, len: length } | _get_index;
get_index("something")

根据 @peak 的说法,在 jq 中获取数组长度是一个常数时间操作,而索引数组也很便宜。我将尝试找到相关引用。
现在让我们尝试实际测量一下。这里是测量简单解决方案的示例:
#!/bin/bash

jq -n ' 

  def get_index(name): 
    name as $name |
    map(.name == $name) | index(true)
  ;

  def gen_input(n):  
    n as $n |
    if ($n == 0) then 
      []
    else
      gen_input($n-1) + [ { "name": $n, "urgent":false } ]
    end
  ;  

  2000 as $n |
  gen_input($n) as $i |
  [(0 | while (.<$n; [ ($i | get_index(.)), .+1 ][1]))][$n-1]
'

当我在我的电脑上运行此代码时,我得到以下结果:
$ time ./simple
1999

real    0m10.024s
user    0m10.023s
sys     0m0.008s

如果我用“快速”版本的get_index替换它:
def get_index(name): 
  name as $name |
  label $out | 
  foreach .[] as $item (
    -1; 
    .+1; 
  if $item.name == $name then 
    ., 
    break $out 
  else 
    empty
  end
) // null;

然后我得到:
$ time ./fast
1999

real    0m13.165s
user    0m13.173s
sys     0m0.000s

如果我用“快速”的递归版本替换它:

def get_index(name): 
  name as $name | 
  def _get_index:
    if (.i >= .len) then
      null
    elif (.array[.i].name == $name) then
      .i
    else
      .i += 1 | _get_index
    end;
  { array: ., i: 0, len: length } | _get_index;

我得到:

$ time ./fast-recursive 
1999

real    0m52.628s
user    0m52.657s
sys     0m0.005s

哎呀!但我们可以做得更好。@peak提到了一个未记录的开关--debug-dump-disasm,让您可以查看jq如何编译您的代码。通过这个,您可以看到修改并将对象传递给_indexof,然后提取数组、长度和索引是很昂贵的。重构只传递索引是一个巨大的改进,而进一步的优化避免将索引与长度进行比较,使它与迭代版本相当:

def indexof($name):
  (.+[{name: $name}]) as $a | # add a "sentinel"
  length as $l | # note length sees original array
  def _indexof:
    if ($a[.].name == $name) then
      if (. != $l) then . else null end
    else
      .+1 | _indexof
    end
  ;


  0 | _indexof
;

我得到:

$ time ./fast-recursive2
null

real    0m13.238s
user    0m13.243s
sys     0m0.005s

所以看起来如果每个元素的概率相等,并且您想要平均情况下的性能,您应该坚持使用简单的实现。(C编码的函数往往很快!)

很高兴看到我没有误读文档 :) 这个完美地运行了!谢谢! - xeor
@Jim D. -- Jeff Mercado的递归实现indexof非常周到,而你对它的改编则不然。最严重的问题可能是效率--你可能想运行一些基准测试。你的实现表明你对jq中数组的实现方式做出了一些错误的假设。至少,应该承认Jeff的努力。同时,感谢你承认我的工作。 - peak
@Jim-D - Jeff 是一位经验丰富、高度能干的 jq 程序员,所以我担心你的程序与他的任何偏差都会有某种不利影响。无疑,效率低下的主要原因是使用 .[1:],仿佛 jq 是 LISP 一样。顺便说一句,数组是按其长度存储的,因此如果输入是数组,则调用 length 的成本是微不足道的,无论其大小。 - peak
1
@Jim-D - jq维基(https://github.com/stedolan/jq/wiki)提供了许多重要信息,而jq本身也有一个反汇编选项(jq --debug-dump-disasm ....)。 - peak
@peak,谢谢;我知道维基,但不知道反汇编函数。 - JimD.
“简单”的答案有一个错误,当元素超过2000个时无法正常工作。我在1000000上进行了性能测试。此外,我无法重现您的测试结果。在我的测试中,这个“简单”的版本比其他所有版本都要慢得多。 - steinybot

11

@Jim-D最初提出的解决方案只适用于JSON对象数组,并且两种最初提出的解决方案都非常低效。在没有满足条件的项目时,它们的行为也可能会令人惊讶。

使用index/1的解决方案

如果您只是想要一个快速简单的解决方案,可以使用内置函数index,如下所示:

map(.name == "something") | index(true)

如果没有满足条件的项,则结果将为null

顺便提一下,如果想要所有满足条件的索引,则可以通过简单地将 index 更改为 indices 来轻松转换为超快速解决方案:

map(.name == "something") | indices(true)

高效解决方案

下面是一个通用且高效的函数,它返回输入数组中第一次出现 (item|f) 为真值(既不为 null 也不为 false)的元素的索引(即偏移量),否则返回 null。(在 jq、javascript 等许多语言中,数组的索引始终基于 0。)

# 0-based index of item in input array such that f is truthy, else null
def which(f):
  label $out
  | foreach .[] as $x (-1; .+1; if ($x|f) then ., break $out else empty end)
  // null ;

使用示例:

which(.name == "something")

4
将数组转换为条目将使您能够访问项目数组中的索引和值。您可以使用它来查找您要查找的值并获取其索引。
def indexof(predicate):
    reduce to_entries[] as $i (null;
        if (. == null) and ($i.value | predicate) then
            $i.key
        else
            .
        end
    );
indexof(.name == "something")

然而,这种方法不会短路并且会遍历整个数组来查找索引。一旦找到第一个索引,您应该立即返回。采用更具功能性的方法可能更合适。

def indexof(predicate):
    def _indexof:
        if .i >= .len then
            null
        elif (.arr[.i] | predicate) then
            .i
        else
            .i += 1 | _indexof
        end;
    { arr: ., i: 0, len: length } | _indexof;
indexof(.name == "something")

请注意,参数以这种方式传递给内部函数是为了利用某些优化。 也就是说,为了利用尾调用优化,函数不能接受任何其他参数。
通过认识到数组及其长度不变,可以获得更快的版本。
def indexof(predicate):
  . as $in
  | length as $len
  |  def _indexof:
       if . >= $len then null
       elif ($in[.] | predicate) then .
       else . + 1 | _indexof
       end;
  0 | _indexof;

是的,TCO仅适用于0元函数。为了可读性,您可以考虑使用JSON对象作为_indexof的输入。效率应该大致相同。 - peak
如果使用对象作为参数同样可以正常工作,那太好了,这些更改看起来更具吸引力。 - Jeff Mercado

2

这里是另一种版本,看起来比@peak和@jeff-mercado的优化版本略快:

label $out | . as $elements | range(length) |
select($elements[.].name == "something") | . , break $out

我认为这篇文章更易读,虽然它仍然依赖于 break (只匹配第一个结果)。

我在一个大约有100万个元素的数组上进行了100次迭代(最后一个元素是要匹配的元素)。我只计算了用户和内核时间,没有计算墙钟时间。平均而言,这个解决方案花费了3.4秒,@peak的解决方案花费了3.5秒,而@jeff-mercado的解决方案则花费了3.6秒。这与我在单次运行中看到的结果相符,尽管公平地说,我曾经运行过一次这个解决方案的平均时间为3.6秒,因此每个解决方案之间可能没有任何统计显着差异。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接