java - 使用 Java 的并行性来解决递归函数

Question

我正在尝试优化一个过程，该过程是计算玩家的所有可能组合以形成分区。为了理解我的问题，我使用以下示例。例如，我们有一组玩家 N = {1,2,3,4,5} ，这个玩家重新分组是这样的{1,2},{3,4},{5} 。这意味着玩家 1 将与玩家 2 作为单人游戏，依此类推。每组玩家都有一套策略或选择。每个玩家选择他想所属的组，例如: 群 {1,2}有这些可能性{{1,2};{1,2,3,4}} ;即玩家{1,2}要么选择呆在一起，要么加入团队{3,4}。 对其他玩家的解释相同:

{3,4}=>{{3,4};{3,4,5};{1,2,3,4}}
{5}=>{{5};{3,4,5}}

现在，选择相同策略的玩家群体将形成一个新的群体(联盟)。例如，组 {1,2}选择策略{1,2,3,4} ;IE。玩家{1,2}想要与玩家{3,4}组成一个新组。玩家{3,4}选择策略{3,4,5} , 玩家{5}选择策略{3,4,5} 。选择相同策略的玩家将被分组在一起，在 final 中形成这样的玩家分区:{1,2},{3,4,5}；玩家 3,4,5 选择了相同的策略，因此他们聚集在一起，玩家 {1,2} 选择了不同的策略，因此他们保持单独。我们对所有可能的玩家策略组合进行同样的操作，以获得基数 = K 的所有可能的玩家分区。最后，我必须选择最优的玩家分区。在前面的示例中:我必须仅生成基数 = 2 的分区: |{1,2,3,4},{5}|=2 |{1,2}{3,4,5}|=3 此分区 Not Acceptable :|{1,2}{3,4}{5}|=3 我已将此过程编程为递归函数，以获取玩家的所有可接受分区。这里的另一个问题是我的函数生成所有可能的分区，而我只得到可接受的分区，这需要很多次!!

现在我的问题是是否可以在java中使用并行性来计算玩家的所有可接受的分区，特别是当我们有很多玩家和如此多的分区时。我必须做什么才能加速大问题的执行？

 import static java.util.Arrays.asList;
 import java.util.ArrayList;
 import java.util.Comparator;
 import java.util.List;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Map;
 import java.util.Set;
 import java.util.stream.Collectors;
 import java.util.stream.Stream;
 public class Test {
 @SafeVarargs
 static <T> Set<T> set(T ... elems) {
  return new HashSet<T>(asList(elems));
 }
 static <T> List<Set<Set<T>>> calcPartitions(List<T> teams, Map<T,    List<Set<T>>> team2Strategies, int k, boolean doParallel) {
if(k == 0) {
  if(teams.isEmpty()) return asList(new HashSet<>());
  else return new ArrayList<>();
} else if(teams.isEmpty()) {
  return new ArrayList<>();
}

Set<T> teamsSet = new HashSet<>(teams);

T team = teams.get(0);
Stream<Set<T>> strategies = 
  (doParallel ? team2Strategies.get(team).parallelStream() : team2Strategies.get(team).stream())
    .filter(strategy ->
      strategy.stream().allMatch(team2 ->
        teamsSet.contains(team2) && team2Strategies.get(team2).contains(strategy)));
  return strategies.flatMap(strategy -> {
    List<T> newTeams = new ArrayList<>(teams);
    newTeams.removeAll(strategy);
    List<Set<Set<T>>> restPartitions = calcPartitions(newTeams, team2Strategies, k - 1, false);
    for(Set<Set<T>> partition: restPartitions) {
      partition.add(strategy);
    }
    return restPartitions.stream();
  })
  .collect(Collectors.toList());
}

public static void main(String[] args) {
List<Set<Integer>> teams = asList(set(0,1,2), set(3,4), set(5),set(6,7,8),set(9,10,11),set(12,13,14));

Map<Set<Integer>, List<Set<Set<Integer>>>> team2Strategies = new HashMap<>();

team2Strategies.put(set(0,1,2), asList(set(set(0,1, 2)),
                                     set(set(0,1, 2), set(3, 4))));
team2Strategies.put(set(3,4), asList(set(set(3, 4), set(5)),
                                     set(set(0,1, 2), set(3, 4))));
team2Strategies.put(set(5), asList(set(set(5)),
                                   set(set(3, 4), set(5)),set(set(5),set(6,7,8)),set(set(5),set(6,7,8),set(9,10,11),set(12,13,14))));


team2Strategies.put(set(6,7,8), asList(set(set(6,7,8)),
        set(set(6, 7,8), set(5)),set(set(5),set(6,7,8),set(9,10,11),set(12,13,14))));

team2Strategies.put(set(9,10,11), asList(set(set(9,10,11)),
        set(set(9, 10,11), set(12,13,14)),set(set(5),set(6,7,8),set(9,10,11),set(12,13,14))));

team2Strategies.put(set(12,13,14), asList(set(set(12,13,14)),
        set(set(12, 13,14), set(9,10,11)),set(set(5),set(6,7,8),set(9,10,11),set(12,13,14))));
List<Set<Set<Set<Integer>>>> partitions = calcPartitions(teams,   team2Strategies, 3, true);

  Comparator<List<Integer>> intListComparator = (a, b) -> {
  int i = 0;
  while(i < a.size() && i < b.size()) {
    if(a.get(i) > b.get(i)) return 1;
    else if(a.get(i) < b.get(i)) return -1;
    i++;
  }
  return a.size() - b.size();
};

//in "partitions" a strategy was a Set<Set<Integer>>
//in "partitionsList" however a strategy is a List<Integer>
List<List<List<Integer>>> partitionsList =
  partitions.stream().map(partition ->
    partition.stream().map(strategy ->
      strategy.stream().flatMap(Set::stream)
                       .sorted()
                       .collect(Collectors.toList()))
    .sorted(intListComparator).collect(Collectors.toList()))
  .collect(Collectors.toList());

System.out.println(partitionsList);

System.out.println(
  partitionsList.stream().map(partition ->
    partition.stream().map(strategy ->
      strategy.stream().map(i -> i.toString()).collect(Collectors.joining(", ", "{", "}")))
    .collect(Collectors.joining()))
  .collect(Collectors.joining("\n")));
 }
}

