LINUX.ORG.RU

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

 


3

2

Привет ЛОР!

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

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

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

Спасибо.

Ответ на: комментарий от qulinxao

«передача через стек у С это по сути сериализация со всеми забавностями сериализации»

В каком это месте?

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

так как типы у компилируемогоС не тегированны и вовремя выполнения это просто битовые наборы - при перегоне через «среду передачи»(стек) и писатель(вызывальщик) и (читатель|отвечатель)(вызванная функция) как правило похардкоженному интерпретируют что же им передали/ответили.

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

А если бы они были тэгированы, то вызывальщик и отвечальщик имели бы похардкоженные правила интерпретирования тэгов. Упс, рекурсия.

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

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

она всегда нужна, если ты не быдлокодер.

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

ты быдлокодер. А Кнут не собирал алгоритмы как рецепты.

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

не не не есть же «самоописывающие» форматы - т.е тежи сопутствующие теги-заголовки по которым процедура(будь в этом необходимость) может получить что за структура данных ей передана.

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

т.е ситуация при передачи аргументов (хоть и синхронном обычно) похожа на разнесённых в пространнстве/времени читателей/писателей у которых либо хардкоженые ожидания либо простенький интерпретатор формата принятых отправленых (на сериализацию) данных.

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

меньше батхёрта плиииииз

она всегда нужна

для космоса.

мань фон-неймана по теме «построение надёжных систем из ненадёжных подсистем|элементов» - т.е требование везде глубоких реализаций очень не_инженерно само по себе.

А Кнут не собирал алгоритмы как рецепты.

но его Опус Магнум и есть поваренная книга.

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

так как типы у компилируемогоС не тегированны и вовремя выполнения это просто битовые наборы - при перегоне через «среду передачи»(стек) и писатель(вызывальщик) и (читатель|отвечатель)(вызванная функция) как правило похардкоженному интерпретируют что же им передали/ответили.

Это имеет значение исключительно для функций принимающих void*, и с переменным числом параметров.

Обычная функция принимает именно то, что ей передали. Просто потому, что ничего другого ты ей не сможешь передать.

И да, стек это принципиально «серилизация». Даже машинный.

emulek
()
Ответ на: меньше батхёрта плиииииз от qulinxao

но его Опус Магнум и есть поваренная книга.

ты так ничего и не понял. Алгоритмы там не более, чем примеры. Речь не о конкретной спискоте как в вике или поваренной книге, речь о _работе_ с алгоритмами. Может это и поваренная книга, но никак не сборник рецептов. Там написано, как мешать поварёшкой борщ, по ходу дела ты узнаёшь, что в борщ надо свёклу добавлять. Но упор на поварёшке, а не на свёкле. Ещё на ноже, которым свёклу режут, на доске, на которой свёклу режут, и т. п. Да, «свёкла» там через каждое слово встречается, но речь не о свёкле. Речь о процессе изготовления супа, на примере свекольного борща. И да, про щи из крапивы там не слова, но тебе не составит труда эти щи из этой крапивы сварить самостоятельно, т.к. ты освоил инструменты, и у тебя есть навыки варить некий суп.

мань фон-неймана по теме «построение надёжных систем из ненадёжных подсистем|элементов» - т.е требование везде глубоких реализаций очень не_инженерно само по себе.

IRL никто и не делает развёрнутый анализ сортировки как у Кнута. Да и саму сортировку IRL никто не делает. Она уже есть готовая. Просто выбери НУЖНУЮ. Но как же ты, быдлокодер, выберешь, ежели не постиг эту «глубину», а именно то, ЧЕМ эти сортировки отличаются, и ПОЧЕМУ их так много разных?

Те формулы, что есть в справочниках, IRL не работают, либо работают не так. Ибо в справочниках пишут про идеальные случаи (поведение алгоритма в бесконечности например), которые вообще говоря к RL отношения не имеют. IRL формулы надо допиливать, а иногда и сами алгоритмы.

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

