Комбинации (n выберите k) параллелизация и эффективность

Недавно я работал с комбинациями слов, чтобы сделать «фразы» на разных языках, и я заметил несколько вещей, которые я мог бы сделать с некоторыми дополнительными экспертными знаниями.Комбинации (n выберите k) параллелизация и эффективность

Определение некоторых констант для этого,

Глубины (n) составляет в среднем 6-7

Длина входного набора составляет ~ 160 уникальных слов.

Память. Генерация n перестановок на 160 слов тратит много места. Я могу злоупотреблять базами данных, записывая их на диск, но потом я получаю удар в производительности, так как мне нужно постоянно ждать ввода-вывода. Другой трюк состоит в том, чтобы сгенерировать комбинации на лету, как объект генератора.
Время - если я не ошибаюсь n choose k получает большой быстро что-то вроде этой формулы factorial(n)/(factorial(depth) * (factorial(n-depth))) это означает, что наборы ввода быстро становятся огромными.

Мой вопрос, таким образом.

Учитывая, что у меня есть функция f(x), которая берет комбинацию и применяет расчет, который имеет стоимость, например.

func f(x) { 
    if query_mysql("text search query").value > 15 { 
     return true 
    } 
    return false 
}

Как я могу эффективно обрабатывать и выполнять эту функцию на огромном наборе комбинаций?

Бонусные вопросы, могут быть сгенерированы комбинации одновременно?

Обновление: Я уже знаю, как их генерировать условно, тем более его эффективность.

источник

2014-02-10 Jakob Bowyer

«глубина» остается постоянной при вычислении. Таким образом, для одного запуска алгоритма ваш вывод представляет собой комбинацию слов 'depth = 6' из слова длиной 160 или всех комбинаций слов в диапазоне' [1,6] '? –

@MattiLyra В идеале я хочу, чтобы глубина была от [n..2], но позвольте мне сосредоточиться на одном на данный момент и удалили строку для ясности. –

Хорошо, что дало бы вам один способ распараллеливания комбинаций, запустить каждый из «n = 3, n = 4 ... n = n' параллельно, поскольку они не зависят друг от друга. –

Используйте один из многих известных алгоритмов для генерации комбинаций. Алгоритм Chiddle Chiddle является одним из самых известных и совершенно подходящих. Он захватывает состояние в массиве, поэтому его можно перезапустить или засеять, если хотите.

См. Algorithm to return all combinations of k elements from n для получения более подробной информации.

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

Этот алгоритм (и многие другие) легко адаптируется для параллельного выполнения, если у вас есть необходимые навыки.

источник

2014-02-10 10:00:57

Это не отвечает на вопрос в малейшей степени. –

Тогда вы должны задать более интересные вопросы. Если вам нужен ответ, в котором объясняется, как использовать сокращение карты или Hadoop, тогда скажите это. –

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

Один из подходов заключается в том, чтобы сначала рассчитать, сколько параллелизма вы можете получить, исходя из количества потоков, которые у вас есть. Пусть число нитей будет T, и разделить работу следующим образом:

сортировать элементы в соответствии с определенным порядком.
Найти наименьшее число d таких, что Choose(n,d) >= T.
Найти все комбинации «глубина» (точно) d (обычно намного ниже, чем до глубины d, и вычислить на одном ядре).
Теперь распространите работу на свои T-сердечники, каждый из которых получает набор «префиксов» (каждый префикс c представляет собой комбинацию размера d), и для каждого случая найдите все суффиксы, в которых их «самый маленький» элемент - больше "max(c) в соответствии с общим заказом.

Этот подход также может быть хорошо переведен на map-reduce парадигма.

map(words): //one mapper 
    sort(words) //by some total ordering function 
    generate all combiations of depth `d` exactly // NOT K!!! 
    for each combination c produced: 
     idx <- index in words of max(c) 
     emit(c,words[idx+1:end]) 
reduce(c1, words): //T reducers 
    combinations <- generate all combinations of size k-d from words 
    for each c2 in combinations: 
     c <- concat(c1,c2) 
     emit(c,f(c))

источник

2014-02-10 10:31:56 amit

Комбинации (n выберите k) параллелизация и эффективность

ответ

Смежные вопросы