0. RonX01 194 24.06.19 12:40 Сейчас в теме

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

В статье рассматриваются способы реализации таких абстрактных структур данных, как стек, очередь и приоритетная очередь, используя готовые типы данных 1С. Выявляются "узкие" места, сложные моменты в реализации и сравнивается скорость работы.

Перейти к публикации

Лучшие комментарии
31. herfis 281 25.06.19 09:35 Сейчас в теме
По классике, приоритетная очередь реализуется на двоичном дереве, уложенном в непрерывный участок памяти (обычный массив) и не требует явной сортировки. Операции добавления и удаления элементов в него осуществляются путем "всплытия" и "погружения" элементов дерева, которые выполняются за O(log N) и при этом как бы автоматически сохраняется нужный порядок элементов. Т.н. сортирующее дерево. Как красно-черное дерево, только намного проще в реализации за счет того, что и требования к приоритетной очереди более простые. И в этом прелесть этой структуры данных. С одной стороны - она относительно простая. С другой - чрезвычайно эффективна по производительности и ресурсам.
Krio2; new_user; for_sale; RonX01; +4 Ответить
36. herfis 281 25.06.19 13:29 Сейчас в теме
В общем, таки не поленился сделать простейшую реализацию на 1С :) Прелесть этой структуры данных еще в том, что можно сделать очередь фиксированного размера и прогонять через нее ЛЮБЫЕ объемы данных. И она всегда будет содержать ТОП 100 элементов (для убывающей очереди в 100 элементов), не падая в производительности и не потребляя больше ресурсов. Чаще всего для подобных алгоритмов ее и используют.
&НаКлиенте
Перем ПриоритетнаяОчередь;

&НаКлиенте
Функция ДобавитьЭлемент(Элемент)
	ПриоритетнаяОчередь.Добавить(Элемент);
	Всплытие(ПриоритетнаяОчередь.Количество() - 1);
КонецФункции

&НаКлиенте
Функция ИзвлечьМаксимум()
	Максимум = ПриоритетнаяОчередь[1];
	ИндексПоследнегоЭлемента = ПриоритетнаяОчередь.Количество() - 1;
	Рокировка(1, ИндексПоследнегоЭлемента);
	ПриоритетнаяОчередь.Удалить(ИндексПоследнегоЭлемента);
	Погружение(1);
	Возврат Максимум;
КонецФункции

&НаКлиенте
Процедура Всплытие(Знач ИндексЭлемента)
	Пока ИндексЭлемента > 1 И ПриоритетнаяОчередь[Цел(ИндексЭлемента / 2)] < ПриоритетнаяОчередь[ИндексЭлемента] Цикл
		ИндексРодительскогоЭлемента = Цел(ИндексЭлемента / 2);
		Рокировка(ИндексЭлемента, ИндексРодительскогоЭлемента);
		ИндексЭлемента = ИндексРодительскогоЭлемента;
	КонецЦикла;
КонецПроцедуры

&НаКлиенте
Процедура Погружение(Знач ИндексЭлемента)
	ИндексПоследнегоЭлемента = ПриоритетнаяОчередь.Количество() - 1;
	Пока ИндексЭлемента*2 <= ИндексПоследнегоЭлемента Цикл
		ИндексПервогоДочернегоЭлемента = ИндексЭлемента*2;
		ИндексВторогоДочернегоЭлемента = ИндексПервогоДочернегоЭлемента + 1;
		ИндексДочернегоЭлементаДляПогружения = ИндексПервогоДочернегоЭлемента;
		Если ИндексДочернегоЭлементаДляПогружения < ИндексПоследнегоЭлемента И ПриоритетнаяОчередь[ИндексВторогоДочернегоЭлемента] > ПриоритетнаяОчередь[ИндексПервогоДочернегоЭлемента] Тогда
			ИндексДочернегоЭлементаДляПогружения = ИндексВторогоДочернегоЭлемента;
		КонецЕсли;
		Если ПриоритетнаяОчередь[ИндексЭлемента] < ПриоритетнаяОчередь[ИндексДочернегоЭлементаДляПогружения] Тогда
			Рокировка(ИндексЭлемента, ИндексДочернегоЭлементаДляПогружения);
			ИндексЭлемента = ИндексДочернегоЭлементаДляПогружения;
		Иначе
			//погружение не требуется
			Прервать;
		КонецЕсли;
	КонецЦикла;
КонецПроцедуры