Answer 1

Java 8 中的 Stream 类能够在可能的情况下自动并行执行操作。 当然，要使其发挥作用，重要的是在可能并行运行的代码中，所有操作都必须是线程安全的。实现这一点的最简单方法是避免对变量或集合进行任何修改。 这是一个使用流的解决方案。它也只遍历每个可能的分区一次，并且应该相当高效。 我将每个分区表示为策略列表。每个策略都是一个团队列表。每个团队依次也是一个列表。 这意味着团队列表可能如下所示: [[1,2]、[3,4]、[5]] 策略可能是这样的 [[3,4], [5]](表示团队[3,4] 和团队[5] 配对)。 分区可能看起来像这样 [[[1,2]], [[3,4], [5]]] 等于 {1,2}{3,4,5}

import static java.util.Arrays.asList;
import java.util.ArrayList;
import java.util.List;
import java.util.HashMap;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Test {
  static <T> List<List<List<T>>> calcPartitions(List<T> teams, Map<T, List<List<T>>> team2Strategies, int k, boolean doParallel) {
    if(k == 0) {
      if(teams.isEmpty()) return asList(new ArrayList<>());
      else return new ArrayList<>();
    } else if(teams.isEmpty()) {
      return new ArrayList<>();
    }

    T team = teams.get(0);
    Stream<List<T>> strategies = 
      (doParallel ? team2Strategies.get(team).parallelStream() : team2Strategies.get(team).stream())
        .filter(strategy ->
          strategy.stream().allMatch(team2 ->
            teams.contains(team2) && team2Strategies.get(team2).contains(strategy)));
      return strategies.flatMap(strategy -> {
        List<T> newTeams = new ArrayList<>(teams);
        newTeams.removeAll(strategy);
        List<List<List<T>>> restPartitions = calcPartitions(newTeams, team2Strategies, k - 1, false);
        for(List<List<T>> partition: restPartitions) {
          partition.add(0, strategy);
        }
        return restPartitions.stream();
      })
      .collect(Collectors.toList());
  }

  public static void main(String[] args) {
    List<List<Integer>> teams = asList(asList(1,2), asList(3,4), asList(5));

    Map<List<Integer>, List<List<List<Integer>>>> team2Strategies = new HashMap<>();

    team2Strategies.put(asList(1,2), asList(asList(asList(1, 2)),
                                            asList(asList(1, 2), asList(3, 4))));
    team2Strategies.put(asList(3,4), asList(asList(asList(3, 4)),
                                            asList(asList(3, 4), asList(5)),
                                            asList(asList(1, 2), asList(3, 4))));
    team2Strategies.put(asList(5), asList(asList(asList(5)),
                                          asList(asList(3, 4), asList(5))));

    List<List<List<List<Integer>>>> partitions = calcPartitions(teams, team2Strategies, 2, true);

    System.out.println(
      partitions.stream().map(partition ->
        partition.stream().map(strategy ->
          strategy.stream().map(team ->
            team.stream().map(i -> i.toString()).collect(Collectors.joining(", ")))
          .collect(Collectors.joining(", ", "{", "}")))
        .collect(Collectors.joining()))
      .collect(Collectors.joining("\n")));
  }
}

该程序的输出是

{1, 2}{3, 4, 5}
{1, 2, 3, 4}{5}

