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

[scholar_vit]

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

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

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

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

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

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

Comments

[larisaka.livejournal.com]

"не всегда верное предположение" :)

[marknn.livejournal.com]

а о чем программка если не секрет?

[scholar-vit.livejournal.com]

Пытается нарисовать разные красивые вещи при помощи PSTricks