讨论串Есть идеи как можно ускорить перебор всех значений? lru_cache уже добавил, но все равно медленно и MemoryError

17 条消息 · 02:37–12:24

Егор Косачев

照片
点击显示

Есть идеи как можно ускорить перебор всех значений? lru_cache уже добавил, но все равно медленно и MemoryError

02:37

🍉
🍉
Лучше подумай над алгоритмом
02:40
1. Е
  Егор Косачев
  Например? Предлагаешь оптимизировать саму рекурсивную функцию?
  02:43
  1. 🍉
    🍉
    Не перебором решить. Попробуй идти от четвёрки, применяя комбинации операций. Поиграйся с числовой прямой, посмотри каким образом число может попасть в 4
    02:50
    1. Е
      Егор Косачев
      Окей
      02:51
      1. 🍉
        🍉
        Вот тебе подсказка: У тебя есть отправная точка (это 4) и две операции
        03:10
        Е
        Егор Косачев
        Почему отправная точка это именно 4? Мне же надо посчитать входные значения которые дают 4
        03:18
        🍉
        🍉
        Тебе надо найти все N, которые "скатываются" в 4. Вместо перебора N, тебе надо идти от обратного, там сложность гораздо меньше
        03:21
    2. Е
      Егор Косачев
      Спасибо
      02:51
      1. K
        KarmaBot
        Правило Лопиталя, Вы увеличили карму 🍉 до 14632.88 (+13.21)
        02:51
M
Mikael
А если просто взять numba?
03:10
1. Е
  Егор Косачев
  Можно вообще тогда на C++ или Rust переписать, хочется продуманно оптимизировать
  03:10
2. 🍉
  🍉
  Тут нужен другой алгоритм, а не брутфорс
  03:11
🍉
🍉
а, я задачу не так прочитал 😁 но если это помогло тебе придумать что-то, то я рад)
03:56
1. Е
  Егор Косачев
  ))) Все равно спасибо)
  04:20
2. Е
  Егор Косачев
  Оказывается что эта функция возвращает на 1 больше чем количество единиц в двоичной записи исходного числа
  12:24
⁣
⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣Andrey Karchevsky
Такое обычно руками решают, берешь первые наборы входных параметров и смотришь, что там происходит. Обычно представлен какой-то базовый алгоритм или представлена некая зависимость, ака степени двойки. Почему так? Потому что иначе задача не решается не в лоб, а значит вообще не решается. Кароче надо научиться быстро искать зависимость выходного значения от входного
09:03