как бы ни уныло это звучало, исползую только пыховский asort()... 1.5 раза в год

там в твоём пыхе ещё есть сортировка, которую ты постоянно юзаешь: сортировка внутри массива. Т.е. когда ты создаёшь массив с символьными ключами, они по любому сортируются. Ну а твоя asort просто пересортировывает «ключи» по другому, так, что «ключом» для сортировки выступает значение, а не индекс.

emulek
()

Чаще всего использую те алгоритмы, которые необходимы в данной ситуации.

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

Обычная функция принимает именно то, что ей передали. Просто потому, что ничего другого ты ей не сможешь передать.

У тебя явно проблемы с пониманием.

// foo.c
#include <stdio.h>
void print_arguments(int a, int b) {
	printf("a = %d, b = %d\n", a, b);
}
// bar.c
void print_arguments(int a, float b);

int main(void) {
	print_arguments(1, 1);
	return 0;
}
$ gcc foo.c bar.c && ./a.out 
a = 1, b = -77954920

Так, надеюсь, понятна идея?

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

Мне так понравилось сравнение с борщем )

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

И еще здесь скорее подходы делятся на два типа. Кому-то просто нужно решить задачу, а кто-то хочет решить ее идеально

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

Так, надеюсь, понятна идея?

идея понятна. Непонятно, ОТКУДА такое появится? IRL void print_arguments(int a, int b); будет прописано в foo.h, и попытка её переопределения приведёт к невозможности компиляции.

Если-же функция void print_arguments(int a, int b); внутренняя для foo.c, то кто мешал тебе её сделать static? В таком случае ошибка будет «не могу найти print_arguments(int,float)», уже от линкера. Ну или будет работать _другая_, правильная void print_arguments(int, float).

Откуда правило: делай все внутренние функции static. Это вот такая в сишечке «инкапсуляция»...

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

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

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

то кто мешал тебе её сделать static?

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

В таком случае ошибка будет «не могу найти print_arguments(int,float)», уже от линкера.

Ты несёшь бред. Линкер не проверяет типы, он занимается только именами. Можешь убедиться: gcc -c foo.c bar.c; gcc -o a.out foo.o bar.o

i-rinat ★★★★★
()

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

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

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

дьявол в деталях: непонятно, КАКОЙ брать алгоритм. И да, их тоже нужно знать, хотя-бы для того, что-бы не изобретать свой велосипед.

И еще здесь скорее подходы делятся на два типа. Кому-то просто нужно решить задачу, а кто-то хочет решить ее идеально

время решения тоже важно. Никому не нужен программист, который решает одну задачу год, если другой решил её за неделю. И уже нет никакой разницы, что первое решение лучше. Второе окупится Over9000 раз, пока первое только готовится.

Ну и потом, нет никакого смысла делать приложение, которое отрабатывает за 100мс, если есть вариант, когда отрабатывает за 500мс, и при этом всё равно нужно чего-то ждать 1000мс. Причём это общее правило — быстродействие в общем случае не нужно. Как и экономия ресурсов. В 95% кода. И только в частных 5% это нужно.

Повторю слова Кнута: преждевременная оптимизация есть зло.

Оптимизировать нужно не весь код, а только 5% кода. Да и то не всегда. Если код грамотно написан, то и оптимизировать там нечего, нужно новое железо. Есть только одна правильная «оптимизация»: исправление ошибок. В частности, смена неправильного алгоритма на другой, правильный.

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

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

ты забыл слово «иногда», или «в моей практике».

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

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

вот именно для этого static и нужен, что-бы ты, или кто-то другой не подменил-бы случайно функции для линкера.

Ты несёшь бред. Линкер не проверяет типы, он занимается только именами. Можешь убедиться:

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

Т.е. для модуля bar.o у тебя будет лишь объявление функции, без её реализации.

