Re[12]: Что-то не так с головой
От: Геннадий Васильев Россия http://www.livejournal.com/users/gesha_x
Дата: 08.02.12 13:41
Оценка: 1 (1)
Здравствуйте, DarkGray, Вы писали:

DG>для кода вида, как во втором примере, требование "незацикливаться" проверяется простым автоматом за O(кол-во операторов в программе), а чтобы проверить на зацикливание код вида, как в первом варианте, необходим алгоритм со сложностью близкой к O(2^кол-во операторов в программе)


Несколько озадачен: если тела циклов одинаковы, то откуда берётся O(2^N) при использовании for? ИМХО, различие будет только на сложность доказательства корректности for/foreach (если индекс неизменен в цикле). Ну, возможно, ещё добавится O(N), то есть по сути возвращаемся к тому же исходному O(N), если предположить, что в каждой строке тела цикла есть обращение к индексной переменной — нужно доказать, что эти обращения не изменяют индекс. Но двойка в степени N...

DG>зы

DG>изолированность хороша тем, что при правильной изоляции функция предсказуемости выглядит как:
DG>Предсказуемость'(код, требование)=Sum(Предсказуемость'(изолированная часть кода_i, требование))
DG>для неизолированного кода функция ведет себя много хуже:
DG>Предсказуемость'(код, требование)=Product(Предсказуемость'(неизолированная часть кода_i, требование))

В целом понятно, только всё равно, ИМХО, сформулировано запредельно громоздко. Нет, сказать по-простому: 1/вычислительная сложность проверки требования. А если вместо "проверки требования T" написать "доказательство свойства P", то получится ещё проще: "1/вычислительная сложность доказательства свойства P". Путаница возникает из-за того, что тривиальное значение слова "предсказуемость" не слишком похоже на твоё определение: интуитивно "предсказуемость" чаще понимается как сама возможность что-либо предсказать, вне количественных оценок сложности предсказания. Хотя соглашусь, что это тоже не бесспорно.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Re[13]: Что-то не так с головой
От: DarkGray Россия http://blog.metatech.ru/post/ogni-razrabotki.aspx
Дата: 08.02.12 14:56
Оценка: 10 (1)
ГВ>Несколько озадачен: если тела циклов одинаковы, то откуда берётся O(2^N) при использовании for? ИМХО, различие будет только на сложность доказательства корректности for/foreach (если индекс неизменен в цикле). Ну, возможно, ещё добавится O(N), то есть по сути возвращаемся к тому же исходному O(N), если предположить, что в каждой строке тела цикла есть обращение к индексной переменной — нужно доказать, что эти обращения не изменяют индекс. Но двойка в степени N...

в данном случае, сравниваются предсказывающие алгоритмы для двух классов кода, а не два конкретных этих примера.
один класс кода — состоит из управляющих операторов: if, for, предоопределенного набора функций Fs1;
а второй класс кода — состоит из управляющих операторов: if, foreach, предопределенного набора функций Fs2(в частности, Reverse).

оценки условные, более точно:

для достаточности конечности второго кода достаточно линейно проверить, что нет вызовов "запрещенных" функций, и дополнительно за O(N*log глубина вызовов) проверить, что функция не вызывает саму себя.

для первого кода, если выход из цикла делается по целочисленной переменной, то необходимо:
1. определить при каких значениях i будет выход из цикла
2. построить матрицу для каждого значения i в какое значение i оно переходит после одной итерации.
3. убедиться, что все пути матрицы из п.2 ведут к значениям i в п.1

приблизительная оценка всего этого O(2^32 * кол-во операторов, которые меняют i * 2^кол-во if-ов,которые зависят от i) для 4-х байтного int-а, если решать задачу в лоб


ГВ>В целом понятно, только всё равно, ИМХО, сформулировано запредельно громоздко. Нет, сказать по-простому: 1/вычислительная сложность проверки требования. А если вместо "проверки требования T" написать "доказательство свойства P", то получится ещё проще: "1/вычислительная сложность доказательства свойства P".


