时间戳

首页 > 解决方案 > 为什么这个未使用的流对结果有影响？

java - 为什么这个未使用的流对结果有影响？

问题描述

为什么以下 有效未使用的行（在方法中：getAllDefinedVars）对最终结果有影响：
List collect = allVars.stream().filter(v -> false).collect(Collectors.toList());

如果我删除整个方法和调用此方法的一行代码（generateOneSetOfBools中的第一行），我最终会得到另一个结果。
我会期待这样的行为，如果......

  1. 提到的行对 List allVars或任何其他变量有影响
  2. 将使用流的结果

据我所知，这一切都没有发生。因此，删除整个方法应该对结果没有影响。

为了说服自己，您可以第一次使用包含流的方法运行 main，第二次不使用此方法，然后比较输出。

public class PairwiseMain {
    
    private static PairwisePermutator pp = new PairwisePermutator();

    public static void main(String[] args) {
        for(int i = 0; i < 20; i++) {
            pp.permutate(i);
            System.out.println("----------------");
        }
    }

}




import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class PairwisePermutator {
    
    private int n;
    
    public Stream<boolean[]> permutate(int n) {
        this.n = n;
        List<Var> vars = generateRequiredVars(n);
        List<TupleSet> table = generateTable(vars);
        generateCombinations(table, vars);
        return null;
    }
    
    private void generateCombinations(List<TupleSet> table, List<Var> vars) {
        TupleSet start = findStartTupleSet(table);
        if(start == null) {
            return; 
        }else {
            Tuple t = start.tuples.get(0);
            start.setVars(t);
            generateOneSetOfBools(table, vars, new HashSet<>(Arrays.asList(start)));
        }
        System.out.println(Arrays.toString(vars.toArray()));
        resetAllVars(vars);
        generateCombinations(table, vars);
    }

    private void resetAllVars(List<Var> vars) {
        vars.stream().forEach(v -> v.value = null);
    }

    private void generateOneSetOfBools(List<TupleSet> table, List<Var> allVars, Set<TupleSet> start) {
        List<Var> alreadyDefinedVars = getAllDefinedVars(allVars); //REMOVAL OF THIS LINE SHOULD HAVE NO IMPACT
        Map<TupleSet, Integer> relevant = findRelevantTuplesInOtherTupleSets(table, start);
        boolean changes = false;
        boolean existsMultipleOptions = false;
        TupleSet minimalMultipleOptions = null;
        int minimalMultipleOptionsNumber = Integer.MAX_VALUE;
        for(Map.Entry<TupleSet, Integer> entry : relevant.entrySet()) {
            if(entry.getValue() == -1) {
                removeTuple(entry.getKey());
                start.add(entry.getKey());
                changes = true;
            }else if(entry.getValue() == 1) {   
                changes = true;
                removeTuple(entry.getKey(), table, allVars);
                start.add(entry.getKey());
            }else if(entry.getValue() >= 2) {    
                existsMultipleOptions = true;
                if(entry.getValue() < minimalMultipleOptionsNumber) {
                    minimalMultipleOptionsNumber = entry.getValue();
                    minimalMultipleOptions = entry.getKey();
                }
            }
        }
        if(!changes && existsMultipleOptions) {
            removeRandomTuple(minimalMultipleOptions, start);
        }else if(!changes) { 
            setVars(table);
        }
        if(areAllVarsDefined(allVars)) {
            removeMatchingTuples(table);
            return;
        }
        generateOneSetOfBools(table, allVars, start);
    }

    private List<Var> getAllDefinedVars(List<Var> allVars) {
        List<Var> collect = allVars.stream().filter(v -> false).collect(Collectors.toList());
        return collect;
    }

    private void removeMatchingTuples(List<TupleSet> table) {
        for(TupleSet ts : table) {
            boolean v1 = ts.x.value;
            boolean v2 = ts.y.value;
            Tuple toRemove = null;
            for(Tuple t : ts.tuples) {
                if(t.a == v1 && t.b == v2) {
                    toRemove = t;
                }
            }
            if(toRemove != null) {
                ts.setVars(toRemove);
            }
        }
    }

    private boolean areAllVarsDefined(List<Var> allVars) {
        return allVars.stream().filter(v -> v.value != null).count() == n;
    }

    private void removeRandomTuple(TupleSet minimalMultipleOptions, Set<TupleSet> start) {
        Tuple toRemove = minimalMultipleOptions.tuples.get(0);
        minimalMultipleOptions.setVars(toRemove);
        start.add(minimalMultipleOptions);
    }

    private void setVars(List<TupleSet> table) {
        boolean foundOne = false;
        for(TupleSet ts : table) {
            if(ts.x.value == null && ts.y.value == null) {
                foundOne = setVars(ts);
            }
        }
        if(!foundOne) {
            for(TupleSet ts : table) {
                if(ts.x.value == null || ts.y.value == null) {
                    if(ts.tuples.isEmpty()){
                        ts.x.value = true;
                        ts.y.value = false;
                    }else {
                        ts.setVars(ts.tuples.get(0));
                    }
                }
            }
        }
        
    }

    private boolean setVars(TupleSet ts) {
        boolean foundOne;
        if(ts.tuples.isEmpty()){
            ts.x.value = true;
            ts.y.value = false;
            foundOne = true;
        }else {
            ts.setVars(ts.tuples.get(0));
            foundOne = true;
        }
        return foundOne;
    }

    private void removeTuple(TupleSet ts, List<TupleSet> table, List<Var> vars) {
        Tuple toRemove = null;
        if(ts.x.value != null) {
            for(Tuple t : ts.tuples) {
                if(t.a == ts.x.value) {
                    toRemove = t;
                }
            }
        }else if(ts.y.value != null) {
            for(Tuple t : ts.tuples) {
                if(t.b == ts.y.value) {
                    toRemove = t;
                }
            }
        }
        if(toRemove != null)
            ts.setVars(toRemove);
    }

    private void removeTuple(TupleSet ts) {
        boolean v1 = ts.x.value;
        boolean v2 = ts.y.value;
        Tuple toRemove = null;
        for(Tuple t : ts.tuples) {
            if(t.a == v1 && t.b == v2) {
                toRemove = t;
            }
        }
        if(toRemove != null) {
            ts.setVars(toRemove);
        }
    }

    private Map<TupleSet, Integer> findRelevantTuplesInOtherTupleSets(List<TupleSet> table, Set<TupleSet> alreadyVisited) {
        Map<TupleSet, Integer> freedomMap = new HashMap<>();
        for(TupleSet ts : table) {
            if(!alreadyVisited.contains(ts)) {
                int degreeOfFreedom = calculateDegreeOfFreedom(ts);
                freedomMap.put(ts, degreeOfFreedom);            }
        }
        return freedomMap;
    }
    
    private int calculateDegreeOfFreedom(TupleSet ts) {
        List<Var> alreadyDefinedVars = new ArrayList<>();
        if(ts.x.value != null) {
            alreadyDefinedVars.add(ts.x);
        }
        if(ts.y.value != null) {
            alreadyDefinedVars.add(ts.y);
        }
        int degreeOfFreedom = 0;
        if(areBothDefinied(alreadyDefinedVars)) {
            degreeOfFreedom = -1; 
        }else if(isExactlyOneDefinied(alreadyDefinedVars)) {
            Var defined = getDefinedVar(alreadyDefinedVars);
            if(defined == ts.x) {
                degreeOfFreedom = (int) ts.tuples.stream().filter(t -> t.a == ts.x.value).count();
            }else if(defined == ts.y) {
                degreeOfFreedom = (int) ts.tuples.stream().filter(t -> t.b == ts.y.value).count();
            }
        }else if(alreadyDefinedVars.isEmpty()) {
            degreeOfFreedom = ts.tuples.size(); 
        }
        return degreeOfFreedom;
    }

    private Var getDefinedVar(List<Var> alreadyDefinedVars) {
        return alreadyDefinedVars.get(0);
    }

    private boolean isExactlyOneDefinied(List<Var> alreadyDefinedVars) {
        return alreadyDefinedVars.size() == 1;
    }

    private boolean areBothDefinied(List<Var> alreadyDefinedVars) {
        return alreadyDefinedVars.size() == 2;
    }

    private TupleSet findStartTupleSet(List<TupleSet> table) {
        TupleSet startingTupleSet = null;
        for(TupleSet ts : table) {
            if(!ts.tuples.isEmpty()) {
                startingTupleSet = ts;
            }
        }
        return startingTupleSet;
    }

    private List<Var> generateRequiredVars(int n) {
        return IntStream.range(0, n).mapToObj(number -> new Var()).collect(Collectors.toList());
    }
    
    private List<TupleSet> generateTable(List<Var> vars) {
        List<TupleSet> tupleSets = new ArrayList<>();
        int kStart = 1;
        for(int i = 0; i < vars.size(); i++) {
            for(int k = kStart; k < vars.size(); k++) {
                tupleSets.add(getInitSet(vars.get(i), vars.get(k)));
            }
            kStart++;
        }
        return tupleSets;
    }
    
    private TupleSet getInitSet(Var x, Var y){
        return new TupleSet(x, y, (new ArrayList<>(Arrays.asList( new Tuple(true, true),
                                            new Tuple(true, false),
                                            new Tuple(false, true),
                                            new Tuple(false, false)))));
    }
    
    private static class TupleSet{
        Var x;
        Var y;
        ArrayList<Tuple> tuples;
        
        TupleSet(Var x, Var y, ArrayList<Tuple> tuples){
            this.x = x;
            this.y = y;
            this.tuples = tuples;
        }
        
        public void setVars(Tuple t) {
            x.value = t.a;
            y.value = t.b;
            tuples.remove(t);
        }

        @Override
        public String toString() {
            return "["+x+","+y+"]"+tuples;
        }
    }
    
    private static class Var{
        public Boolean value;
        
        @Override
        public String toString() {
            return value == null ? "null" : value.toString();
        }
    }
    
    private static class Tuple{
        public Boolean a;
        public Boolean b;
        
        public Tuple(Boolean a, Boolean b) {
            this.a = a;
            this.b = b;
        }
        
        @Override
        public String toString() {
            return "("+a+","+b+")";
        }
    }

}

