[/b/] [/d/] [/tu/] [/a/] [/ph/] [/wa/] [/cg/] [/t/] [/p/]
Допустим, стоит некая задача. В приоритете только время ее решения. Допустим, известен алгоритм решения и для него известно затрачиваемое время. Вопрос: в общем случае для достижения минимального времени решения нужно сначала искать более эффективный алгоритм (поиск займет N времени) и потом его выполнять, или сразу выполнять известный алгоритм? Возможен ли вообще ответ на такой вопрос? Если нужно сначала найти более эффективный алгоритм, то, по аналогии, тогда нужно искать более эффективный алгоритм нахождения более эффективного алгоритма? Что делать с рекурсией?
Как правило под "задачей" подарзумевается что-либо, что в результате сводится к чему-то вроде дифура, который надо решить, чтобы добраться до сути.Нахождение более эффективного алгоритма решения обобщенной задачи, в общем-то, всегда приоритетно, поскольку она обобщенная. То есть, мы можем провести исследование один раз, оно будет в разу больше самой задачи, но зато потом оно позволит решать задачи такого же типа гораздо быстрее.>Что делать с рекурсией?Ничего особенного рекурсия обычно вырубается вышматом, если становится более-менее очевидной. В крайнем случае, если полученное уравнение - нелинейный дифур, его можно отпинать численными методами с нужной точностью.Вообще, есть целый раздел матана, посвещенный этой вот фигне - решению задач, но я в нем ни бельмеса не знаю.
Как правило под "задачей" подарзумевается что-либо, что в результате сводится к чему-то вроде дифура, который надо решить, чтобы добраться до сути.Нахождение более эффективного алгоритма решения обобщенной задачи, в общем-то, всегда приоритетно, поскольку она обобщенная. То есть, мы можем провести исследование один раз, оно будет в разу больше самой задачи, но зато потом оно позволит решать задачи такого же типа гораздо быстрее.
>Что делать с рекурсией?
Ничего особенного рекурсия обычно вырубается вышматом, если становится более-менее очевидной. В крайнем случае, если полученное уравнение - нелинейный дифур, его можно отпинать численными методами с нужной точностью.Вообще, есть целый раздел матана, посвещенный этой вот фигне - решению задач, но я в нем ни бельмеса не знаю.
А как можно оценить эффективность алгоритма кроме попытки его выполнить и измерить время выполнения? Получается, что для выбора оптимального из N алгоритмов задачу уже придётся решить N раз, притом что требуется решить её лишь один раз.Можно, конечно, попробовать протестировать алгоритмы на примере короткой эталонной задачи, но тут есть подвох. На примере классической задачи о сортировке массива видно, что метод пузырька на коротком массиве оказывается эффективнее метода последовательных максимумов, а вот на длинных безнадёжно проигрывает.Вывод: эффективнее всего выбрать случайным образом любой из N алгоритмов и решить задачу с его помощью.
>>95238>Нахождение более эффективного алгоритма решения обобщенной задачи, в общем-то, всегда приоритетно, поскольку она обобщенная. То есть, мы можем провести исследование один раз, оно будет в разу больше самой задачи, но зато потом оно позволит решать задачи такого же типа гораздо быстрее.Имеется в виду, что мы не знаем, какие будут задачи в дальнейшем. Считаем, что они все разные. >А как можно оценить эффективность алгоритма кроме попытки его выполнить и измерить время выполнения?Рассчитать время выполнения. Считаем, что это возможно для каждого алгоритма и сам расчет занимает время.
>>95238
>Нахождение более эффективного алгоритма решения обобщенной задачи, в общем-то, всегда приоритетно, поскольку она обобщенная. То есть, мы можем провести исследование один раз, оно будет в разу больше самой задачи, но зато потом оно позволит решать задачи такого же типа гораздо быстрее.
Имеется в виду, что мы не знаем, какие будут задачи в дальнейшем. Считаем, что они все разные.
>А как можно оценить эффективность алгоритма кроме попытки его выполнить и измерить время выполнения?
Рассчитать время выполнения. Считаем, что это возможно для каждого алгоритма и сам расчет занимает время.
>>95239Нет, там есть более общие методы, которые могут помочь с классификацией задачи и методами, которыми ее можно решить. Я имею в виду математические методы, поскольку задача приведения ее к виду, пригодному к обработке, наверняка займет куда больше времени чем ее решение в таком виде - в общем случае.Правда, если речь идет о непосредственной задачи на стороне самой вычислительной системы, тут начинают действовать какие-то другие правила.>Вывод: эффективнее всего выбрать случайным образом любой из N алгоритмов и решить задачу с его помощью.Если мы решаем ее один раз, и у нас нет времени рассуждать - но такого же не бывает почти. Да и вообще, эти алгоритмы надо было соответствующим образом разработать, а не с потолка взять. Тупейшую сортировку ты как стал бы делать прямо сейчас?
>>95239Нет, там есть более общие методы, которые могут помочь с классификацией задачи и методами, которыми ее можно решить. Я имею в виду математические методы, поскольку задача приведения ее к виду, пригодному к обработке, наверняка займет куда больше времени чем ее решение в таком виде - в общем случае.Правда, если речь идет о непосредственной задачи на стороне самой вычислительной системы, тут начинают действовать какие-то другие правила.
>Вывод: эффективнее всего выбрать случайным образом любой из N алгоритмов и решить задачу с его помощью.
Если мы решаем ее один раз, и у нас нет времени рассуждать - но такого же не бывает почти. Да и вообще, эти алгоритмы надо было соответствующим образом разработать, а не с потолка взять. Тупейшую сортировку ты как стал бы делать прямо сейчас?
>>95241> Тупейшую сортировку ты как стал бы делать прямо сейчас?В абсолютном большинстве случаев я применяю метод "пузырька", так как в своё время додумался до него сам. Ешё до того, как начал читать умные книжки. Понятно, что я изобрёл велосипед, но я его всё-таки изобрёл.
>>95241
> Тупейшую сортировку ты как стал бы делать прямо сейчас?
В абсолютном большинстве случаев я применяю метод "пузырька", так как в своё время додумался до него сам. Ешё до того, как начал читать умные книжки. Понятно, что я изобрёл велосипед, но я его всё-таки изобрёл.
>>95237Ты формализуй задачу сначала.>Возможен ли вообще ответ на такой вопрос? Пока ты не уточнил вид задачи, и каким образом ищется новый более эффективный алгоритм, ответ будет писан вилами по воде. Не решаются такие задачи в общем случае. Это как бы еще одна Формула Всего.Пример конкретный: задача найти массив коэффициентов для нейросети заданной архитектуры, такой, чтобы нейросеть аппроксимировала известную функцию многих аргументов заданных (...дается функция...). Исходный алгоритм поиска коэффициентов: (...дается алгоритм...). Метод поиска нового алгоритма: (...дается метод поиска нового алгоритма...).>>95238>Как правило под "задачей" подарзумевается что-либо, что в результате сводится к чему-то вроде дифура, который надо решить, чтобы добраться до сути.Ха-ха. Я уверен, есть множество задач, которые дифурами не описываются.
>>95237Ты формализуй задачу сначала.
>Возможен ли вообще ответ на такой вопрос?
Пока ты не уточнил вид задачи, и каким образом ищется новый более эффективный алгоритм, ответ будет писан вилами по воде. Не решаются такие задачи в общем случае. Это как бы еще одна Формула Всего.Пример конкретный: задача найти массив коэффициентов для нейросети заданной архитектуры, такой, чтобы нейросеть аппроксимировала известную функцию многих аргументов заданных (...дается функция...). Исходный алгоритм поиска коэффициентов: (...дается алгоритм...). Метод поиска нового алгоритма: (...дается метод поиска нового алгоритма...).
>Как правило под "задачей" подарзумевается что-либо, что в результате сводится к чему-то вроде дифура, который надо решить, чтобы добраться до сути.
Ха-ха. Я уверен, есть множество задач, которые дифурами не описываются.
Если время поиска лучшего алгоритма << временеи решения первым попавшимся алгоритмом то вполне логично вначале поискать лучший алгоритм, если соизмеримо или меньше, то проще решить задачу первым попавшимся алгоритмом.
Левин: универсальный поиск.Юрген Шмидтхубер: машина Гёделя, OOPS.Маркус Хуттер: The shortest and fastest algorithm for solving any well-defined problem.
Каким-то схожим вопросом я задался вчера, прочитав статью TCP ex Machina из соседнего треда.
- wakaba 3.0.7 + futaba + futallaby -