Блог пользователя danpol

Мой оптимайз в Delphi
Автор danpol, 12 лет назад, По-русски

Предисловие:

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 секунд на нем же и сдал задачу.

  • Проголосовать: нравится
  • -13
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Ускорение более чем в сто раз? Что-то тут нечисто. Непохоже на неасимптотическую оптимизацию. Ты видно какое-то самое важное изменение не заметил.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Видимо, дело тут просто в RandSeed. Я добавил рандомизацию в QSort и Randomize в изначальный код автора, получил AC. Без Randomize — TL 79.

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      Ну все правильно, по умолчанию randseed равен нулю, а значит можно сгенерить тест. Наверное, кто-то так и сделал.

      → Ответить
»
12 лет назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

Мне в таких случаях всегда лезет на язык мораль "Don't write in Pascal, write in [C++/Java](подставьте нужное)".

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    Это не мораль, а субъективное мнение, которое думающий человек не стал бы диктовать другим.

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится -45 Проголосовать: не нравится

      ОК, я не буду читать кому-то мораль (Вам в особенности, если это Вас, паскалиста, так задевает), а буду просто писать на Java, стану оранжевым, потом красным. Вы же будете писать на Паскале и навечно останетесь в Div2. Насчет причины подумайте сами, Вы же думающий человек :).

      → Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

    Вспомнился чувак, что писал в своём резюме на работу "знание языков: PASKAL". Надо футболку себе такую сделать — "Я ЗНАЮ PASKAL". А вообще если отбросить всякие предрассудки Pascal приемлемый язык.
    Когда я начинал программировать и пытался получше узнать бейсик, я прочитал в книжке замечательную вещь: "рекурсия в QBasic возможна, но бесполезна". Не помню в деталях, но суть была в том, что вы можете написать рекурсивный вызов, это скомпилируется(проинтерпретируется) но работать это будет не так как вы ожидали или не будет вообще.
    В паскале есть всё необходимое, и к тому же в нем меньше способов выстрелить себе в ногу, чем в плюсах.
    Плюсы если потребуется, изучить успеете, главное сейчас научиться программировать.

    → Ответить
»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Я просто прохожу мимо не пишу на Delphi, но насколько я знаю начиная с Delphi 2005 (и fpc какой-то там версии) есть такая штука как inline. поэтому дублировать код процедур в коде не обязательно.

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Больше быдлокода только лишь ради скорости?

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Ваня, ты же видел как Нияз пробовал найти ошибку и не нешел. А затем мы с ним вместе ставили эти оптимайзы.

    Я не спорю, что паскаль тормознутый.

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Подтверждаю, присваивание record'ов тормозило сильно. Хотя я не знаю почему.

      → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
        ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

        Мне почему-то кажется, что дело не в присваивании record'ов. Во всяком случае, присваивание ar[i] := ar[j]компилируется в такие ассемблерные команды:

        MOV ECX,DWORD PTR DS:[40A050]
MOV EDX,DWORD PTR DS:[40A040]
MOV EAX,DWORD PTR DS:[EDX*8+40A058]
MOV DWORD PTR DS:[ECX*8+40A058],EAX
MOV EAX,DWORD PTR DS:[EDX*8+40A05C]
MOV DWORD PTR DS:[ECX*8+40A05C],EAX

        Ну не может это все тормозить настолько сильно, чтобы ТЛЕ был из-за этого.

        UPD. Фактически, этот код эквивалентен свапанию отдельных полей.
        UPD2. Автору же в самом начале все объяснили, а мы тут продолжаем вести дискуссию...

        → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        А в чем проблема просто посмотреть ассемблерный код?

        Например, здесь
        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. Чуть опоздал.

        → Ответить
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          ← Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

          Задача была на геометрию, поэтому думаю, что там int64 фигурировало.

          В ассемблере особо не разбираюсь, инструкция movsd, случайно, не тормозит?

          type point = record
  x,y:int64;
end;
//...
a:=b;
c.x:=d.x;
c.y:=d.y;

          При присваивании записей получается примерно так:

          mov esi, $004097ac
mov edi, $0040979c
movsd
movsd
movsd
movsd

          А при присваивании полей:

          mov eax, [d]
mov [c], eax
mov eax, [d + $4]
mov [c + $4], eax
mov eax, [d + $8]
mov [c + $8], eax
mov eax, [d + $C]
mov [c + $C], eax
          → Ответить
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +6 Проголосовать: не нравится

            Да уж!
            Действительно, вариант с movsd (присваивание записей) у меня работает примерно в 5 раз медленней, чем присваивание по полям.
            Руки надо открутить тому, кто впопыхах делал в DELPHI генерацию кода для int64. В том числе и из-за mod.

            → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Даня, зато в какой то другой задаче у тебя было решение в 5 раз быстрее моего, хотя асимптотика та же самая была. P.S. Это же hull? У меня был на нем тл из за atan2

      → Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Оффтоп: если из-за этого быдлокода перестаёт тормозить UI и прокрутка меню становится плавной без четырёхядерного процессора, то да.

    → Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi everyone, need help. How to return array in Delphi? I write like this:

const
 massiv = array [0..500000] of longint;
function go : massiv;

But this is not correct.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    type, not const.

    → Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    you should write

    type
  MyArray = array [1 .. 500000] of int64;

function go(): MyArray;
begin
...
end;

    You can also return a pointer (it will be faster)

    type
  PointMyArray = ^MyArray;
  MyArray = array [1 .. 500000] of int64;

function go():PointMyArray;
begin 
...
end;

    As far as I know, there is no other way to return an array. You can only define it in "type".

    → Ответить
»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Ещё немного магии: создаём параллельный массив (ta[]) с исходным (a[]) и свапаем номера в нём, до выполнения сорта в нём должны быть числа от 0 до n-1, это своебразные ссылки на ячейки исходного массива, соответственно в функции-компараторе нужно обращаться через эти ссылки, как-то так: a[ta[i]].

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Помнится еще со студенчества такой парадокс, что паскальщики не думали указателями, и считали их лишней ересью сишников. В итоге простую сортировку указателей можно встретить в виде вот такого расписанного аж в три строки концепта )

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Есть подозрение, что это потому, что паскаль преподавали до темы представления данных в памяти.

      → Ответить