Предисловие:
1) На одном из раундов CF я получил TL на халявной задаче и не смог его отладить, несмотря на то что асимптотика решения была O(NlogN), что влезало в LT
2) На одном из туров в ЛКШ у меня не прошла задача на тупое построение выпуклой оболочки за O(NlogN), что влезало в TL.
Итак, я был зол...
В первой задаче в итоге мне хватило только random-а в QSort-е. Но со второй не так-то уж все и просто оказалось.
Что же я сделал?
о1) Будем передавать все параметры по ссылке, а не по значению. (var или const)
о2) Будем делать рандомизтрованный QSort
о3) Магия: вместо свопанья структурок будем свопать отдельные поля! (Если убрать остальные оптимайзы, и оставить только о3 все проходит!
о4) Т.к. TL критичен, избавимся от лишних вызовов "быстрых" {O(1)} функций.
o5) функции "в одну строчку" типа подсчета скалярного произведения выкиним вообще и будем каждый раз вычислять в длинных формулах.
Вот так с 1.006 секунд на тесте, на котором я получал TL, я получил 0.010 секунд на нем же и сдал задачу.
Ускорение более чем в сто раз? Что-то тут нечисто. Непохоже на неасимптотическую оптимизацию. Ты видно какое-то самое важное изменение не заметил.
Видимо, дело тут просто в RandSeed. Я добавил рандомизацию в QSort и Randomize в изначальный код автора, получил AC. Без Randomize — TL 79.
Ну все правильно, по умолчанию randseed равен нулю, а значит можно сгенерить тест. Наверное, кто-то так и сделал.
Мне в таких случаях всегда лезет на язык мораль "Don't write in Pascal, write in [C++/Java](подставьте нужное)".
Это не мораль, а субъективное мнение, которое думающий человек не стал бы диктовать другим.
ОК, я не буду читать кому-то мораль (Вам в особенности, если это Вас, паскалиста, так задевает), а буду просто писать на Java, стану оранжевым, потом красным. Вы же будете писать на Паскале и навечно останетесь в Div2. Насчет причины подумайте сами, Вы же думающий человек :).
Да, да. И кто тут по рейтингу первый?!
Слов на вас цензурных нет
Не Вы :).
Вспомнился чувак, что писал в своём резюме на работу "знание языков: PASKAL". Надо футболку себе такую сделать — "Я ЗНАЮ PASKAL". А вообще если отбросить всякие предрассудки Pascal приемлемый язык.
Когда я начинал программировать и пытался получше узнать бейсик, я прочитал в книжке замечательную вещь: "рекурсия в QBasic возможна, но бесполезна". Не помню в деталях, но суть была в том, что вы можете написать рекурсивный вызов, это скомпилируется(проинтерпретируется) но работать это будет не так как вы ожидали или не будет вообще.
В паскале есть всё необходимое, и к тому же в нем меньше способов выстрелить себе в ногу, чем в плюсах.
Плюсы если потребуется, изучить успеете, главное сейчас научиться программировать.
Я
просто прохожу мимоне пишу на Delphi, но насколько я знаю начиная с Delphi 2005 (и fpc какой-то там версии) есть такая штука как inline. поэтому дублировать код процедур в коде не обязательно.Больше быдлокода только лишь ради скорости?
Ваня, ты же видел как Нияз пробовал найти ошибку и не нешел. А затем мы с ним вместе ставили эти оптимайзы.
Я не спорю, что паскаль тормознутый.
Подтверждаю, присваивание record'ов тормозило сильно. Хотя я не знаю почему.
Мне почему-то кажется, что дело не в присваивании record'ов. Во всяком случае, присваивание
ar[i] := ar[j]компилируется в такие ассемблерные команды:Ну не может это все тормозить настолько сильно, чтобы ТЛЕ был из-за этого.
UPD. Фактически, этот код эквивалентен свапанию отдельных полей.
UPD2. Автору же в самом начале все объяснили, а мы тут продолжаем вести дискуссию...
да. я все же не прав
А в чем проблема просто посмотреть ассемблерный код?
Например, здесь
type
R = record
a, b: longint;
end;
var c, d: R;
begin
// между этим
c := d;
// и этим
c.a := d.a; c.b:= d.b;
end.
нет никакой разницы, по 4 команды
mov eax,[d]
mov [c],eax
mov eax,[d + $4]
mov [c + $4],eax
А у вас есть разница?
UPD. Чуть опоздал.
Задача была на геометрию, поэтому думаю, что там int64 фигурировало.
В ассемблере особо не разбираюсь, инструкция movsd, случайно, не тормозит?
При присваивании записей получается примерно так:
А при присваивании полей:
Да уж!
Действительно, вариант с movsd (присваивание записей) у меня работает примерно в 5 раз медленней, чем присваивание по полям.
Руки надо открутить тому, кто впопыхах делал в DELPHI генерацию кода для int64. В том числе и из-за mod.
Даня, зато в какой то другой задаче у тебя было решение в 5 раз быстрее моего, хотя асимптотика та же самая была. P.S. Это же hull? У меня был на нем тл из за atan2
Оффтоп: если из-за этого быдлокода перестаёт тормозить UI и прокрутка меню становится плавной без четырёхядерного процессора, то да.
Hi everyone, need help. How to return array in Delphi? I write like this:
But this is not correct.
type, not const.
you should write
You can also return a pointer (it will be faster)
As far as I know, there is no other way to return an array. You can only define it in "type".
Ещё немного магии: создаём параллельный массив (ta[]) с исходным (a[]) и свапаем номера в нём, до выполнения сорта в нём должны быть числа от 0 до n-1, это своебразные ссылки на ячейки исходного массива, соответственно в функции-компараторе нужно обращаться через эти ссылки, как-то так: a[ta[i]].
Помнится еще со студенчества такой парадокс, что паскальщики не думали указателями, и считали их лишней ересью сишников. В итоге простую сортировку указателей можно встретить в виде вот такого расписанного аж в три строки концепта )
Есть подозрение, что это потому, что паскаль преподавали до темы представления данных в памяти.