Распараллеливание алгоритма комбинаторики

Question

Я пишу программу, которая рассчитывает комбинации C (n, k) и имеет большую разницу между n и k (например, n = 39, k = 13 -> 8122425444 комбинации). Кроме того, мне нужно сделать некоторые вычисления с каждой комбинацией в режиме реального времени. Вопрос в том, как разделить алгоритм на несколько потоков, чтобы он стал быстрее?

public void getCombinations(List<Item> items) {
    int n = items.size();
    int k = 13;
    int[] res = new int[k];
    for (int i = 1; i <= k; i++) {
        res[i - 1] = i;
    }
    int p = k;
    while (p >= 1) {
        //here I make a Set from items in List by ids in res[]
        Set<Item> cards = convert(res, items);
        //some calculations
        if (res[k - 1] == n) {
            p--;
        } else {
            p = k;
        }
        if (p >= 1) {
            for (int i = k; i >= p; i--) {
                res[i - 1] = res[p - 1] + i - p + 1;
            }
        }
    }
}

private Set<Item> convert(int[] res, List<Item> items) {
    Set<Item> set = new TreeSet<Item>();
    for (int i : res) {
        set.add(items.get(i - 1));
    }
    return set;
}

Answer 1

Если вы используете JDK 7, вы можете использовать fork / join, чтобы разделить и победить этот алгоритм.

Если вы хотите, чтобы все было просто, я бы просто получил поток для вычисления подмножества входных данных и использовал CountDownLatch до тех пор, пока все потоки не будут завершены. Количество потоков зависит от вашего процессора.

Вы также можете использовать карту / уменьшение Hadoop, если вы думаете, что вход будет расти, так что вы можете вычислить на нескольких компьютерах. Вам нужно будет нормализовать это как операцию отображения / уменьшения - но посмотрите на примеры.

Answer 2

Я работал над кодом, который работает с комбинаторными множествами такого размера.Вот несколько советов для получения результатов в разумные сроки.

• Вместо того, чтобы составлять список комбинаций и затем обрабатывать их, напишите свою программу, чтобы получить ранг для комбинации.Вы можете безопасно назначать 64-битные значения со знаком каждой комбинации для всех значений k вплоть до n = 66. Это позволит вам легко разбить систему счисления и назначить ее различным потокам / аппаратным средствам.
• Если ваши вычисленияэто просто, вы должны посмотреть на использование OpenCL или CUDA для выполнения этой работы.Есть несколько вариантов для этого. Rootbeer и Aparapi - это варианты для того, чтобы остаться на Java и позволить библиотеке позаботиться о деталях графического процессора. JavaCL - хорошая привязка к OpenCL, если вы не против писать ядра непосредственно в C99.AWS имеет экземпляр GPU для выполнения этого типа работы.
• Если вы собираетесь собирать результаты для каждой комбинации, вам действительно нужно учитывать пространство для хранения.Для вашего примера C (39,13) вам понадобится немного меньше 61 гига, чтобы хранить лонг для каждой комбинации.Вам нужна хорошая стратегия для работы с наборами данных такого размера.
  • Если вы пытаетесь свернуть эти данные в простой результат для всего набора комбинаций, то следуйте предложению @algolicious и посмотрите на карту / уменьшить, чтобы решить эту проблему.
  • Есливам действительно нужны ответы для каждой комбинации, но с небольшой ошибкой все в порядке, вы можете посмотреть на использование алгоритмов ИИ или линейного решателя для сжатия данных.Имейте в виду, что эти методы будут работать только в том случае, если есть что-то, чему можно научиться в результирующих данных.
  • Если какая-то ошибка не сработает, но вам нужен каждый ответ, вы можете просто подумать о ее повторном вычислении каждый раз, когда вам нужноэто, основываясь на ранге элемента.

Answer 3

Ваш вопрос довольно расплывчатый.

Какая проблема у вас сейчас? Реализация части алгоритма «разделяй и властвуй» (многопоточность, объединение и т. Д.) Или выяснение, как разделить проблему на ее части.

Позднее должен быть ваш первый шаг. Знаете ли вы, как разбить исходную проблему на несколько более мелких проблем (которые затем можно отправить в потоки Executor или аналогичный механизм для обработки) и как объединить результаты?

Answer 4

Самый простой способ разделения комбинаций - это иметь комбинации комбинаций. ;)

Для каждого возможного «первого» значения вы можете создать новую задачу в пуле потоков. Или вы можете создать каждую возможную пару «первый» и «второй» в качестве новой задачи. или три и т. д. Вам нужно всего лишь создать столько задач, сколько у вас есть процессоров, так что вам не нужно переходить за борт.

например. скажем, вы хотите создать все возможные выборы из 13 из 39 предметов.

for(Item item: items) {
   List<Item> items2 = new ArrayList<Item>(items);
   items2.remove(item);
   // create a task which considers all selections of 12 from 38 (plus item)
   createCombinationsOf(item, item2, 12);
}

Это создает примерно равную работу для 39 процессоров, что может быть более чем достаточно. Если вы хотите больше, создайте пары (39 * 38/2) из ​​них.