Вход | Регистрация


Информационные технологии :: Математика и алгоритмы

Пригодился ли вам алгоритм сортировки?

Пригодился ли вам алгоритм сортировки?
Я
   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
(50) Шейкерная дает не хилый результат на Миллиардах.

И не совсем хороший на 100 ;)
   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) Когда поймёшь, что бухать - тоже зря - возвращайся, мы тут ещё чего-нить интересного вспомним.


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Тема не обновлялась длительное время, и была помечена как архивная. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.
Рекламное место пустует