Имя: Пароль:
IT
 
Пригодился ли вам алгоритм сортировки?
0 breezee
 
26.09.16
15:13
Собственно, сабж. Лично мне не разу. Везде есть встроенные методы как, например "Сортировать()" в 1С.
1 Garykom
 
гуру
26.09.16
15:15
Уточни какой именно
2 Господин ПЖ
 
26.09.16
15:15
повод для гордости?
3 Flyd-s
 
26.09.16
15:16
Мне пригодился как-то. На собеседовании тестовое задание решил, правда туда все равно не пошел работать
4 Волшебник
 
модератор
26.09.16
15:16
Сортирую пузырьком и ниипёт
5 Garykom
 
гуру
26.09.16
15:20
6 Смотрящий
 
26.09.16
15:20
Бинарный поиск - вещь!
7 b_ru
 
26.09.16
15:20
Пригождалось для понимания того, какое место в коде оптимизировать и как.
Грубо говоря, можно не помнить как работает qsort, но знать что в 1С именно он, и знать его алгоритмическую сложность.
8 Торин
 
26.09.16
15:22
Когда-то оч.давно, в СССР-е, когда я, МНС в красноярском Институте Физики программно моделировал движение доменных стенок в тонких плёнках, почти вся программа сводилось к непрерывной пересортировке двумерных массивов. И да, замена алгоритма пузырька на шейкер-сортировку ускорила работу программки раз так в тридцать. Так что Вирту я очень благодарен.

А в 1С-ке ни разу не пригодилась...
9 Starhan
 
26.09.16
15:39
Да, я по нему и другим алгоритмам изучал алгоритмирование :)
10 Это_mike
 
26.09.16
15:53
(8) Да, Вирт (http://cv01.twirpx.net/0001/0001776.jpg) в свое время стал внезапным открытием. Когда писали ассемблер (или дизассемблер - уже не помню) - были поражены, насколько квиксорт быстрее "интуитивного" пузырька.
11 Jokero
 
26.09.16
15:56
А знание модели OSI, а способность рассчитать, сколько памяти требуется для n-цветного дисплея c количеством пикселей MxK?

Учат всегда не тому, что нужно в жизни...
12 oslokot
 
26.09.16
15:58
А мне очень пригождается Сортировать() таблицу значений, полученную например при чтении строк из файла. Ну а чем еще сортировать?
13 iceman2112
 
26.09.16
16:00
(0) эти задачки нужны были для построения алгоритмического мышления. ВАШ КЭП
14 Это_mike
 
26.09.16
16:06
(12) а можно не сортировать, а построить индекс, и выбирать по индексу...
15 oslokot
 
26.09.16
16:09
(14) можно, только зачем если есть готовый метод сортировки?
16 oslokot
 
26.09.16
16:11
разве что он вероятно, медленнее
17 Это_mike
 
26.09.16
16:11
(15) так индекс - это по сути та же сортировка, только без передвигания содержимого.
18 Михаил Козлов
 
26.09.16
16:15
(14) Самому построить индекс нужно уметь.
19 jsmith
 
26.09.16
16:15
Нет. Чтобы отсортировать тот же массив, можно использовать список значений.
20 oslokot
 
26.09.16
16:15
(17) это да, но если ТЗ это реквизит ТП, то проще сортировать() ее перед выводом на форму
21 NorthWind
 
26.09.16
18:56
(0) пригодился бинарный поиск, когда понадобилось ускорить формирование таблицы 1.5 в книге учета по ОСНО 1С:Предприниматель (для 7.7). В 2004 году.
22 WebberNSK
 
26.09.16
20:58
в 1С эффективней использовать функции платформы сортировки
для не стандартных случаев в типовых пишут "свои" сортировки
23 Torquader
 
26.09.16
21:02
(10) Там ещё метод быстрой перестановки был - который очень даже хорошо сортирует.
Только сама сортировка не спасает - нужно ещё и упорядочивание хранить как-то, чтобы объекты в памяти не переставлять.
24 ovrfox
 
28.09.16
17:17
Сортировки - нет, а вот поиск в отсортированном - да.
А в 1С всегда достаточно встроенной сортировки.
25 Кирпич
 
28.09.16
17:35
а как же. на собеседование без пузырька еще ни разу не обошлось.
26 scanduta
 
28.09.16
17:52
Нет никогда.
27 Torquader
 
28.09.16
17:52
(25) А вот интересно - вопрошающе про метод перестановок рассказать сами смогут или им википедия понадобится ?
28 PLUT
 
28.09.16
18:42
(27) нет ничего проще "пузырька". даже википедия вопрошающим не нужна
29 Garykom
 
гуру
28.09.16
19:18
Кстати а какой лучший алгоритм десортировки?

Чтобы в отсортированных данных навел полный бардак, так чтобы отсортировать заняло дофига времени?

Причем очень быстро это сделал и качественно! Примерно как перетасовка карточной колоды.
30 Loky9
 
28.09.16
19:20
(29) Сначала нужно знать как будут сортировать.
31 Garykom
 
гуру
28.09.16
19:23
(30) Хорошо лучший для каждого из известных/популярных как будут сортировать и в среднем по всем
32 ERWINS
 
28.09.16
19:31
(29) смотря какой алгоритм сортировки
насколько я помню быструю сортировку убивал напрочь если выбраемый элемент есть мнмальный
если выбираемый первый, то отсортированный массив будет сортироваться дольше всего
если центральный, но ставим в центр минимальный, а остальные по возрастанию добавляем справа и слева.
33 ERWINS
 
28.09.16
19:33
сортировке слияниями пофиг, она не зависит от порядка.
сортировке вставками если используется список, то по возрастанию самое страшное.
34 NorthWind
 
28.09.16
21:34
Кстати, вот чисто случайно наткнулся на наглядный пример того, как понимание алгоритмов позволяет существенно оптимизировать специфическую выборку данных по скорости:
http://catalog.mista.ru/public/551583/
35 Garykom
 
гуру
28.09.16
21:44
(34) Илдарович товарищ конечно умный, но иногда слишком заумно решает проблему которая имеет намного более простое решение.

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

В результате поиск нужных исходных интервалов (записей) по искомой позиции будет банальным, путем одного индекса (неважно слева или справа) для нашей таблицы индексов.
36 Гобсек
 
28.09.16
22:31
Вспомнилась газетная статья из тех времен, когда появились первые калькуляторы. В статье обсуждался вопрос, нужно ли современному школьнику знать таблицу умножения и умение считать в столбик. ИМХО - нужно. И об алгоритмах сортировки программист представление тоже должен иметь.
37 Franchiser
 
гуру
28.09.16
22:36
Пригодился при поступлении в институт)
38 Torquader
 
