Эта статья продолжает историю, начатую в двух моих предыдущих статьях:
Одним из основных обещаний статически типизированного Groovy является возможность легко смешивать динамический и статический код вместе. Сегодня я собираюсь показать, как это делается и что происходит во время компиляции.
Как обычно, мы будем работать с некоторым примером, который должен помочь нам увидеть все в действии. В качестве дополнительных бонусов поговорим о хвостовой рекурсии и параллелизме.
Задача: для заданного диапазона целых чисел сгенерировать отчет XML, содержащий для каждого числа либо простое число, либо все делители числа
Вот отчет, который мы хотим сгенерировать
<numbers>
<number value='2' prime='true' />
<number value='3' prime='true' />
<number value='4' prime='false'>
<divisor value='2' />
<divisor value='2' />
</number>
<number value='5' prime='true' />
<number value='6' prime='false'>
<divisor value='2' />
<divisor value='3' />
</number>
<number value='7' prime='true' />
<number value='8' prime='false'>
<divisor value='2' />
<divisor value='2' />
<divisor value='2' />
</number>
<numbers>
Вот решение проблемы
new MarkupBuilder ().numbers {
def divisors = { int n, Collection alreadyFound = [] ->
if (n > 3)
for(candidate in 2..<n)
if (n % candidate == 0)
return doCall (n / candidate, alreadyFound << candidate)
alreadyFound << n
}
(2..1500).each {
def divs = divisors(it) ]
if (divs.size () == 1)
number ([value: it, prime:true ])
else {
number ([value: it, prime:false]) {
divs.each { div ->
divisor([value: div])
}
}
}
}
}
Да, это правда — 23 строки выше — это действительно так. Благодаря выразительности Groovy и мощным стандартным библиотекам.
Давайте проанализируем, что здесь происходит. Прежде всего, наш основной инструмент — замечательный groovy.xml.MarkupBuilder , который заботится о генерации XML-вывода. Каждый, кто знаком с Groovy, узнает следующий код.
new MarkupBuilder ().numbers {
...................
(2..1500).each {
def divs = divisors(it)
if (divs.size () == 1)
number ([value: it, prime:true ])
else {
number ([value: it, prime:false]) {
divs.each { div ->
divisor([value: div])
}
}
}
}
}
Но здесь интересно то, что есть только четыре вызова, которые отправляются динамически (или медленно, если хотите). И это именно те вызовы, которые мы наблюдаем, чтобы быть динамическими (чтобы позволить MarkupBuilder выполнять свою работу)
- цифры — строка 1
- номер — линии 6 и 8
- делитель — строка 10
Всем остальным не нужно вводить какие-либо динамические издержки, так что это не так. Через секунду мы увидим, что для компилятора очевидно, что делителями (it) является java.util.Collection, а остальное следует из простого вывода типа.
NB : Метод каждый используемый выше немного отличается от стандартного , который используется в Groovy выполнения. Он делает то же самое, но без динамических вызовов Iterator и Closure. Компилятор распознает, когда это не нужно, и использует оптимизированную версию.
Давайте теперь посмотрим на расчет делителей. Наш алгоритм рядом с тривиальным
- проверить кандидатов, пока мы нашли делитель
- когда найден, вставьте его в результат java.lang.Collection
- примените ту же процедуру к исходному числу, разделенному на найденный делитель
def divisors = { int n, Collection alreadyFound = [] ->
if (n > 3)
for(candidate in 2..<n)
if (n % candidate == 0)
return doCall (n / candidate, alreadyFound << candidate)
alreadyFound << n
}
Здесь вся мощь хвостовой рекурсии встречается вместе с выводом типа и параметрами по умолчанию. Вся информация о типах, которую мы должны были предоставить, была типами параметров нашего закрытия. Компилятор может вычесть остальное, включая возвращаемый тип расчета ( java.util.Collection ). Похоже на убийственную комбинацию.
Вызов метода doCall кажется немного волшебным, но не тем, кто знаком с анатомией замыканий Groovy. Это условное название для методов, реализуемых замыканиями.
Фактически, то, что мы видим выше, это метод doCall, вызывающий себя рекурсивно. Именно тот случай, который может быть оптимизирован компилятором.
Мы сделали с нашей основной задачей.
Давайте теперь добавим немного параллелизма в микс.
Мы хотим сгенерировать наши делители несколькими потоками (используя java.util.concurrent.Executor ) и создать разметку в основном потоке.
Модификации, требуемые нашим кодом, минимальны.
new MarkupBuilder ().numbers {
def divisors = { int n, Collection alreadyFound = [] ->
if (n > 3)
for(candidate in 2..<n)
if (n % candidate == 0)
return doCall (n / candidate, alreadyFound << candidate)
alreadyFound << n
}
(2..1500).iterator().mapConcurrently(Executors.newFixedThreadPool(10), false, 50) {
new Pair(it, divisors(it))
}.each { pair ->
if (pair.second.size () == 1)
number ([value: pair.first, prime:true ])
else {
number ([value: pair.first, prime:false]) {
pair.second.each { div ->
divisor([value: div])
}
}
}
}
}
Прежде всего, мы изменим немного наш основной each- цикл. Теперь он не вычисляет делители, а работает с парами (целое число, набор делителей). Пары Thease представлены с использованием Iterator <Pair <Integer, Collection >>. Class Pair является частью стандартной библиотеки, которая разрабатывается вместе со статическим Groovy. Надеюсь, легко представить, что он делает.
Во-вторых, и что более интересно, мы используем другой стандартный метод, который отображает Iterator в Iterator (в нашем случае Iterator <Integer>, сопоставленный с Iterator <Pair <Integer, Collection>), выполняя данную функцию отображения для данного java.util.concurrent.Executor и убедитесь, что одновременно выполняется не более указанного числа отображений (в нашем случае 50). Этот метод также может контролировать, нужно ли нам сохранять порядок элементов или nor (false в нашем случае)
Это звучит как довольно сложный алгоритм, но на самом деле это не так. Вот немного упрощенный код (без контроля порядка, без обработки значений по умолчанию для параметров)
static <T, R> Iterator<R> mapConcurrently(Iterator<T> self,
Executor executor,
int maxConcurrentTasks,
Function1<T, R> op) {
[ pending: new AtomicInteger(),
ready: new LinkedBlockingQueue<R>(),
scheduleIfNeeded: {->
while (self && ready.size() + pending.get() < maxConcurrentTasks) {
pending.incrementAndGet()
def nextElement = self.next()
executor.execute {-> ready << op.apply(nextElement); pending.decrementAndGet() }
}
},
next: {->
def res = ready.take()
scheduleIfNeeded()
res
},
hasNext: {-> scheduleIfNeeded(); !ready.empty || pending.get() > 0 },
remove: {-> throw new UnsupportedOperationException("remove () is unsupported by the iterator") },
]
}
Что меня действительно впечатляет, так это то, как выразительность Groovy позволяет писать нетривиальный параллельный алгоритм всего за несколько строк кода. Я оставляю любопытному читателю реализовать то же самое с Java.
Спасибо за чтение и до следующего раза.