согласен, так лучше

ГВ> Путаница возникает из-за того, что тривиальное значение слова "предсказуемость" не слишком похоже на твоё определение: интуитивно "предсказуемость" чаще понимается как сама возможность что-либо предсказать, вне количественных оценок сложности предсказания. Хотя соглашусь, что это тоже не бесспорно.


поведение программы всегда предсказуемо: достаточно ее выполнить для всего набора входных данных.
так даже задача предсказания зацикленности решается: запустить программу и подождать 10^N секунд (10^K тактов),
если программа завершилась раньше, то значит она конечная,
если не завершилась, то гарантии что она бесконечная — нет, но есть зато оценка снизу, что быстрее, чем за 10^N секунд программа не завершается.

поэтому интересует не просто предсказуемо — да/нет, а какая вычислительная сложность предсказания и насколько это предсказание — точное(есть точный ответ, дает оценку сверху/снизу, дает корреляцию при определенных условиях и т.д.)
Re[15]: Что-то не так с головой
От: DarkGray Россия http://blog.metatech.ru/post/ogni-razrabotki.aspx
Дата: 08.02.12 15:08
Оценка:
DG>>тогда уж (если все-таки хочется инкапсуляцию)
DG>>
DG>>LazyMaker selectedElementMaker = new LazyMaker(()=>UpdateControl_ForSelectedElement(selectedElement.Control),
DG>> delegate { return selectedElement; }
DG>>);
DG>>


U>Не вижу здесь никакой дополнительной инкапсуляции. Что изменилось-то от того, что ты код обработки вынес из LazyMaker'а в функцию этого же контрола?


это первый шаг инкапсуляции. и на этом шаге от lazy maker-а инкапсулировали конкретный набор правил вывода выделенного элемента

дальнейшие шаги могут быть:
2. выделенность элемента инкапсулируется от lazy maker-а (lazy maker перестает знать о выделенности):
LazyMaker selectedElementMaker = new LazyMaker(()=>UpdateControl(element.Control, element),
 delegate { return element; }
);
//..

void UpdateControl(Control control, Element element)
{
  UpdateControl_ForElement(control, element);

  if (element.isSelected)
   UpdateControl_ForSelectedElement(control, element);
}

3. вынос функции UpdateControl в отдельный модуль
LazyMaker selectedElementMaker = new LazyMaker(()=>MyCoolBusinessLogic.UpdateControl(element.Control, element),
 delegate { return element; }
);

4. статическая функция часто неудобна, и может быть заменена на вызов метода и приведение к честному MVC
LazyMaker selectedElementMaker = new LazyMaker(()=>controller.UpdateControl(element.Control, element),
 delegate { return element; }
);


отмечу что выбор сигнатуры функции UpdateControl произошел на шаге 1, а на шагах 2-4 сигнатура функции уже UpdateControl не менялась, менялся только способ выбора этой функции.

вернемся к шагу 1 — при вынесении кода в функцию UpdateControl есть два сильно отличающихся способа ее задать (сформировать ее сигнатуру): Push и Pull.

//первый способ (Push)
void PartialUpdateControl(Control control, Element element)
{
  control.Font = new Font{Bold=true, Size = default.Font.Size * 1.1};
  control.Color = Colors.Green;
}
//второй способ (Pull)
ControlState ElementPartialView(Element element)
{
  return new ControlState
  {
    Font = new FontState{Bold=true, SizeK = 1.1};
    Color = Colors.Green;
  };
}

для первого способа код lazy maker-а уже приводился, для второго способа будет:
var maker = new LazyMaker(
 () => ControlSynchronizer.Synchronize(element_with_control.Control, ElementPartialView(element_with_control.Element)),
 () => element_with_control
);