&НаКлиенте
Процедура Рокировка(ИндексПервогоЭлемента, ИндексВторогоЭлемента)
	ПервыйЭлемент = ПриоритетнаяОчередь[ИндексПервогоЭлемента];
	ПриоритетнаяОчередь[ИндексПервогоЭлемента] = ПриоритетнаяОчередь[ИндексВторогоЭлемента];
	ПриоритетнаяОчередь[ИндексВторогоЭлемента] = ПервыйЭлемент;
КонецПроцедуры

&НаКлиенте
Процедура Опустошение()
	Для ИндексЭлемента = 1 По ПриоритетнаяОчередь.Количество() - 1 Цикл
		Сообщить(ИзвлечьМаксимум());
	КонецЦикла;
КонецПроцедуры

&НаКлиенте
Процедура ДемоИнициализация()
	ПриоритетнаяОчередь.Очистить();
	ПриоритетнаяОчередь.Добавить(0);
	ГСЧ = Новый ГенераторСлучайныхЧисел(ТекущаяУниверсальнаяДатаВМиллисекундах());
	Для НомерЭлемента = 1 По 30 Цикл
		СЧ = ГСЧ.СлучайноеЧисло(0, 100);
		Сообщить(СЧ);
		ДобавитьЭлемент(СЧ);
	КонецЦикла;
КонецПроцедуры

&НаКлиенте
Процедура Тест(Команда)
	Сообщить("Инициализация");
	ДемоИнициализация();
	Сообщить("Опустошение");
	Опустошение();
КонецПроцедуры

ПриоритетнаяОчередь = Новый Массив;
Показать
Krio2; beefit; for_sale; RonX01; +4 Ответить
37. herfis 281 25.06.19 13:48 Сейчас в теме
Еще одна прикольная особенность такой реализации - расходы на "сортировку" делятся между помещением элемента в очередь и извлечением элемента из очереди. Каждый момент времени гарантируется только, что корневой элемент является максимальным/минимальным. Чтобы получить всю последовательность в отсортированном виде необходимо выполнить процедуру по извлечению всех элементов из очереди (с соответствующей перестройкой дерева в процессе).
for_sale; RonX01; +2 Ответить
45. Alias 153 26.06.19 15:34 Сейчас в теме
(36)
Объясните мне, пожалуйста, ведь это Вы явно не двоичное дерево организовали, верно? Это всё тот же массив. Просто после добавления элемента Вы начинаете всплывать, погружаться и рокироваться элементами чтобы он занял более-менее правильную позицию (первый всегда правильный)?

Но в наше время это называлось просто "методом половинного деления", и выглядело как-то попроще. Вместо погружений-всплытий-рокировок для этого было бы достаточно одной функции, которая будет возвращать номер позиции, куда нужно поместить новый элемент. Как-то так:
&НаКлиенте
Функция НайтиКудаВставлять(ЧтоВставлять, Очередь, Начиная, Заканчивая)
	Если Начиная=Заканчивая Тогда
		Ответ = Начиная
	Иначе
		Проверяем = Окр((Начиная+Заканчивая)/2, 0, 0);
		Если Проверяем=Заканчивая Тогда
			Ответ = Заканчивая; // уже ясно что новый в конец
		ИначеЕсли Очередь[Проверяем]<ЧтоВставлять Тогда // с начала
			Ответ = НайтиКудаВставлять(ЧтоВставлять, Очередь, Начиная, Проверяем);
		Иначе // до конца
			Ответ = НайтиКудаВставлять(ЧтоВставлять, Очередь, Проверяем+1, Заканчивая);
		КонецЕсли;
	КонецЕсли;
	Возврат Ответ
КонецФункции
Показать


Смотрите, я сделал обработку, в которой есть как Ваш метод, так и мой, более простой. На 100 элементов Ваш тратит 115 мс на инициализацию и 458 на опустошение (всего 673). Мой, в тех же условиях, 406 на инициализацию и только 6 на опустошение (всего 412). То есть на треть меньше -- и эта закономерность сохраняется с увеличением количества элементов. При этом также, в каждый момент времени гарантируется то что корневой является максимальным. Но кроме того бонусом ещё и то что остальные все сразу упорядочены.

Вопрос -- зачем тогда сложности? Только ради быстрой инициализации -- в каких-то системах возможно и имеет смысл (ценой общего увеличения времени!). Но для 1С, если смотреть на общее количество кода и общее время выполнения -- лучше как проще и быстрее.
Прикрепленные файлы:
ТестПриоритетнаяОчередь.epf
new_user; +1 Ответить
46. herfis 281 26.06.19 16:17 Сейчас в теме
(45)
ведь это Вы явно не двоичное дерево организовали, верно? Это всё тот же массив.