Вот, посмотри этот пример: http://stackoverflow.com/questions/5319361/static-function-in-c

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

Линкер не сможет найти неправильную функцию.

Ну или будет работать _другая_, правильная void print_arguments(int, float).

Ты уже своих слов не помнишь, что ли?

i-rinat ★★★★★
()
Последнее исправление: i-rinat (всего исправлений: 1)

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

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

А что, у них много книжек известных? "Цифровая обработка изображений" же.

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

Те алгоритмы — для приблизительной аппроксимации поверхностей по набору точек. А у меня — векторное поле, и интегрировать надо очень точно. Вроде, добился более-менее приличных результатов тупыми наименьшими квадратами с полиномами Жао (ортонормированные линейные комбинации градиентов полиномов Цернике) и даже с тупыми градиентами полиномов Цернике (все равно наименьшим квадратам на ортогональность базиса наплевать), но что-то с моделью разобраться не могу (еще давно я трассировщик на куде написал, который мне моделирует снимки, полученные с помощью "кривого" зеркала, но что-то все никак концы с концами не сведу: обработка полученных гартманнограмм какая-то кривая выходит, совершенно не то, что было в оригинале).

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

слушай, я тебя не понимаю: ты мне показал на проблему, я объяснил, как её решить. Тебе непонятно решение? Учи матчасть.

линкер не сможет найти _неправильную_ функцию, потому-что она static. И потому он либо возьмёт правильную, если она есть, либо свалится с ошибкой, если её нет.

А у тебя проблема как раз в том и заключается, что линкер линкует не ту функцию, которая у тебя описана в прототипе.

Как и в C++, в классе должны быть только несколько нужных публичных методов, которые составляют интерфейс класса. Всё остальное делается private. В сишечке без плюсов такого нет, за то есть возможность делать static функции, которые, как и private методы не торчат наружу. И потому ни с чем не конфликтуют. И ты их можешь менять как угодно, не опасаясь того, что смена типа функции как-то порушит другой код, который использует твой.

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

А вообще, конечно, можно будет попробовать и триангуляцию сделать: нормаль к каждому треугольнику считать как среднюю нормаль по вершинам, а потом наименьшими квадратами попытаться их все "состыковать".

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

Пузырек для мелких данных, квик для больших. Все пишу сам.

интересно, какой ЯП?

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

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

Тут просто некоторые утверждают, что если этого нет в Кнуте, то оно почти что и не алгоритм :D

У Кнута почти ничего нет по графам и вычислительной геометрии, например. Да и судя по названию ненаписанных томов, и не предвидится.

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

слушай, я тебя не понимаю: ты мне показал на проблему, я объяснил, как её решить. Тебе непонятно решение? Учи матчасть.

Неа. Ты проявил непонимание довольно простой вещи: проблема с вызовом функции с неправильными типами параметров. Я показал пример, где это проявляется. Пока что твоё знание матчасти хромает. Иначе ты бы всё понял сразу.

И потому он либо возьмёт правильную, если она есть, либо свалится с ошибкой, если её нет.

Как он узнает правильную? Ты считаешь, что линкер знает типы аргументов функций? Он не знает.

А у тебя проблема как раз в том и заключается, что линкер линкует не ту функцию, которая у тебя описана в прототипе.

Просто ты с таким не сталкивался. В книжках-то всё идеально. :) Про факапы там не пишут.

i-rinat ★★★★★
()

Таки обход графов (DFS, BFS) пару раз встречался на работе.

Часто пользуюсь сортировкой и поиском из стандартной библиотеки.

Вроде всё.

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

Неа. Ты проявил непонимание довольно простой вещи: проблема с вызовом функции с неправильными типами параметров. Я показал пример, где это проявляется. Пока что твоё знание матчасти хромает. Иначе ты бы всё понял сразу.

это ты до сих пор похоже не понял, что проблема не в ЯП, а в линкере. Который не различает разные (с т.з. ЯП) функции. Вот и приходится применять костыль static, дабы прятать от линкера функции, что-бы он в них не путался.