Разница в сигнатурах void PartialUpdateControl(Control control, Element element) и ControlState ElementPartialView(Element element) начинает проявляться, когда происходит переход к задаче комбинирования правил вывода, в частности, в задаче декорирования.
в первом случае, декоратор переводит Control -> Control (при этом в Control-е намешано к этому времени уже куча всего: данные от зависимых правил вывода, состояние по умолчанию, память от предыдущих изменений и т.д.),
во втором случае, декоратор переводит ControlState -> ControlState, при этом в ControlState лежат данные только от зависимых правил вывода.
Re[8]: Что-то не так с головой
От: Ромашка Украина  
Дата: 08.02.12 15:45
Оценка:
Здравствуйте, IT, Вы писали:
Р>>>>"Сложность", по определению, это количество ошибок на километр кода.
IT>>>Откуда такое "поопределение"?
Р>>У тебя есть другое, которое не сводится к ошибкам на километр? Озвучь, пожалуйста.

IT>Если коротко, то я это понимаю как меру усилий, требуемых для решения поставленной задачи.


"Кол-во ошибок на километр кода" это такая же самая мера усилий. Наши определения тождественны.


Всё, что нас не убивает, ещё горько об этом пожалеет.
Re[9]: Что-то не так с головой
От: IT Россия linq2db.com
Дата: 08.02.12 16:45
Оценка:
Здравствуйте, Ромашка, Вы писали:

IT>>Если коротко, то я это понимаю как меру усилий, требуемых для решения поставленной задачи.

Р>"Кол-во ошибок на километр кода" это такая же самая мера усилий. Наши определения тождественны.

"Кол-во ошибок на километр кода" говорит не о сложности задачи, а о кривизне рук и наличии мозгов у разработчика. Здесь наиболее наглядно проявляется правило 80/20. 20% разработчиков создают 80% багов вне зависимости от сложности решаемой задачи.
Если нам не помогут, то мы тоже никого не пощадим.
Re[10]: Что-то не так с головой
От: Ромашка Украина  
Дата: 08.02.12 20:22
Оценка:
Здравствуйте, IT, Вы писали:
IT>"Кол-во ошибок на километр кода" говорит не о сложности задачи, а о кривизне рук и наличии мозгов у разработчика.

Твоя мера сложности так же зависит от кривизны рук и/или наличия мозгов у программиста. При прямых руках и нормальных мозгах усилий на решение задачи будет затрачено меньше, чем при кривых руках и тараканах в голове. Наши определения тождественны.


Всё, что нас не убивает, ещё горько об этом пожалеет.
Re[11]: Что-то не так с головой
От: IT Россия linq2db.com
Дата: 08.02.12 20:44
Оценка: +1
Здравствуйте, Ромашка, Вы писали:

Р>Твоя мера сложности так же зависит от кривизны рук и/или наличия мозгов у программиста. При прямых руках и нормальных мозгах усилий на решение задачи будет затрачено меньше, чем при кривых руках и тараканах в голове. Наши определения тождественны.


Мозги и руки лишь одна из состовляющих моего определения. Наши определения не могу быть тождественны, как не могут быть тождественны целое и его часть.
Если нам не помогут, то мы тоже никого не пощадим.
Re[12]: Что-то не так с головой
От: Ромашка Украина  
Дата: 08.02.12 21:24
Оценка:
Здравствуйте, IT, Вы писали:
IT>Мозги и руки лишь одна из состовляющих моего определения.

Ну, ты озвучь тогда уж все составляющие.

IT>Наши определения не могу быть тождественны, как не могут быть тождественны целое и его часть.


Как математик, я с тобой не согласен.


Всё, что нас не убивает, ещё горько об этом пожалеет.
Re[13]: Что-то не так с головой
От: IT Россия linq2db.com
Дата: 08.02.12 23:42
Оценка:
Здравствуйте, Ромашка, Вы писали:

IT>>Мозги и руки лишь одна из состовляющих моего определения.

Р>Ну, ты озвучь тогда уж все составляющие.

Всё здесь
Автор(ы): Игорь Ткачёв
Дата: 06.12.2002
.

IT>>Наши определения не могу быть тождественны, как не могут быть тождественны целое и его часть.

