LINUX.ORG.RU

Какие алгоритмы вы чаще всего используете?

 ,


3

2

Привет ЛОР!

Углубляюсь в тему алгоритмов.

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

На чем их реализуете?

Спасибо.

Алгоритм перехода дороги на зелёный свет. Так и не понял, что тебя конкретно интересует.

anonymous ()
Ответ на: комментарий от anonymous

Меня интересует степень востребованности разных алгоритмов в коммерческих проектах.

Понятно, что есть стандартные, про которые написали книги Кнут, Кормен и т.д.

Но кроме них, есть же еще. По ним отдельные книги на много страниц.

Хочется узнать, какие часто используют на практике, без каких обходятся

amidala ()
Ответ на: комментарий от amidala

Но кроме них, есть же еще. По ним отдельные книги на много страниц.

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

gag ★★★★★ ()
Ответ на: комментарий от amidala

Хочется узнать, какие часто используют на практике, без каких обходятся

на практике часто используют готовые реализации не понимая (зная) как они работают.

mashina ★★★★★ ()

Расскажите, какие алгоритмы вы чаще всего используете в вашей реальной работе

Те, которые требуются для решения поставленной задачи.

На чем их реализуете?

Что вы хотите узнать этим вопросом?

no-such-file ★★★★★ ()
Ответ на: комментарий от gag

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

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

anonymous ()
Ответ на: комментарий от amidala

Хочется узнать, какие часто используют на практике, без каких обходятся

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

anonymous ()
Ответ на: комментарий от anonymous

Что-то типа «хочется узнать, как люди на оплачиваемой работе чаще водят рукой, слева направо или сверху вниз».

Nick: amidala
Дата регистрации: 28.10.2013 11:03:06

Это норма.

sT331h0rs3 ★★★★★ ()
Ответ на: комментарий от gag

Да, вместо перебора всех пар точек в пространстве побил все на квадраты, посчитал хеши и засунул все точки в хешмапу в родной хеш и 9 соседних. После этого нашел все пары близлежащих.

Результирующий алгоритм: 1 h vs 5 sec

И да, counting sort не добавляют в стандартные библиотеки и потому в подходящих для него случаях никто его не использует, а шпарят quicksort/mergesort из стандартной

vertexua ★★★★★ ()
Последнее исправление: vertexua (всего исправлений: 1)
Ответ на: комментарий от mashina

С одной стороны логично, если есть готовое, и если количество усилий затраченное на разработку/понимание какого-то алгоритма не сравнимо с пользой, которую он дает на выходе

amidala ()
Ответ на: комментарий от anonymous

Тоже логично, если программирование воспринимать не просто как инструмент

amidala ()
Ответ на: комментарий от gag

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

По сабжу, из общеупотребимого я юзаю интерполяции всякие. Остальное слишком специфично.

AIv ★★★★★ ()

Много чего использую, но чаще всего сталкиваюсь с ситуацией, когда тупо нет готовых реализаций! Приходится велосипедить.

Anon ()
Ответ на: комментарий от amidala

есть же еще.

Интересно, зачем ту страничку в педивикии составили? "Список алгоритмов" — это нечто необъятное и постоянно растущее, эдакая микроВселенная.

Anon ()

какие алгоритмы вы чаще всего используете в вашей реальной работе

те, что доктор Кнут прописал.

А что, есть другие?

На чем их реализуете?

да на чём угодно. Какая разница-то? То, что подходит получше. Обычно на сишечке...

emulek ()
Ответ на: комментарий от emulek

те, что доктор Кнут прописал

Я его последний том не читал, но сдается мне, что в моей области таки Гонзалез с Вудсом и то рулезней.

Anon ()
Ответ на: комментарий от amidala

Но кроме них, есть же еще.

мощная спискота. У Кнута есть почти всё. Того, чего нет у Кнута, и «алгоритмом» назвать нельзя. Это скорее «реализация». Ну LZ77 к примеру. В спискоту оно попало лишь из-за того, что является одно из очень важных реализаций.

Хочется узнать, какие часто используют на практике, без каких обходятся

а это смотря чем ты занимаешься... Я вот про астрономию и не слышал, но в спискоте оно есть. Значит кому-то нужно... А посмотрел — там они Пасху вычисляют... Да, годнота...

emulek ()
Ответ на: комментарий от vertexua

Да, вместо перебора всех пар точек в пространстве побил все на квадраты, посчитал хеши и засунул все точки в хешмапу в родной хеш и 9 соседних. После этого нашел все пары близлежащих.

у меня для тебя плохие новости: это стандартная и всем известная http://ru.wikipedia.org/wiki/Блочная_сортировка

И да, counting sort не добавляют в стандартные библиотеки

как ты её добавишь, если для её работы необходимо знание внутренней структуры эл-тов? Стандартные сортировки требуют только ОДНОГО — дать им какую-нить функцию, которая даёт «true», если один элемент «меньше» другого. А тебе всю структуру данных надо знать, как расковыривать. В твоём случае тебе понадобилось знание об этом пространстве, дабы разделить его на области, и присвоить каждой области свой хеш.

Но что самое печальное, в твоём алгоритме есть ошибки: если есть две очень близкие точки, которые лежат по разные стороны границы, то они ближайшие, но твой алгоритм считает их «далёкими». Как ты это решил?

emulek ()
Ответ на: комментарий от Anon

Я его последний том не читал, но сдается мне, что в моей области таки Гонзалез с Вудсом и то рулезней.

конечно рулёзней. Но там нет ничего кардинально нового.

emulek ()
Ответ на: комментарий от AIv

погуглите LRnLA. Заявили громко, выигрыш коллосальный, кроме нас никто не пользуется.