影响的一个示例是运行 pp.permutate(5) 并具有以下输出：
使用流：运行发布的代码

[true, true, true, true, true]  
[false, false, false, true, false]  
[false, false, false, false, true]  
[true, true, true, false, false]  
[true, false, false, true, false]  
[false, false, true, true, false]  
[true, true, true, false, false]

没有流：只删除 generateOneSetOfBool() 中的第一行

[true, true, true, true, true]  
[false, false, false, true, false]  
[false, false, false, false, true]  
[true, true, true, false, false]  
[false, true, true, true, false]  
[true, false, true, true, false]  
[true, true, false, false, false]

两个输出不同，例如最后一行

标签： javajava-8java-stream

解决方案

您获得的结果差异与 line 无关List collect = allVars.stream().filter(v -> false).collect(Collectors.toList());。问题是您的算法是不确定的。我已经获取了您的代码并针对相同的输入多次运行它：

for(int i = 0; i < 20; i++) {
    pp.permutate(5);
    System.out.println("----------------");
}

是否有您在谈论的那一行都没关系-我得到了您提到的两个输出（只有这两个变体出现）：

[true, true, true, true, true]
[false, false, false, true, false]
[false, false, false, false, true]
[true, true, true, false, false]
[true, false, false, true, false]
[false, false, true, true, false]
[true, true, true, false, false]
----------------
[true, true, true, true, true]
[false, false, false, true, false]
[false, false, false, false, true]
[true, true, true, false, false]
[false, true, true, true, false]
[true, false, true, true, false]
[true, true, false, false, false]

我没有逐行浏览您的代码，所以我不确定，但我猜您的某些集合并不能保证元素的顺序。

然而，有趣的是，当我main多次运行时，不同版本的输出出现的顺序总是相同的（或者至少在我尝试过的 5 次中）。更重要的是，当你提到的那一行被删除时，这个顺序就会改变——但在 main 调用之间保持不变。当我们加上在不同的机器上它的行为不同的事实时，我的结论是它可能与程序如何放置在内存中有关。

推荐阅读