我正在处理的数据结构基本上是排序的、不重叠的整数范围的列表:
1,2,3
1-5
0,1,3-4,6,8-10
我需要对这些列表对执行基本操作(并集和交集),例如:
$ list_and '1,2,3' '0,1,3-4,6,8-10'
1,3
$ list_or '1-5' '0,1,3-4,6,8-10'
0-6,8-10
我可以在关联数组中显式地构造每个集合,在成对的成员上执行操作,然后将结果集折叠回这种形式,但在大范围内它将非常慢。
在纯Bash中连接和交叉这样的“范围列表”最有效的方法是什么?
发布于 2021-06-17 17:06:25
在join(1)
、comm(1)
和sort(1)
等命令的帮助下,集合操作将变得容易得多,但它们只能在bash
中完成。我确实同意oguz的观点,另一种语言会更合适。您可以使用比shell所支持的更好的数据结构来获得非常奇特且高效的稀疏整数集。
使用一些shell算法,将输入范围拆分成几行单独的数字作为这些程序的输入也很容易。
#!/usr/bin/env bash
# Turn a string like 1,3,5-10 into one number per line, filling in ranges
expand() {
local IFS=,
# For each comma-separated element
for elem in $1; do
# If it's a range, print out each number in the range
if [[ $elem =~ ([0-9]+)-([0-9]+) ]]; then
for (( i = BASH_REMATCH[1]; i <= BASH_REMATCH[2]; i++ )); do
printf "%d\n" "$i"
done
else
# And if it's just a scalar, print that number.
printf "%d\n" "$elem"
fi
done
}
list_and() {
# Add each element in the first argument to an associate array,
# and then for each element of the second argument, see if it also
# exists in that array. If so, add it to the result.
local -A arr1
for elem in $(expand "$1"); do
arr1[$elem]=1
done
local -a intersection
for elem in $(expand "$2"); do
if [[ -v arr1[$elem] ]]; then
intersection+=("$elem")
fi
done
local IFS=,
printf "%s\n" "${intersection[*]}"
}
list_or() {
# Populate a sparse array using the numbers from arguments
# as indexes.
local -a union
for elem in $(expand "$1") $(expand "$2"); do
union[$elem]=$elem
done
local IFS=,
printf "%s\n" "${union[*]}"
}
printf "%s\n" "$(list_and '1,2,3' '0,1,3-4,6,8-10')"
printf "%s\n" "$(list_or '1-5' '0,1,3-4,6,8-10')"
在输出中将诸如1,2,3
之类的内容转换为1-3
,留给读者作为练习。(我不想为你做所有的作业…)
https://stackoverflow.com/questions/68013498
复制相似问题