如何获取流中元素的索引？

Question

作为学习Java 8+ Streams的练习，我想将一些简单的Codility实现转换为Stream解决方案。

例如，BinaryGap问题..使用Streams的一个简单的线性解决方案可能类似于：

public static int solution(int N) {
    return Integer.toBinaryString(N).chars().
                     filter(x -> x == 1).whichIndexes().diff().max();
}

唯一的问题是，虽然，whichIndexes并且diff不存在。我需要一种方法来获取已过滤元素的索引，然后计算它们的成对差异，这将是基于Streams的单线解决方案的良好起点。

更新：这是我的C ++ BinaryGap解决方案，但是Java非Stream-ed版本将非常相似：

#include <bitset>
#include <iostream>
#include <math.h>

using namespace std;

int solution(int N) {
    bitset<32> bs(N);
    int maxGap = 0;
    std::size_t i = 0;
    while (bs[i] == 0) {
        i++;
    }
    int startPos = i;
    for (; i < bs.size(); ++i) {
        if (bs[i] == 1) {
            int gap = i - startPos - 1;
            if (gap > maxGap) {
                maxGap = gap;
            }
            startPos = i;
        }
    }
    return maxGap;
}

int main() {
    cout << solution(9) << " must be 2" << endl;
    cout << solution(529) << " must be 4" << endl;
    cout << solution(20) << " must be 1" << endl;
    cout << solution(32) << " must be 0" << endl;
    cout << solution(1041) << " must be 5" << endl;
    return 0;
}

Answer 1

获取索引很简单；流一个整数范围，而不是字符串中的字符。

String s = Integer.toBinaryString(N);
IntStream.range(0, s.length())
    .filter(i -> s.charAt(i) == '1')
    . // more stream operations

计算最大差异比较困难，因为这取决于流中的连续对，而不是单个元素。任何依赖于流中多个元素（而不是一次一个）的操作都必须在collect阶段中完成。这样做有点棘手：IntStream.collect方法采用三个参数：

• 甲Supplier<R>供给类型的一个新对象R，以在收集的结果，
• 一个ObjIntConsumer<R>将一个类型R为int 的对象再加上一个int 的对象，
• 一个BiConsumer<R, R>不这样做在非平行流什么。

该类型R将需要跟踪当前的最大差异以及所看到的最后一个数字，以便可以计算与下一个数字的差异。一种实现方法是使用List两个数字中的a，其中索引0保存到目前为止的最大差，索引1保存之前看到的数字（如果有）。

String s = Integer.toBinaryString(N);
int maxDiff = IntStream.range(0, s.length())
    .filter(i -> s.charAt(i) == '1')
    .collect(
        // supply a new list to hold intermediate results
        () -> {
            List<Integer> acc = new ArrayList<Integer>();
            acc.add(0); // initial max diff; and result if no "gap" exists
            return acc;
        },
        // accumulate one more number into the result
        (List<Integer> list, int num) -> {
            if(list.size() == 1) {
                // this is the first number, no diffs yet
                list.add(num);
            } else {
                int max = list.get(0);
                int lastNum = list.get(1);
                int diff = num - lastNum;
                list.set(0, diff > max ? diff : max);
                list.set(1, num);
            }
        },
        // combine two accummulators; shouldn't be called
        (List<Integer> list1, List<Integer> list2) -> {
            throw new RuntimeException("combiner shouldn't be called");
        }
    )
    .get(0); // max diff is at index 0 in the list

几乎可以肯定，这是比尝试使用流之前更糟糕的解决方案，但是...嗯，您想要一个流解决方案，所以就在这里。

Answer 2

您无法获得单个流中元素的索引（IntStream技巧也可以完成其他操作），并且您不能对连续元素进行操作，您所看到的（在collect阶段之外）只是手头的元素（除了如下所示的肮脏技巧和reduce方法）。

顺便说一句。这是我在途中发现的潜在一线，也许在二进制间隙方面存在一些边缘情况的缺陷，但实际上我并不熟悉其精美的字样，并且与OP无关。

Arrays.stream(Integer.toBinaryString(n).replaceAll("0*$|^0*", "").split("1"))
      .map(String::length)
      .reduce(0, Math::max)

这一次我觉得是接近你可以（不荏苒）您最初的想法，与来自@ Kaya3清理元素和这个有趣的黑客摆脱连续元素对（{1,2,3,4} -> {{1,2},{2,3},{3,4}}）。您也可以在map-to-pair的步骤中进行比较，也许省去了另一行，但是像这样很奇怪：

        String st = Integer.toBinaryString(N);
        Integer max = IntStream.range(0, st.length() - 1)
                .filter(i -> st.charAt(i) == '1')
                .boxed()
                .map(new Function<Integer, Pair>() {
                    Integer previous;

                    @Override
                    public Pair apply(Integer i) {
                        Pair p = new Pair(previous, i);
                        previous = i;
                        return p;
                    }
                }).skip(1) //first element is {null, smthg}
                .map(i -> (i.right - i.left) - 1)
                .max(Integer::compareTo)
                .orElse(0);

但请注意：“此[map hack]与流框架的设计完全相反，并且直接违反了map API的约定，因为匿名函数不是无状态的。请尝试在并行流上运行它，并且...将会看到……偶发的随机“错误”几乎不可能重现……这可能是灾难性的。”

我认为，与parallelStream()它一起使用将为您提供甚至保证是错误的结果，因为那样一来，就会丢失与流分区一样多的对。