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

Яндекс Квал 2, Задача С, TL 101
Автор Shtrix, 14 лет назад, По-русски
Замечательные впечатления оставил следующий эксперемент. Одно и тоже решение задачи С использующее priority_queue было сдано на двух компиляторах. 

Итог:

Visual Studio 2005: TL 101 (как и на контесте)
GCC 4.6+: AC, 1090ms

Посылки:
442400
442399

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

14 лет назад, # |
← Rev. 2   Проголосовать: нравится -7 Проголосовать: не нравится

Под студией свободно проходило с использованием не priority_queue, а своей рукописной кучи (330 мс), причем без всяких прочих модернизаций. Вывод: меньше priority_queue - больше профита ) и лениться не надо писать свой код, когда знаешь, что stl работает дольше
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится
    Точно! Вы на всех контестах вместо мапа пишете свое сбалансированное двоичное дерево, или только на КФ?
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Я только про stl-кую очередь с приоритетами писал, вообще-то
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        у меня решение на priority_queue работает 530 мс, так-что не много вы выиграли написав ручками. А тайм лимит и правда плохой выставлен, совсем не очевидно что на сетах завалится, я просто подумал что мало-ли, и написал на очереди, а на сетах потом затлилось. оба решения писал в дорешке.
        → Ответить
    • 14 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      Стандартные доводы: а вы умеете писать замену map так, чтобы она заработала без особого дебага?
      Я лично знаю несколько человек, которые пишут на C++, используя sort и ту же очередь с приоритетами, совершенно не имея представления, как это работает. Имхо, это плохо, т.к. такие простые вещи, раз уж ты их используешь, ты должен уметь реализовывать сам
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я иронизировал конкретно по поводу фразы "и лениться не надо писать свой код, когда знаешь, что stl работает дольше". Ясно же, что ручной мап работает быстрее СТЛевского, но его никто не пишет.
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Согласен насчет мапа, но тут конкретно про priority_queue разговор был. Мне кажется, в таких задачах, где правильное решение может не пройти по TL, имеет смысл оптимизировать,  в том числе заменяя шаблонные алгоритмы рукописными. Вон, люди пострадали
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Конкретно в этой задаче надо было не приорити кью тогда уже оптимизировать, а асимптотику решения. А вообще, очень редко бывает что стлевской приорити кью не хватает, если авторами предполагалось именно это решение, а не более быстрое асимптотически.
            → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            c priority_queue зашло на 101 тесте за 550 млс, 102 - 580... Проблема видимо в неоптимальности других частей решения
            → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Попробуйте использовать make_heap.
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Разные оптимизаторы оптимизируют по разному. Это стандартное явление, более того, 2008 версия может работать намного быстрее 2005...а может и дольше...=)

По статистике вижак 2005 намного медленнее последнего GCC.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если не сложно, приведите эту статистику, очень хотелось бы на нее посмотреть, чтобы не наступать больше на такие грабли.
    → Ответить
    • 14 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      просто посылай под GCC, а статистика проста: попробуй задачки на sgu например посылать под GCC или под MS VS C++...разница сразу будет заметна.
      → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Зато gcc частенько оптимизирует неправильно. Где-то тут проскакивала пара тем, про то, как RE на GCC превращалось в AC на MS VC++
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Кроме того, вот эти тесты говорят об обратном.
    → Ответить
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Если заменить

vector<bool> used;

на

vector<int> used;
то проходит на MS C++

→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Очень интересная информация. А Вы знаете, с чем это связанно?
    Как часто такое вообще бывает, как бороться?
    Никогда не думал, что такие мелочи на столько замедляют.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      vector<bool> использует битовое сжатие
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Это как? Если я правильно понял, это использование 1 int32 для 32 битов?
        → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        vector<int> a(3);
        vector<bool> b(3);
        cout<<sizeof(a)<<endl;
        cout<<sizeof(b)<<endl;

        Хм... Кто-то может объяснить, почему у меня вывело числа 24 и 36?..
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Потому что vector<> выделяет память динамически - это не массив. Соответственно, он хранит указатель на начало и еще что-нибудь. sizeof возвращает суммарный размер класса/структуры, и не смотрит, что там лежит по указателям. К тому же он считается на этапе компиляции.
          Если Вы объявите vector<int> a(100500);, то sizeof будет выдавать такие же числа.
          → Ответить
          • 14 лет назад, # ^ |
            ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Да, но вектор - шаблонный класс. То есть в общем случае при подстановке должен был выйти одинаковый код, а учитывая, что sizeof(int)=4*sizeof(bool), размер не должен был выйти больше. Видимо, для типа бул просто прописана отдельная достановка, реализованная несколько по-другому. Может как раз из-за сжатия. 
            А тот же код для инта, лонг лонга и чара выдает одинаковые 24, что как раз и логично.
            → Ответить
            • 14 лет назад, # ^ |
              ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              Вашу реализацию STL можно посмотреть: как правило его исходники находятся прямо в хедерах. На моем g++, например, <vector> инклудит <bits/stl_bvector.h> и <bits/stl_vector.h> — в первом исходники сжатого вектора, в котором все по-другому.
              → Ответить
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              для bool отдельная реализация.
              → Ответить
        • 14 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
           
          → Ответить
      • 14 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        double
        → Ответить
14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Может быть немножко оффтоп, но я написал решение с очередью на яве, в конце контеста посмотрел на время, понял что ни к чему хорошему эти 11 секунд не приведут. Переписал очень просто. без всяких структур, за N^2.
→ Ответить