Uint8List中的序列搜索

Question

是否有快速(本机)方法来搜索Uint8List中的序列

///
/// Return index of first occurrence of seq in list
///
int indexOfSeq(Uint8List list, Uint8List seq) {
  ...
}

编辑:将List<int>更改为Uint8List

Answer 1

不是的。没有内置的方式来搜索列表中的元素序列。我也不知道任何基于dart:ffi的实现。

最简单的办法是：

extension IndexOfElements<T> on List<T> {
  int indexOfElements(List<T> elements, [int start = 0]) {
    if (elements.isEmpty) return start;
    var end = length - elements.length;
    if (start > end) return -1;
    var first = elements.first;
    var pos = start;
    while (true) {
      pos = indexOf(first, pos);
      if (pos < 0 || pos > end) return -1;
      for (var i = 1; i < elements.length; i++) {
        if (this[pos + i] != elements[i]) {
          pos++;
          continue;
        }
      }
      return pos;
    }
  }
}

这具有最坏的时间复杂度O(length*elements.length)。有更多的算法具有更好的最坏情况复杂度，但它们也有更大的常数因子和更昂贵的预计算(KMP，BMH)。除非您多次搜索相同的长列表，或者在一个非常非常长的列表中搜索，否则它们在实践中不太可能更快(而且它们可能有一个API，您可以先编译模式，然后使用它进行搜索)。

Answer 2

您可以按照您的建议使用dart:ffi从string.h绑定到memmem。

我们对malloc与stdlib.h in package:ffi (来源)的绑定也是如此。

final DynamicLibrary stdlib = Platform.isWindows
    ? DynamicLibrary.open('kernel32.dll')
    : DynamicLibrary.process();

final PosixMalloc posixMalloc =
    stdlib.lookupFunction<Pointer Function(IntPtr), Pointer Function(int)>('malloc');

编辑:正如lrn所指出的，目前我们不能公开Uint8List的内部数据指针，因为GC可能会重新定位它。

可以使用dart_api.h并使用FFI将TypedData通过FFI蹦床作为Dart_Handle，并使用来自dart_api.h的Dart_TypedDataAcquireData访问内部数据指针。

(如果你想在颤振中使用这一点，我们需要在Dart_TypedDataAcquireData和Dart_TypedDataReleaseData中公开dart_api_dl.h https://github.com/dart-lang/sdk/issues/40607 --我已经提交了https://github.com/dart-lang/sdk/issues/44442来跟踪这一点。)

或者，可以寻址https://github.com/dart-lang/sdk/issues/36707，这样我们就可以直接在FFI蹦床中公开Uint8List的内部数据指针。