Р>Как математик, я с тобой не согласен.

Как человек, привыкший пользоваться здравым смыслом, я не могу понять, как по твоей логике мы с тобой можем быть тождественны, находя в тысячах километрах друг от друга
Если нам не помогут, то мы тоже никого не пощадим.
Re[16]: Что-то не так с головой
От: Undying Россия  
Дата: 09.02.12 04:28
Оценка:
Здравствуйте, DarkGray, Вы писали:

DG>это первый шаг инкапсуляции. и на этом шаге от lazy maker-а инкапсулировали конкретный набор правил вывода выделенного элемента


Здесь есть дополнительный слой абстракции, а является этот дополнительный слой абстракции инкапсуляцией или логическим мусором не зная задачи, которую мы решаем, сказать нельзя.

DG>отмечу что выбор сигнатуры функции UpdateControl произошел на шаге 1, а на шагах 2-4 сигнатура функции уже UpdateControl не менялась, менялся только способ выбора этой функции.


Я не понимаю какое все это отношение имеет к обсуждению LazyMaker'а? LazyMaker это способ позволяющий определить нужно или не нужно в данный момент времени произвести обновление. На способ обновления LazyMaker не накладывает никаких ограничений, соответственно то каким способом лучше производить обновление это совершенно отдельный вопрос. Можно, конечно, и этот вопрос обсудить, но с начала все же хотелось бы определиться с LazyMaker'ом. Считаешь ли ты LazyMaker хорошим решением для взаимодействия геттерного и сеттерного кода? Лучше ли решение на LazyMaker, чем решение на активных синхронайзерах? Какие проблемы ты видишь при использовании LazyMaker'а?

DG>Разница в сигнатурах void PartialUpdateControl(Control control, Element element) и ControlState ElementPartialView(Element element) начинает проявляться, когда происходит переход к задаче комбинирования правил вывода, в частности, в задаче декорирования.


Разница понятна, но как ни странно не шибко заметно на реальных задачах. Т.к. если контрол пассивный, т.е. не активирует событий при изменении своих свойств, то в общем-то без разницы сколько раз мы присваивали его конкретное свойство — один или несколько. А если активный, то проблемы возникают и при одиночном изменении свойства, и при множественном.
Re[3]: Что-то не так с головой
От: matumba  
Дата: 09.02.12 08:05
Оценка:
Здравствуйте, IT, Вы писали:

M>>Был бы у каждой системы второй шанс — всё было бы намного лучше.


IT>Второго шанса может не понадобиться, если изначально закладывать в систему возможность ошибаться.


Это ещё сложнее, чем вообще написать безошибочную систему
Кроме того, ошибки одной системы могут "наводить" ошибки на другие. (как "плохая" структура данных поганит весь код, который ею оперирует)

И потом, в системах не всегда "всё плохо" — достаточно вовремя остановиться и подправить то, что изначально было архитектурным высером — тогда есть шанс "выправить" остальные системы и всё будет хорошо.
Re[10]: Что-то не так с головой
От: FR  
Дата: 09.02.12 09:08
Оценка:
Здравствуйте, DarkGray, Вы писали:

DG>основная проблема, что математики хотят всегда точное решение. и в статье по ссылке подразумевается, что теории могут быть только точными. на практике же в большинстве задач достаточно теорий и решений, которые описывают и решают задачу с частичной потерей точности.


Угу вот в этой самой потере точности и прячутся и баги и неопределенности.
Re[11]: Что-то не так с головой
От: DarkGray Россия http://blog.metatech.ru/post/ogni-razrabotki.aspx
Дата: 09.02.12 11:20
Оценка: :)
DG>>основная проблема, что математики хотят всегда точное решение. и в статье по ссылке подразумевается, что теории могут быть только точными. на практике же в большинстве задач достаточно теорий и решений, которые описывают и решают задачу с частичной потерей точности.

FR>Угу вот в этой самой потере точности и прячутся и баги и неопределенности.


