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

Первый раз столкнулся с тем, что реализация имеет значение.
Автор mezhaka, 13 лет назад, перевод, По-русски

Моё решение div. 2 B round #92 не прошло по времени. Сейчас я его поправил и оно проходит тесты, но что интересно сложность по-идее у него такая же. Вот если кому интересно оба варианта тут: http://pastebin.com/scSwyuEq. Быстрая функция -- f, а медленная f1 (если захотите запустить медленную, то надо поменять имена.).

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

13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Ну да сравнивать int'ы быстрее чем string'и, асимптотика та же, а константы другие.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я попробовал это профайлить и хотспоты были в конвертации string -> int через stringstream.
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится
      Попробуй заменить d.push_back(convert<int>(tmp)); на d.push_back(atoi(tmp.c_str()));
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Потоки в принципе очень медленные.
      Если нужно быстро преобразовать в int - sscanf (stdio.h) либо atoi (stdlib.h).
      → Ответить
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Complexity doesn't matter too much when inputs are small, ex. insertion sort performs better than merge sort on small inputs, brute multiplication O(n^2) and FFT, and can become even worst, the constant factor can't be always ignored... it depends on processor architecture, caches... should not happen, but:
"In theory there is no difference between the theory and practice, in practice there is..."
→ Ответить