scholar_vit (scholar_vit) wrote,
scholar_vit
scholar_vit

Categories:

Программистское

В Ницце мы с соавтором обнаружили небольшой баг в одной моей (выложенной в open source) программке годичной давности. Так как у нас на неё (программку) есть свои виды, взялся за починку.

Последовательно выяснилось следующее:

  1. Исправление бага требует полного переписывания этак процентов 60 кода. Помните, дети, что сказал Кнут: "Premature optimization is the root of all evil". То есть я слишком глубоко вовнутрь заложил раннюю и, как оказалось, вредную оптимизацию.
  2. После исправления бага часть новых тестов обрабатывается нормально. А часть нет. Расследование показало, что в алгоритме использовано не всегда верное предположение.
  3. Более глубокое расследование привело к контрпримеру: набору данных, для которого доказуемо, что никакой алгоритм не может привести к требуемому результату.

Решил поступить, как классический профессор математики у Пойа. Помните: "Если у вас не получается решить задачу, придумайте себе другую". Описал результат, который мой алгоритм даёт всегда, и именно его объявил требуемым.

Что интересно, помимо программки этот алгоритм мы изложили в паре статеек. Впрочем, удивительным образом оказалось, что статейки рассказывают о желаемом результате недостаточно четко, так что тонкое различие между возможным и тем, что мне тогда казалось возможным, в них не отражено. Так что статьи, как ни странно, верны.

А в остальном, прекрасная маркиза...

Tags: computers, лытдыбр
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 3 comments