#algorithm #recursion #mergesort
Вопрос:
Это функция mergeSort, реализованная с использованием языка программирования C, когда мы рекурсивно вызываем функцию merge_sort в строке 5 и строке 6 , они работают параллельно или первая выполнила задание , остальные строки кода приостановлены?, как насчет строки 8, она также работает параллельно с ними?
1- void mergeSort(int arr[], int l, int r)
2- {
3-if (l < r) {
4 - int m = l (r - l) / 2;
5 - // Sort first and second halves
6 - mergeSort(arr, l, m);
7 - mergeSort(arr, m 1, r);
8 - merge(arr, l, m, r);
}
}
Комментарии:
1. Вы задавали вопросы раньше, но никогда не отмечали ответ как принятый. Есть для этого какие-нибудь причины? Есть по крайней мере один из тех, где ответ очень хорошего качества. Если вы не отметите ответы как принятые, у людей может быть меньше мотивации рассматривать ваши вопросы.
2. Об этом вопросе: реализуйте его на выбранном вами языке программирования и запустите его с помощью хорошего отладчика, шаг за шагом, и он ответит на ваш вопрос.
3. Выполняются ли эти строки параллельно или последовательно, зависит от используемого языка. Можете ли вы добавить это к своему вопросу?
4. Спасибо за ваши отзывы
Ответ №1:
Все программы выполняются строка за строкой. Не будет никакого параллельного механизма, если вы не выполняете многопоточность, которой явно не было в вашем коде.
строка 5 будет выполнена после строки 4
, строка 6 будет выполнена после строки 5
, строка 7 будет выполнена после строки 6
, строка 8 будет выполнена после строки 7
Если вы не верите, что код на самом деле выполняется строка за строкой. Здесь я приведу пример.
// a recursive function, like mergeSort
void print(int i, int j) {
printf("%d %dn", i, j);
if (j > 0) print(i, j - 1);
}
int main() {
print(1, 2);
print(2, 2);
return 0;
}
Выход:
1 2
1 1
1 0
2 2
2 1
2 0
Теперь ясно, что печать(1, 2) будет полностью выполнена до печати(2, 2)
Комментарии:
1. Можете ли вы поделиться более подробной информацией? Что заставляет вас думать, что это не выполняется параллельно?
2. @NicoHaase Это не будет выполняться параллельно. Здесь нет многопоточного кода.
3. Откуда ты это знаешь? Какой язык программирования вы предполагаете?
4. @NicoHaase Для того, чтобы он работал параллельно. Компилятор или интерпретатор должен знать, что эти коды не будут влиять друг на друга, и размещать их в разных потоках. Однако, когда вы смотрите на код, компилятору/интерпретатору просто невозможно его узнать. Внутри одного потока ясно, что инструкции будут выполняться только одна за другой и без параллельного выполнения.
5. @NicoHaase На самом деле любой язык выглядит как Java. Однако то же самое относится и к любым другим языкам, таким как JavaScript, Python, C и т.д.