Нет, это именно двоичное дерево, несмотря на то, что оно в массиве :)
"Всплытие" и "погружение" элементов происходит именно "по дереву", между дочерними и родительскими элементами.
Ессно в 1С это решение не претендует на эффективность. Это просто модель "настоящей" низкоуровневой реализации priority queue, выполненная средствами 1С. Я поэтому и писал в (30) и продублирую здесь:
priority queue - моя любимая структура данных по изяществу и эффективности.
К сожалению, в 1С возможно реализовать лишь модели такого рода структур. Вся прелесть эффективности их реализации недоступна в 1С.
Остальные комментарии
Избранное Подписка Сортировка: Древо
1. ArchLord42 68 24.06.19 13:20 Сейчас в теме
        Попытка
		Значение = Стек[ИндексПоследнегоЭлемента];
		Стек.Удалить(ИндексПоследнегоЭлемента);
		Возврат Значение;
	Исключение
		Возврат Неопределено;
	КонецПопытки;
Показать


тут (и в других методах) не так сложно проверить количество элементов в массиве, зачем все эти попытки \ исключения ? code smells в общем
taiwanchik; for_sale; imushov; TODD22; boln; +5 Ответить
6. RonX01 194 24.06.19 13:57 Сейчас в теме
(1) Страсть как захотелось использовать здесь попытку вместо условия. Кому code smells используйте так:
	Если Стек_Пустой(Стек) Тогда
		Возврат Неопределено;
	Иначе
		ИндексПоследнегоЭлемента = Стек.ВГраница();
		Значение = Стек[ИндексПоследнегоЭлемента];
		Стек.Удалить(ИндексПоследнегоЭлемента);
		Возврат Значение;
	КонецЕсли;
Показать
7. TODD22 18 24.06.19 14:16 Сейчас в теме
(6)
Страсть как захотелось использовать здесь попытку вместо условия.

В 1С не рекомендуется в общем случае перехватывать исключения.
Rustig; boln; +2 Ответить
8. RonX01 194 24.06.19 14:27 Сейчас в теме
(7) Не знал, спасибо. Теперь страсть свою поумерю.
21. for_sale 770 24.06.19 21:14 Сейчас в теме
9. for_sale 770 24.06.19 17:19 Сейчас в теме
(6)
Страсть чем-то объясняется или просто "страсть"?)

Ещё момент - Неопределено теоретически может быть правильным значением элемента. Т.е. Неопределено и "Такого элемента не существует" будут разными случаями.
12. RonX01 194 24.06.19 20:38 Сейчас в теме
(9) Я думал по поводу Неопределено, можно возвращать NULL, но это также теоретически может быть правильным значением.
Вообще эти структуры данных используют программисты, а не пользователи, поэтому мне кажется, что проверки на пустую структуру данных внутри методов _Получить() излишни. Для проверки предполагается использовать метод _Пустой(), который возвращает вполне себе однозначный ответ :)

Здесь "страсть" объясняется тем, что с одной стороны мне не нравится проверка на пустую структуру данных внутри методов, а с другой стороны нужно предусмотреть появление ошибки, не нагромаждая код. Хотелось сделать как можно меньше кода.
13. for_sale 770 24.06.19 20:40 Сейчас в теме
(12)
Я думал по поводу Неопределено, можно возвращать NULL, но это также теоретически может быть правильным значением.

Я думаю, тут можно просто разделить сущности. Т.е. возвращаемое значение - это возвращаемое значение, а сама функция возвращает (или устанавливает переданный) флаг того, что что-то было найдено или ничего не было найдено.
19. RonX01 194 24.06.19 21:04 Сейчас в теме
22. for_sale 770 24.06.19 21:15 Сейчас в теме
(19)
Функция Стек_ВзятьБезУдаления(Стек, Значение)
	
	Если _СтекПустой() Тогда
		Возврат Ложь;
	Иначе
Значение = Стек[ИндексПоследнегоЭлемента];
Возврат Истина;
	КонецЕсли;
КонецФункции

Значение = "";
Если Стек_ВзятьБезУдаления(Стек, Значение) Тогда
// значение можно использовать
Иначе
// ничё нет
КонецЕсли;
Показать


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

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

// если у меня могут быть Неопределено как значения, тогда
ЕстьЗнч = Ложь;
Если Стек_Взять(Стек, ЕстьЗнч) Тогда
КонецЕсли;