неопределенность не ведет к багам, если ее правильно готовить.
Re[17]: Что-то не так с головой
От: DarkGray Россия http://blog.metatech.ru/post/ogni-razrabotki.aspx
Дата: 09.02.12 13:00
Оценка:
U>Считаешь ли ты LazyMaker хорошим решением для взаимодействия геттерного и сеттерного кода? Лучше ли решение на LazyMaker, чем решение на активных синхронайзерах? Какие проблемы ты видишь при использовании LazyMaker'а?

синхронайзер решает другую задачу, поэтому его стоит вынести за скобки.

и тогда вопрос будет: что лучше — активный опрос или пассивное применение?
и краткий ответ: первое лучше обеспечивает достоверность и актуальность вывода данных, второе — более экономично.

в частности, через LazyMaker тяжело обеспечить достоверный и актуальный вывод результата функции, которая зависит от времени, или от меняющихся самостоятельно внешних данных
Re[4]: Что-то не так с головой
От: IT Россия linq2db.com
Дата: 09.02.12 15:58
Оценка:
Здравствуйте, matumba, Вы писали:

IT>>Второго шанса может не понадобиться, если изначально закладывать в систему возможность ошибаться.

M>Это ещё сложнее, чем вообще написать безошибочную систему

Речь идёт не о результате, а о процессе.
Если нам не помогут, то мы тоже никого не пощадим.
Re[18]: Что-то не так с головой
От: Undying Россия  
Дата: 13.02.12 10:49
Оценка:
Здравствуйте, DarkGray, Вы писали:

DG>и тогда вопрос будет: что лучше — активный опрос или пассивное применение?

DG>и краткий ответ: первое лучше обеспечивает достоверность и актуальность вывода данных, второе — более экономично.

Как раз с актуальностью данных у синхронайзера плохо. Т.к. высокую частоту синхронизации нельзя поставить по соображениям производительности, а при частоте в единицы герц задержка при обновлении хорошо заметна глазом. Соответственно в реальном коде все равно приходится вставлять ForceSynchronize. Единственное достоинство синхронайзера это надежность, он гарантирует, что даже если явное обновление сделать забудут, то программа будет работать хоть и не оптимально, но более-менее нормально. Но этот плюс легко получить и при построении логики преобразований на LazyMaker'ах, используя синхронайзер только на верхнем уровне (например, раз в секунду перерисовывая главную форму).

DG>в частности, через LazyMaker тяжело обеспечить достоверный и актуальный вывод результата функции, которая зависит от времени, или от меняющихся самостоятельно внешних данных


В этом случае самый правильный подход это использовании синхронайзера на верхнем уровне и LazyMaker'ов на всех нижележащих уровнях. К примеру, переписывание по этому принципу логики отрисовки gridSynchronizer'а позволило кардинально упростить код.

DG>а переход с push на pull может давать и увеличение кол-ва сущностей, особенно на стыке с внешним окружением: как минимум требуется писать синхронайзер под каждый класс из внешнего окружения)


