主页 / 问题 / 1237447
Accepted
Andrew Kachalin
Asked:2022-01-29 19:07:02 +0800 CST2022-01-29 19:07:02 +0800 CST

如果有使用旧工具的解决方案，如何使用流 api java 解决 O(n*log(n)) 中重叠段的问题？

  • 772

有一个类：

public class Segment {
    int start;
    int finish;

public Segment(int start, int finish) {
    this.start = start;
    this.finish = finish;
}
}

此类覆盖equals和hashcode。该段定义了一个闭合区间，例如[5;5] - 一个点，[5; 8] - 四点5, 6, 7, 8。

您需要编写一个方法（使用 lambdas），该方法需要两个这些段的数组。在输出中，该方法应该给出一个合并的段数组，并且来自第二个数组的段肯定会到达那里，并且从第一个开始 - 只有那些没有被第二个数组重叠的段。第二段与第一段重叠。一个简单的例子 - 在第一个数组中的一个段[0; 10]，在第二个片段[5; 6]。输出是一个包含三个元素的数组 - [0;4]，[5; 6] , [7; 10]；由于听起来不清楚，所以我画了该方法应该做什么。 在此处输入图像描述 在此处输入图像描述 在此处输入图像描述 在此处输入图像描述

我还写了一个方法。在 O(nlog(n)) 中运行 - 大概。它的本质是：

  1. 复制两个输入数组。
  2. 数组首先按开头排序。O(nlog(n))
  3. 然后有两个循环 - 外部循环（绕过第一个数组）和内部循环 - 绕过内部循环。在这些循环中，对段进行比较，并从第一个数组中删除段，不包括在内，有时甚至完全包括在内。
  4. 只要其中一个段的结尾开始位于第二个段的开头之前（反之亦然），就会从数组中删除该段，以免在与其他段进行比较时浪费额外的资源。

一般来说，这个方法很长。

  static ArrayList<Segment> overlap(ArrayList <Segment> one_in, ArrayList <Segment> two_in){
       ArrayList <Segment> one = new ArrayList<>(one_in);
       ArrayList <Segment> two = new ArrayList<>(two_in);
        one.sort(base);
        two.sort(base);
      ArrayList <Segment> result = new ArrayList<>();

      ListIterator <Segment> one_iter = one.listIterator();
      ListIterator <Segment> two_iter = two.listIterator();
      Segment s = null;
      Segment t = null;
      OUTER:
      for(;one_iter.hasNext();)
      {
           s = one_iter.next();
          two_iter=two.listIterator();
         for(;two_iter.hasNext();){
           t = two_iter.next();
             if(t.start>s.finish) {
               result.add(s);
               one.remove(s);
               one_iter=one.listIterator();
               continue OUTER;
             }
             if(t.finish<s.start){
                 two.remove(t);
                 result.add(t);
                 two_iter = two.listIterator();
                 continue;
             }

             if(s.start<t.start){
               result.add(new Segment(s.start, t.start-1));
               if(t.finish>=s.finish){
                 //  two.remove(t); //ew
                 //  result.add(t);
                   two_iter = two.listIterator();
                   one.remove(s); //ew
                   one_iter=one.listIterator(); //ew
                   continue OUTER;
               }
               if(t.finish<s.finish){
                   result.add(t);
                   two.remove(t);
                   two_iter = two.listIterator();
                   s.start = t.finish+1;
                   continue;
               }
             }
             else { //Не явно s.start>=t.start
                 if(t.finish>=s.finish)
                 {
                     if(!one_iter.hasNext()) {
                         result.addAll(two);
                         two.clear(); //Костыль - На случай кросс
                     }
                     one.remove(s);
                     one_iter=one.listIterator();
                     continue OUTER;
                 }
                 if(t.finish<s.finish){
                     s.start=t.finish+1;
                     result.add(t);
                     two.remove(t);
                     two_iter = two.listIterator();
                 }
             }
         }
      }
        result.addAll(two);
        result.addAll(one);
        return result;
    }

问题：这样的方法可以接收两个数组，每个数组有一千个元素。如何使用流 API java 8简明扼要地重写它？可以做到吗？因此，没有完全绕过将每个与每个进行比较（ O(n^2) - 不满意，您需要 O(n*log(n))，在极端情况下为 O(n^1.1) ）。从更广泛的意义上说，问题是 - 有没有任何算法可以使用 java 8 工具快速重写旧的遗留代码？

java

