Как сохранить счет «все сделано» в рекурсивном алгоритме в Java?
-
09-06-2019 - |
Вопрос
У меня есть рекурсивный алгоритм, который просматривает строку, символ за символом, и анализирует его, чтобы создать древовидную структуру. Я хочу иметь возможность отслеживать индекс символа, в котором в данный момент находится анализатор (для сообщений об ошибках, как и все остальное), но я не заинтересован в реализации чего-либо вроде кортежа для обработки нескольких возвращаемых типов.
Я попытался использовать тип Integer, объявленный вне метода и переданный в рекурсивный метод, но поскольку он является окончательным, приращения рекурсивного вызова «забыты»; когда я вернусь. (Поскольку приращение значения Integer делает эталонную точку переданного по значению объекта новым объектом)
Есть ли способ получить что-то похожее на работу, которая не будет загрязнять мой код?
Решение
Поскольку вы уже обнаружили псевдо-изменяемое целое число " hack, " как насчет этого варианта:
Имеет ли смысл создавать отдельный класс Parser? Если вы сделаете это, вы можете сохранить текущее состояние в переменной-члене. Возможно, вам нужно подумать о том, как вы собираетесь решать любые проблемы безопасности потоков, и это может быть излишним для этого конкретного приложения, но это может сработать для вас.
Другие советы
Это что-то вроде хака, но иногда я использую AtomicInteger, который является изменяемым, чтобы делать такие вещи. Я также видел случаи, когда передается int [] размера 1.
Текущее решение, которое я использую:
int[] counter = {0};
и затем передайте его рекурсивному алгоритму:
public List<Thing> doIt (String aString, int[] counter) { ... }
и когда я хочу увеличить его:
counter[0]++;
Не супер элегантно, но работает ...
Целые числа являются неизменяемыми, что означает, что когда вы передаете его в качестве аргумента, он создает копию, а не ссылку на тот же элемент. ( объяснение ). р>
Чтобы получить поведение, которое вы ищете, вы можете написать свой собственный класс, который похож на Integer только изменяемый. Затем просто передайте его в рекурсивную функцию, он увеличивается в пределах рекурсии, и при повторном доступе к нему после завершения рекурсии он все равно сохранит свои новые значения.
Редактировать. Обратите внимание, что использование массива int [] является разновидностью этого метода ... В Java массивы также передаются по ссылке, а не копируются как примитивы или неизменные классы.
Вы можете просто использовать статическую переменную класса int, которая увеличивается при каждом вызове метода doIt.
Вы также можете сделать:
private int recurse (int i) {
if (someConditionkeepOnGoing) {
i = recurse(i+1);
}
return i;
}
Если честно, я бы перекодировал функцию, чтобы сделать ее линейным алгоритмом, использующим цикл. Таким образом, у вас нет шансов исчерпать пространство кучи, если вы шагаете через чрезвычайно большую строку. Кроме того, вам не нужно иметь дополнительный параметр, чтобы отслеживать количество.
Вероятно, это также приведет к ускорению алгоритма, поскольку не нужно вызывать функцию для каждого символа.
Если, конечно, нет конкретной причины, она должна быть рекурсивной.
Одна из возможностей, которую я могу придумать, - сохранить счетчик в переменной-члене класса. Это, конечно, предполагает, что открытый метод doIt
вызывается только одним потоком.
Другой вариант - это реорганизовать открытый метод для вызова частного вспомогательного метода. Закрытый метод принимает список в качестве параметра и возвращает количество. Например:
public List<Thing> doIt(String aString) {
List<Thing> list = new ArrayList<Thing>();
int count = doItHelper(aString, list, 0);
// ...
return list;
}
private int doItHelper(String aString, List<Thing> list, int count) {
// ...
// do something that updates count
count = doItHelper(aString, list, count);
// ...
return count;
}
Предполагается, что вы можете выполнять обработку ошибок в общедоступном методе doIt
, поскольку переменная count
фактически не передается вызывающей стороне. Если вам нужно сделать это, вы, конечно, можете выдать исключение:
public List<Thing> doIt(String aString) throws SomeCustomException {
List<Thing> list = new ArrayList<Thing>();
int count = doItHelper(aString, list, 0);
// ...
if (someErrorOccurred) {
throw new SomeCustomException("Error occurred at chracter index " + count, count);
}
return list;
}
Трудно понять, поможет ли это, не зная больше о том, как на самом деле работает ваш алгоритм.