Реализуем Стек, Очередь и Приоритетную очередь в 1С

57 Comments

1. ArchLord42 24.06.2019 at 13:20

   Попытка
   Значение = Стек[ИндексПоследнегоЭлемента];
   Стек.Удалить(ИндексПоследнегоЭлемента);
   Возврат Значение;
   Исключение
   Возврат Неопределено;
   КонецПопытки;
   

   Показать

   тут (и в других методах) не так сложно проверить количество элементов в массиве, зачем все эти попытки исключения ? code smells в общем

   Reply ↓
2. vadim1011985 24.06.2019 at 13:44

   (2) При желании можно найти применение , например с помощью стека проверяют соответствие открывающихся и закрывающихся скобок (или тех же кавычек) в выражениях. В любом случае это полезные структуры

   Reply ↓
3. boln 24.06.2019 at 13:47

   (2)

   не понятно, что делать с этим кодом в практическом плане.
   
   возможно его стоит предложить старшему воспитателю группы детского сада

   Я, например, использую стек для организации последовательности завершения вложенных асинхронных процедур:
   
   https://www.1c-uc3.ru/modal.html

   Reply ↓
4. VmvLer 24.06.2019 at 13:56

   (4) я имел ввиду

   этот код

   , то что многие используют подобные алгоритмы я не сомневаюсь.

   Reply ↓
5. RonX01 24.06.2019 at 13:57

   (1) Страсть как захотелось использовать здесь попытку вместо условия. Кому code smells используйте так:
   

   Если Стек_Пустой(Стек) Тогда
   Возврат Неопределено;
   Иначе
   ИндексПоследнегоЭлемента = Стек.ВГраница();
   Значение = Стек[ИндексПоследнегоЭлемента];
   Стек.Удалить(ИндексПоследнегоЭлемента);
   Возврат Значение;
   КонецЕсли;
   

   Показать

   Reply ↓
6. TODD22 24.06.2019 at 14:16

   (6)

   Страсть как захотелось использовать здесь попытку вместо условия.

   В 1С не рекомендуется в общем случае перехватывать исключения.

   Reply ↓
7. RonX01 24.06.2019 at 14:27

   (7) Не знал, спасибо. Теперь страсть свою поумерю.

   Reply ↓
8. for_sale 24.06.2019 at 17:19

   (6)
   
   Страсть чем-то объясняется или просто «страсть»?)

   Ещё момент — Неопределено теоретически может быть правильным значением элемента. Т.е. Неопределено и «Такого элемента не существует» будут разными случаями.

   Reply ↓
9. acsent 24.06.2019 at 18:20

   а если сделать раелизацию на списке.
   
   те на структуре, где один из элементов — другая структура?

   Reply ↓
10. MikeI 24.06.2019 at 20:37

    (6)Дурацкий вопрос: Если заменить Стек.ВГраница(), на Стек.Количество()-1. Шустрее не будет?

    Или вообще не использовать метод Количество() для подсчета элементов в очереди, а Один раз посчитать, а потом уменьшать это число на единицу

    Reply ↓
11. RonX01 24.06.2019 at 20:38

    (9) Я думал по поводу Неопределено, можно возвращать NULL, но это также теоретически может быть правильным значением.
    
    Вообще эти структуры данных используют программисты, а не пользователи, поэтому мне кажется, что проверки на пустую структуру данных внутри методов _Получить() излишни. Для проверки предполагается использовать метод _Пустой(), который возвращает вполне себе однозначный ответ 🙂

    Здесь «страсть» объясняется тем, что с одной стороны мне не нравится проверка на пустую структуру данных внутри методов, а с другой стороны нужно предусмотреть появление ошибки, не нагромаждая код. Хотелось сделать как можно меньше кода.

    Reply ↓
12. for_sale 24.06.2019 at 20:40

    (12)

    Я думал по поводу Неопределено, можно возвращать NULL, но это также теоретически может быть правильным значением.

    Я думаю, тут можно просто разделить сущности. Т.е. возвращаемое значение — это возвращаемое значение, а сама функция возвращает (или устанавливает переданный) флаг того, что что-то было найдено или ничего не было найдено.

    Reply ↓
13. RonX01 24.06.2019 at 20:45

    (11) Вопрос, кстати не дурацкий, я им сам задавался :). Стек.Количество()-1 будет медленней.

    Reply ↓
14. MikeI 24.06.2019 at 20:47

    (14)тогда в методах Пустая нужно использовать Стек.Вграница()+1

    Reply ↓
15. MikeI 24.06.2019 at 20:49

    (15)Но ИМХО , когда в 1С стали приходить true программеры с ООП, то стало конфы стали тормознее, заморочитей, менее логичны и сложны для отладки. ))))

    Reply ↓