2 个回答

  1. Best Answer

    问题可以解决O(nlogn)。问题可以通过线程来解决。解决方案很复杂，因为它依赖于清扫。

    克利提出扫地以解决以他命名的问题：克利测度问题。俄语：求一条线上线段并集的长度。

    扫地是一种常见的技术。您有一个有序的事件队列，处理更新状态（状态）的事件。根据状态变化，您打印（输出）结果。该算法是流式传输的：从流中读取事件并将结果输出到另一个流。在复杂的情况下，可以将多个扫描组合成一个管道。

    下面我们解决以下问题：您需要删除被蓝色部分覆盖的绿色部分。这不是问题的全部任务，而是其中最困难的部分。完成后，剩下的是将蓝色段混合到结果中。

    在我们的任务中，事件将是段的结束。一个事件的特征是一个坐标，一个结束类型（开始或结束），事件点本身是否包含在片段中（半间隔，间隔），颜色（绿色或蓝色）。

    例如，绿色段 [0, 10] 会产生两个绿色事件，可以描述如下：

    0         10
01234567890123
[         ]

    对于蓝色段，问题的作者提出了一个[5, 6]令人困惑的符号。让我们变换蓝色段：[5, 6] -> (4, 7)- 段被扩展，其末端被排除。事件将是点4和7：

    0         10
01234567890123
    (  )

    绿色[0, 10]和蓝色[5, 6]一起：

    0         10
01234567890123
[   (  )  ]

    状态将由两个位组成：位g表示“在绿色段中”，位表示b“在蓝色段内”（在这个短语中，“in”和“inside”是不同的东西！）。最后一行是“没有蓝色的绿色”：

    0         10
01234567890123
[   (  )  ]
-----------   g        покрыто зелёным отрезком
     --       b        покрыто синим интервалом
-----  ----   g & ~b   зелёный, но не синий

    让我们列出最后一张图片的事件和状态：

     x e g b g&~b комментарий
     0 0 0
 0 [ 1 0 1    переход g&~b 0->1: печатаем '0['
 4 ( 1 1 0    переход g&~b 1->0: печатаем '4]'
 7 ) 1 0 1    переход g&~b 0->1: печатаем '7['
10 ] 0 0 0    переход g&~b 1->0: печатаем '10]'

    最终打印输出。可以成对组装得到段：

    0[, 4], 7[, 10]    ->    [0, 4], [7, 10]

    更复杂的例子。绿党[0, 3], [5, 8], [10, 13], [18, 20]。蓝色[2, 6], [9, 13], [17, 17], [18, 18]。注意最后的两个蓝色段 - 它们相交：

    0         10        20
012345678901234567890123456789
[  ] [  ] [  ]    [ ]
 (     )(     ) ( )
                 ( )
---- ---- ----    ---   g
  -----  -----   --     b
--     --          --   g & ~b

    事件和状态：

     x e g b g&~b комментарий
     0 0 0
 0 [ 1 0 1    переход g&~b 0->1: печатаем '0['
 1 ( 1 1 0    переход g&~b 1->0: печатаем '1]'
 3 ] 0 1 0
 5 [ 1 1 0
 7 ) 1 0 1    переход g&~b 0->1: печатаем '7['
 8 ] 0 0 0    переход g&~b 1->0: печатаем '8]'
 8 ( 0 1 0
10 [ 1 1 0
13 ] 0 1 0
14 ) 0 0 0
16 ( 0 1 0
17 ( 0 2 0    синие могут пересекаться. b - не бит, а счётчик
18 ) 0 1 0
18 [ 1 1 0
19 ) 1 0 1    переход g&~b 0->1: печатаем '19['
20 ] 0 0 0    переход g&~b 1->0: печатаем '20]'

    全印：

    [0, 1], [7, 8], [19, 20]

    因此，以蓝色突出显示的区域从绿色段中移除。生成的片段必须与原始（未膨胀的）蓝色片段混合，这将给出答案。

    扫描允许您在线性时间内计算分段集合上的任何布尔函数（预排序添加nlogn）。

    程序：

    import java.util.function.Consumer;
import java.util.function.Function;
import java.util.stream.Stream;

public class SegmentOverlapping {

    public static void main(String... args) {
        test(
            new Segment[] { new Segment(0, 3), new Segment(5, 8), new Segment(10, 13), new Segment(18, 20) },
            new Segment[] { new Segment(2, 6), new Segment(9, 13), new Segment(17, 17), new Segment(18, 18) }
        );
        test(
            new Segment[] { new Segment(0, 10), new Segment(11, 11) },
            new Segment[] { new Segment(5, 6), new Segment(11, 11) }
        );
    }

    private static void test(Segment[] green, Segment[] blue) {
        System.out.println("-");
        printSegments("g", Stream.of(green));
        printSegments("b", Stream.of(blue));
        printSegments("r", maskGreenByBlue(green, blue));
    }

