5

Here's simple code:

import std.algorithm;
import std.array;
import std.file;

void main(string[] args)
{
    auto t = args[1].readText()
        .splitter('\n')
        .split("---")
    ;
}

Looks like it should work, but it won't compile. DMD 2.068.2 fails with this error:

Error: template std.algorithm.iteration.splitter cannot deduce function from
argument types !()(Result, string), candidates are:
...
Error: template instance std.array.split!(Result, string) error instantiating

It compiles if I insert .array before .split.

Am I missing something? Or is it a bug? I've tried to make a brief search in the bug tracker, but didn't found anything.

4

1 回答 1

19

底线：此类问题通常可以通过.array在有问题的功能之前拨打电话来解决。这为其提供了一个具有足够功能的缓冲区来运行算法。

以下是库背后的原因以及您也可以用来实现它的其他一些想法：

无法编译的原因与 std.algorithm 和范围背后的理念有关：它们尽可能便宜地将成本决策推向顶层。

在 std.algorithm（以及大多数编写良好的范围和范围消耗算法）中，模板约束将拒绝任何不能免费提供所需内容的输入。类似地，转换范围，如过滤器、拆分器等，将仅返回它们可以以最低成本提供的功能。

通过在编译时拒绝它们，它们迫使程序员在最高级别做出关于他们希望如何支付这些成本的决定。您可能会重写该函数以使其以不同的方式工作，您可能会使用各种技术自己缓冲它以预先支付成本，或者您可以找到其他任何可行的方法。

因此，您的代码会发生以下情况：readText返回一个数组，这是一个几乎功能齐全的范围。（由于它返回string由 UTF-8 制成的 .想了解更多）因为在可变长度的 utf-8 字符列表中查找 Unicode 代码点需要全部扫描。全部扫描并不是最低成本，因此除非您特别要求，否则 Phobos 永远不会尝试它。）

无论如何，readText返回一个具有大量功能的范围，包括splitter需要的可保存性。为什么splitter需要储蓄？考虑它承诺的结果：从最后一个分割点开始并继续到下一个分割点的一系列字符串。在为最通用的范围编写此代码时，它可能以便宜的价格实现，实现是什么样的？

沿着这些思路：首先，save您的起始位置，以便您以后可以返回。然后，使用popFront，通过它，直到找到分割点。当它发生时，将保存的范围返回到分割点的点。然后，popFront越过分割点并重复该过程，直到你吃完整个东西 ( while(!input.empty))。

所以，既然splitter的实现需要save起点的能力，那么它至少需要一个向前的范围（这只是一个可保存的范围。安德烈现在觉得这样命名有点傻，因为名字太多了，但当时他在写std.algorithm他仍然相信给他们所有的名字）。

并非所有范围都是前向范围！数组是，保存它们就像从当前位置返回一个切片一样简单。许多数值算法也是如此，保存它们只是意味着保留当前状态的副本。如果他们正在转换的范围是可保存的，那么大多数转换范围都是可保存的——同样，他们需要做的就是返回当前状态。

......当我写这篇文章时，实际上，我认为你的例子应该是可以保存的。而且，确实存在一个接受谓词并编译的重载！

http://dlang.org/phobos/std_algorithm_iteration.html#.splitter.3

    import std.algorithm;
    import std.array;
    import std.stdio;

    void main(string[] args)
    {
            auto t = "foo\n---\nbar"
                    .splitter('\n')
                    .filter!(e => e.length)
                    .splitter!(a => a == "---")
            ;
            writeln(t);
    }

输出：[["foo"], ["bar"]]

是的，它在与特定事物相等的行上编译和拆分。另一个重载 ,.splitter("---")无法编译，因为该重载需要切片功能（或窄字符串，Phobos 通常拒绝切片......但知道它实际上可以，所以该函数是特殊情况的。你看到了所有在图书馆上方。）

但是，为什么它需要切片而不是保存呢？老实说，我不知道。也许我也遗漏了一些东西，但是确实有效的重载的存在对我来说意味着我对算法的概念是正确的；可以这样做。我确实相信切片会便宜一些，但保存版本也足够便宜（你会计算你弹出多少项目以到达拆分器，然后返回saved.take(that_count)......也许这就是原因：您将迭代项目两次，一次在算法内部，然后再次在外部，并且库认为提高一个级别的成本足够高。（谓词版本通过使您的函数进行扫描，因此 Phobos 认为它​​不再是它的问题，你知道你自己的函数在做什么。）

我可以看到其中的逻辑。不过，我可以双向进行，因为实际上再次碾过它的决定仍然在外面，但我不明白为什么不经过深思熟虑就无法做到这一点。

最后，为什么不在splitter其输出上提供索引或切片？为什么也不filter提供呢？为什么map提供它？

好吧，这又与低成本理念有关。map可以提供它（假设它的输入确实如此），因为map实际上并没有改变元素的数量：输出中的第一个元素也是输入中的第一个元素，只是在结果上运行了一些函数。最后一个也是如此，以及介于两者之间的所有其他人。

filter改变了这一点。过滤掉 [1,2,3] 的奇数只得到 [2]：长度不同，现在在开头而不是中间找到 2。但是，在您实际应用过滤器之前，您无法知道它在哪里- 如果不缓冲结果，您就无法跳来跳去。

splitter类似于过滤器。它改变了元素的位置，并且算法不知道它在哪里分裂，直到它真正穿过元素。所以它可以在你迭代时告诉你，但不是在迭代之前，所以索引会O(n)很快——计算上太昂贵了。索引应该非常便宜。

无论如何，既然我们理解了为什么存在这个原则 - 让你，最终程序员决定昂贵的事情，比如缓冲（这需要比可用内存更多的内存）或额外的迭代（这需要更多的 CPU 时间而不是免费的）算法），并且通过考虑它的实现来了解为什么splitter需要它，我们可以寻找满足算法的方法：我们需要使用占用更多 CPU 周期的版本并使用我们的自定义比较来编写它函数（参见上面的示例），或以某种方式提供切片。最直接的方法是将结果缓冲在一个数组中。

import std.algorithm;
import std.array;
import std.file;

void main(string[] args)
{
    auto t = args[1].readText()
        .splitter('\n')
        .array // add an explicit buffering call, understanding this will cost us some memory and cpu time
        .split("---")
    ;
}

您也可以在本地缓冲它或自己进行缓冲以降低分配成本，但是无论您这样做，都必须在某个地方支付成本，Phobos 更喜欢您的程序员，他了解您的程序的需求，如果您愿意是否支付这些费用，做出决定，而不是在不告诉您的情况下代表您支付。

于 2015-10-28T01:57:41.320 回答