// если немогут или неважно
Знч = Стек_Взять(Стек);
Показать
oleganatolievich; PLAstic; RonX01; +3 Ответить
23. RonX01 194 24.06.19 21:23 Сейчас в теме
(22) Понял, получается 2 в одном. Почему бы и нет.
24. leemuar 25.06.19 01:11 Сейчас в теме
(23) попытка получить значение из пустой коллекции всегда должна бросать исключение. Любое значение встроенного языка может храниться в коллекции, поэтому не допустимо использовать «особое» возвращаемое значение как признак невозможности получения жначения

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

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

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


p.s. Подумайте на досуге, а так ли нужна вообще операция получения без удаления (peek)? Когда вы ею последний раз пользовались и зачем?
ltfriend; RonX01; +2 Ответить
27. RonX01 194 25.06.19 07:29 Сейчас в теме
(24) Совсем недавно использовал операцию без удаления из приоритетной очереди. Необходимо было найти вершину графа, которая ближе всех расположена к углу (по оси х и у). Обход вершин графа с правильным вычислением приоритетов дал результат и вконце требовалось только получить один элемент с наивысшим приоритетом. Поэтому использовал получить без удаления, хотя мог использовать и с удалением. Выигрыш конечно микро секунды, но все же.
Думаю могут быть ситуации, когда это будет полезно.
Perfolenta; leemuar; +2 Ответить
40. ltfriend 377 25.06.19 19:43 Сейчас в теме
(22) Лучше ни каких проверок не делать. Пусть возникает исключение, а программист должен сам его обрабатывать на своё усмотрение. Тогда получиться так:
Функция Стек_ВзятьБезУдаления(Стек)
   
    Возврат Стек[ИндексПоследнегоЭлемента];

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

Попытка
    Значение = Стек_ВзятьБезУдаления(Стек)
Исключение
    // Обработка по своим требованиям
КонецПопытки;
Показать
41. for_sale 770 25.06.19 20:23 Сейчас в теме
(40)
Кому лучше?
Тем более, мы рассматриваем ситуацию, когда Неопределено может быть значением. У вас, по-моему, другая ситуация описывается.
42. RonX01 194 26.06.19 06:02 Сейчас в теме
(40) Я уже убрал в статье какие либо проверки. В данном случае считается, что программист сам решает как ему обработать исключение, либо вообще не допустит такой ситуации. Есть функция Пустой()
11. MikeI 72 24.06.19 20:37 Сейчас в теме
(6)Дурацкий вопрос: Если заменить Стек.ВГраница(), на Стек.Количество()-1. Шустрее не будет?

Или вообще не использовать метод Количество() для подсчета элементов в очереди, а Один раз посчитать, а потом уменьшать это число на единицу
14. RonX01 194 24.06.19 20:45 Сейчас в теме
(11) Вопрос, кстати не дурацкий, я им сам задавался :). Стек.Количество()-1 будет медленней.
15. MikeI 72 24.06.19 20:47 Сейчас в теме
(14)тогда в методах Пустая нужно использовать Стек.Вграница()+1
16. MikeI 72 24.06.19 20:49 Сейчас в теме
(15)Но ИМХО , когда в 1С стали приходить true программеры с ООП, то стало конфы стали тормознее, заморочитей, менее логичны и сложны для отладки. ))))
Irwin; Perfolenta; tsukanov; +3 Ответить
18. RonX01 194 24.06.19 21:03 Сейчас в теме
(16) Согласен. с ООП тоже есть проблемы, и часто всё превращается в лапшу.
Поэтому "Простота требует проектирования и хорошего вкуса" Линус Торвальдс.
17. RonX01 194 24.06.19 20:55 Сейчас в теме
(15) Стек.Количество() = 0; будет работать чуть-чуть быстрее нежели Стек.ВГраница() = -1; Почему-то
25. kuzyara 785 25.06.19 06:23 Сейчас в теме
(6)
code smells

Guard clauses
мб так?

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


https://softwareengineering.stackexchange.com/questions/350472/developer-insists-if-statements-shouldnt-have-negated-conditions-and-should-al
26. RonX01 194 25.06.19 07:09 Сейчас в теме
36. herfis 281 25.06.19 13:29 Сейчас в теме
В общем, таки не поленился сделать простейшую реализацию на 1С :) Прелесть этой структуры данных еще в том, что можно сделать очередь фиксированного размера и прогонять через нее ЛЮБЫЕ объемы данных. И она всегда будет содержать ТОП 100 элементов (для убывающей очереди в 100 элементов), не падая в производительности и не потребляя больше ресурсов. Чаще всего для подобных алгоритмов ее и используют.
&НаКлиенте
Перем ПриоритетнаяОчередь;

&НаКлиенте
Функция ДобавитьЭлемент(Элемент)
	ПриоритетнаяОчередь.Добавить(Элемент);
	Всплытие(ПриоритетнаяОчередь.Количество() - 1);
КонецФункции

&НаКлиенте
Функция ИзвлечьМаксимум()
	Максимум = ПриоритетнаяОчередь[1];
	ИндексПоследнегоЭлемента = ПриоритетнаяОчередь.Количество() - 1;
	Рокировка(1, ИндексПоследнегоЭлемента);
	ПриоритетнаяОчередь.Удалить(ИндексПоследнегоЭлемента);
	Погружение(1);
	Возврат Максимум;
КонецФункции

&НаКлиенте
Процедура Всплытие(Знач ИндексЭлемента)
	Пока ИндексЭлемента > 1 И ПриоритетнаяОчередь[Цел(ИндексЭлемента / 2)] < ПриоритетнаяОчередь[ИндексЭлемента] Цикл
		ИндексРодительскогоЭлемента = Цел(ИндексЭлемента / 2);
		Рокировка(ИндексЭлемента, ИндексРодительскогоЭлемента);
		ИндексЭлемента = ИндексРодительскогоЭлемента;
	КонецЦикла;
КонецПроцедуры

&НаКлиенте
Процедура Погружение(Знач ИндексЭлемента)
	ИндексПоследнегоЭлемента = ПриоритетнаяОчередь.Количество() - 1;
	Пока ИндексЭлемента*2 <= ИндексПоследнегоЭлемента Цикл
		ИндексПервогоДочернегоЭлемента = ИндексЭлемента*2;
		ИндексВторогоДочернегоЭлемента = ИндексПервогоДочернегоЭлемента + 1;
		ИндексДочернегоЭлементаДляПогружения = ИндексПервогоДочернегоЭлемента;
		Если ИндексДочернегоЭлементаДляПогружения < ИндексПоследнегоЭлемента И ПриоритетнаяОчередь[ИндексВторогоДочернегоЭлемента] > ПриоритетнаяОчередь[ИндексПервогоДочернегоЭлемента] Тогда
			ИндексДочернегоЭлементаДляПогружения = ИндексВторогоДочернегоЭлемента;
		КонецЕсли;
		Если ПриоритетнаяОчередь[ИндексЭлемента] < ПриоритетнаяОчередь[ИндексДочернегоЭлементаДляПогружения] Тогда
			Рокировка(ИндексЭлемента, ИндексДочернегоЭлементаДляПогружения);
			ИндексЭлемента = ИндексДочернегоЭлементаДляПогружения;
		Иначе
			//погружение не требуется
			Прервать;
		КонецЕсли;
	КонецЦикла;
КонецПроцедуры

&НаКлиенте
Процедура Рокировка(ИндексПервогоЭлемента, ИндексВторогоЭлемента)
	ПервыйЭлемент = ПриоритетнаяОчередь[ИндексПервогоЭлемента];
	ПриоритетнаяОчередь[ИндексПервогоЭлемента] = ПриоритетнаяОчередь[ИндексВторогоЭлемента];
	ПриоритетнаяОчередь[ИндексВторогоЭлемента] = ПервыйЭлемент;
КонецПроцедуры

&НаКлиенте
Процедура Опустошение()
	Для ИндексЭлемента = 1 По ПриоритетнаяОчередь.Количество() - 1 Цикл
		Сообщить(ИзвлечьМаксимум());
	КонецЦикла;
КонецПроцедуры

&НаКлиенте
Процедура ДемоИнициализация()
	ПриоритетнаяОчередь.Очистить();
	ПриоритетнаяОчередь.Добавить(0);
	ГСЧ = Новый ГенераторСлучайныхЧисел(ТекущаяУниверсальнаяДатаВМиллисекундах());
	Для НомерЭлемента = 1 По 30 Цикл
		СЧ = ГСЧ.СлучайноеЧисло(0, 100);
		Сообщить(СЧ);
		ДобавитьЭлемент(СЧ);
	КонецЦикла;
КонецПроцедуры

&НаКлиенте
Процедура Тест(Команда)
	Сообщить("Инициализация");
	ДемоИнициализация();
	Сообщить("Опустошение");
	Опустошение();
КонецПроцедуры