    private static void printSegments(String prefix, Stream<Segment> segments) {
        System.out.print(prefix + ":");
        segments.forEach(s -> System.out.print(" " + s));
        System.out.println();
    }

    private static Stream<Segment> maskGreenByBlue(Segment[] green, Segment[] blue) {
        Stream<Event> masked = maskGreenByBlueEvents(green, blue);

        Stream.Builder<Segment> builder = Stream.builder();

        Stream
        .concat(
            masked,
            makeStream(blue, Color.BLUE, 0)
        )
        .sorted()
        .forEach(new SegmentHandler(builder));

        return builder.build();
    }

    private static Stream<Event> maskGreenByBlueEvents(Segment[] green, Segment[] blue) {
        Stream.Builder<Event> builder = Stream.builder();

        Stream
        .concat(
            makeStream(green, Color.GREEN, 0),
            makeStream(blue, Color.BLUE, 1)
        )
        .sorted()
        .forEach(new BlueMaskHandler(builder));

        return builder.build();
    }

    private static Stream<Event> makeStream(Segment[] segments, Color color, int margin) {
        return Stream
            .of(segments)
            .map(s -> Stream.of(
                new Event(color, Edge.START , s.start  - margin,  margin),
                new Event(color, Edge.FINISH, s.finish + margin, -margin)
            ))
            .flatMap(Function.identity())
        ;
    }
}

class Segment {
    public final int start;
    public final int finish;

    public Segment(int start, int finish) {
        this.start = start;
        this.finish = finish;
    }

    @Override
    public String toString() {
        return "[" + start + ", " + finish + "]";
    }
}

enum Edge { START, FINISH; }

enum Color { GREEN, BLUE; }

class Event implements Comparable<Event> {
    public final Color color;
    public final Edge edge;
    public final int x;
    public final int dx;
    public Event(Color color, Edge edge, int x, int dx) {
        this.color = color;
        this.edge = edge;
        this.x = x;
        this.dx = dx;
    }

    @Override
    public int compareTo(Event other) {
        int cX = Integer.compare(x, other.x);
        if (cX != 0) {
            return cX;
        }
        return Integer.compare(dx, other.dx);
    } 

    @Override
    public String toString() {
        return "" + color + " " + edge + " " + x;
    }
}

class BlueMaskHandler implements Consumer<Event> {
    private final Stream.Builder<Event> builder;
    private int inGreen;
    private int inBlue;

    public BlueMaskHandler(Stream.Builder<Event> builder) {
        this.builder = builder;
        inGreen = 0;
        inBlue = 0;
    }

    @Override
    public void accept(Event event) {
        switch (event.color) {
        case GREEN:
            switch (event.edge) {
            case START:
                if (inGreen == 0 && inBlue == 0) {
                    builder.add(event);
                }
                ++inGreen;
                break;
            case FINISH:
                --inGreen;
                if (inGreen == 0 && inBlue == 0) {
                    builder.add(event);
                }
                break;
            }
            break;
        case BLUE:
            switch (event.edge) {
            case START:
                if (inBlue == 0 && inGreen > 0) {
                    builder.add(new Event(Color.GREEN, Edge.FINISH, event.x, 0));
                }
                ++inBlue;
                break;
            case FINISH:
                --inBlue;
                if (inBlue == 0 && inGreen > 0) {
                    builder.add(new Event(Color.GREEN, Edge.START, event.x, 0));
                }
                break;
            }
            break;
        }
    }
}

class SegmentHandler implements Consumer<Event> {
    private final Stream.Builder<Segment> builder;
    private int start;

    public SegmentHandler(Stream.Builder<Segment> builder) {
        this.builder = builder;
        start = 0;
    }

    @Override
    public void accept(Event event) {
        switch (event.edge) {
        case START:
            start = event.x;
            break;
        case FINISH:
            builder.add(new Segment(start, event.x));
            break;
        }
    }
}

    $ javac SegmentOverlapping.java && java SegmentOverlapping 
-
g: [0, 3] [5, 8] [10, 13] [18, 20]
b: [2, 6] [9, 13] [17, 17] [18, 18]
r: [0, 1] [2, 6] [7, 8] [9, 13] [17, 17] [18, 18] [19, 20]
-
g: [0, 10] [11, 11]
b: [5, 6] [11, 11]
r: [0, 4] [5, 6] [7, 10] [11, 11]
    • 2

  2. 如果元素的迭代顺序很重要，那么使用 Java 8 流 API 重写任何代码似乎都是徒劳的。流本身非常适合对所有元素应用相同类型的操作。当需要将一个元素与数组的另一个元素进行比较时，流不适合，因为它们不支持next()操作；所以到 2021 年，迭代器可能应该留在这部分代码中。

    • 0

相关问题