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


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 или кнопку "Обновить" в браузере.
Рекламное место пустует