ПриоритетнаяОчередь = Новый Массив;
Показать
Krio2; beefit; for_sale; RonX01; +4 Ответить
43. RonX01 194 26.06.19 06:09 Сейчас в теме
(36) Огромное спасибо за реализацию. Одно дело понимать теорию, а другое реализовать, да еще и в 1с :)
44. herfis 281 26.06.19 09:36 Сейчас в теме
(43) Не за что. Самому было интересно :) Я практически один к одному передрал ключевые моменты принстонской реализации https://algs4.cs.princeton.edu/24pq/MaxPQ.java.html из их книжки по алгоритмам.
45. Alias 153 26.06.19 15:34 Сейчас в теме
(36)
Объясните мне, пожалуйста, ведь это Вы явно не двоичное дерево организовали, верно? Это всё тот же массив. Просто после добавления элемента Вы начинаете всплывать, погружаться и рокироваться элементами чтобы он занял более-менее правильную позицию (первый всегда правильный)?

Но в наше время это называлось просто "методом половинного деления", и выглядело как-то попроще. Вместо погружений-всплытий-рокировок для этого было бы достаточно одной функции, которая будет возвращать номер позиции, куда нужно поместить новый элемент. Как-то так:
&НаКлиенте
Функция НайтиКудаВставлять(ЧтоВставлять, Очередь, Начиная, Заканчивая)
	Если Начиная=Заканчивая Тогда
		Ответ = Начиная
	Иначе
		Проверяем = Окр((Начиная+Заканчивая)/2, 0, 0);
		Если Проверяем=Заканчивая Тогда
			Ответ = Заканчивая; // уже ясно что новый в конец
		ИначеЕсли Очередь[Проверяем]<ЧтоВставлять Тогда // с начала
			Ответ = НайтиКудаВставлять(ЧтоВставлять, Очередь, Начиная, Проверяем);
		Иначе // до конца
			Ответ = НайтиКудаВставлять(ЧтоВставлять, Очередь, Проверяем+1, Заканчивая);
		КонецЕсли;
	КонецЕсли;
	Возврат Ответ
КонецФункции
Показать


Смотрите, я сделал обработку, в которой есть как Ваш метод, так и мой, более простой. На 100 элементов Ваш тратит 115 мс на инициализацию и 458 на опустошение (всего 673). Мой, в тех же условиях, 406 на инициализацию и только 6 на опустошение (всего 412). То есть на треть меньше -- и эта закономерность сохраняется с увеличением количества элементов. При этом также, в каждый момент времени гарантируется то что корневой является максимальным. Но кроме того бонусом ещё и то что остальные все сразу упорядочены.

Вопрос -- зачем тогда сложности? Только ради быстрой инициализации -- в каких-то системах возможно и имеет смысл (ценой общего увеличения времени!). Но для 1С, если смотреть на общее количество кода и общее время выполнения -- лучше как проще и быстрее.
Прикрепленные файлы:
ТестПриоритетнаяОчередь.epf
new_user; +1 Ответить
46. herfis 281 26.06.19 16:17 Сейчас в теме
(45)
ведь это Вы явно не двоичное дерево организовали, верно? Это всё тот же массив.

Нет, это именно двоичное дерево, несмотря на то, что оно в массиве :)
"Всплытие" и "погружение" элементов происходит именно "по дереву", между дочерними и родительскими элементами.
Ессно в 1С это решение не претендует на эффективность. Это просто модель "настоящей" низкоуровневой реализации priority queue, выполненная средствами 1С. Я поэтому и писал в (30) и продублирую здесь:
priority queue - моя любимая структура данных по изяществу и эффективности.
К сожалению, в 1С возможно реализовать лишь модели такого рода структур. Вся прелесть эффективности их реализации недоступна в 1С.
47. Alias 153 26.06.19 16:33 Сейчас в теме
(46)
>"Всплытие" и "погружение" элементов происходит именно "по дереву", между дочерними и родительскими элементами.
Ну что ж, попробую разобраться повнимательнее -- в механизме отображения дерева на массив... возможно, будет интересно. А то когда я вижу в коде Цел(ИндексЭлемента/2), я вижу обычное половинное деление, даже если назвать переменную ИндексРодительскогоЭлемента :) в дереве всё же наполнение веток может быть сильно неравномерным, да и связи где-то должны храниться (или хотя бы неизменно определяться). А тут мы всё время середину интервала берём.
Но мой код всё равно короче и в общем быстрее :)
48. herfis 281 26.06.19 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 строится поверх неизменяемых массивов (фактически просто непрерывных кусков памяти) и оптимизирован под минимальное количество перестановок и копирований. Реализовывать ее с помощью динамического массива - это уже смешно. Эти алгоритмы и структуры данных как раз и составляют "потроха" реализации библиотечной функциональности высокоуровневых языков.
Alias; RonX01; +2 Ответить
49. RonX01 194 27.06.19 06:43 Сейчас в теме
(45) Вот здесь в пункте 4 "Массив и двоичное дерево" можете более детально посмотреть как на массиве отобразить двоичное дерево
2. VmvLer 24.06.19 13:32 Сейчас в теме
не понятно, что делать с этим кодом в практическом плане.
возможно его стоит предложить старшему воспитателю группы детского сада
"1С: пупс"
3. vadim1011985 65 24.06.19 13:44 Сейчас в теме
(2) При желании можно найти применение , например с помощью стека проверяют соответствие открывающихся и закрывающихся скобок (или тех же кавычек) в выражениях. В любом случае это полезные структуры
Rustig; CyberCerber; for_sale; Perfolenta; RonX01; boln; +6 Ответить
51. ValeriVP 1014 27.06.19 14:54 Сейчас в теме
(3)
соответствие открывающихся и закрывающихся скобок (или тех же кавычек)

