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


1С:Предприятие ::

Метки: 

Сортировка слиянием

Я
   vi0
 
10.07.18 - 16:50
Предлагаю вспомнить вузовскую программу - сортировка слиянием через рекурсию. У кого какая есть критика, мысли - прошу высказываться
Функция mergeSort(A)
    
    n = A.Количество();
    
    if n = 1 Тогда
        return A 
    КонецЕсли;
    
    middle = Цел(n/2);
    
    leftHalf = ЧастьМассива(A, 0, middle-1);
    rightHalf = ЧастьМассива(A, middle, n-1);
    
    L = mergeSort(leftHalf);  // разбиваем еще раз

    R = mergeSort(rightHalf);//

    
    
    return merge(L, R);// сортировка слиянием

    
КонецФункции

function merge(A, B)
    
    // дошли нижнего уровня рекурсии

    if not ЗначениеЗаполнено(A) then
        return B;
    endif;
    
    if not ЗначениеЗаполнено(B) then
        return A;
    endif;
    
    
    An = A.Количество()-1;
    Bn = B.Количество()-1;
    
    if A[0] < B[0] then
        m = merge(ЧастьМассива(A,1,An), B);
        return concat(A[0], m); 
    else
        m = merge(A, ЧастьМассива(B,1,Bn));
        return concat(B[0], m);
    endif
    
КонецФункции 

Функция concat(Значение, Массив)
    
    Результат = Массив;
    Результат.Вставить(0, Значение);
    
    возврат Результат;
    
КонецФункции

Функция ЧастьМассива(Массив, ИндексПервого, ИндексПоследнего)
    
    результат = Новый Массив;
    
    Для сч=ИндексПервого по ИндексПоследнего Цикл
        результат.Добавить(Массив[сч]);
    КонецЦикла;
    
    
    Возврат результат;
    
КонецФункции

Процедура Пример()
    
    A = new Array;
    A.Добавить(6);
    A.Добавить(5);
    A.Добавить(3);
    A.Добавить(1);
    A.Добавить(8);
    A.Добавить(7);
    A.Добавить(2);
    A.Добавить(4);
    
    
    A_сорт = mergeSort(A);
    Для каждого элемент Из A_сорт Цикл
        Сообщить(элемент);
    КонецЦикла;
    
КонецПроцедуры
 
 
   vi0
 
1 - 10.07.18 - 16:54
   МихаилМ
 
2 - 10.07.18 - 17:23
цель какая ?
   vi0
 
3 - 11.07.18 - 03:58
Погружаюсь в алгоритмику
интересна обратная связь от сообщества
   МихаилМ
 
4 - 11.07.18 - 04:09
для 1с алгоритм медленный, тк требует создания копий данных
   vi0
 
5 - 11.07.18 - 04:13
(4) это сам алгоритм такой, что требует копий данных и требовательный к памяти
   vi0
 
6 - 11.07.18 - 04:14
1с использую здесь просто как платформу для обучения
понимаю, что встроенные в платформу сортировки могут быть быстрее
   VladZ
 
7 - 11.07.18 - 05:55
(0) Критикую:

Пиши на одном языке. Выбрал русский - пиши по-русски. Хочешь на буржуйском - пиши на буржуйском. Но не стоит прыгать туда-сюда. Привыкай делать сразу правильно. Разработчики, которые будут сопровождать твой код, проклянут тебя и предадут анафеме.
   VladZ
 
8 - 11.07.18 - 06:14
+7 По поводу самой сортировки: программисту 1с это не нужно. Предлагаю не забивать голову ненужным хламом.

Шерлок Холмс: ...Ватсон, поймите: человеческий мозг — это пустой чердак, куда можно набить всё, что угодно. Дурак так и делает: тащит туда нужное и ненужное. И наконец наступает момент, когда самую необходимую вещь туда уже не запихнёшь. Или она запрятана так далеко, что ее не достанешь. Я же делаю всё по-другому. В моём чердаке только необходимые мне инструменты. Их много, но они в идеальном порядке и всегда под рукой. А лишнего хлама мне не нужно.
   Emery
 
9 - 11.07.18 - 06:22
(0) > сортировка слиянием через рекурсию. У кого какая есть критика, мысли - прошу высказываться

На эту тему есть статья: «Рабочий алгоритм на С++ внешней сортировки «естественным слиянием» (Natural Merge Sort) с неубывающими и убывающими упорядоченными подпоследовательностями», в которой описан алгоритм имени моего имени :) http://emery-emerald.narod.ru/Cpp/2E1562.html .
   vi0
 
10 - 11.07.18 - 06:50
(9) посмотрю
 
 Рекламное место пустует
   vi0
 
11 - 11.07.18 - 06:50
(7) критика больше интересна по сути
   vi0
 
12 - 11.07.18 - 06:53
(8) ты считаешь что алгоритмическое мышление одинеснику не нужно?
   Cyberhawk
 
13 - 11.07.18 - 07:29
Латиница в коде 1С - УГ
   VladZ
 
14 - 11.07.18 - 07:34
(12) Любой программист должен "думать алгоритмами".  Я говорил про то, что 1с-нику не нужны сортировки.
   WhiteDragon93
 
15 - 11.07.18 - 09:02
(0) чисто из интереса: что происходит в голове при написании такого кода?

if n = 1 Тогда
  return A 
КонецЕсли;


Говнокод или обфускация?
   МимохожийОднако
 
16 - 11.07.18 - 09:07
(15) Может быть,  в пятницу открыть голосовалку? ))
   vi0
 
17 - 11.07.18 - 09:19
Ребят, вяло
Активнее и больше по теме
   ERWINS
 
18 - 11.07.18 - 09:26
Зачем?
   Митяйский
 