что-то я вам не верю. Если я правильно понял вашу идею, то вы разбиваете область по границе распространения возмущений. Но неужели вы это первыми придумали? Это же очевидно!

...хотя если подумать, то да... Способ с «бесконечно быстрым светом» проще концептуально.

emulek ()
Ответ на: комментарий от emulek

не мы наверное, но мы первые (и пока к сожалению последние) сделали для современных PC. В хаскеле вроде в компиляторе че то похожее заложено, но оно универсально и поэтому неэффективно.

AIv ★★★★★ ()

Расширенный алгоритм Евклида и соотношение Безу.

Deathstalker ★★★★★ ()
Ответ на: комментарий от emulek

ОК. В следующий раз персонально тебя буду спрашивать. А пока: я уже больше двух лет бьюсь на интегрировании векторного поля с неравномерно расположенными опорными токами. Как?

Anon ()
Ответ на: комментарий от Anon

Как?

<drBatty-mode>Читай Кнута, там всё есть!</drBatty-mode>

i-rinat ★★★★★ ()
Ответ на: комментарий от emulek

Но что самое печальное, в твоём алгоритме есть ошибки: если есть две очень близкие точки, которые лежат по разные стороны границы, то они ближайшие, но твой алгоритм считает их «далёкими». Как ты это решил?

В 9 близжайших хешей так же помещается элемент. Но поиск не больше радиуса одного квадрата.

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

vertexua ★★★★★ ()
Ответ на: комментарий от Anon

ОК. В следующий раз персонально тебя буду спрашивать. А пока: я уже больше двух лет бьюсь на интегрировании векторного поля с неравномерно расположенными опорными токами. Как?

я сказал «плохо ищешь», а не «я это всё знаю». Я не знаю.

Могу дать совет: у Кнута всё есть :)

Если серьёзно, есть. Только надо уметь читать. Математика она большая. И расчёт электрических токов внутри схемы с разными сопротивлениями, вполне годен для анализа времени работы алгоритмов. Математический аппарат тот же самый. Т.е. совет в том, что решение вовсе не обязательно находится в этой области, может оно принципиально из иной какой-то левой области, и ты про него просто не знаешь.

emulek ()

Алгоритм икрементации целых чисел.

fmap ()
Ответ на: комментарий от emulek

И расчёт электрических токов внутри схемы с разными сопротивлениями, вполне годен для анализа времени работы алгоритмов.

Продолжай :)

nerdogeek ()
Ответ на: комментарий от vertexua

В 9 близжайших хешей так же помещается элемент. Но поиск не больше радиуса одного квадрата.

т.е. ты 9 раз копируешь одну точку в 9 разных квадратов?

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

она и есть. Я её называю «сортировка расстановкой». Ты ничего не сортируешь, а просто раскладываешь элементы по нужным областям. Очевидно сложность этого процесса равна O(n), т.е. лучше любой сортировки на месте.

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

emulek ()
Ответ на: комментарий от nerdogeek

Продолжай :)

я забыл поставить (C)Кнут. Продолжение у него-же.

emulek ()

google:«Кулинария - это искусство, благородная наука; все кулинары - джентльмены»

рецепт есть следствие какое же блюдо желают.

qulinxao ★★☆ ()
Ответ на: комментарий от Waterlaz

кнут очень глубок - редко когда нужна та глубина,

и да - не все направления покрыты ( 7 томов так и не изданы ;) )

Однако - вся суть кнута(и всякого компендиума алгоритмов с возможно с их обоснованием)

Есть рецепты - их можно самостоятельно (пере)открыть и есть они же(в части уже известных человечеству в части кому важно) уже собранные - полезно понимать что возможно , что нет и какие перспективы в блюдах.

qulinxao ★★☆ ()
Ответ на: комментарий от fornlr

лжёш

большая часть тобой используемые(вавшиеся) алгоритмы - уже давно в общественной собственности - в частности «круглое катить» ну и вообще «колесо и прочая вторая сигнальная »

qulinxao ★★☆ ()
Ответ на: комментарий от amidala

Хочется узнать, какие часто используют на практике, без каких обходятся

те(алгоритмы) о которых известно разработчикам при решение части встречающихся им задач

достаточно быть грамотным.

начни с понимания как работают простые(где индекс по натуральному) массивы ; как работают ассоциативные ( db key-value); «передача через стек у С это по сути сериализация со всеми забавностями сериализации»

и так далее

qulinxao ★★☆ ()
Ответ на: комментарий от amidala

покури Бенли «Жемчужины программирования» - не для константного знания им упомянутых вычислительных/датарулинг алгоритмов , а для премения им описанных алгоритмов/рецептов «как решать задачи » ну и прочий

Пойя Д. / Как решать задачу / - вот эти рецепты|эвристики тебе могут пригодится очень очень - наряду с частными заклинаниями как же сортануть набор и прочая числомагия

qulinxao ★★☆ ()
Ответ на: комментарий от vertexua

И да, counting sort не добавляют в стандартные библиотеки и потому в подходящих для него случаях никто его не использует, а шпарят quicksort/mergesort из стандартной

кста отличный пример как «фреймворк|библиотека|язык|RAD...|„человеку держащему молоток окружающие[предметы|обьекты] воспринимаются гвоздями“ » изменив метрику сложности «процесса изготовления» программы влияют на распространнёность тех или иных решений ( в сравнении с идеальными в критерии выч. оптимальности работающего процесса)

qulinxao ★★☆ ()
Последнее исправление: qulinxao (всего исправлений: 1)

И дня не проходит, чтобы я не использовал законы деМоргана.

tailgunner ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.