Сортировка слиянием от “Программирования Scala” вызывает переполнение стека
Прямое, вырезанное и вставленное следующего алгоритма:
def msort[T](less: (T, T) => Boolean)
(xs: List[T]): List[T] = {
def merge(xs: List[T], ys: List[T]): List[T] =
(xs, ys) match {
case (Nil, _) => ys
case (_, Nil) => xs
case (x :: xs1, y :: ys1) =>
if (less(x, y)) x :: merge(xs1, ys)
else y :: merge(xs, ys1)
}
val n = xs.length / 2
if (n == 0) xs
else {
val (ys, zs) = xs splitAt n
merge(msort(less)(ys), msort(less)(zs))
}
}
вызывает StackOverflowError в 5 000 длинных списков.
Там какой-либо путь состоит в том, чтобы оптимизировать это так, чтобы это не происходило?
2 ответа
Это происходит потому, что это не хвостовая рекурсия. Вы можете исправить это, используя нестрогую коллекцию или сделав ее хвостовой рекурсивной.
Последнее решение выглядит следующим образом:
def msort[T](less: (T, T) => Boolean)
(xs: List[T]): List[T] = {
def merge(xs: List[T], ys: List[T], acc: List[T]): List[T] =
(xs, ys) match {
case (Nil, _) => ys.reverse ::: acc
case (_, Nil) => xs.reverse ::: acc
case (x :: xs1, y :: ys1) =>
if (less(x, y)) merge(xs1, ys, x :: acc)
else merge(xs, ys1, y :: acc)
}
val n = xs.length / 2
if (n == 0) xs
else {
val (ys, zs) = xs splitAt n
merge(msort(less)(ys), msort(less)(zs), Nil).reverse
}
}
Использование нестрогости предполагает либо передачу параметров по имени, либо использование нестрогих коллекций, таких как Stream . В следующем коде используется Stream только для предотвращения переполнения стека и List в другом месте:
def msort[T](less: (T, T) => Boolean)
(xs: List[T]): List[T] = {
def merge(left: List[T], right: List[T]): Stream[T] = (left, right) match {
case (x :: xs, y :: ys) if less(x, y) => Stream.cons(x, merge(xs, right))
case (x :: xs, y :: ys) => Stream.cons(y, merge(left, ys))
case _ => if (left.isEmpty) right.toStream else left.toStream
}
val n = xs.length / 2
if (n == 0) xs
else {
val (ys, zs) = xs splitAt n
merge(msort(less)(ys), msort(less)(zs)).toList
}
}
Также необходимо задать размер кэша инструкций для экземпляра подключения. Я предполагаю, что размер кэша по умолчанию равен 0. Следовательно, ничего не будет кэшировано.
-121--3691415-Мне кажется, что ваша проблема связана главным образом с тем, как вы (ab) используете пространства имен, а не с самими пространствами имен.
Похоже, что вы выбрасываете много минимально связанных «вещей» в одно пространство имен, в основном (когда вы приступаете к нему), потому что они были разработаны одним и тем же человеком. По крайней мере, ИМО, пространство имен должно отражать логическую организацию кода, а не только тот несчастный случай, когда куча утилит была написана одним и тем же человеком.
Имя пространства имен обычно должно быть достаточно длинным и описательным, чтобы предотвратить более чем наиболее удаленную возможность столкновения. Например, я обычно включаю свое имя, дату записи и краткое описание функциональности пространства имен.
Большинство клиентских кодов не должны (и часто не должны) использовать реальное имя пространства имен напрямую. Вместо этого он должен определять псевдоним пространства имен, и в большинстве кодов должно использоваться только имя псевдонима.
Объединяя точки 2 и 3, мы можем получить код примерно так:
#include "jdate.h"
namespace dt = Jerry_Coffin_Julian_Date_Dec_21_1999;
int main() {
dt::Date date;
std::cout << "Please enter a date: " << std::flush;
std::cin>>date;
dt::Julian jdate(date);
std::cout << date << " is "
<< jdate << " days after "
<< dt::Julian::base_date()
<< std::endl;
return 0;
}
Это удаляет (или, по крайней мере, резко уменьшает) связь между кодом клиента и конкретной реализацией классов даты/времени. Например, если бы я хотел повторно реализовать те же самые классы даты/времени, я мог бы поместить их в другое пространство имен и переключиться между одним и другим, просто изменив псевдоним и перекомпилировав.
На самом деле я время от времени использовал это как своего рода механизм полиморфизма времени компиляции. Например, я написал несколько версий небольшого класса «дисплея», одна из которых отображает выходные данные в списке Windows, а другая - вывод через iostreams. Код затем использует псевдоним что-то вроде:
#ifdef WINDOWED
namespace display = Windowed_Display
#else
namespace display = Console_Display
#endif
Остальная часть кода просто использует дисплеи:: независимо от , так что пока оба пространства имен реализуют весь интерфейс, я могу использовать либо один, без изменения остального кода вообще, и без каких-либо накладных расходов времени выполнения от использования указателя/ссылки на базовый класс с виртуальными функциями для реализаций.
На случай, если решения Дэниела не дали достаточно ясности, проблема заключается в том, что рекурсия слияния имеет такую же глубину, как и длина списка, и не является хвостовой рекурсией, поэтому ее нельзя преобразовать в итерацию.
Скала может преобразовать решение Даниэля по рекурсивному слиянию в нечто, приблизительно эквивалентное этому:
def merge(xs: List[T], ys: List[T]): List[T] = {
var acc:List[T] = Nil
var decx = xs
var decy = ys
while (!decx.isEmpty || !decy.isEmpty) {
(decx, decy) match {
case (Nil, _) => { acc = decy.reverse ::: acc ; decy = Nil }
case (_, Nil) => { acc = decx.reverse ::: acc ; decx = Nil }
case (x :: xs1, y :: ys1) =>
if (less(x, y)) { acc = x :: acc ; decx = xs1 }
else { acc = y :: acc ; decy = ys1 }
}
}
acc.reverse
}
, но он отслеживает все переменные для вас.
(хвостовым рекурсивным методом является метод, в котором метод вызывает только , чтобы получить полный ответ для передачи обратно; он никогда не называет себя, а затем делает что-то с результатом, прежде чем передать его обратно. Кроме того, нельзя использовать хвостовую рекурсию, если метод может быть полиморфным, поэтому он обычно работает только в объектах или с классами, помеченными как конечные.)