19 - 11.07.18 - 09:50
(0) Мердж в рекурсии, написанный на 1с - гвно гвняное, просто кошмар. Я сам это обнаружил где-то с полгода назад, когда так же, как ты заморочился с вузовской теорией.

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

И сравни их время работы по отладчику. Можешь еще прикрутить счетчики количества сравнений и перезаписей, если очень уж хочется.
   vi0
 
20 - 11.07.18 - 10:03
(19) > Мердж в рекурсии, написанный на 1с - гвно гвняное, просто кошмар
Соглашусь. Сам это понял, когда писал
   vi0
 
21 - 11.07.18 - 10:05
(14) этой темы коснулся только в контексте сложности алгоритма  n*log(n)
https://habr.com/post/196226/
   vi0
 
22 - 11.07.18 - 15:24
(15) взял код из статьи и дописал русскими конструкциями
   МихаилМ
 
23 - 11.07.18 - 21:42
(22)  "взял код из статьи" - подход школьника.
я так делал в 7-8 классе.  на 1  курсе работал программистом-стажером в 92 году. сразу сказали -бред:

берешь библиотеки и из них используешь.

на лекции и семинары про сортировки я не ходил. все это было описано до х86.
   NSSerg
 
24 - 11.07.18 - 22:07
(23) Если в рабочем проекте - то да. А если хочешь поднять свой скилл в алгоритмике - то без попыток реализовать в том числе и простейшие методы - уровень не поднимешь.
В 89-ом году, на сборах на союз (10-11 класс, победители финала чемпионата Ленинграда)  в том числе писали и сортировку фон-Нейманом, и другие тривиальные методы в качестве подготовки.
Если писал фон-Неймана в 80-ые годы в 7-8 классе - то по тем временам это просто зашеаливающий уровень.
   NSSerg
 
25 - 11.07.18 - 22:10
(23) виноват, не так проситал.
   NSSerg
 
26 - 11.07.18 - 22:11
(25) *прочитал :)
   МихаилМ
 
27 - 11.07.18 - 22:21
(24)тут важен подход. как исследовательский так и практический. просто к какому-то моменту у прога должна появляться  библиотека наработок. которая пополняется из библиотеки экспериментов и чужих наработок .

соответственно процесс постоянный. конечно "открытия" возможны на всех уровнях и даже школьном.
   NSSerg
 
28 - 11.07.18 - 22:30
(27) Смысл изучения алгоритмов ведь не в том чтоб знать их, всё есть в библиотеках, а в том чтоб научиться  придумывать  эффективные алгоритмы в нестандартных ситуациях, и чтоб знать что у задачи есть такие решения. Иначе увидев задачу можно и не понять, что для неё есть готовые алгоритмы. Можно привести пример задачи о рюкзаке. На форуме ветки по ней возникают с завидной периодичностью, и если бы вопрошающие знали хотя бы название задачи, то смогли бы нагуглить всяких алгоритмов. А когда ты знаешь условие, но не знаешь названия - нагуглить что-либо очень проблематично, и начинается изобретение велосипеда.
   МихаилМ
 
29 - 11.07.18 - 22:33
библиотек алгоритмов с исходниками на других языках на порядки больше тк у студентов лабы не на 1с.

и прочие алгоритмы тоже появляются не на 1с.

и адаптация к 1с - спец тема ввиду заточенности 1с для других задач.
   едолюб
 
30 - 11.07.18 - 22:35
(28) >На форуме ветки по ней возникают с завидной периодичностью

пруф?
   NSSerg
 
31 - 11.07.18 - 22:36
(30) набери в поиске гугли
задача о рюкзаке site:forum.mista.ru
   NSSerg
 
32 - 11.07.18 - 22:36
   МихаилМ
 
33 - 11.07.18 - 22:39
(28) на  этом форуме про рюкзак кроме Вас и козлова.

никто не отвечает.

те можно плавно перейти к теме программист 1с - не программист.

я хочу сделать акцент на выборе инструмента для прокачки темы алгоритмики в программировании. и бесмысленности  портирования в 1с.
 
 
   NSSerg
 
34 - 11.07.18 - 22:50
(33)  Учитывая что большая часть веток на мисте - это вопросы по решению простых алгоритмических задач, а учитывая что эти ветки иногда висят без решения непозволительно долго, ИМХО для многих 1Сников было бы не лишним поизучать алгоритму.
Если твой основной инструмент 1С - то почему бы не писать решения простых алгоритмических задач в качестве тренировки на 1С? Хотя, опять-таки ИМХО, лучше выучить еще какой язык, чтоб решать эти задачи на сайтах с автоматической проверкой решения.
   vi0
 
35 - 12.07.18 - 05:05
(34) все верно
Сейчас один из вопросов у меня - найти хороший сборник задач по алгоритмам
   vi0
 
36 - 12.07.18 - 05:13
(34) > чтоб решать эти задачи на сайтах с автоматической проверкой решения.
Какие хорошие сайты есть?
   vi0
 
37 - 12.07.18 - 09:54
(33) > и бесмысленности  портирования в 1с
да хоть на псевдокоде
   Timon1405
 
38 - 12.07.18 - 10:00
   NSSerg
 
39 - 12.07.18 - 11:25
(35) codeforces.ru
На нем все, начиная с начинающих до профи.
Регистрируешься, заходишь в Архив, сортируешь задачи по количеству решивших, и начинаешь решать начиная с самых простых. То есть с тех которые решили больше народу.
http://codeforces.com/problemset?order=BY_SOLVED_DESC
   NSSerg
 
40 - 12.07.18 - 11:27
https://informatics.msk.ru/moodle/
Вот тут попроще.
   vi0
 
41 - 13.07.18 - 03:59
Спасибо всем за рекомендации



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