Все-таки я так и не понял откуда взялись лишние сущности при использовании LazyMaker'ов? Если задача простая, то взаимодействовать с сеттерным кодом можно напрямую из обработчика LazyMaker'а, проблем это не создает. Если задача сложная, то при любом подходе (хоть сеттерном, хоть событийном, хоть на синхронайзерах, хоть на LazyMaker'ах) работа с сеттерным кодом будет как-то инкапсулирована путем создания дополнительных оберток. С чего при использовании LazyMaker'ов этих оберток будет больше?
Re[19]: Что-то не так с головой
От: DarkGray Россия http://blog.metatech.ru/post/ogni-razrabotki.aspx
Дата: 13.02.12 12:08
Оценка:
U>Все-таки я так и не понял откуда взялись лишние сущности при использовании LazyMaker'ов?

я уже выше показывал, что lazymaker — это не одна сущность.
это три сущности в одном месте: структурный кэш + синхронайзер (в данном случае, каждый раз по месту) + целевое состояние (тоже по месту)

зы
попробуй представить как бы ты описал на maker-ах сложное поведение: например, поведение крестика закладки в хроме:
в хроме, когда закладок много — пространство делится между всеми закладками.
при нажатии на крестик, следующая закладка анимировано сдвигается на место предыдущей, при этом крестик оказывается точно под мышкой, и т.д.
и только при убирание мышки — закладки увеличиваются (с анимацией), чтобы занять всё пространство.
Re: Что-то не так с головой
От: Real 3L0 Россия http://prikhodko.blogspot.com
Дата: 13.02.12 21:14
Оценка:
Здравствуйте, HrorH, Вы писали:

HH> А что если предположить, что баг не должно быть вообще? Почему человек не может думать без ошибок? В чем причина ошибок?


Я пока придерживаюсь того мнения, что "никто не использует предыдущие наработки". Пока — потому что не видел, что это не так.
Грубо говоря, если один программист написал велосипед, то другой программист в большинстве случаев тоже пишет свой велосипед для аналогичной задачи. В одном велосипеде — одни баги, в другом — другие и/или те же самые.
Вселенная бесконечна как вширь, так и вглубь.
Re[20]: Что-то не так с головой
От: Undying Россия  
Дата: 14.02.12 16:11
Оценка:
Здравствуйте, DarkGray, Вы писали:

DG>я уже выше показывал, что lazymaker — это не одна сущность.

DG>это три сущности в одном месте: структурный кэш + синхронайзер (в данном случае, каждый раз по месту) + целевое состояние (тоже по месту)

Ты точно читаешь на что отвечаешь? Никакого синхронайзера нет, т.к. максимум нужен один синхронайзер на самом верхнем уровне (т.е. в общем случае синхронайзер один на множество LazyMaker'ов) и при этом он занимает где-то три строки кода, причем стандартных (т.е. создание этого синхронайзера можно вообще вынести в функцию и заменить на один вызов). Что такое структурный кэш и целевое состояние я не совсем понял. Реально есть сам LazyMaker и в сложных случаях какая-то обвязка над логикой действия. Причем примерно такая же обвязка над логикой будет и при любом другом подходе.

DG>попробуй представить как бы ты описал на maker-ах сложное поведение: например, поведение крестика закладки в хроме:

DG>в хроме, когда закладок много — пространство делится между всеми закладками.
DG>при нажатии на крестик, следующая закладка анимировано сдвигается на место предыдущей, при этом крестик оказывается точно под мышкой, и т.д.
DG>и только при убирание мышки — закладки увеличиваются (с анимацией), чтобы занять всё пространство.

И в чем проблема? Как я понимаю соль здесь в том, что текущего логического состояния для определения как нужно выводить закладки не достаточно, необходима еще информация о предыдущем логическом состоянии. Соответственно такую информацию нужно добавить, например, в виде начального числа закладок. Логика работы будет такой, при нажатии на крестик, удаляем закладку и вызываем перерисовку, срабатывает LazyMaker, видит, что начальное число закладок не соответствует текущему, значит, размещение закладок нужно выполнить особым образом. При уходе мыши с панели сбрасываем начальное число закладок в текущее и вызываем перерисовку. На LazyMaker'а эта задача становится примитивней некуда, хотя подозреваю, что реализовывать это на событиях радость еще та.

С анимацией тоже самое. Выставляем время начала анимации, запускаем таймер периодически дергающий отрисовку, отрисовщик по времени прошедшему с начала анимации определяет какой кадр сейчас нужно показать.
Re[21]: Что-то не так с головой
От: DarkGray Россия http://blog.metatech.ru/post/ogni-razrabotki.aspx
Дата: 14.02.12 17:34
Оценка:
U> Никакого синхронайзера нет

мы до сих пор говорим про сущности, или про названия классов?


U>И в чем проблема?


приведи рабочий код, тогда можно поговорить: сколько сущностей необходимо, чтобы его выразить.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.