OberonCore https://forum.oberoncore.ru/ |
|
Оптимизация алгоритмов https://forum.oberoncore.ru/viewtopic.php?f=5&t=3620 |
Страница 4 из 4 |
Автор: | albobin [ Понедельник, 24 Октябрь, 2011 16:25 ] |
Заголовок сообщения: | Re: Оптимизация алгоритмов |
alexus писал(а): Если интересно, то могу привести код на ассемблере (без ухищрений, чтобы было легче воспринимать). Приведите, подозреваю он будет соответствовать тому о чём уже неоднократно писал Илья Ермаков (повторное использование фрейма в стеке) |
Автор: | alexus [ Понедельник, 24 Октябрь, 2011 17:02 ] |
Заголовок сообщения: | Re: Оптимизация алгоритмов |
Код: procedure QuickSort(var a: TAOFI; const left, right: Integer); procedure QS_Asm(const l, r: Integer); register; var left, right : Integer; asm mov [left],edx mov [right],ecx mov edi,[esi + edx * 4] mov ebx,-1 @@1: cmp ecx,edx ; if (j = i) then je @@5 ; goto @@5 or ebx,ebx ; if (d = False) then jz @@2 ; goto @@2 mov eax,[esi + ecx * 4] ; eax := a[j] cmp edi,eax ; if (x <= a[j]) then jle @@3 ; goto @@3 ( dec(j) ) mov [esi + edx * 4],eax ; a[i] := a[j] not ebx ; d := False jmp @@4 ; goto @@4 ( inc(i) ); @@2: mov eax,[esi + edx * 4] ; eax := a[i] cmp eax,edi ; if (a[i] <= x) then jle @@4 ; goto @@4 ( inc(i) ) mov [esi + ecx * 4],eax ; a[j] := a[i] not ebx ; d := True @@3: dec ecx ; dec(j) jmp @@1 ; goto loop_start @@4: inc edx ; inc(i) jmp @@1 ; goto loop_start @@5: mov [esi + edx * 4],edi ; a[i] := x dec edx ; dec(i) inc ecx ; inc(j) cmp [left],edx ; if (left >= i) then jge @@6 ; goto @@6 xchg ecx,[left] ; save ecx xchg ecx,edx ; edx := left; ecx = i; call QS_Asm mov ecx,[left] ; restore ecx (j) @@6: cmp ecx,[right] ; if (j >= right) then jge @@7 ; goto @@7 mov edx,ecx ; edx := j mov ecx,[right] ; ecx := right call QS_Asm @@7: end; asm push ebx push esi push edi mov esi,eax ; esi = address array call QS_Asm pop edi pop esi pop ebx end; ebx -> d edx -> i ecx -> j esi -> address of array |
Автор: | Владислав Жаринов [ Понедельник, 24 Октябрь, 2011 17:08 ] |
Заголовок сообщения: | Re: Оптимизация алгоритмов |
Разрисовать бы примерно как здесь... |
Автор: | alexus [ Понедельник, 24 Октябрь, 2011 17:30 ] |
Заголовок сообщения: | Re: Оптимизация алгоритмов |
Владислав Жаринов писал(а): Разрисовать бы примерно как здесь... Вроде бы всё прокомментировано... К сожалению табуляция другая...
|
Автор: | albobin [ Понедельник, 24 Октябрь, 2011 17:35 ] |
Заголовок сообщения: | Re: Оптимизация алгоритмов |
albobin писал(а): подозреваю он будет соответствовать тому о чём уже неоднократно писал Илья Ермаков (повторное использование фрейма в стеке) Ошибся в подозрениях. Подумал, что Вы собирались показать борьбу с рекурсией. Но это не важно. Любопытство моё удовлетворено, спасибо. |
Автор: | alexus [ Понедельник, 24 Октябрь, 2011 17:50 ] |
Заголовок сообщения: | Re: Оптимизация алгоритмов |
albobin писал(а): albobin писал(а): подозреваю он будет соответствовать тому о чём уже неоднократно писал Илья Ермаков (повторное использование фрейма в стеке) Ошибся в подозрениях. Подумал, что Вы собирались показать борьбу с рекурсией. Но это не важно. Любопытство моё удовлетворено, спасибо. |
Автор: | albobin [ Понедельник, 24 Октябрь, 2011 19:09 ] |
Заголовок сообщения: | Re: Оптимизация алгоритмов |
alexus писал(а): Борьбу с рекурсией тоже можно показать... Мой проявленный интерес носит отчасти праздный характер, будет лучше если Вы найдёте действительно заинтересованного собеседника по сабжу. |
Автор: | Илья Ермаков [ Вторник, 25 Октябрь, 2011 11:27 ] |
Заголовок сообщения: | Re: Оптимизация алгоритмов |
Цитата: Хм?.. Непонятно, о каких гарантиях идёт речь?.. Я имею в виду, что если в стандарте языка будет указано, что "компилятор языка обязан трансформировать статически обнаруженный концевой рекурсивный вызов", то я смогу писать алгоритм, полагаясь на этот факт (например, программировать "бесконечно" работающий КА); а иначе на каком-нибудь компиляторе получу вылет за стек после первой же тысячи-другой переходов автомата Цитата: Ух, тут бы не ошибиться... если в одной процедуре количество формальных параметров, передаваемых через стек, будет иным, чем в той процедуре, откуда прыгали (jump), то... проблемы возникнут при разгрузке стека. Тоже относится к совокупному размеру локальных переменных... Ну, jump компилятор пусть генерирует, если процедуры без параметров (например, прыгаем между вложенными процедурами), а в противном случае пусть обычный call, но сначала разгружает стек уже оконченной вызывающей процедуры. Да, да, есть ещё вопрос, как с VAR-параметрами - можно запретить. Вообще, этот механизм может решить все проблемы, когда одномерное структурное программирование "жмёт". Вместо goto - концевая передача управления от процедуры к процедуре. Может быть, стоит не делать оптимизацию концевого вызова, а ввести отд. оператор, который обозначает совершение такого вызова с завершением вызывающей процедуры. Нюансов много, но простой вариант найти можно, а овчинка выделки стоит. Оптимизация рекурсий, автоматность, строгий вариант goto для алгоритмов управляющего характера - всё одним средством. |
Автор: | alexus [ Вторник, 25 Октябрь, 2011 13:31 ] |
Заголовок сообщения: | Re: Оптимизация алгоритмов |
Илья Ермаков писал(а): Я имею в виду, что если в стандарте языка будет указано, что "компилятор языка обязан трансформировать статически обнаруженный концевой рекурсивный вызов", то я смогу писать алгоритм, полагаясь на этот факт (например, программировать "бесконечно" работающий КА); а иначе на каком-нибудь компиляторе получу вылет за стек после первой же тысячи-другой переходов автомата Не думаю, что это хорошая идея... Проще/правильнее сделать работу на основе сообщений. В противном случае, единожды скомпилированный код будет работать по одной и той же схеме, что не очень гибко... Представьте, что в том же QiuckSort вместо концевых вызовов отсылаются соответствующие сообщения. По мере возможности исполнитель обрабатывает эти сообщения... параллельно (каждое сообщение определяет свою часть массива, и эти части не пересекаются, это очень удобно для параллельной обработки). Сообщения можно упорядочить, по "уровню вложенности" (чем больше "уровень вложенности", тем позже обрабатывается/ниже приоритет сообщения).А если делать переходы, то точки перехода нужно оставить программируемыми, типа: Код: jmp [jump_address] Тогда адрес перехода можно будет менять в зависимости от условий/результата выполнения данного перехода или... извне.Илья Ермаков писал(а): Ну, jump компилятор пусть генерирует, если процедуры без параметров (например, прыгаем между вложенными процедурами), а в противном случае пусть обычный call, но сначала разгружает стек уже оконченной вызывающей процедуры. Разгрузив стек до перехода, мы утрачиваем контекст исполнения (фактические параметры, локальные переменные, результаты...). Сообщения всё же лучше... Их можно перенаправлять, перехватывать, игнорировать, откладывать, переставлять в каком-то заданном порядке, обобщать, делать пакетную обработку и т.п...Илья Ермаков писал(а): Да, да, есть ещё вопрос, как с VAR-параметрами - можно запретить. Простым запрещением эту задачу не решить, IMHO. Нужен полноценный аппарат разрешения конфликтов.Илья Ермаков писал(а): Вообще, этот механизм может решить все проблемы, когда одномерное структурное программирование "жмёт". Вместо goto - концевая передача управления от процедуры к процедуре. Собственно, что-то всё равно нужно... либо адрес возврата, либо адрес перехода, альтернатива им... halt/передача управления системе, но это не слишком разумно.Может быть, стоит не делать оптимизацию концевого вызова, а ввести отд. оператор, который обозначает совершение такого вызова с завершением вызывающей процедуры. Илья Ермаков писал(а): Нюансов много, но простой вариант найти можно, а овчинка выделки стоит. Оптимизация рекурсий, автоматность, строгий вариант goto для алгоритмов управляющего характера - всё одним средством. ... сообщением...
|
Автор: | Илья Ермаков [ Вторник, 25 Октябрь, 2011 14:32 ] |
Заголовок сообщения: | Re: Оптимизация алгоритмов |
Это уже выше уровнем, дальше от оборудования... По поводу принятия решения о переходе: так никто не запрещает писать IF ... THEN A ELSE B END. Компилятор статически способен легко определить, что здесь оба вызова концевые. |
Автор: | alexus [ Вторник, 25 Октябрь, 2011 15:24 ] |
Заголовок сообщения: | Re: Оптимизация алгоритмов |
Илья Ермаков писал(а): Это уже выше уровнем, дальше от оборудования... Не обязательно выше... Уровень определяется абстракциями, которыми мы оперируем. Можно считать, что нижний уровень абстракций - оператор, например, i := 8;, а кто то думает, что процессор посылает сообщение контроллеру памяти, записать в двойное слово, по адресу [ebp - 12], значение 8... Илья Ермаков писал(а): По поводу принятия решения о переходе: Да, конечно.
так никто не запрещает писать IF ... THEN A ELSE B END. Компилятор статически способен легко определить, что здесь оба вызова концевые. |
Автор: | Владислав Жаринов [ Среда, 26 Октябрь, 2011 19:10 ] |
Заголовок сообщения: | Re: Оптимизация алгоритмов |
alexus писал(а): Владислав Жаринов писал(а): Разрисовать бы примерно как здесь... Вроде бы всё прокомментировано... К сожалению табуляция другая... |
Страница 4 из 4 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |