|
Информационные технологии
:: Математика и алгоритмы
|
|
| ||
breezee 26.09.16 - 15:13 | Собственно, сабж. Лично мне не разу. Везде есть встроенные методы как, например "Сортировать()" в 1С. | ||
Garykom 1 - 26.09.16 - 15:15 | Уточни какой именно | ||
Господин ПЖ 2 - 26.09.16 - 15:15 | повод для гордости? | ||
Flyd-s 3 - 26.09.16 - 15:16 | Мне пригодился как-то. На собеседовании тестовое задание решил, правда туда все равно не пошел работать | ||
Волшебник Модератор 4 - 26.09.16 - 15:16 | Сортирую пузырьком и ниипёт | ||
Garykom 5 - 26.09.16 - 15:20 | |||
Смотрящий 6 - 26.09.16 - 15:20 | Бинарный поиск - вещь! | ||
b_ru 7 - 26.09.16 - 15:20 | Пригождалось для понимания того, какое место в коде оптимизировать и как.
Грубо говоря, можно не помнить как работает qsort, но знать что в 1С именно он, и знать его алгоритмическую сложность. | ||
Торин 8 - 26.09.16 - 15:22 | Когда-то оч.давно, в СССР-е, когда я, МНС в красноярском Институте Физики программно моделировал движение доменных стенок в тонких плёнках, почти вся программа сводилось к непрерывной пересортировке двумерных массивов. И да, замена алгоритма пузырька на шейкер-сортировку ускорила работу программки раз так в тридцать. Так что Вирту я очень благодарен.
А в 1С-ке ни разу не пригодилась... | ||
Starhan 9 - 26.09.16 - 15:39 | Да, я по нему и другим алгоритмам изучал алгоритмирование :) | ||
Это_mike 10 - 26.09.16 - 15:53 | (8) Да, Вирт (http://cv01.twirpx.net/0001/0001776.jpg) в свое время стал внезапным открытием. Когда писали ассемблер (или дизассемблер - уже не помню) - были поражены, насколько квиксорт быстрее "интуитивного" пузырька. | ||
Jokero 11 - 26.09.16 - 15:56 | А знание модели OSI, а способность рассчитать, сколько памяти требуется для n-цветного дисплея c количеством пикселей MxK?
Учат всегда не тому, что нужно в жизни... | ||
oslokot 12 - 26.09.16 - 15:58 | А мне очень пригождается Сортировать() таблицу значений, полученную например при чтении строк из файла. Ну а чем еще сортировать? | ||
iceman2112 13 - 26.09.16 - 16:00 | (0) эти задачки нужны были для построения алгоритмического мышления. ВАШ КЭП | ||
Это_mike 14 - 26.09.16 - 16:06 | (12) а можно не сортировать, а построить индекс, и выбирать по индексу... | ||
oslokot 15 - 26.09.16 - 16:09 | (14) можно, только зачем если есть готовый метод сортировки? | ||
oslokot 16 - 26.09.16 - 16:11 | разве что он вероятно, медленнее | ||
Это_mike 17 - 26.09.16 - 16:11 | (15) так индекс - это по сути та же сортировка, только без передвигания содержимого. | ||
Михаил Козлов 18 - 26.09.16 - 16:15 | (14) Самому построить индекс нужно уметь. | ||
jsmith 19 - 26.09.16 - 16:15 | Нет. Чтобы отсортировать тот же массив, можно использовать список значений. | ||
oslokot 20 - 26.09.16 - 16:15 | (17) это да, но если ТЗ это реквизит ТП, то проще сортировать() ее перед выводом на форму | ||
NorthWind 21 - 26.09.16 - 18:56 | (0) пригодился бинарный поиск, когда понадобилось ускорить формирование таблицы 1.5 в книге учета по ОСНО 1С:Предприниматель (для 7.7). В 2004 году. | ||
WebberNSK 22 - 26.09.16 - 20:58 | в 1С эффективней использовать функции платформы сортировки
для не стандартных случаев в типовых пишут "свои" сортировки | ||
Torquader 23 - 26.09.16 - 21:02 | (10) Там ещё метод быстрой перестановки был - который очень даже хорошо сортирует.
Только сама сортировка не спасает - нужно ещё и упорядочивание хранить как-то, чтобы объекты в памяти не переставлять. | ||
ovrfox 24 - 28.09.16 - 17:17 | Сортировки - нет, а вот поиск в отсортированном - да.
А в 1С всегда достаточно встроенной сортировки. | ||
Кирпич 25 - 28.09.16 - 17:35 | а как же. на собеседование без пузырька еще ни разу не обошлось. | ||
scanduta 26 - 28.09.16 - 17:52 | Нет никогда. | ||
Torquader 27 - 28.09.16 - 17:52 | (25) А вот интересно - вопрошающе про метод перестановок рассказать сами смогут или им википедия понадобится ? | ||
PLUT 28 - 28.09.16 - 18:42 | (27) нет ничего проще "пузырька". даже википедия вопрошающим не нужна | ||
Garykom 29 - 28.09.16 - 19:18 | Кстати а какой лучший алгоритм десортировки?
Чтобы в отсортированных данных навел полный бардак, так чтобы отсортировать заняло дофига времени? Причем очень быстро это сделал и качественно! Примерно как перетасовка карточной колоды. | ||
Loky9 30 - 28.09.16 - 19:20 | (29) Сначала нужно знать как будут сортировать. Рекламное место пустует | ||
Garykom 31 - 28.09.16 - 19:23 | (30) Хорошо лучший для каждого из известных/популярных как будут сортировать и в среднем по всем | ||
ERWINS 32 - 28.09.16 - 19:31 | (29) смотря какой алгоритм сортировки
насколько я помню быструю сортировку убивал напрочь если выбраемый элемент есть мнмальный если выбираемый первый, то отсортированный массив будет сортироваться дольше всего если центральный, но ставим в центр минимальный, а остальные по возрастанию добавляем справа и слева. | ||
ERWINS 33 - 28.09.16 - 19:33 | сортировке слияниями пофиг, она не зависит от порядка.
сортировке вставками если используется список, то по возрастанию самое страшное. | ||
NorthWind 34 - 28.09.16 - 21:34 | Кстати, вот чисто случайно наткнулся на наглядный пример того, как понимание алгоритмов позволяет существенно оптимизировать специфическую выборку данных по скорости:
http://catalog.mista.ru/public/551583/ | ||
Garykom 35 - 28.09.16 - 21:44 | (34) Илдарович товарищ конечно умный, но иногда слишком заумно решает проблему которая имеет намного более простое решение.
Кто мешает в его "задачке интервалов" построить на отдельных таблицах свой индекс, который получается путем наложения интервалов друг на друга, получением всех "точек пересечений". Затем из этих "точек пересечений" получаем "минимальные отрезки не пересекающиеся отрезки" и строим из них индекс, где будет отрезок и в какие исходные интервалы он входит. В результате поиск нужных исходных интервалов (записей) по искомой позиции будет банальным, путем одного индекса (неважно слева или справа) для нашей таблицы индексов. | ||
Гобсек 36 - 28.09.16 - 22:31 | Вспомнилась газетная статья из тех времен, когда появились первые калькуляторы. В статье обсуждался вопрос, нужно ли современному школьнику знать таблицу умножения и умение считать в столбик. ИМХО - нужно. И об алгоритмах сортировки программист представление тоже должен иметь. | ||
Franchiser 37 - 28.09.16 - 22:36 | Пригодился при поступлении в институт) | ||
Torquader 38 - 28.09.16 - 22:38 | (36) Лучше ещё и о хранении данных подумать, так как сама по себе сортировка - ничего не решает, особенно, если в набор данных будут добавления или удаления.
Там уже будут немного другие слова об оптимальности. | ||
Jump 39 - 29.09.16 - 04:59 | (0)Программист - понятие широкое.
Большая часть современных программистов работает с фреймворками. Т.е это не чисто программирование, а больше конфигурирование фремворка. Это и 1с, и вся веб-разработка, и создание оконных приложений в большинстве своем. И любые задачи надо решать встроенными в фреймворк методами. Если ты использовал самописный алгоритм - это gовнокод, велосипедостроение, в общем - вон из профессии. Тут ценится скорость разработки, и понятность коду, а не быстродействие и эффективное использование ресурсов. Это не плохо, не хорошо, просто так есть. А алгоритмы, в том числе и сортировки нужны при низкоуровневом программировании, без их знания там будет трудно. | ||
Провинциальный 1сник 40 - 29.09.16 - 05:48 | (39) Даже прикладнику надо знать о порядке быстродействия и потребности в памяти используемых алгоритмов, чтобы не написать код, который умрет при определенном объеме данных. Типичный пример такой ситуации - сохранение большого количества строк с автовысотой в xls из 7.7. Так что, считаю, программист в любом случае должен знать об сортировках, двоичных и прочих деревьях и вообще о всём что написано у Вирта. Это как сопромат для инженера-строителя. | ||
Лодырь 41 - 29.09.16 - 05:56 | Да пригодился. Особенно пригодились внешние методы сортировки. А так же всякая мелочевка типа решающих деревьев и т.д. | ||
Jump 42 - 29.09.16 - 06:37 | (40) Не факт.
Работая с фреймворком довольно трудно предсказать потребность в памяти и эффективность работы алгоритма, через несколько уровней абстракции. | ||
Провинциальный 1сник 43 - 29.09.16 - 06:43 | (42) Приходится доверять разработчикам фреймворка, да. Предполагать, что они используют максимально оптимальные алгоритмы и методы. В точности так же, как строитель не отправляет каждый куль цемента на лабораторное исследование, доверяя указанной марке. | ||
Sammo 44 - 29.09.16 - 06:48 | Была пару раз ситуация, когда сортировал своими методами.
Из забавного - как-то использовал метод ветвей и границ | ||
Emery 45 - 29.09.16 - 07:55 | > Пригодился ли вам алгоритм сортировки?
Очень хороший вопрос! Дает повод похвастаться изобретением собственного метода сортировки имени моего имени : ) . Алгоритм описан в статьях «Внешняя сортировка «естественным слиянием» ( http://emery-emerald.narod.ru/Cpp/2E1562.html ) и «Work C++ Algorithm of External Natural Merge Sort with Non-decreasing and Decreasing Ordered Sub Sequences» ( http://www.codeproject.com/Articles/92761/Work-C-Algorithm-of-External-Natural-Merge-Sort-wi ) Преимущество указанного алгоритма в том, что он использует по максимуму существующий частичный порядок данных. И даже в случае абсолютно равномерно распределенной случайной последовательности данных их средняя длина L упорядоченных подпоследовательностей (УПП) > 2, так как любые две сравнимые величины всегда образуют УПП. Хотя возможен частный случай «зигзагообразной» последовательности данных произвольной длины, средняя длина L УПП которой в точности равна двум. Например, для последовательности нулей и единиц: {0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1, . . .} : L = Lmin = 2 Фактически эта последовательность обладает минимальным порядком для целей нашего алгоритма. Однако нашим преимуществом остается один проход для функции Split, фиксированный объем данных для ее параметров и наличие только двух файловых буферов (с учетом неизменности исходных данных). Но вернемся к случаю равномерно распределенной случайной последовательности данных. Какова будет средняя длина L (определяемая как отношение суммарной длины последовательности к количеству всех УПП на ней)? Ясно, что в этом случае L > Lmin = 2 и тем самым мы можем использовать этот дополнительный порядок для более быстрой сортировки. А это можно сказать уже алгоритмическое преимущество. Задача по вычислению средней длины УПП L для равномерно распределенной случайной последовательности данных не кажется очень сложной, однако в Интернете не удалось найти готовое решение, поэтому пришлось озадачить форум математиков и после совместного обсуждения проблемы (в теме: «Распределение порядка во всех перестановках») мне (под ником Scholium) удалось вычислить эту величину ( http://dxdy.ru/topic25746.html ): L = 2e – 3 = 2.436563656918 . Не правда ли интересно? Случайная последовательность и обладает частичным порядком больше минимального! Что уж тут говорить про реальные данные упорядоченность которых всегда выше абсолютно равномерного распределения случайных величин. Вот почему данный алгоритм представляет особый интерес. К тому изобретен он был для практических целей – сортировки больших массивов внешних данных, вроде dbf-файлов. Думаю, что я еще вернусь к этим исследованиям и разработкам в дальнейшем. | ||
DrZombi 46 - 29.09.16 - 07:57 | (4) Пузырек не самый быстрый метод ;) | ||
DrZombi 47 - 29.09.16 - 08:03 | (0)Держи Шейкерную сортировку, на больших объемах работает быстрее пузырьков :)
https://ru.wikipedia.org/wiki/Сортировка_перемешиванием А вообще, вот тут почитай... https://ru.wikipedia.org/wiki/Алгоритм_сортировки | ||
NorthWind 48 - 29.09.16 - 08:03 | (42) Ну и соответственно когда штатное перестает работать, дело все равно кончается велосипедами, чтобы хоть как-то решить задачу. На практике я бы не возводил ничего в абсолют, в том числе и механизмы фреймворков. Главое - решить поставленный вопрос, а уж как - это проблемы программиста. Если решил плохо - авось другие перерешают или сам со временем. | ||
Jump 49 - 29.09.16 - 08:06 | (48) Ну не всегда так.
Если проект большой, а ты на своем участке сделал костыль нештатными методами - при следующем же релизе это вылезет, и все придется переписывать. Если ты целиком контролируешь проект тогда можно. | ||
Jump 50 - 29.09.16 - 08:14 | (46) Вообще быстрота не единственный и не всегда главный показатель. Есть еще такие вещи как потребляемая память.
Ну и опять же быстрый на каком объеме данных. Разные алгоритмы работают с разной эффективностью в зависимости от размера. Так что надо учитывать сколько элементов - 100 или 100миллиардов. | ||
Это_mike 51 - 29.09.16 - 08:16 | (48) А как же "использовать только методы, освященные Нуралиевым, и записанные в священных ЖКК и ЖЖК"? :-) | ||
DrZombi 52 - 29.09.16 - 08:19 | (50) Ага, скорость не важна, можно и подождать день другой :DDD | ||
jsmith 53 - 29.09.16 - 08:20 | Вы не попутали мисту с хаброй? | ||
DrZombi 54 - 29.09.16 - 08:20 | |||
jsmith 55 - 29.09.16 - 08:20 | Тут серьезными проектами занимаются, а сортировки и прочие досуги нердов обсуждают там. | ||
Это_mike 56 - 29.09.16 - 08:21 | (52) если задача разовая - можно за час написать, и пусть хоть два дня считает.
если задача ежедневная для 100 юзверей - то лишняя минута работы алгоритма в день будет ежемесячно обходиться компании в четверть средней зарплаты. | ||
DrZombi 57 - 29.09.16 - 08:22 | (55) Да бросьте, народ кроме пузырька не чего не знает :) | ||
Это_mike 58 - 29.09.16 - 08:23 | (54) если эти "милллиарды" влезут в память с произвольным доступом. | ||
DrZombi 59 - 29.09.16 - 08:23 | (56) Нет нечего постоянней, чем временное :) | ||
Jump 60 - 29.09.16 - 08:24 | (52) Я же говорю не всегда важна.
Кроме скорости есть потребление памяти. Например выбрал ты алгоритм который работает в два раза быстрее, но потребляет в два раза больше памяти. На реальной задаче у тебя памяти банально не хватает, комп уходит в подкачку, и в результате твой быстрый алгоритм работает в сто раз медленнее. Хоть и быстрый. Рекламное место пустует | ||
Это_mike 61 - 29.09.16 - 08:24 | (59) не "временное", а "разовое". там выходят на повестку совсем другие критерии. | ||
DrZombi 62 - 29.09.16 - 08:27 | (61) Для разового и сортировки не надо :) | ||
Провинциальный 1сник 63 - 29.09.16 - 09:17 | (54) Как я помню по Вирту, самая лучшая сортировка - пирамидальная. В отличие от "быстрой" она не может выродиться в O(n*n) при неудачном наборе данных. | ||
DrZombi 64 - 29.09.16 - 09:45 | (63) Мне трудно говорить про Пирамидку.
Но Шейкерную я писал, в свое время... Сравнивал с пузырьками. ... Так сказать видел все в воочию :) | ||
DrZombi 65 - 29.09.16 - 09:47 | + Все дело было еще во времена Пней :) | ||
Повелитель 66 - 29.09.16 - 09:49 | (0) Мне однажды продавец в магазине попросили сдачу монетами по порядку выложить.
Если бы не знал методов сортировки, не смог бы. | ||
Torquader 67 - 29.09.16 - 09:55 | (66) Это не совсем сортировка - это заполнение массива данными с сортировкой. Хотя, чаще всего, проще сначала заполнить, а потом сортировать. | ||
Повелитель 68 - 29.09.16 - 10:06 | (67) Все я ушел бухать, жизнь прожита зря... | ||
Torquader 69 - 29.09.16 - 10:10 | (68) Когда поймёшь, что бухать - тоже зря - возвращайся, мы тут ещё чего-нить интересного вспомним. |
|
Список тем форума
|