遍历列表直到满足特定条件

Question

我想创建一个简单的 SML 程序，从左到 right.Let 遍历列表，假设我有一个包含 N 个项目的列表，其中 K 个不同 types.For 例如列表 1 3 1 3 1 3 3 2 2 1 有 10 个数字 3(1,2,3) 类型。

我想做的是从左到右浏览这个列表，当我发现所有 K 个不同时停止numbers.In在这种情况下，我会在偶然发现第一个 2 后立即停止。

这可以通过在每个步骤中将列表拆分为头部和尾部并处理头部来完成element.However我如何跟踪我找到的不同数字？

这可以在 C/C++ 中通过简单地持有一个计数器和一个包含 K 个元素的布尔数组来完成。如果我偶然发现带有 bool[i]=false 的元素 i，我将其设为 true 并且 counter=counter+1.

据说数组不是 SML 的最佳选择，所以我想知道我是否必须使用另一种数据结构，或者我是否必须创建一个新函数来每次检查我之前是否见过这个元素（这会增加时间复杂度）。

Answer 1

how could I keep track of the different numbers I have found?

[...] in C/C++ by [...] a boolean array with K elements

抽象地说，我会把你想要的数据结构称为位集。

我会给你两个答案，一个使用稀疏容器，一个使用位集。

稀疏

我会使用列表来跟踪您已经看到的元素：

fun curry f x y = f (x, y)

val empty = []
fun add x set = curry op:: x set
fun elem x set = List.exists (curry op= x) set

fun seen k xs =
    let fun seen_ 0 _ _  = true
          | seen_ _ [] _ = false
          | seen_ k (x::xs) set =
              if elem x set
              then seen_ k xs set
              else seen_ (k-1) xs (add x set)
    in seen_ k xs empty end

你也可以使用平衡二叉树作为集合类型；这将减少对 O(lg n) 的查找。使用实际容器（列表或树）而不是位数组的优点是sparse arrays/matrices。这适用于 ''a list 秒。

位设置

[...] boolean array with K elements [...]

If i stumble upon an element i [...]

到目前为止，您还没有说过元素始终是从 0 到 K-1 的无符号整数，如果它们应该由唯一表示，这将是一个要求长度数组中的索引 K.

SML 有一个名为 Word / word 的 module/type，用于无符号整数 (words)。添加此约束后，输入列表的类型应为 word list 而不是 ''a list.

当你在许多命令式、编译语言中创建原始类型数组时，你会变得可变，unboxed arrays. SML's Array 类型也是可变的，但是这样的数组中的每个 bool 都会被装箱。

获得不可变、未装箱位数组的一种简单方法是对IntInf使用按位运算(SML/NJ;implementations vary);它会随着位的翻转而自动增长。这可能看起来像：

fun bit x = IntInf.<< (1, x)

val empty = IntInf.fromInt 0
fun add x set = IntInf.orb (set, bit x)
fun elem x set = IntInf.> (IntInf.andb (set, bit x), 0)

函数 seen 是一样的。

k 递归减少而 set 动态增长的事实意味着您不限于 [0,K-1][ 范围内的元素=85=]，大小为 K.

的数组就是这种情况
使用示例：

- seen 5 [0w4, 0w2, 0w1, 0w9]; val it = false : bool - seen 5 [0w1, 0w2, 0w3, 0w4, 0w8]; val it = true : bool

如果元素很大，此解决方案会使用大量内存：

- seen 1 [0w100000000]; *eats my memory slowly* val it = true : bool

您可以做的其他事情：

创建一个模块 structure BitSet = struct ... end，它封装了具有操作 empty、add 和 elem 的抽象类型，隐藏了特定的实现（无论是 IntInf.int，或 bool Array.array 或 ''a list).

创建一个函数，fun fold_until f e xs = ... 提取 seen_ 的递归方案，以避免手动递归；常规 foldl 是不够的，因为它会一直持续到列表为空。您可以使用 error-aware return type 或使用异常来构建它。

考虑 Bloom filters。

遍历列表直到满足特定条件

Traversing a list until certain criterion is met

functional-programming

list

sml

smlnj

稀疏

位设置