?

Log in

No account? Create an account

Previous Entry | Next Entry

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

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

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

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

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

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

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

Comments

( 3 comments — Leave a comment )
larisaka
Jul. 2nd, 2007 11:32 pm (UTC)
"не всегда верное предположение" :)
marknn
Jul. 3rd, 2007 07:19 am (UTC)
а о чем программка если не секрет?
scholar_vit
Jul. 3rd, 2007 10:13 pm (UTC)
Пытается нарисовать разные красивые вещи при помощи PSTricks
( 3 comments — Leave a comment )

Profile

knot
scholar_vit
scholar_vit

Latest Month

September 2017
S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930

Tags

Powered by LiveJournal.com
Designed by Paulina Bozek