Как найти современный алгоритм для конкретной задачи

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

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

Пробовали ли вы поговорить со старшим научным сотрудником в вашем учреждении или с более старшим научным сотрудником?
Современный уровень техники может быть не лучшим выбором для вашей конкретной проблемы. Требуется инженерная оценка.
Вы ищете Stack Exchange.

Ответы (2)

  1. Обычно я просматриваю обзорные статьи в полевых условиях и также стараюсь цитировать их, если в статье есть какое-либо предложение, «утверждающее, что предыдущий метод — это SOTA» .
  2. Есть также эталонные сайты.
  3. Известные наборы данных даже имеют свои личные эталоны, связанные с их сайтами.
  4. Вы можете использовать Research Gate или любой другой форум и задать вопрос там.
  5. Вы можете попробовать выполнить поиск по ключевым словам в Google Scholar и посмотреть, претендует ли какая-либо статья на это.

Что касается разницы в настройке, обычно у «хорошо известных» документов SOTA таких проблем нет. По крайней мере, это то, что я заметил в основном в своей области.

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

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

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

Алгоритмы оцениваются как хорошие или плохие на основе теоретических соображений, а не на основе выборочных данных. Теоретические меры делают их независимыми от оборудования в определенных пределах. Быстрый алгоритм будет работать быстрее, чем медленный, на разных компьютерах с похожей архитектурой (см. предостережения ниже). Некоторые алгоритмы (пузырьковая сортировка) всегда плохи. Другие всегда лучше (сортировка выбором). Третьи «всегда» хороши (сортировка слиянием, но см. предостережения).

Таким образом, идея «другого оборудования» — отвлекающий маневр, при условии, что оборудование имеет схожую архитектуру.

Предостережения, и их довольно много.

Некоторым алгоритмам требуется много памяти (быстрая сортировка большого набора), поскольку они сильно рекурсивны. Если на машине недостаточно быстрой памяти, то быстрая сортировка большого набора данных будет ограничена независимой эффективностью системы памяти.

Некоторые «медленные» алгоритмы хорошо работают с небольшими наборами данных и могут быть предпочтительнее «быстрых» алгоритмов, если ожидается, что набор данных будет небольшим. Но эти вещи известны и обычно включаются в работающее программное обеспечение. Например, при быстрой сортировке после того, как «разделение» приведет к сегменту размером 10 или около того, для завершения сортировки вступит в действие квадратичный алгоритм. Но это всего лишь хорошая разработка программного обеспечения, и оно использует известные теоретические результаты для различных вариантов.

Однако, если архитектура машины резко изменится (как GPU отличается от CPU), то и игра изменится, и некоторые алгоритмы, быстрые на одном, будут медленнее на другом. Например, все еще сортируя вещи, если архитектура делает сравнения «бесплатными», тогда алгоритм, который использует множество сравнений, а не перестановок, будет предпочтительнее для этой архитектуры . Но, опять же, это основано на теоретических соображениях, которые измеряют различные виды операций, требуемых алгоритмом.

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

Еще одно предостережение. Есть некоторые прикладные задачи, которые довольно плохо структурированы и (пока) не поддаются теоретическому анализу, принятому выше. Возможно, здесь присутствует некий хаос. Для них в настоящее время могут потребоваться некоторые эмпирические измерения. Но некоторые из этих проблем также могут побудить людей изобретать новые архитектуры, способные эффективно справляться с этими проблемами. Но такого же рода проблемы также побуждают теоретиков изобретать новые алгоритмы, поддающиеся общему анализу эффективности. Но результаты, скорее всего, будут представлены в теоретическом плане, а не в таймингах на конкретном железе. Вероятно, это то, что вы видите. И, надеюсь, часть их анализа включает ограничения на то, когда можно ожидать, что алгоритм будет вести себя хорошо.

