dart 如何最好地实现可迭代的分区函数?

fdbelqdn  于 2023-11-14  发布在  其他
关注(0)|答案(4)|浏览(139)

我越来越喜欢dart的列表操作函数。然而,我经常发现自己需要一个“分区”函数,根据布尔标准将列表分成两部分。意思是,与.where相同,但不会丢弃假的。
明显的实施:

Iterable partition(Iterable list, filter) {
  var matches    = [];
  var nonMatches = [];
  list.forEach((e) {
    if (filter(e)) {
      matches.add(e);
    } else {
      nonMatches.add(e);
    }
  });
  return [matches, nonMatches];
}

字符串
然而,我也越来越喜欢where返回的懒惰迭代。
另一种实现是使用集合:

Iterable partition(Iterable list, filter) {
  var matches    = list.where(filter);
  var nonMatches = list.toSet().difference(matches.toSet()).toList();
  return [matches, nonMatches];
}


我很乐意看到一个优雅的惰性实现是如何完成的(如果它很容易的话)。我相信从列表中构造一个集合是一个O(n)操作,所以这两个实现在效率上应该不会有太大的差异。

更新set实现有缺陷。我不太明白为什么它不工作,但nonMatches不包含matches中不包含的所有数字。

ocebsuys

ocebsuys1#

怎么样:

Iterable partition(Iterable list, filter) {
  return [list.where((e) => filter(e)), list.where((e) => !filter(e))];
}

字符串
此致罗伯特

wlp8pajw

wlp8pajw2#

您可以将其无缝地混合到视图中,例如UnmodifiableListView

import "package:unittest/unittest.dart";
import "dart:collection";

class Tuple<A,B> {
  final A a;
  final B b;
  const Tuple(this.a, this.b);
  String toString() {
    return "(a: $a, b : $b)";
  }
}

abstract class  partitionMixin<RES, E>{
  Iterable<E> where(bool test(E element));
  Map<E, bool> _filterCache = new Map();
  Tuple<RES,RES> partition(bool filter(E e)) {
    bool cachedFilter(E e) {
      if (_filterCache.containsKey(e)) return _filterCache[e];
      else {
        bool filterRes = filter(e);
        _filterCache[e] = filterRes;
        return filterRes;
      }
    }
    return new Tuple(this.where(cachedFilter),
        this.where((E e) => !cachedFilter(e)));
  }
}

 class  ExtULV<E> = UnmodifiableListView<E> with
                              partitionMixin<ExtULV<E>,E>;

void main() {

  test('Split one iterable in two"', () {

    var foo = (e) => (e % 2) == 0;
    var fooA =  [2,4,6,8, 10, 12, 14];
    var fooB =  [1,3,5,7,9,11,13];
    var fooRes = new Tuple(fooA, fooB);

    var tested = new ExtULV([1,2,3,4,5,6,7,8,9,10,11,12,13,14]);
    var testRes = tested.partition(foo);
    print("fooRes : $fooRes\ntestRes: $testRes");
    expect(testRes.a.toList().toString() == fooRes.a.toString(), true);
    expect(testRes.b.toList().toString() == fooRes.b.toString(), true);

  });
}

字符串

bjp0bcyl

bjp0bcyl3#

如果你把它概括起来,它会变得更简单

Map groupedBy(f, list) {
    var grouped = {};
    for (var thing in list) {
      grouped.putIfAbsent(f(thing), () => []).add(thing);  
    }
   return grouped;
  }

字符串
尽管让它变懒并不容易

kuarbcqp

kuarbcqp4#

dart 版本:

$ dart --version
Dart SDK version: 3.1.3 (stable) (Tue Sep 26 14:25:13 2023 +0000) on "linux_x64"

字符串
配分函数:

(List, List) partition<T>(Iterable<T> iter, bool Function(T) pred) {
  return iter.fold(([], []), (res, item) {
    var (l1, l2) = res; // bc cannot pattern match on func params without type annotations
    switch (pred(item)) {
      case true:  l1.add(item);
      case false: l2.add(item);
    }
    return (l1, l2);
  });
}

partition([1, 2, 3, 4, 5, 6, 7], (n) => n.isEven); // ([2, 4, 6], [1, 3, 5, 7])


作为Iterables的扩展:

extension PartIterable on Iterable {
  (List, List) partition<T>(bool Function(T) pred) {
    return fold(([], []), (res, item) {
      var (l1, l2) = res;
      switch (pred(item)) {
        case true:  l1.add(item);
        case false: l2.add(item);
      }
      return (l1, l2);
    });
  }
}

[1, 2, 3, 4, 5, 6, 7].partition((int n) => n.isEven); // ([2, 4, 6], [1, 3, 5, 7])


对于两个列表的返回值来说,懒惰是什么意思?这个问题没有太大的意义。原则上,你可以实现一个懒惰计算的Iterable。但是你会返回什么呢?

void main(List<String> arguments) {
  var part = Partition([1, 2, 3, 4, 5, 6, 7], (n) => n.isEven);
  for (final item in part) {
    print(item);
  }
}

class Partition<T> extends Iterable<(List<T>, List<T>)> {
  List<T> inputList;
  bool Function(T) pred;
  Partition(this.inputList, this.pred);

  @override
  Iterator<(List<T>, List<T>)> get iterator =>
      PartitionIterator(inputList, pred);
}

class PartitionIterator<T> implements Iterator<(List<T>, List<T>)> {
  int index = 0;
  bool Function(T) pred;
  List<T> inputList;
  List<T> left = [];
  List<T> right = [];

  PartitionIterator(this.inputList, this.pred);

  @override
  get current => (left, right); // what to return here ???

  @override
  bool moveNext() {
    switch (index >= inputList.length) {
      case true:
        return false;
      case false:
        final item = (inputList[index]);
        switch (pred(item)) {
          case true:
            left.add(item);
          case false:
            right.add(item);
        }
        index++;
        return true;
    }
  }
}


main的输出:

([], [1])
([2], [1])
([2], [1, 3])
([2, 4], [1, 3])
([2, 4], [1, 3, 5])
([2, 4, 6], [1, 3, 5])
([2, 4, 6], [1, 3, 5, 7])

相关问题