编辑:

我必须单独代表每个团队才能使该策略发挥作用。但是您可以通过使用集合而不是列表来改进它。这样 [[3,4],[5]] 将等于 [[5],[3,4]]。集合还应该使整个程序更快。找到解决方案后，您可以将其转换为更好的形式，即将 [[3,4],[5]] 转换为 [3,4,5] 并同时对数字进行排序。

import static java.util.Arrays.asList;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Test {
  @SafeVarargs
  static <T> Set<T> set(T ... elems) {
    return new HashSet<T>(asList(elems));
  }

  static <T> List<Set<Set<T>>> calcPartitions(List<T> teams, Map<T, List<Set<T>>> team2Strategies, int k, boolean doParallel) {
    if(k == 0) {
      if(teams.isEmpty()) return asList(new HashSet<>());
      else return new ArrayList<>();
    } else if(teams.isEmpty()) {
      return new ArrayList<>();
    }

    Set<T> teamsSet = new HashSet<>(teams);

    T team = teams.get(0);
    Stream<Set<T>> strategies = 
      (doParallel ? team2Strategies.get(team).parallelStream() : team2Strategies.get(team).stream())
        .filter(strategy ->
          strategy.stream().allMatch(team2 ->
            teamsSet.contains(team2) && team2Strategies.get(team2).contains(strategy)));
      return strategies.flatMap(strategy -> {
        List<T> newTeams = new ArrayList<>(teams);
        newTeams.removeAll(strategy);
        List<Set<Set<T>>> restPartitions = calcPartitions(newTeams, team2Strategies, k - 1, false);
        for(Set<Set<T>> partition: restPartitions) {
          partition.add(strategy);
        }
        return restPartitions.stream();
      })
      .collect(Collectors.toList());
  }

  static List<Set<Integer>> teams = new ArrayList<>();
  static Map<Set<Integer>, List<Set<Set<Integer>>>> team2Strategies = new HashMap<>();

  private static Set<Integer> toSet(String string) {
    return Stream.of(string.split(" ")).map(s -> Integer.valueOf(s.trim())).collect(Collectors.toSet());
  }

  @SafeVarargs
  private static void defineTeams(List<String> ... definitions) {
    for(List<String> def: definitions) {
      teams.add(toSet(def.get(0)));
    }

    for(List<String> def: definitions) {
      Set<Integer> team = toSet(def.get(0));
      Stream<Set<Integer>> strategies = def.stream().skip(1).map(s -> toSet(s));
      List<Set<Set<Integer>>> startegiesList =
        strategies.map(strat -> teams.stream().filter(strat::containsAll).collect(Collectors.toSet()))
                  .collect(Collectors.toList());
      team2Strategies.put(team, startegiesList);
    }
  }

  public static void main(String[] args) {
    defineTeams(asList("0 1 2", "0 1 2", "0 1 2 3 4"),
                asList("3 4", "3 4 5", "0 1 2 3 4"),
                asList("5", "5", "3 4 5", "5 6 7 8", "5 6 7 8 9 10 11 12 13 14"),
                asList("6 7 8", "6 7 8", "5 6 7 8", "5 6 7 8 9 10 11 12 13 14"),             
                asList("9 10 11", "9 10 11", "9 10 11 12 13 14", "5 6 7 8 9 10 11 12 13 14"),
                asList("12 13 14", "12 13 14", "9 10 11 12 13 14", "5 6 7 8 9 10 11 12 13 14"));

    System.out.println("teams = "+ teams);
    System.out.println("team trategies = " + team2Strategies);
    System.out.println();

    List<Set<Set<Set<Integer>>>> partitions = calcPartitions(teams, team2Strategies, 3, true);

    Comparator<List<Integer>> intListComparator = (a, b) -> {
      int i = 0;
      while(i < a.size() && i < b.size()) {
        if(a.get(i) > b.get(i)) return 1;
        else if(a.get(i) < b.get(i)) return -1;
        i++;
      }
      return a.size() - b.size();
    };

    System.out.println(partitions);

    //in "partitions" a strategy was a Set<Set<Integer>>
    //in "partitionsList" however a strategy is a List<Integer>
    List<List<List<Integer>>> partitionsList =
      partitions.stream().map(partition ->
        partition.stream().map(strategy ->
          strategy.stream().flatMap(Set::stream)
                           .sorted()
                           .collect(Collectors.toList()))
        .sorted(intListComparator).collect(Collectors.toList()))
      .collect(Collectors.toList());

    System.out.println(partitionsList);

    System.out.println(
      partitionsList.stream().map(partition ->
        partition.stream().map(strategy ->
          strategy.stream().map(i -> i.toString()).collect(Collectors.joining(", ", "{", "}")))
        .collect(Collectors.joining()))
      .collect(Collectors.joining("\n")));
  }
}