В самом ЯП такой проблемы нет, и никогда не было. Это _разные_ функции, и компилятор их никогда не спутает. Он и в твоём примере их не путал, а спутал линкер.

Как он узнает правильную? Ты считаешь, что линкер знает типы аргументов функций? Он не знает.

линкер не может этого узнать. Это вообще не его задача. Его задача — линковать то, и только то, что нужно. А вот твою функцию очевидно не нужно, т.к. у неё совсем другой тип. А имя — тоже самое. Это «конфликт имён» называется. И для его решения требуется прятать лишние имена.

Просто ты с таким не сталкивался. В книжках-то всё идеально. :) Про факапы там не пишут.

при чём тут «книжки»? Это как раз моя практика. Я как-то уже наступил на эти грабли, и понял, зачем для функций нужен static. Вот как раз для того и нужен, что-бы грабли зубцами вниз класть. Пока не наступишь, не поймёшь.

По уму для каждого модуля нужна реализация foo.c и заголовки foo.bar. Причём в заголовках должны быть прописаны прототипы всех «публичных» функций, а в реализации, публичные должны быть прописаны без static, а не публичные С static.

И вот тогда конфликт имён будет невозможен. И fuckup тоже. Можешь сам проверить все варианты.

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

это ты до сих пор похоже не понял, что проблема не в ЯП, а в линкере. Который не различает разные (с т.з. ЯП) функции. Вот и приходится применять костыль static, дабы прятать от линкера функции, что-бы он в них не путался.

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

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

Никто не спрашивает у тебя, как решить ту или иную проблему.

конечно. Никакой быдлокодер не признается в том, что он быдлокодер. Проще ЯП хейтить. Дескать «проблема в ЯП». А тот факт, что проблема Over9000 лет назад решена, быдлокодера не волнует.

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

По уму для каждого модуля нужна реализация foo.c и заголовки foo.bar. Причём в заголовках должны быть прописаны прототипы всех «публичных» функций, а в реализации, публичные должны быть прописаны без static, а не публичные С static.

Ты еще скажи, что никогда такого не бывает, что не подключили заголовочный файл, но с объектным слинковали.

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

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

в твоей сишечки может и нет модулей, это твои проблемы, и проблемы твоей сишечки.

Разгадка проста: в математике первоклассника тоже мало чего есть. Там нет даже дробных чисел и возведения в степень. Это чья проблема? Математика плохая?

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

в твоей сишечки может и нет модулей, это твои проблемы, и проблемы твоей сишечки.

А я-то думал, мы говорим о функциях в си :3

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

это ты до сих пор похоже не понял, что проблема не в ЯП, а в линкере. Который не различает разные (с т.з. ЯП) функции.

Ой-вей, ты же только что говорил, что линкер выберет правильную функцию. Да ты «плывёшь», как студент на экзамене. :)

при чём тут «книжки»? Это как раз моя практика.

Где она, твоя практика? Сплошная демагогия, никакой практики.

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

Что ты талдычишь всё одно и то же? С этим никто и не спорит кроме тебя. Это ж азы.

И вот тогда конфликт имён будет невозможен. И fuckup тоже.

Ну надо же, всё надо разжёвывать. Ну ладно. Не всё в мире написано на C. Иногда нужно сопрягать бинарники с Python, например. Дай угадаю, у Кнута этого нету?

По уму для каждого модуля нужна реализация foo.c и заголовки foo.bar. Причём в заголовках должны быть прописаны прототипы всех «публичных» функций, а в реализации, публичные должны быть прописаны без static, а не публичные С static.

Ой-вей, да ты изобрёл http://ru.wikipedia.org/wiki/Язык_описания_интерфейсов !

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

Ты еще скажи, что никогда такого не бывает, что не подключили заголовочный файл, но с объектным слинковали.

