我提供了一个解决方案给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编码的函数往往很快!)
.[1:]
,仿佛 jq 是 LISP 一样。顺便说一句,数组是按其长度存储的,因此如果输入是数组,则调用length
的成本是微不足道的,无论其大小。 - peak