Я предполагаю, что этот ответ применим к сравнению множества видов сортировки, но удачи вам в вашей «теоретической» оценке любого машинного или статистического подхода к обучению.
@Libor, на самом деле, любой алгоритм (при условии, что это действительно алгоритм) можно проанализировать и предсказать его эффективность. Случайность, например, не является препятствием. Некоторые вещи сложнее, чем другие, конечно. Но алгоритмика не мертвое искусство.
Ладно, теоретически скажите мне, какой дизайн автоэнкодера имеет наилучшую производительность, а я подожду здесь.
@Libor, хорошо, ты делаешь это.
@Libor И есть некоторые вещи, которые представляют интерес, но не подходят под определение алгоритма. Я не включаю их, поскольку они выходят за рамки вопроса.
Я думаю, что этот ответ либо совершенно неверен, либо вы используете слово «алгоритм» не так, как привыкли многие люди.
@ user2316602, см. редактирование. Алгоритм имеет формальное определение в CS и математике (обратите внимание на теги). Я имею в виду это значение, а не какой-то неофициальный синоним «компьютерной программы». Значение слов имеет значение, я думаю. Если вы хотите получить ответ на более широкий вопрос, то задайте его.
Да, это ссылка на википедию для алгоритма. Дело в том, что многие алгоритмы не поддаются точному анализу эффективности, как вы описали, и что эффективность и производительность не являются синонимами, независимо от того, сколько раз вы их смешиваете .
@Libor, ты просишь меня ответить на вопрос, отличный от того, который задан ОП? Если да, то укажите это. Я думаю, что здесь происходит много сравнений яблок и апельсинов или, по крайней мере, алгоритмов и программ.
Спасибо за подробный ответ! Я понимаю, что существуют разные коннотации слова «эффективный» в зависимости от проблемы, с которой я сталкиваюсь. Я не хотел сказать, что существует только один эффективный алгоритм для конкретной темы. Мой вопрос касался только поиска лучшего алгоритма для конкретной задачи (который учитывает использование памяти, размер задачи и т. д.) в большой куче академических статей в Интернете.
Я думаю, что путаница здесь в том, что слово «алгоритм» используется по-разному в разных областях. В машинном обучении, хотя «архитектуры» в некоторых случаях придумываются как алгоритмы, они не совсем связаны теми же правилами, что и упомянутые выше. То, как Баффи сформулировала это утверждение, верно в отношении того, какими должны быть алгоритмы, но неверно в отношении того, как алгоритмы «воспринимаются» в разных областях». * Теоретические меры не ограничивают алгоритмы в других областях, и я думаю, что проблема здесь в этом. , И в общих исследованиях алгоритмов также нет проблем с «обобщаемостью».
@Aymous, я понимаю, что люди за пределами CS и математики могут использовать термины неформально. Но я также зависел от конкретных тегов вопроса. А в математике и компьютерных науках алгоритм имеет особое значение, которое остается стабильным уже более полувека. Утверждение об алгоритмах может не применяться к неалгоритму. Я подозреваю, что теперь, когда ОП на самом деле имел в виду нечто иное, чем то, что сказано буквально. Отчасти я пытался дать толчок обучению ОП, у которого где-то есть путаница. Но они спросили, почему статьи по алгоритмам имеют определенную структуру, и я написал об этом. Не о других вещах.
@Aymous, и ваш ответ, хотя я думаю, что он больше о «полезных компьютерных программах», чем об алгоритмах (и хорошо в этом контексте), может быть больше тем, что интересовало здесь ОП. Возможно, они нас просветят.
@Buffy Я на самом деле имел в виду, что внутри самого CS термин «алгоритм» используется по-другому! Многие места в CS они называют "полезными компьютерными программами" как "алгоритмы". Я думаю, отсюда и возникла путаница. Я полностью согласен с тем, что вы сказали об алгоритмах, но это слово имеет другое значение в нескольких областях внутри самой CS.
@ Баффи Я проголосовал за ваш ответ и считаю его очень полезным. Вы рекомендуете мне вместо этого переименовать мой вопрос в «современную программу»?
Я думаю, что у людей, изучающих «алгоритмы и структуры данных», есть формальное определение алгоритма, которое отличается от того, что используют другие люди, даже внутри TCS. Я думаю, что, если не указано иное, это не следует считать определением, подразумеваемым ОП и мной, поэтому я думаю, что все в порядке. Обратите внимание, что я говорю это как человек, специально занимающийся алгоритмами, поэтому я привык к тому значению, которое использует Баффи.
Другая причина разрыва между теоретической и практической эффективностью заключается в том, что теоретиков в основном волнует сложность в наихудшем случае (и, возможно, некоторое абстрактное понятие сложности в среднем случае). Часто эти случаи не совсем репрезентативны для практических входных данных. Ярким примером являются решатели SAT, где лучшие методы имеют меньшую теоретическую сложность, чем другие, но быстрее решают практические примеры (миллионы переменных).
Как найти современный алгоритм для конкретной задачи
СпросиСетьПолитика конфиденциальности1y, 0v