а ты про стеклянный член никогда не слышал?

Причём тут ДВОЙНАЯ ошибка должна быть, если ты просто слинкуешь с чем-то, что без заголовка, то у тебя не соберётся код, ибо компилятор-то не в курсе, что ты линкуешь, и напишет просто — «функция не найдена». Т.е. до линкера и не дойдёт. Это тебе надо как-то извратится, и я не знаю, как именно.

Но да, если ты не понимаешь что творишь, то конец немного предсказуем. Вот только ЯП тут не при чём. Как и вообще программирование.

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

пфф... очень просто. У тебя есть a.h с a.o и b.h с b.o. Если в обеих модулях есть функция f, то ты без проблем слинкуешь a.o при заголовочном файле b.h.

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

Ой-вей, ты же только что говорил, что линкер выберет правильную функцию. Да ты «плывёшь», как студент на экзамене.

это ты «поплыл». В демагогию ударился...

Где она, твоя практика? Сплошная демагогия, никакой практики.

вот именно.

Что ты талдычишь всё одно и то же? С этим никто и не спорит кроме тебя. Это ж азы.

от оно как! теперь уже «азы». А почему ты забыл про азы, когда писал этот быдлокод: Какие алгоритмы вы чаще всего используете? (комментарий) ? Хотел проверить мои знания? Знаю-ли я про static? Вот видишь — знаю. Я надеюсь, что ты усвоил урок, и больше такого быдлокода писать не станешь.

Ну надо же, всё надо разжёвывать. Ну ладно. Не всё в мире написано на C. Иногда нужно сопрягать бинарники с Python, например. Дай угадаю, у Кнута этого нету?

круто! Значит слился на сишечке, и теперь её хейтишь тем, что она с питоном не стыкуется в твоих руках? Ну хорошо, что хоть сама с собой у тебя состыковалась... А про питон тебе домашнее задание.

Ой-вей, да ты изобрёл

ничего я не изобретал. Но всё равно рад, что ты сегодня узнал много нового.

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

пфф... очень просто. У тебя есть a.h с a.o и b.h с b.o. Если в обеих модулях есть функция f, то ты без проблем слинкуешь a.o при заголовочном файле b.h.

как получилось, что у тебя без ошибок линкуется проект, в котором есть две публичные f в разных *.o ?

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

это ты «поплыл». В демагогию ударился...

О, проекция. Агрессивная. Ты сначала говорил, что линкер выберет нужную функцию, потом, что он не сможет выбрать нужную функцию, а потом вообще назвал это проблемами «сишечки», как ты её называешь. Ты уж определись.

вот именно.

Есть что показать по существу? Давайте все вместе посмотрим на код мастера. Нет? Всё у Кнута? Ох...

А почему ты забыл про азы,

Я не забыл, я объяснял азы тебе.

Я надеюсь, что ты усвоил урок, и больше такого быдлокода писать не станешь.

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

круто! Значит слился на сишечке, и теперь её хейтишь тем, что она с питоном не стыкуется в твоих руках?

Во-первых, я не мог слиться, ибо даже не спорил с тобой о C. Во-вторых, я ничего не «хейтю», «хейтишь» всё подряд ты. В-третьих, стыковка с другими системами — это весьма актуальная задача; она просто есть, и её бесполезно «хейтить». Ты неминуемо столкнулся бы с ней, если бы что-то делал, а не языком на форумах чесал.

ничего я не изобретал. Но всё равно рад, что ты сегодня узнал много нового.

Ты не тот человек, от которого можно узнать что-то новое. Наоборот, это я тебя учу новому. А у тебя от этого батхёрт. :-)

А ты всё молишься на Кнута, это у тебя реально религия. Но ссылки давать не можешь. Может ты и не читал его вовсе?

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

Наоборот, это я тебя учу новому.

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

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

десятикратным дублированием

Да 8бит референса * 10 = 80 байт. Норм

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