algorithm - Scala - 基于 Future 结果谓词排序

Question

我有一个要排序的对象数组，其中排序谓词是异步的。 Scala 是否具有标准或第 3 方库函数，用于基于类型签名为 (T, T) -> Future[Bool] 而不仅仅是 (T, T) 的谓词进行排序-> bool ?

或者，是否有其他方法可以构建此代码？我考虑过查找列表元素的所有 2 对排列，对每对运行谓词并将结果存储在 Map((T, T), Bool) 或某种结构中，然后对其进行排序 - 但我怀疑执行的比较会比天真的排序算法执行的要多得多。

Answer 1

如果您的谓词是异步的，您可能更愿意也获得异步结果并避免使用 Await 阻塞线程

如果你想根据 future 的 bool 谓词对 List[(T,T)] 进行排序，最简单的方法是对 List[(T,T,Boolean)] 进行排序

假设你有一个 List[(T,T)] 和一个谓词 (T, T) -> Future[Bool]，你如何得到一个 List[(T,T,Boolean)]？或者更确切地说是 Future[List[(T,T,Boolean)]] 因为你想保持异步行为。

val list: List[(T,T)] = ...
val predicate = ...
val listOfFutures: List[Future[(T,T,Boolean]] = list.map { tuple2 => 
  predicate(tuple2).map( bool => (tuple2._1, tuple2._2, bool) 
}
val futureList: Future[List[(T,T,Boolean)]] = Future.sequence(listOfFutures)
val futureSortedResult: Future[List[(T,T)]] = futureList.map { list =>
    list.sort(_._3).map(tuple3 => (tuple3._1,tuple3._2))
}

这是伪代码，我没有编译它，也可能不会，但你明白了。

关键是 Future.sequence，非常有用，它以某种方式允许将 Monad1[Monad2[X]] 转换为 Monad2[Monad1[X]] 但请注意，如果您的任何谓词 future 失败，则全局排序操作也将失败。

---

如果您想要更好的性能，“批量”调用返回 Future[Boolean] 的服务可能是更好的解决方案。例如，代替 (T, T) -> Future[Bool] 也许你可以设计一个服务(如果你显然拥有它)像 List[(T, T)] -> Future [List[(T,T,Bool)] 这样您就可以在一次异步调用中获得所需的一切。