16. RonX01 24.06.2019 at 20:55

    (15) Стек.Количество() = 0; будет работать чуть-чуть быстрее нежели Стек.ВГраница() = -1; Почему-то

    Reply ↓
17. RonX01 24.06.2019 at 21:03

    (16) Согласен. с ООП тоже есть проблемы, и часто всё превращается в лапшу.
    
    Поэтому «Простота требует проектирования и хорошего вкуса» Линус Торвальдс.

    Reply ↓
18. RonX01 24.06.2019 at 21:04

    (13) Как бы вы реализовали?

    Reply ↓
19. RonX01 24.06.2019 at 21:11

    (10) Тогда необходимо подумать что будет ключами структуры? И для получения первого элемента необходимо вызывать конструкцию типа Для каждого Из Цикл. Мне кажется это будет затратно по времени, но надо тестить.

    Reply ↓
20. for_sale 24.06.2019 at 21:14

    Перенёс ответ ниже

    Reply ↓
21. for_sale 24.06.2019 at 21:15

    (19)
    

    Функция Стек_ВзятьБезУдаления(Стек, Значение)
    
    Если _СтекПустой() Тогда
    Возврат Ложь;
    Иначе
    Значение = Стек[ИндексПоследнегоЭлемента];
    Возврат Истина;
    КонецЕсли;
    КонецФункции
    
    Значение = «»;
    Если Стек_ВзятьБезУдаления(Стек, Значение) Тогда
    // значение можно использовать
    Иначе
    // ничё нет
    КонецЕсли;

    Показать

    Или наоборот:

    Функция Стек_ВзятьБезУдаления(Стек, ЕстьЗначение = Истина)
    
    Если _СтекПустой() Тогда
    ЕстьЗначение = Ложь;
    Иначе
    ЕстьЗначение = Истина;
    Возврат  Стек[ИндексПоследнегоЭлемента];
    КонецЕсли;
    КонецФункции
    
    // если у меня могут быть Неопределено как значения, тогда
    ЕстьЗнч = Ложь;
    Если Стек_Взять(Стек, ЕстьЗнч) Тогда
    КонецЕсли;
    
    // если немогут или неважно
    Знч = Стек_Взять(Стек);

    Показать

    Reply ↓
22. RonX01 24.06.2019 at 21:23

    (22) Понял, получается 2 в одном. Почему бы и нет.

    Reply ↓
23. leemuar 25.06.2019 at 01:11

    (23) попытка получить значение из пустой коллекции всегда должна бросать исключение. Любое значение встроенного языка может храниться в коллекции, поэтому не допустимо использовать «особое» возвращаемое значение как признак невозможности получения жначения

    для проверки стека и организации цикла стеку необходим метод, возвращающий количество элементов в нем:

    Пока Стек.Количество() > 0 Цикл
    //
    КонецЦикла
    
    Пока Не Стек.Пустой() > 0 Цикл
    //
    КонецЦикла
    

    Показать

    p.s. Подумайте на досуге, а так ли нужна вообще операция получения без удаления (peek)? Когда вы ею последний раз пользовались и зачем?

    Reply ↓
24. kuzyara 25.06.2019 at 06:23

    (6)

    code smells

    Guard clauses
    
    мб так?

        Если Стек_Пустой(Стек) Тогда
    Возврат Неопределено;
    КонецЕсли;
    ИндексПоследнегоЭлемента = Стек.ВГраница();
    Значение = Стек[ИндексПоследнегоЭлемента];
    Стек.Удалить(ИндексПоследнегоЭлемента);
    Возврат Значение;
    

    https://softwareengineering.stackexchange.com/questions/350472/developer-insists-if-statements-shouldnt-have-negated-conditions-and-should-al

    Reply ↓
25. RonX01 25.06.2019 at 07:09

    (25) Спасибо за ссылки

    Reply ↓
26. RonX01 25.06.2019 at 07:29

    (24) Совсем недавно использовал операцию без удаления из приоритетной очереди. Необходимо было найти вершину графа, которая ближе всех расположена к углу (по оси х и у). Обход вершин графа с правильным вычислением приоритетов дал результат и вконце требовалось только получить один элемент с наивысшим приоритетом. Поэтому использовал получить без удаления, хотя мог использовать и с удалением. Выигрыш конечно микро секунды, но все же.
    
    Думаю могут быть ситуации, когда это будет полезно.

    Reply ↓
27. Scorpion4eg 25.06.2019 at 07:54

    Хорошая статья. Твою бы статью, да когда я LRU кэш организовывал…
    
    Получилась очень сложная конструкция из таблицы значение, соответствия и пары параметров. Зато без проблем кэширую http запросы с контролем памяти.

    Reply ↓
