open-policy-agent - Rego Set 查找是否会迭代集合中的所有项目？

Question

package example

default allow = false

input = {
    "value_2": {"c", "b", "c", "b", "c", "b", "c", "b", "c", "b", "c", "b", "c", "b", "c", "b", "c", "b", "c", "b", "c", "a", "a"},
    "value_1": ["c", "b", "c", "b", "c", "b", "c", "b", "c", "b", "c", "b", "c", "b", "c", "b", "c", "b", "c", "b", "c", "a", "a"]
}

allow {
    input.value_1[_] == "a"
    input.value_2["a"] == "a"
}

按照这个例子，哪一个会更快地进行查找？

Answer 1

设置查找是常数时间：

a_set["a"]  # <-- this is constant time

集合元素的迭代和比较没有（当前）优化并且是线性时间的：

a_set[_] == "a" # <-- this is linear-time

上面的例子虽然无效，因为input.value_2它被定义为一个数组（不是一个集合），所以input.value_2["a"]是无效的。如果您尝试此示例，您将收到来自编译器的类型错误：

1 error occurred: policy.rego:12: rego_type_error: undefined ref: data.example.input.value_2.a
    data.example.input.value_2.a
                               ^
                               have: "a"
                               want (type): number

假设您最初想使用一个集合，只需使用查找语法（s[k]false

请注意，OPA 网站上的Policy Reference页面解释了如何对数组、对象和集合执行查找、比较和迭代。