28.09.16
22:38
(36) Лучше ещё и о хранении данных подумать, так как сама по себе сортировка - ничего не решает, особенно, если в набор данных будут добавления или удаления.
Там уже будут немного другие слова об оптимальности.
39 Jump
 
29.09.16
04:59
(0)Программист - понятие широкое.
Большая часть современных программистов работает с фреймворками.
Т.е это не чисто программирование, а больше конфигурирование фремворка.
Это и 1с, и вся веб-разработка, и создание оконных приложений в большинстве своем.
И любые задачи надо решать встроенными в фреймворк методами.
Если ты использовал самописный алгоритм - это gовнокод, велосипедостроение, в общем - вон из профессии.
Тут ценится скорость разработки, и понятность коду, а не быстродействие и эффективное использование ресурсов.
Это не плохо, не хорошо, просто так есть.

А алгоритмы, в том числе и сортировки нужны при низкоуровневом программировании, без их знания там будет трудно.
40 Провинциальный 1сник
 
29.09.16
05:48
(39) Даже прикладнику надо знать о порядке быстродействия и потребности в памяти используемых алгоритмов, чтобы не написать код, который умрет при определенном объеме данных. Типичный пример такой ситуации - сохранение большого количества строк с автовысотой в xls из 7.7. Так что, считаю, программист в любом случае должен знать об сортировках, двоичных и прочих деревьях и вообще о всём что написано у Вирта. Это как сопромат для инженера-строителя.
41 Лодырь
 
29.09.16
05:56
Да пригодился. Особенно пригодились внешние методы сортировки. А так же всякая мелочевка типа решающих деревьев и т.д.
42 Jump
 
29.09.16
06:37
(40) Не факт.
Работая с фреймворком довольно трудно предсказать потребность в памяти и эффективность работы алгоритма, через несколько уровней абстракции.
43 Провинциальный 1сник
 
29.09.16
06:43
(42) Приходится доверять разработчикам фреймворка, да. Предполагать, что они используют максимально оптимальные алгоритмы и методы. В точности так же, как строитель не отправляет каждый куль цемента на лабораторное исследование, доверяя указанной марке.
44 Sammo
 
29.09.16
06:48
Была пару раз ситуация, когда сортировал своими методами.
Из забавного - как-то использовал метод ветвей и границ
45 Emery
 
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-файлов.

Думаю, что я еще вернусь к этим исследованиям и разработкам в дальнейшем.
46 DrZombi
 
гуру
29.09.16
07:57
(4) Пузырек не самый быстрый метод ;)
47 DrZombi
 
гуру
29.09.16
08:03
(0)Держи Шейкерную сортировку, на больших объемах работает быстрее пузырьков :)

https://ru.wikipedia.org/wiki/Сортировка_перемешиванием

А вообще, вот тут почитай...
https://ru.wikipedia.org/wiki/Алгоритм_сортировки
48 NorthWind
 
29.09.16
08:03
(42) Ну и соответственно когда штатное перестает работать, дело все равно кончается велосипедами, чтобы хоть как-то решить задачу. На практике я бы не возводил ничего в абсолют, в том числе и механизмы фреймворков. Главое - решить поставленный вопрос, а уж как - это проблемы программиста. Если решил плохо - авось другие перерешают или сам со временем.
49 Jump
 
29.09.16
08:06
(48) Ну не всегда так.
Если проект большой, а ты на своем участке сделал костыль нештатными методами - при следующем же релизе это вылезет, и все придется переписывать.

Если ты целиком контролируешь проект тогда можно.
50 Jump
 
29.09.16
08:14
(46) Вообще быстрота не единственный и не всегда главный показатель. Есть еще такие вещи как потребляемая память.

Ну и опять же быстрый на каком объеме данных. Разные алгоритмы работают с разной эффективностью в зависимости от размера.
Так что надо учитывать сколько элементов - 100 или 100миллиардов.
51 Это_mike
 
29.09.16
08:16
(48) А как же "использовать только методы, освященные Нуралиевым, и записанные в священных ЖКК и ЖЖК"? :-)
52 DrZombi
 
гуру
29.09.16
08:19
(50) Ага, скорость не важна, можно и подождать день другой :DDD
53 jsmith
 
29.09.16
08:20
Вы не попутали мисту с хаброй?
54 DrZombi
 
гуру
29.09.16
08:20
(50) Шейкерная дает не хилый результат на Миллиардах.

И не совсем хороший на 100 ;)
55 jsmith
 
29.09.16
08:20
Тут серьезными проектами занимаются, а сортировки и прочие досуги нердов обсуждают там.
56 Это_mike
 
29.09.16
08:21
(52) если задача разовая - можно за час написать, и пусть хоть два дня считает.
если задача ежедневная для 100 юзверей - то лишняя минута работы алгоритма в день будет ежемесячно обходиться компании в четверть средней зарплаты.
57 DrZombi
 
гуру
29.09.16
08:22
(55) Да бросьте, народ кроме пузырька не чего не знает :)
58 Это_mike
 
29.09.16
08:23
(54) если эти "милллиарды" влезут в память с произвольным доступом.
59 DrZombi
 
гуру
29.09.16
08:23
(56) Нет нечего постоянней, чем временное :)
60 Jump
 
29.09.16
08:24
(52) Я же говорю не всегда важна.
Кроме скорости есть потребление памяти.

Например выбрал ты алгоритм который работает в два раза быстрее, но потребляет в два раза больше памяти.
На реальной задаче у тебя памяти банально не хватает, комп уходит в подкачку, и в результате твой быстрый алгоритм работает в сто раз медленнее. Хоть и быстрый.
61 Это_mike
 
29.09.16
08:24
(59) не "временное", а "разовое". там выходят на повестку совсем другие критерии.
62 DrZombi
 
гуру
29.09.16
08:27
(61) Для разового и сортировки не надо :)
63 Провинциальный 1сник
 
29.09.16
09:17
(54) Как я помню по Вирту, самая лучшая сортировка - пирамидальная. В отличие от "быстрой" она не может выродиться в O(n*n) при неудачном наборе данных.
64 DrZombi
 
гуру
29.09.16
09:45
(63) Мне трудно говорить про Пирамидку.
Но Шейкерную я писал, в свое время... Сравнивал с пузырьками.

...
Так сказать видел все в воочию :)
65 DrZombi
 
гуру
29.09.16
09:47
+ Все дело было еще во времена Пней :)
66 Повелитель
 
29.09.16
09:49
(0) Мне однажды продавец в магазине попросили сдачу монетами по порядку выложить.
Если бы не знал методов сортировки, не смог бы.
67 Torquader
 
29.09.16
09:55
(66) Это не совсем сортировка - это заполнение массива данными с сортировкой. Хотя, чаще всего, проще сначала заполнить, а потом сортировать.
68 Повелитель
 
29.09.16
10:06
(67) Все я ушел бухать, жизнь прожита зря...
69 Torquader
 
29.09.16
10:10
(68) Когда поймёшь, что бухать - тоже зря - возвращайся, мы тут ещё чего-нить интересного вспомним.
Компьютеры — это как велосипед. Только для нашего сознания. Стив Джобс