Вот вы можете отличить программу которую писала большая корпорация 10 лет от программы которую слабал Петя за 15 минут с кофе? Как правило, первая большая, с большим количеством осмысленных инструкций, хорошо структурирована и пр. А Петя начеркал 100 кривых строчек на скорую руку.
Можно ли сказать что одна программа сложнее другой? Или же это все не объективно и нельзя точно сказать?
Что если Петя создал 100 строк, которые сгенерили 10 млн. строк программного кода. Ведь мы можем сказать что хоть их и 10 млн., они проще чем 1 млн. строк, которые создавала корпорация 5 лет?
Есть ли в информатике понятие сложности программы?
Есть вычислительная сложность алгоритма, но это совсем другое.
Здравствуйте, Shmj, Вы писали:
S>Есть ли в информатике понятие сложности программы?
Сложность это мера неоднородности. Для ее численного выражения существует мера цикломатической сложности
S>Есть вычислительная сложность алгоритма, но это совсем другое.
То что тебе нужно рассматривается не в информатике, а в теории сложных систем.
Здравствуйте, LaptevVV, Вы писали:
S>>Есть ли в информатике понятие сложности программы? S>>Есть вычислительная сложность алгоритма, но это совсем другое. LVV>Колмогоровская сложность
как мне кажется есть две категории "сложности".
есть сложность обьективная: насколько сама задача обьективно сложная. колмогоровская сложность здесь в тему.
есть сложность субьективная: как программа воспринимается неким человеком, знакомым с предметной областью. насколько сложно/просто понять как она устроена, править в ней баги, продолжить разработку и т.д.
S>>>Есть ли в информатике понятие сложности программы? S>>>Есть вычислительная сложность алгоритма, но это совсем другое. LVV>>Колмогоровская сложность DM>как мне кажется есть две категории "сложности". DM>есть сложность обьективная: насколько сама задача обьективно сложная. колмогоровская сложность здесь в тему. DM>есть сложность субьективная: как программа воспринимается неким человеком, знакомым с предметной областью. насколько сложно/просто понять как она устроена, править в ней баги, продолжить разработку и т.д.
Ну, ТС спрашивал об объективной сложности.
Восприятие сложности текста (в том числе и текста программы) субъективно, но тоже основано не на пустом месте.
Зависит от построения текста. Например, длинные предложения воспринимаются хуже (более сложные), чем короткие.
Есть исследования по оцениванию сложности текстов.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, pestis, Вы писали:
P>Сложность это мера неоднородности. Для ее численного выражения существует мера цикломатической сложности
Ну смотрите. Вася сбацал за 15 мин прогу, которая на основе ГСЧ дает миллионы циклов и условий. А корпорация делала осмысленно прогу с таким же кол-вом циклов и условий несколько лет.
Здравствуйте, LaptevVV, Вы писали:
LVV>Колмогоровская сложность
Вы сможете сбацать кодогенератор, который на основе ГСЧ выдаст вам прогу с произвольной колмогоровской сложностью (пусть эта прога ничего полезного и не делает)? Но ведь будет понятно что это всего лишь кодогенеренная прога и трудовые затраты на ее создание не велики.
Здравствуйте, DreamMaker, Вы писали:
DM>есть сложность субьективная: как программа воспринимается неким человеком, знакомым с предметной областью. насколько сложно/просто понять как она устроена, править в ней баги, продолжить разработку и т.д.
Вот это уже ближе. Ведь можно сгенерить прогу с произвольным количеством условий и циклов, но спецу будет видно что это фуфло ничего полезного не делает.
Здравствуйте, LaptevVV, Вы писали:
LVV>Зависит от построения текста. Например, длинные предложения воспринимаются хуже (более сложные), чем короткие. LVV>Есть исследования по оцениванию сложности текстов.
Смотрите. Мой вопрос в корне имеет эволюцию. Вот всем нам понятно что ДНК человека совершеннее ДНК козы. Совершеннее. И больше по размеру. И дает качественно иной результат. Но как это выразить математически?
Вот я хочу сделать эволюцию программ. А как мне сделать сравнение на уровне системы какая программа более совершенная (такие должны "выживать") а какая программа менее совершенная (такие должны "погибать")?
Здравствуйте, Sinix, Вы писали:
S>>Смотрите. Мой вопрос в корне имеет эволюцию. Вот всем нам понятно что ДНК человека совершеннее ДНК козы. Совершеннее. S>Дафния смотрит на вас с недоумением.
Она больше по размеру -- но кто сказал что сложнее?
Я вам могу дать проект, в котором миллион классов, 10 млн. функций, некие циклы и условия. Причем все совсем разное, архиватором не сильно ужимается. Но потрачено времени на его разработку всего лишь пара часов -- все автогенеренное на основе ГСЧ.
Понятна идея?
Размер != сложность.
S>Если коротко, то в итоге получится как-то так
Здравствуйте, Shmj, Вы писали:
S>Здравствуйте, LaptevVV, Вы писали:
LVV>>Колмогоровская сложность
S>Вы сможете сбацать кодогенератор, который на основе ГСЧ выдаст вам прогу с произвольной колмогоровской сложностью (пусть эта прога ничего полезного и не делает)?
Нет, не получится. У всех этих сгенеренных программ сложность будет не выше, чем размер самого генератора. См. определение.
Более того, эта сложность вообще невычислима, насколько я помню.
Здравствуйте, D. Mon, Вы писали:
DM>Более того, эта сложность вообще невычислима, насколько я помню.
Однако, оказывается, что тот факт, что конкретная строка сложна, не может быть формально доказан, если сложность строки выше определённого порога. wiki
Получается для очень систем эта оценка сложности не применима.
S>Она больше по размеру -- но кто сказал что сложнее? S>Размер != сложность.
Это зависит от исходных постулатов.
Вполне можно строить некую теорию на основе вот такой простой меры — длина строки.
Другое дело, что эта теория не совсем нас устраивает чисто субъективно.
Ибо:
abababababababababababababababababababababababababababababababab
4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf
Две строки — одного размера, но первая строка выглядит проще второй. Или вторая — сложнее первой.
Колмогоровская сложность — как раз и есть некоторая формализация вот такого интуитивного представления.
Неформально можно сказать, что сложность — мера разнообразия.
Первая строка — однообразна, вторая — намного разнообразнее.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
LVV>>Есть исследования по оцениванию сложности текстов. S>Чтобы его оценить -- его нужно понять. А математика такими терминами пока не оперирует. Видимо в этом проблема.
Не обязательно. Смысл — это субъективная интерпретация.
Так же как теория формальных грамматик не оперирует смыслом, а только формой — можно строить понятие сложности текста на основе сложности формы.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, Shmj, Вы писали:
S>Здравствуйте, LaptevVV, Вы писали:
LVV>>Колмогоровская сложность
S>Вы сможете сбацать кодогенератор, который на основе ГСЧ выдаст вам прогу с произвольной колмогоровской сложностью (пусть эта прога ничего полезного и не делает)? Но ведь будет понятно что это всего лишь кодогенеренная прога и трудовые затраты на ее создание не велики.
Не все так просто.
Слово "произвольный" — тут не подходит.
На практике невозможно создать программу генерирующую строку бесконечной сложности.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
DM>>Более того, эта сложность вообще невычислима, насколько я помню. S>Однако, оказывается, что тот факт, что конкретная строка сложна, не может быть формально доказан, если сложность строки выше определённого порога. wiki S>Получается для очень систем эта оценка сложности не применима.
Ну дык есть алгоритмически неразрешимые проблемы. И что?
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Теория систем объясняет только часть сложности программы. Например, из неё следует, что сложность программы определяется не столько количеством компонентов, из которых она состоит, сколько количеством связей между ними. Поэтому мы имеем кучу паттернов, пытающихся контролировать связи, типа всякие MVC, SRP и прочие адаптеры.
Но есть ещё и сложность восприятия кода конкретным разработчиком. Что сложно и непонятно новичку может быть элементарным опытному перцу. Также, например, всякие оптимизации неизбежно вносят взрывной рост сложности в приложение и т.п.
Если нам не помогут, то мы тоже никого не пощадим.
Здравствуйте, D. Mon, Вы писали:
S>>Вы сможете сбацать кодогенератор, который на основе ГСЧ выдаст вам прогу с произвольной колмогоровской сложностью (пусть эта прога ничего полезного и не делает)? DM>Нет, не получится. У всех этих сгенеренных программ сложность будет не выше, чем размер самого генератора. См. определение.
Это не верно. Есть принципиальная разница между ГСЧ и псевдо ГСЧ, первый, в отличии от второго, не может быть записан в виде программы.
Здравствуйте, IT, Вы писали:
IT>Но есть ещё и сложность восприятия кода конкретным разработчиком. Что сложно и непонятно новичку может быть элементарным опытному перцу. Также, например, всякие оптимизации неизбежно вносят взрывной рост сложности в приложение и т.п.
Это скорее про используемые модели, абстракции, идиомы. У новичка ничего такого нет. Потому часто опытный перец и новичок смотрят на код друг друга с недоумением — обоим код другого кажеся не в меру усложненным и непонятным.
Здравствуйте, LaptevVV, Вы писали:
LVV>Две строки — одного размера, но первая строка выглядит проще второй. Или вторая — сложнее первой. LVV>Колмогоровская сложность — как раз и есть некоторая формализация вот такого интуитивного представления.
Колмгоровская сложность это скорее про количество информации. Например фрактал можно представить картинкой, конского размера, а можно представить короткой программой.
С т.з. человека второй спосб может быть как сложнее первого, так и проще первого. Все зависит от того, что уже напихано в голову и чего там не хватает. Колмгоровская сложность это абсолютная величина, а вот человеческая — относительная.
Здравствуйте, Ikemefula, Вы писали:
I>Изучал. Называется "Общая теория систем"
Вы вопрос не так поняли. Вам преподаватель объяснил какой термин в этой теории используется для сложности программы? Именно в том ракурсе, о котором мы говорим.
Здравствуйте, Shmj, Вы писали: S>Можно ли сказать что одна программа сложнее другой? Или же это все не объективно и нельзя точно сказать?
сложность это мера неожиданности событий
то есть сложность программного кода можно измерять в "what the fuck/minute". или, в рамках программы импортозамещения в возгласах "это что за хрень? в минуту" при изучении этого кода человеком, который его никогда прежде не видел.
высококачественный код имеет этот показатель меньше 1. типичный код, написанный Васей имеет этот рейт в десятки.
эта мера не обьективна, потому что зависит от человека и личного опыта, да и знакомства с Васей и его стилем, но можно брать некий усредненный показатель по людям
Здравствуйте, Shmj, Вы писали:
I>>Изучал. Называется "Общая теория систем"
S>Вы вопрос не так поняли. Вам преподаватель объяснил какой термин в этой теории используется для сложности программы? Именно в том ракурсе, о котором мы говорим.
Именно для сложости программы ничего нет и не будет. Сложность есть у системы
Здравствуйте, Shmj, Вы писали:
S>Ну смотрите. Вася сбацал за 15 мин прогу, которая на основе ГСЧ дает миллионы циклов и условий. А корпорация делала осмысленно прогу с таким же кол-вом циклов и условий несколько лет. S>Вы то сможете отличить одно от другого?
С чего ты взял что между этими случаями есть какая-то разница? Результат современных технологий кодогенерации применяемый, например, для сверхэффективной оптимизации или для построения деревьев решений в ML для человека гораздо сложнее чем рукописный код. В полном соответствии с.
Здравствуйте, Shmj, Вы писали:
S>Вот вы можете отличить программу которую писала большая корпорация 10 лет от программы которую слабал Петя за 15 минут с кофе?
Чаще всего — да. S> Как правило, первая большая, с большим количеством осмысленных инструкций, хорошо структурирована и пр. А Петя начеркал 100 кривых строчек на скорую руку. S>Можно ли сказать что одна программа сложнее другой? Или же это все не объективно и нельзя точно сказать?
Есть объективные метрики сложности. Можно и свою придумать, в зависимости от того, для чего это нужно
S>Что если Петя создал 100 строк, которые сгенерили 10 млн. строк программного кода. Ведь мы можем сказать что хоть их и 10 млн., они проще чем 1 млн. строк, которые создавала корпорация 5 лет?
Это цикломатическая сложность (ссылку уже приводили
)
Вы вначале определитесь, сложность чего именно Вам интересна и всё встанет на свои места.
Если интересна сложность конечного результирующего кода (например, чтобы оценить затраты ресурсов на компиляцию) — то нет смысла эти случаи разделять, разницы нет, написан код руками или программой.
Если интересна сложность ручной работы (например, чтобы оценить трудозатраты) — то просто скармливайте гипотетической программе измерения сложности только ту часть кода, что написана руками (в хорошо структурированном проекте её не сложно выделить).
Здравствуйте, pestis, Вы писали:
P>С чего ты взял что между этими случаями есть какая-то разница? Результат современных технологий кодогенерации применяемый, например, для сверхэффективной оптимизации или для построения деревьев решений в ML для человека гораздо сложнее чем рукописный код. В полном соответствии с.
Не, кодогенератор написан с нуля. Понятно что если кодогенератор писала другая корпорация и человеко-месяцев ушло больше, то и выход может быть сложнее.
Здравствуйте, Shmj, Вы писали:
S>Здравствуйте, DreamMaker, Вы писали:
DM>>есть сложность субьективная: как программа воспринимается неким человеком, знакомым с предметной областью. насколько сложно/просто понять как она устроена, править в ней баги, продолжить разработку и т.д.
S>Вот это уже ближе. Ведь можно сгенерить прогу с произвольным количеством условий и циклов, но спецу будет видно что это фуфло ничего полезного не делает.
Тут есть ещё один момент: сколько времени ему понадобится для такого вывода, и какова вероятность его ошибки.
Всё сказанное выше — личное мнение, если не указано обратное.
Здравствуйте, Shmj, Вы писали:
S>Здравствуйте, pestis, Вы писали:
P>>Сложность это мера неоднородности. Для ее численного выражения существует мера цикломатической сложности
S>Ну смотрите. Вася сбацал за 15 мин прогу, которая на основе ГСЧ дает миллионы циклов и условий. А корпорация делала осмысленно прогу с таким же кол-вом циклов и условий несколько лет.
S>Вы то сможете отличить одно от другого?
Имхо легко корп. код будет пестрить отсылками к бизес модели, change requestam и под завязку набит деталями и нюансами.
Здравствуйте, Shmj, Вы писали:
LVV>>Зависит от построения текста. Например, длинные предложения воспринимаются хуже (более сложные), чем короткие. LVV>>Есть исследования по оцениванию сложности текстов.
S>Смотрите. Мой вопрос в корне имеет эволюцию. Вот всем нам понятно что ДНК человека совершеннее ДНК козы. Совершеннее. И больше по размеру. И дает качественно иной результат. Но как это выразить математически? S>Вот я хочу сделать эволюцию программ. А как мне сделать сравнение на уровне системы какая программа более совершенная (такие должны "выживать") а какая программа менее совершенная (такие должны "погибать")?
Тогда при поиске надо не максимизировать сложность, а наоборот минимизировать. Максимизировать только способности решать задачи.
Если бы эволюция максимизировала сложность, тогда бы у человека были и рога и хвост и жабры (чтобы не утонуть) и еще много чего. Вместо этого даже за год у космонавтов в невесомости организм избавляется от ненужной костной ткани и мышц.
Определенный класс задач коза решает лучше человека — бодается лучше, по горам скачет лучше и быстрее. Определись сначала что за задачи надо решать (т.е. задачи это фактически среда где происходит эволюция).
Здравствуйте, Shmj, Вы писали:
LVV>>Колмогоровская сложность
S>Вы сможете сбацать кодогенератор, который на основе ГСЧ выдаст вам прогу с произвольной колмогоровской сложностью (пусть эта прога ничего полезного и не делает)? Но ведь будет понятно что это всего лишь кодогенеренная прога и трудовые затраты на ее создание не велики.
А разве такое вообще может быть, что сложность похожая по смыслу на Колмогоровскую сложность, большая и программа ничего не делает?
Если о такой сложности речь, то ведь подразумевается, что весь мертвый код удален(который никогда не вызывается). В том числе удален код результаты работы которого отбрасываются, перезаписываются без чтения.
Раскрытые циклы свернуты (нет тысяч операций, которые можно было бы свернуть в циклы).
Т.е. программа подвергнута оптимизации по размеру.
Если программа сложная, что-то уж делать она должна.
А в плане полезности, то для 99% пользователей ПК, SQL Server, или 1C бухгалтерия,..., ничего полезного не делают и мало отличаются от строк кода сгенеренных по ГСЧ.
S>Есть ли в информатике понятие сложности программы?
S>Есть вычислительная сложность алгоритма, но это совсем другое.
ИМХО. Программа это текст.
Объективная сложность программы может быть измерена по Колмогорову. Например, число pi в десятичном представлении имеет бесконечную сложность, но объективная сложность любого отрезка pi может быть определена рядом Лейбница.
Есть еще субъективная сложность – сложность понимания программы человеком. Конечно, она сильно зависит от конкретного человека, но для среднестатистического программиста, знающего язык данной программы, я бы определил субъективную сложность по формуле:
Если нам не помогут, то мы тоже никого не пощадим.