это легче проверить по количеству символов - четность для кавычек, равенство для скобок
52. vadim1011985 65 27.06.19 15:23 Сейчас в теме
53. vadim1011985 65 27.06.19 15:25 Сейчас в теме
(51) В приведенном примере количество скобок четное , но для [ нет закрывающей скобки , так что по количеству не проверишь
54. ValeriVP 1014 27.06.19 16:55 Сейчас в теме
(53) странный пример
((([(((([)))))
((((((( 7
[[ 2
))))) 5

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

Другое дело, что со строкой типа ([)] есть некоторые проблемы. Но все то же самое - считаем количество квадратных скобок между круглых скобок - получаем не сходимость.
new_user; +1 Ответить
55. vadim1011985 65 27.06.19 18:11 Сейчас в теме
(54) Со стеком проще гораздо , просто если будут [({)]} т.е. 3 вида скобок как тогда измениться ваш способ ? А при стеке - изменения минимальный. Поэтому стек в данном случае удобнее
58. ValeriVP 1014 28.06.19 13:03 Сейчас в теме
(55) я задачу разбора такой строки решал бы рекурсией
60. RonX01 194 28.06.19 13:48 Сейчас в теме
(58) Кстати, использование стека - это один из способов избавления от рекурсии :).
56. RonX01 194 28.06.19 06:33 Сейчас в теме
(54) Со стеком это решается так - кладем в стек только открывающие скобки, а когда встречается закрывающая, то берем из стека и смотрим соответствие вида скобки.
Вконце стек должен быть пустым, т.е. в стеке не должно остаться открывающих скобок. Так же, если встречается закрывающая скобка, а стек пустой, то тоже ошибка.
Мне кажется здесь проще и надежнее использовать стек, нежели подсчет скобок.
57. ValeriVP 1014 28.06.19 10:23 Сейчас в теме
(56)а кавычки? Когда класть и забирать?
Я решал задачу разбора файлов 1С с фигурными скобками и кавычками - решение получилось без стека.

Т.о. практического применения описанных механизмов не понимаю, хотя и не отрицаю возможность применения.
Но как я уже говорил - это частные задачи и они требуют индивидуального подхода.
new_user; +1 Ответить
59. RonX01 194 28.06.19 13:37 Сейчас в теме
(57) Если есть открывающая и закрывающая («»), то можно также. А можно с помощью состояний или флага.
Мне больше нравится состояние, получится конечный автомат. Встретилась кавычка - кладем ее в стек и переходим в состояние, например ЦИТАТА. Когда в этом состоянии еще раз встретилась кавычка - берем из стека и переходим в прежнее состояние. В состоянии ЦИТАТА можно, например, не считать скобки, все зависит от поставленной задачи.
4. boln 997 24.06.19 13:47 Сейчас в теме
(2)
не понятно, что делать с этим кодом в практическом плане.
возможно его стоит предложить старшему воспитателю группы детского сада
Я, например, использую стек для организации последовательности завершения вложенных асинхронных процедур:
https://www.1c-uc3.ru/modal.html
Rustig; mvxyz; RonX01; +3 Ответить
5. VmvLer 24.06.19 13:56 Сейчас в теме
(4) я имел ввиду
этот код
, то что многие используют подобные алгоритмы я не сомневаюсь.
63. RonX01 194 10.07.19 11:37 Сейчас в теме
(5) вот здесь https://infostart.ru/public/1088569/ примеры практического применение этого кода (очередь и приоритетная очередь)
10. acsent 1135 24.06.19 18:20 Сейчас в теме
а если сделать раелизацию на списке.
те на структуре, где один из элементов - другая структура?
20. RonX01 194 24.06.19 21:11 Сейчас в теме
(10) Тогда необходимо подумать что будет ключами структуры? И для получения первого элемента необходимо вызывать конструкцию типа Для каждого Из Цикл. Мне кажется это будет затратно по времени, но надо тестить.
39. acsent 1135 25.06.19 18:12 Сейчас в теме
(20) ссылку на последний можно хранить в первом.
Если эта куча то вообще ни чего этого не нужно
28. Scorpion4eg 248 25.06.19 07:54 Сейчас в теме
Хорошая статья. Твою бы статью, да когда я LRU кэш организовывал...
Получилась очень сложная конструкция из таблицы значение, соответствия и пары параметров. Зато без проблем кэширую http запросы с контролем памяти.
29. RonX01 194 25.06.19 08:54 Сейчас в теме
30. herfis 281 25.06.19 09:06 Сейчас в теме
priority queue - моя любимая структура данных по изяществу и эффективности.
К сожалению, в 1С возможно реализовать лишь модели такого рода структур. Вся прелесть эффективности их реализации недоступна в 1С.
31. herfis 281 25.06.19 09:35 Сейчас в теме
По классике, приоритетная очередь реализуется на двоичном дереве, уложенном в непрерывный участок памяти (обычный массив) и не требует явной сортировки. Операции добавления и удаления элементов в него осуществляются путем "всплытия" и "погружения" элементов дерева, которые выполняются за O(log N) и при этом как бы автоматически сохраняется нужный порядок элементов. Т.н. сортирующее дерево. Как красно-черное дерево, только намного проще в реализации за счет того, что и требования к приоритетной очереди более простые. И в этом прелесть этой структуры данных. С одной стороны - она относительно простая. С другой - чрезвычайно эффективна по производительности и ресурсам.
Krio2; new_user; for_sale; RonX01; +4 Ответить
32. RonX01 194 25.06.19 10:01 Сейчас в теме
(31) Вначале статьи я указал, что буду использовать готовые типы данных 1с. Как бы намекая на то, что не буду пытаться реализовывать кучи для приоритетной очереди :). Хотя мне очень интересно посмотреть реализацию "по классике" в 1с.
33. herfis 281 25.06.19 10:26 Сейчас в теме
(32) На массиве делается вполне аутентично. Но вот эффективность может хромать вследствие тормознутости 1С как скриптового языка (вполне может оказаться, что использование библиотечной сортировки на больших коллекциях более эффективно, чем "ручные" операции на массиве, несмотря на O(log N)).
34. herfis 281 25.06.19 10:30 Сейчас в теме
(32) Вот тут глянь в самом начале: http://ti.math.msu.su/wiki/lib/exe/fetch.php?media=algo:algo-13.pdf
Там все очень просто и красиво.
35. RonX01 194 25.06.19 11:14 Сейчас в теме
37. herfis 281 25.06.19 13:48 Сейчас в теме
Еще одна прикольная особенность такой реализации - расходы на "сортировку" делятся между помещением элемента в очередь и извлечением элемента из очереди. Каждый момент времени гарантируется только, что корневой элемент является максимальным/минимальным. Чтобы получить всю последовательность в отсортированном виде необходимо выполнить процедуру по извлечению всех элементов из очереди (с соответствующей перестройкой дерева в процессе).
for_sale; RonX01; +2 Ответить
38. comol 4057 25.06.19 15:26 Сейчас в теме
Ну спасибо! Теперь вопросы на собеседования новые выдумывать :(
50. Jimbo 6 27.06.19 12:45 Сейчас в теме
Зачем вот это вот всё ? А если на С написать тоже подобное или С++ с шаблонами STL, где всё это уже реализовано и позасекать время?
61. new_user 171 08.07.19 16:53 Сейчас в теме
62. RonX01 194 09.07.19 06:25 Сейчас в теме
(61) Ну это как посмотреть. Я считаю, что первый добавленный элемент кладется на "дно", следующий на него. Если по другому представить массив, то у него есть голова и хвост, я считаю, что новый элемент увеличивает хвост, вы же считаете, что новый элемент увеличивает голову. А слово "вставка" пусть не вводит вас в заблуждение.
new_user; +1 Ответить
Оставьте свое сообщение
Новые вопросы с вознаграждением
Автор темы объявил вознаграждение за найденный ответ, его получит тот, кто первый поможет автору.

Вакансии

Программист 1С
Екатеринбург
зарплата от 120 000 руб. до 120 000 руб.
Полный день

Бизнес-аналитик 1С
Москва
зарплата от 140 000 руб. до 200 000 руб.
Полный день

Руководитель проектов 1С
Санкт-Петербург
Полный день

Бизнес-архитектор 1С, ведущий консультант
Санкт-Петербург
Полный день