28. RonX01 25.06.2019 at 08:54

    (28) Спасибо. LRU это круто.

    Reply ↓
29. herfis 25.06.2019 at 09:06

    priority queue — моя любимая структура данных по изяществу и эффективности.
    
    К сожалению, в 1С возможно реализовать лишь модели такого рода структур. Вся прелесть эффективности их реализации недоступна в 1С.

    Reply ↓
30. RonX01 25.06.2019 at 10:01

    (31) Вначале статьи я указал, что буду использовать готовые типы данных 1с. Как бы намекая на то, что не буду пытаться реализовывать кучи для приоритетной очереди :). Хотя мне очень интересно посмотреть реализацию «по классике» в 1с.

    Reply ↓
31. herfis 25.06.2019 at 10:26

    (32) На массиве делается вполне аутентично. Но вот эффективность может хромать вследствие тормознутости 1С как скриптового языка (вполне может оказаться, что использование библиотечной сортировки на больших коллекциях более эффективно, чем «ручные» операции на массиве, несмотря на O(log N)).

    Reply ↓
32. herfis 25.06.2019 at 10:30

    (32) Вот тут глянь в самом начале: http://ti.math.msu.su/wiki/lib/exe/fetch.php?media=algo:algo-13.pdf
    
    Там все очень просто и красиво.

    Reply ↓
33. RonX01 25.06.2019 at 11:14

    (34) Спасибо

    Reply ↓
34. comol 25.06.2019 at 15:26

    Ну спасибо! Теперь вопросы на собеседования новые выдумывать 🙁

    Reply ↓
35. acsent 25.06.2019 at 18:12

    (20) ссылку на последний можно хранить в первом.
    
    Если эта куча то вообще ни чего этого не нужно

    Reply ↓
36. ltfriend 25.06.2019 at 19:43

    (22) Лучше ни каких проверок не делать. Пусть возникает исключение, а программист должен сам его обрабатывать на своё усмотрение. Тогда получиться так:
    

    Функция Стек_ВзятьБезУдаления(Стек)
    
    Возврат Стек[ИндексПоследнегоЭлемента];
    
    КонецФункции
    
    Попытка
    Значение = Стек_ВзятьБезУдаления(Стек)
    Исключение
    // Обработка по своим требованиям
    КонецПопытки;
    

    Показать

    Reply ↓
37. for_sale 25.06.2019 at 20:23

    (40)
    
    Кому лучше?
    
    Тем более, мы рассматриваем ситуацию, когда Неопределено может быть значением. У вас, по-моему, другая ситуация описывается.

    Reply ↓
38. RonX01 26.06.2019 at 06:02

    (40) Я уже убрал в статье какие либо проверки. В данном случае считается, что программист сам решает как ему обработать исключение, либо вообще не допустит такой ситуации. Есть функция Пустой()

    Reply ↓
39. RonX01 26.06.2019 at 06:09

    (36) Огромное спасибо за реализацию. Одно дело понимать теорию, а другое реализовать, да еще и в 1с 🙂

    Reply ↓
40. herfis 26.06.2019 at 09:36

    (43) Не за что. Самому было интересно 🙂 Я практически один к одному передрал ключевые моменты принстонской реализации https://algs4.cs.princeton.edu/24pq/MaxPQ.java.html из их книжки по алгоритмам.

    Reply ↓
41. Alias 26.06.2019 at 16:33

    (46)
    
    >»Всплытие» и «погружение» элементов происходит именно «по дереву», между дочерними и родительскими элементами.
    
    Ну что ж, попробую разобраться повнимательнее — в механизме отображения дерева на массив… возможно, будет интересно. А то когда я вижу в коде Цел(ИндексЭлемента/2), я вижу обычное половинное деление, даже если назвать переменную ИндексРодительскогоЭлемента 🙂 в дереве всё же наполнение веток может быть сильно неравномерным, да и связи где-то должны храниться (или хотя бы неизменно определяться). А тут мы всё время середину интервала берём.
    
    Но мой код всё равно короче и в общем быстрее 🙂

    Reply ↓
42. herfis 26.06.2019 at 18:01

    (47) Здесь не середина интервала берется. Здесь вычисляется адрес дочерних/родительских элементов умножением/делением на 2. Проще всего разобраться с бумажкой и ручкой. 1 2 3 — 2 и 3 это листья 1. 1 2 3 4 5 6 7 — 4 и 5 — это листья 2, а 6 и 7 — это листья у 3 и так далее.
    

    Но мой код всё равно короче и в общем быстрее 🙂

    Нашли чем хвастаться 🙂 А если использовать встроенную сортировку списка значений, то может получиться еще быстрее чем половинным делением на определенном размере очереди.
    
    1С — это тормознутый скриптовый язык без низкоуровневых примитивов. Оптимизация на нем как правило упирается не в знание базовых алгоритмов, а в эффективное использование библиотечного функционала.
    
    Даже массив в 1С — это достаточно высокоуровневая динамическая структура данных под капотом. Оригинальный алгоритм priority queue строится поверх неизменяемых массивов (фактически просто непрерывных кусков памяти) и оптимизирован под минимальное количество перестановок и копирований. Реализовывать ее с помощью динамического массива — это уже смешно. Эти алгоритмы и структуры данных как раз и составляют «потроха» реализации библиотечной функциональности высокоуровневых языков.

    Reply ↓
43. RonX01 27.06.2019 at 06:43

    (45) Вот здесь в пункте 4 «Массив и двоичное дерево» можете более детально посмотреть как на массиве отобразить двоичное дерево

    Reply ↓
44. Jimbo 27.06.2019 at 12:45

    Зачем вот это вот всё ? А если на С написать тоже подобное или С++ с шаблонами STL, где всё это уже реализовано и позасекать время?

    Reply ↓
45. ValeriVP 27.06.2019 at 14:54

    (3)

    соответствие открывающихся и закрывающихся скобок (или тех же кавычек)

    это легче проверить по количеству символов — четность для кавычек, равенство для скобок

    Reply ↓
46. vadim1011985 27.06.2019 at 15:23

    (51) ((([(((([)))))

    Reply ↓
47. vadim1011985 27.06.2019 at 15:25

    (51) В приведенном примере количество скобок четное , но для [ нет закрывающей скобки , так что по количеству не проверишь

    Reply ↓
48. ValeriVP 27.06.2019 at 16:55

    (53) странный пример
    
    ((([(((([)))))
    
    ((((((( 7
    
    [[ 2
    
    ))))) 5

    7 <> 5 для ()
    
    2 <> 0 для []
    
    т.е. по количеству проверяется элементарно

    Другое дело, что со строкой типа ([)] есть некоторые проблемы. Но все то же самое — считаем количество квадратных скобок между круглых скобок — получаем не сходимость.

    Reply ↓
49. vadim1011985 27.06.2019 at 18:11

    (54) Со стеком проще гораздо , просто если будут [({)]} т.е. 3 вида скобок как тогда измениться ваш способ ? А при стеке — изменения минимальный. Поэтому стек в данном случае удобнее

    Reply ↓
50. RonX01 28.06.2019 at 06:33

    (54) Со стеком это решается так — кладем в стек только открывающие скобки, а когда встречается закрывающая, то берем из стека и смотрим соответствие вида скобки.
    
    Вконце стек должен быть пустым, т.е. в стеке не должно остаться открывающих скобок. Так же, если встречается закрывающая скобка, а стек пустой, то тоже ошибка.
    
    Мне кажется здесь проще и надежнее использовать стек, нежели подсчет скобок.

    Reply ↓
51. ValeriVP 28.06.2019 at 10:23

    (56)а кавычки? Когда класть и забирать?
    
    Я решал задачу разбора файлов 1С с фигурными скобками и кавычками — решение получилось без стека.

    Т.о. практического применения описанных механизмов не понимаю, хотя и не отрицаю возможность применения.
    
    Но как я уже говорил — это частные задачи и они требуют индивидуального подхода.

    Reply ↓
52. ValeriVP 28.06.2019 at 13:03

    (55) я задачу разбора такой строки решал бы рекурсией

    Reply ↓
53. RonX01 28.06.2019 at 13:37

    (57) Если есть открывающая и закрывающая («»), то можно также. А можно с помощью состояний или флага.
    
    Мне больше нравится состояние, получится конечный автомат. Встретилась кавычка — кладем ее в стек и переходим в состояние, например ЦИТАТА. Когда в этом состоянии еще раз встретилась кавычка — берем из стека и переходим в прежнее состояние. В состоянии ЦИТАТА можно, например, не считать скобки, все зависит от поставленной задачи.

    Reply ↓
54. RonX01 28.06.2019 at 13:48

    (58) Кстати, использование стека — это один из способов избавления от рекурсии :).

    Reply ↓
55. new_user 08.07.2019 at 16:53

    

    Reply ↓
56. RonX01 09.07.2019 at 06:25

    (61) Ну это как посмотреть. Я считаю, что первый добавленный элемент кладется на «дно», следующий на него. Если по другому представить массив, то у него есть голова и хвост, я считаю, что новый элемент увеличивает хвост, вы же считаете, что новый элемент увеличивает голову. А слово «вставка» пусть не вводит вас в заблуждение.

    Reply ↓
57. RonX01 10.07.2019 at 11:37

    (5) вот здесь https://infostart.ru/public/1088569/ примеры практического применение этого кода (очередь и приоритетная очередь)

    Reply ↓