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

24.06.19

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

Стек

Стек - это абстрактный тип данных, представляющий собой список элементов, организованных по принципу ЛИФО ("последним пришел - первым вышел").

Основные операции со стеком это:

Push – вставка элемента наверх стека;
Top – получение верхнего элемента без удаления;
Pop – получение верхнего элемента и его удаление;
isEmpty – возвращает true, если стек пуст.

Для реализации стека будем использовать тип данных Массив. Реализуем вышеописанные операции:

#Область Стек

Функция Стек_Новый()
	Возврат Новый Массив;
КонецФункции

// Push
Процедура Стек_Положить(Стек, Значение)
	Стек.Добавить(Значение);
КонецПроцедуры

// Top
Функция Стек_ВзятьБезУдаления(Стек)
	Возврат Стек[Стек.ВГраница()];
КонецФункции

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

// isEmpty
Функция Стек_Пустой(Стек)
	Возврат Стек.Количество() = 0;
КонецФункции

#КонецОбласти

Эти операции работают как в тонком так и в других клиентах.

Пример того, как использовать стек

	// Инициализируем
	Стек = Стек_Новый(); 
	
	// Наполняем
	Для Сч = 1 По 6 Цикл 
		Стек_Положить(Стек, "Элемент №" + Строка(Сч));
	КонецЦикла;
	
	// Берем элементы из стэка пока он не закончится
	Сообщение = Новый СообщениеПользователю;
	
	Пока Не Стек_Пустой(Стек) Цикл // 
		Сообщение.Текст = Стек_Взять(Стек);
		Сообщение.Сообщить();
	КонецЦикла;

	// В результате выведутся следующие сообщения:
	//Элемент №6
	//Элемент №5
	//Элемент №4
	//Элемент №3
	//Элемент №2
	//Элемент №1

Вроде все просто и быстро работает.

Очередь

Очередь - это абстрактный тип данных, представляющий собой список элементов, организованных по принципу ФИФО ("первый пришел - первый вышел").

Основные операции с очередью это:

Добавить элемент в конец очереди;
Получить элемент из начала очереди (без удаления из очереди);
Получить элемент из начала очереди (с удалением из очереди);
Проверка пустая ли очередь.

Так же как и для стека будем использовать тип данных Массив. Реализуем вышеописанные операции.

#Область Очередь

Функция Очередь_Новый()
	Возврат Новый Массив;
КонецФункции

Процедура Очередь_Добавить(Очередь, Значение)
	Очередь.Добавить(Значение);
КонецПроцедуры

Функция Очередь_ПолучитьБезУдаления(Очередь)
	Возврат Очередь[0];
КонецФункции

Функция Очередь_Получить(Очередь)
	Значение = Очередь[0];
	Очередь.Удалить(0);
	Возврат Значение;
КонецФункции

Функция Очередь_Пустой(Очередь)
	Возврат Очередь.Количество() = 0;
КонецФункции

#КонецОбласти

Пример использования очереди

	// Инициализируем
	Очередь = Очередь_Новый(); 
	
	// Наполняем
	Для Сч = 1 По 6 Цикл 
		Очередь_Добавить(Очередь, "Элемент №" + Строка(Сч));
	КонецЦикла;
	
	// Берем элементы пока они не закончатся
	Сообщение = Новый СообщениеПользователю;
	
	Пока Не Очередь_Пустой(Очередь) Цикл // 
		Сообщение.Текст = Очередь_Получить(Очередь);
		Сообщение.Сообщить();
	КонецЦикла;
	
	// В результате выведутся следующие сообщения:
	//Элемент №1
	//Элемент №2
	//Элемент №3
	//Элемент №4
	//Элемент №5
	//Элемент №6

Здесь тоже все просто, но что по скорости? Поскольку отличие в только в способе получения элемента данных, то сравним скорость работы функции Очередь_Получить(Очередь) с Стек_Взять(Стек). Замеры производительности показали:

Строка кода	10 000 элементов		50 000 элементов		100 000 элементов
Строка кода	Время чистое	%	Время чистое	%	Время чистое	%
Стек (Стек_Взять(Стек))	0,170986	43,97	0,877694	21,25	1,703886	14,30
ИндексПоследнегоЭлемента = Стек.ВГраница();	0,064098	16,48	0,330289	8,00	0,639357	5,37
Значение = Стек[ИндексПоследнегоЭлемента];	0,047934	12,33	0,244083	5,91	0,475707	3,99
Стек.Удалить(ИндексПоследнегоЭлемента);	0,058954	15,16	0,303322	7,34	0,588822	4,94

Очередь (Очередь_Получить(Очередь))	0,217842	56,03	3,253449	78,75	10,2105	85,70
Значение = Очередь[0];	0,058589	15,07	0,333911	8,08	0,535987	4,50
Очередь.Удалить(0);	0,159253	40,96	2,919538	70,67	9,674513	81,20

Итого	0,388828	100,00	4,131143	100,00	11,914386	100,00

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

Если размер очереди не превышает 10 000 элементов, то разница в скорости между очередью и стеком не заметна, т.е. такая реализация Очереди работает также быстро как и Стек. В остальном же, чем больше элементов в очереди, тем медленнее будет работать операция получения. А что делать, если у нас могут быть очереди огромных размеров? Способ известен, избавляемся от удаления нулевого элемента в массиве и у нас получается следующее:

#Область Очередь

Функция Очередь_Новый()
	Возврат Новый Структура("Данные, Голова, Хвост", Новый Массив, 0, 0)
КонецФункции

Процедура Очередь_Добавить(Очередь, Значение)
	Очередь.Данные.Добавить(Значение);
	Очередь.Хвост = Очередь.Хвост + 1;
КонецПроцедуры

Функция Очередь_ПолучитьБезУдаления(Очередь)
	Возврат Очередь.Данные[Очередь.Голова];
КонецФункции

Функция Очередь_Получить(Очередь)
	Значение = Очередь.Данные[Очередь.Голова];
	Очередь.Голова = Очередь.Голова + 1;
	Возврат Значение;
КонецФункции

Функция Очередь_Пустой(Очередь)
	Возврат Очередь.Голова = Очередь.Хвост;
КонецФункции

#КонецОбласти

Сравним скорость работы со стектом

Строка кода	10 000 элементов		50 000 элементов		100 000 элементов
Строка кода	Время чистое	%	Время чистое	%	Время чистое	%
Стек	0,330505	43,37	1,633625	44,14	3,288941	43,81
Возврат Новый Массив;	0,000014	0,00	0,000014	0,00	0,000015	0,00
Стек.Добавить(Значение);	0,069462	9,11	0,340238	9,19	0,680083	9,06
ИндексПоследнегоЭлемента = Стек.ВГраница();	0,063925	8,39	0,321949	8,70	0,649467	8,65
Значение = Стек[ИндексПоследнегоЭлемента];	0,047449	6,23	0,239641	6,47	0,477748	6,36
Стек.Удалить(ИндексПоследнегоЭлемента);	0,05953	7,81	0,29952	8,09	0,597924	7,96
Возврат Стек.Количество() = 0;	0,090125	11,83	0,432263	11,68	0,883704	11,77

Очередь	0,431625	56,63	2,067537	55,86	4,219035	56,19
Возврат Новый Структура("Данные, Голова, Хвост", Новый Массив, 0, 0)	0,000054	0,01	0,000046	0,00	0,000049	0,00
Очередь.Данные.Добавить(Значение);	0,09672	12,69	0,442808	11,96	0,943409	12,57
Очередь.Хвост = Очередь.Хвост + 1;	0,096046	12,60	0,4312	11,65	0,857976	11,43
Значение = Очередь.Данные[Очередь.Голова];	0,075233	9,87	0,37646	10,17	0,752637	10,02
Очередь.Голова = Очередь.Голова + 1;	0,083533	10,96	0,418471	11,31	0,835261	11,12
Возврат Очередь.Голова = Очередь.Хвост;	0,080039	10,50	0,398552	10,77	0,829703	11,05

Итого	0,76213	100,00	3,701162	100,00	7,507976	100,00

Конечно, очередь все равно работает чуть медленнее стека, но разница не так заметна и она уже не растет при размере более 10 000. Но у нас растет размер массива.

Приоритетная очередь

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

Очередь с приоритетом использует такие же операции что и обычная очередь:

Добавить элемент в конец очереди;
Получить элемент из начала очереди (без удаления из очереди);
Получить элемент из начала очереди (с удалением из очереди);
Проверка пустая ли очередь.

Какой же тип выбрать для этой структуры данных? Теперь наряду с элементом, необходимо хранить приоритет. Простым способом будет выбрать тип, у которого есть методы сортировки. Очевидно, что массив не подойдет. Что мы имеем:

Соответствие - при добавлении элемента сортирует данные по ключу, но ключ должен быть уникальным. Нам не подходит, потому как могут быть элементы с одинаковым приоритетом. На самом деле можно сделать ключ уникальным и "правильным" для нас образом сортируемым. Но сейчас я не буду рассматривать его как претендента для реализации приоритетной очереди.
ТаблицаЗначений - есть метод Сортировать(), а также можно добавлять сколь угодно колонок. Подходит, но есть ограничение - не работает в тонком клиенте.
СписокЗначений - есть методы СортироватьПоПредставлению() и СортироватьПоЗначению(). Подходит, работает как в тонком, так и в других клиентах.

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

Реализуем приоритетную очередь используя тип ТаблицаЗначений:

#Область ПриоритетнаяОчередь_ТаблицаЗначений

Функция ПриоритетнаяОчередь_Новый()
	Очередь = Новый Структура;
	Очередь.Вставить("Отсортировано",	Истина);
	Очередь.Вставить("Данные",		Новый ТаблицаЗначений);
	Очередь.Данные.Колонки.Добавить("Значение");
	Очередь.Данные.Колонки.Добавить("Приоритет", Новый ОписаниеТипов("Число"));
	Очередь.Данные.Колонки.Добавить("Позиция", Новый ОписаниеТипов("Число"));
	Очередь.Вставить("Позиция", 0);
	Возврат Очередь;
КонецФункции

Процедура ПриоритетнаяОчередь_Добавить(Очередь, Значение, Приоритет)
	Очередь.Отсортировано = Ложь;
	НоваяСтрока = Очередь.Данные.Добавить();
	НоваяСтрока.Значение = Значение;
	НоваяСтрока.Приоритет = Приоритет;
	НоваяСтрока.Позиция = Очередь.Позиция + 1;
	Очередь.Позиция = НоваяСтрока.Позиция;
КонецПроцедуры

Функция ПриоритетнаяОчередь_ПолучитьБезУдаления(Очередь)
	Данные = Очередь.Данные;
	Если Не Очередь.Отсортировано Тогда
		Очередь.Отсортировано = Истина;
		Данные.Сортировать("Приоритет, Позиция");
	КонецЕсли;
	Возврат Данные[0].Значение;
КонецФункции

Функция ПриоритетнаяОчередь_Получить(Очередь)
	Данные = Очередь.Данные;
	Если Не Очередь.Отсортировано Тогда
		Очередь.Отсортировано = Истина;
		Данные.Сортировать("Приоритет, Позиция");
	КонецЕсли;
	Значение = Данные[0].Значение;
	Данные.Удалить(0);
	Возврат Значение;
КонецФункции

Функция ПриоритетнаяОчередь_Пустой(Очередь)
	Возврат Очередь.Данные.Количество() = 0;
КонецФункции

#КонецОбласти

Пример использования приоритетной очереди

	// Инициализируем
	ПриоритетнаяОчередь = ПриоритетнаяОчередь_Новый(); 
	
	// Наполним
	Для Сч = 1 По РазмерОчереди Цикл 
		Приоритет = Цел(РазмерОчереди / Сч);
		Элемент = СтрШаблон("Приоритет <%1> Номер в очереди <%2>", Строка(Приоритет), Строка(Сч));
		
		ПриоритетнаяОчередь_Добавить(ПриоритетнаяОчередь, Элемент, Приоритет);
	КонецЦикла;
	
	// Берем элементы пока не закончатся
	Сообщение = Новый СообщениеПользователю;
	
	Пока Не ПриоритетнаяОчередь_Пустой(ПриоритетнаяОчередь) Цикл 
		//ПриоритетнаяОчередь_Получить(ПриоритетнаяОчередь);
		Сообщение.Текст = ПриоритетнаяОчередь_Получить(ПриоритетнаяОчередь);
		Сообщение.Сообщить();
	КонецЦикла;
	
	// При размере очереди = 10 получим следущиие сообщения:
	//Приоритет <1> Номер в очереди <6>
	//Приоритет <1> Номер в очереди <7>
	//Приоритет <1> Номер в очереди <8>
	//Приоритет <1> Номер в очереди <9>
	//Приоритет <1> Номер в очереди <10>
	//Приоритет <2> Номер в очереди <4>
	//Приоритет <2> Номер в очереди <5>
	//Приоритет <3> Номер в очереди <3>
	//Приоритет <5> Номер в очереди <2>
	//Приоритет <10> Номер в очереди <1>

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

Далее реализуем приоритетную очередь на списке значений и уже там сравним скорость работы.

Реализуем приоритетную очередь используя тип СписокЗначений:

В Списке значений для хранения Приоритета будем использовать Представление. И вот здесь наталкиваемся на ограничение - Представление имеет тип Строка, а Приоритет у нас Число. Таким образом Приоритет из Числа преобразуется в Строку и метод СортироватьПоПредставлению() неправильно будет работать для нашей цели (например строки 1, 2, 10, 20, 100, 200 будут упорядочены сделующим образом 1, 10, 100, 2, 20, 200). Чтобы добиться "правильной" сортировки нам необходимо число привести в соответствующий строковый вид, например, числа 1, 2, 10, 20, 100, 200 приводим к строкам 001, 002, 010, 020, 100, 200. Для этого нам необхомо с определиться с длиной (разрядностью) и "дорисовать" лидирующие нули. Длина влияет на скорость сортировки, поэтому будем реализовывать так, чтобы можно было заранее указать разрядность. Вспоминаем еще один момент со "сдвигами" индексов, список значений эту "проблему" имеет, поэтому сортируем по убыванию, а получаем элемент сверху. В результате получаем следующее:

#Область ПриоритетнаяОчередь_СписокЗначений

&НаКлиенте
Функция ПриоритетнаяОчередь_Новый(РазрядностьПриоритета = 16, РазрядностьПозиции = 16)
	Очередь = Новый Структура;
	Очередь.Вставить("Отсортировано", Истина);
	Очередь.Вставить("Данные", Новый СписокЗначений);
	Очередь.Вставить("ФорматнаяСтрокаПриоритета", "ЧЦ=" + РазрядностьПриоритета + "; ЧН=; ЧВН=; ЧГ=0");
	Очередь.Вставить("ФорматнаяСтрокаПозиции", "ЧЦ=" + РазрядностьПозиции + "; ЧН=; ЧВН=; ЧГ=0");
	Очередь.Вставить("Позиция", 0);
	Возврат Очередь;
КонецФункции

&НаКлиенте
Процедура ПриоритетнаяОчередь_Добавить(Очередь, Значение, Приоритет)
	Очередь.Отсортировано = Ложь;
	Очередь.Позиция = Очередь.Позиция + 1;
	ПриоритетСтрока =  Формат(Приоритет, Очередь.ФорматнаяСтрокаПриоритета) + Формат(Очередь.Позиция, Очередь.ФорматнаяСтрокаПозиции);
	Очередь.Данные.Добавить(Значение, ПриоритетСтрока);
КонецПроцедуры

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

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

&НаКлиенте
Функция ПриоритетнаяОчередь_Пустой(Очередь)
	Возврат Очередь.Данные.Количество() = 0;
КонецФункции

#КонецОбласти

Если удобней передавать максимальное число, а не разрядность то фукнция ПриоритетнаяОчередь_Новый() будет выглядеть так:

&НаКлиенте
Функция ПриоритетнаяОчередь_Новый(МаксимальноеЧислоПриоритета = Неопределено, МаксимальноеЧислоПозиции = Неопределено)
	
	РазрядностьПриоритета = ?(МаксимальноеЧислоПриоритета = Неопределено, 16, СтрДлина(Формат(МаксимальноеЧислоПриоритета, "ЧГ=0")));
	РазрядностьПозиции = ?(МаксимальноеЧислоПозиции = Неопределено, 16, СтрДлина(Формат(МаксимальноеЧислоПозиции, "ЧГ=0")));
	
	Очередь = Новый Структура;
	Очередь.Вставить("Отсортировано", Истина);
	Очередь.Вставить("Данные", Новый СписокЗначений);
	Очередь.Вставить("ФорматнаяСтрокаПриоритета", "ЧЦ=" + РазрядностьПриоритета + "; ЧН=; ЧВН=; ЧГ=0");
	Очередь.Вставить("ФорматнаяСтрокаПозиции", "ЧЦ=" + РазрядностьПозиции + "; ЧН=; ЧВН=; ЧГ=0");
	Очередь.Вставить("Позиция", 0);
	
	Возврат Очередь;
	
КонецФункции

Сравним обе реализиции приоритетной очереди по скорости:

Строка кода	10 000 элементов		50 000 элементов		100 000 элементов
Строка кода	Время чистое	%	Время чистое	%	Время чистое	%
Приоритетная очередь (таблица значений)	1,1063	35,81	6,100376	37,26	12,214519	37,28
Очередь = Новый Структура;	0,000014	0,00	0,000013	0,00	0,000014	0,00
Очередь.Вставить("Отсортировано", Истина);	0,000023	0,00	0,000022	0,00	0,000022	0,00
Очередь.Вставить("Данные", Новый ТаблицаЗначений);	0,000025	0,00	0,000023	0,00	0,000024	0,00
Очередь.Данные.Колонки.Добавить("Значение");	0,000049	0,00	0,000071	0,00	0,000046	0,00
Очередь.Данные.Колонки.Добавить("Приоритет", Новый ОписаниеТипов("Число"));	0,000049	0,00	0,000049	0,00	0,000048	0,00
Очередь.Данные.Колонки.Добавить("Позиция", Новый ОписаниеТипов("Число"));	0,00004	0,00	0,000041	0,00	0,000041	0,00
Очередь.Вставить("Позиция", 0);	0,000014	0,00	0,000014	0,00	0,000014	0,00
Очередь.Отсортировано = Ложь;	0,059319	1,92	0,296483	1,81	0,599376	1,83
НоваяСтрока = Очередь.Данные.Добавить();	0,128262	4,15	0,758155	4,63	1,073491	3,28
НоваяСтрока.Значение = Значение;	0,066091	2,14	0,332992	2,03	0,672613	2,05
НоваяСтрока.Приоритет = Приоритет;	0,060047	1,94	0,305085	1,86	0,610112	1,86
НоваяСтрока.Позиция = Очередь.Позиция + 1;	0,098084	3,17	0,461481	2,82	0,903573	2,76
Очередь.Позиция = НоваяСтрока.Позиция;	0,060872	1,97	0,298918	1,83	0,616223	1,88
Данные = Очередь.Данные;	0,06077	1,97	0,305511	1,87	0,603819	1,84
Если Не Очередь.Отсортировано Тогда	0,050897	1,65	0,252758	1,54	0,499659	1,52
Очередь.Отсортировано = Истина;	0,000004	0,00	0,000005	0,00	0,000004	0,00
Данные.Сортировать("Приоритет, Позиция");	0,127592	4,13	1,042711	6,37	2,588318	7,90
КонецЕсли;	0,029566	0,96	0,148514	0,91	0,290742	0,89
Значение = Данные[0].Значение;	0,10961	3,55	0,583075	3,56	1,152302	3,52
Данные.Удалить(0);	0,142949	4,63	0,738205	4,51	1,485553	4,53
Возврат Очередь.Данные.Количество() = 0;	0,112023	3,63	0,57625	3,52	1,118525	3,41

Приоритетная очередь (список значений)	1,983387	64,19	10,273666	62,74	20,553372	62,72
Очередь = Новый Структура;	0,000016	0,00	0,000016	0,00	0,000025	0,00
Очередь.Вставить("Отсортировано", Истина);	0,000022	0,00	0,000023	0,00	0,000024	0,00
Очередь.Вставить("Данные", Новый СписокЗначений);	0,000019	0,00	0,000019	0,00	0,000019	0,00
Очередь.Вставить("ФорматнаяСтрокаПриоритета", "ЧЦ=" + РазрядностьПриоритета + "; ЧН=; ЧВН=; ЧГ=0");	0,000063	0,00	0,000052	0,00	0,000051	0,00
Очередь.Вставить("ФорматнаяСтрокаПозиции", "ЧЦ=16; ЧН=; ЧВН=; ЧГ=0");	0,000014	0,00	0,000014	0,00	0,000014	0,00
Очередь.Вставить("Позиция", 0);	0,000014	0,00	0,000014	0,00	0,000014	0,00
Очередь.Отсортировано = Ложь;	0,056188	1,82	0,284132	1,74	0,560949	1,71
Очередь.Позиция = Очередь.Позиция + 1;	0,104786	3,39	0,443424	2,71	0,866142	2,64
ПриоритетСтрока = Формат(Приоритет, Очередь.ФорматнаяСтрокаПриоритета)+ Формат(Очередь.Позиция, Очередь.ФорматнаяСтрокаПозиции);	0,951056	30,78	4,927951	30,10	9,781007	29,85
Очередь.Данные.Добавить(Значение, ПриоритетСтрока);	0,125726	4,07	0,630631	3,85	1,257842	3,84
Данные = Очередь.Данные;	0,052208	1,69	0,261573	1,60	0,51975	1,59
ИндексПоследнегоЭлемента = Данные.Количество() - 1;	0,092614	3,00	0,508852	3,11	0,949622	2,90
Если Не Очередь.Отсортировано Тогда	0,049787	1,61	0,239129	1,46	0,478487	1,46
Очередь.Отсортировано = Истина;	0,000005	0,00	0,000005	0,00	0,000005	0,00
Данные.СортироватьПоПредставлению(НаправлениеСортировки.Убыв);	0,1789	5,79	1,101879	6,73	2,400442	7,33
КонецЕсли;	0,027553	0,89	0,134654	0,82	0,271737	0,83
Значение = Данные[ИндексПоследнегоЭлемента].Значение;	0,069322	2,24	0,344562	2,10	0,690922	2,11
Данные.Удалить(ИндексПоследнегоЭлемента);	0,159925	5,18	0,774589	4,73	1,612728	4,92
Возврат Очередь.Данные.Количество() = 0;	0,115169	3,73	0,622147	3,80	1,163592	3,55

Итого	3,089687	100,00	16,374042	100,00	32,767891	100,00

Важное замечание - метод сортировки во всех случаях запускался 1 раз. Сначала набиралась очередь до нужного количества элементов (10 000, 50 000 или 100 000), а потом при при первом получении происходила сортировка. Как видим, что сортировка занимает не мало времени.

У списка значений большую часть времени зняло вычисление проиоритета - перевода чисел в строку. При тестировнии я не указывал разрядность и она по умолчанию была 16, т.е. длина сортировочной строки была 32 символа (16 приоритет и 16 позиция в очереди). В тестируемых примерах я мог указать разрядность 6 и тогда сортировочная строка была бы 12 символов, что, в свою очередь, должно положительно сказаться на сортировке (а может еще и на вычислении приоритетной строки).

ПС: тесты проводились на платформе 1С 8.3.10 в файловом режиме и на процессоре Core 2 Duo 2,33GHz. И соответственно, при тестировании на другом компьютере чистое время будет другим, но процентное соотношение должно остаться прежним.

ПСС: Конструктивная критика приветствуется.

Обновлено: избавился в коде от конструкции Попытка - Исключение. Считаю, что проверка на пустую коллекцию лишняя, потому как у каждой структуры данных есть метод Пустой(), которым и должен пользоваться разработчик.

абстрактная структура данных стек очередь приоритет приоритетная приоритетом

+92 –

См. также

Загрузка табличного документа в таблицу значений. Пять строк кода, которые изменили мир

Универсальные функции Программист Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Благодаря этим пяти строчкам можно больше не заморачиваться с загрузкой из внешних файлов. Пользуюсь везде, всегда и постоянно.

21.05.2024 20126 dimanich70 81

144

Генерация штрихкода и QR, разбор настроек и примеры

БСП (Библиотека стандартных подсистем) Сканер штрих-кода Универсальные функции Этикетки, ценники Программист Бизнес-аналитик Конфигурации 1cv8 Бесплатно (free)

Разберем на примерах использование компоненты из БСП для генерации штрихкода и матричных кодов.

15.09.2023 18292 YA_418728146 9

119

Валидация JSON через XDTO (включая массивы)

WEB-интеграция Универсальные функции Механизмы платформы 1С Программист Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

При работе с интеграциями рано или поздно придется столкнуться с получением JSON файлов. И, конечно же, жизнь заставит проверять файлы перед тем, как записывать данные в БД.

28.08.2023 14732 YA_418728146 7

166

Печать непроведенных документов для УТ, КА, ERP. Настройка печати по пользователям, документам и печатным формам

Пакетная печать Печатные формы Адаптация типовых решений Универсальные функции Платформа 1С v8.3 1С:ERP Управление предприятием 2 1С:Управление торговлей 11 1С:Комплексная автоматизация 2.х Россия Абонемент ($m)

Расширение для программ 1С:Управление торговлей, 1С:Комплексная автоматизация, 1С:ERP, которое позволяет распечатывать печатные формы для непроведенных документов. Можно настроить, каким пользователям, какие конкретные формы документов разрешено печатать без проведения документа.

2 стартмани

22.08.2023 3580 56 progmaster 8

Расширение: Быстрые отборы через буфер [Alt+C] Копировать список, [Alt+V] Вставить список, [Ctrl+C] Копировать из файлов

Инструментарий разработчика Универсальные функции Платформа 1С v8.3 Конфигурации 1cv8 1С:Розница 2 1С:ERP Управление предприятием 2 1С:Бухгалтерия 3.0 1С:Управление торговлей 11 1С:Комплексная автоматизация 2.х 1С:Зарплата и Управление Персоналом 3.x Абонемент ($m)

Копирует в буфер значения из списков, из ячеек отчетов, таблиц, настроек списков, других отборов и вставляет в выбранную настройку отбора. Работает с Объект не найден. Работает как в одной так и между разными базами 1С. Использует комбинации [Alt+C] Копировать список, [Alt+V] Вставить список. Также для копирования данных используется стандартная [Ctrl+C] (например из открытого xls, mxl, doc и т.п. файла скопировать список наименований)

1 стартмани

13.10.2022 18478 171 sapervodichka 112

135

Система контроля ведения учета [БСП]

Универсальные функции Механизмы типовых конфигураций БСП (Библиотека стандартных подсистем) Программист Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

В данном материале рассмотрим типовой алгоритм подсистемы контроля учета БСП в конфигурациях на примерах.

18.07.2022 8371 quazare 8

111

Хитрости СКД. Часть 3

СКД Универсальные функции Программист Стажер Платформа 1С v8.3 Система компоновки данных Конфигурации 1cv8 Бесплатно (free)

Столкнулся с тем, что мне приходится писать гору отчетов. Во многих приходится использовать повторяющиеся приемы. Решил написать шпаргалку, которая, надеюсь пригодится не только мне. В этой статье: Объединение ячеек в отчете только на определенном уровне иерархии, Постобработка итогов в табличном документе, Скрытие колонок в зависимости от количества месяцев в периоде.

28.05.2022 10436 milkers 11

Модули общего назначения - готовые полезные функции и процедуры конфигураций на БСП

Универсальные функции БСП (Библиотека стандартных подсистем) Программист Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

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

25.04.2022 19170 quazare 11

139

Отзывы

31. herfis 513 25.06.19 09:35 Сейчас в теме

По классике, приоритетная очередь реализуется на двоичном дереве, уложенном в непрерывный участок памяти (обычный массив) и не требует явной сортировки. Операции добавления и удаления элементов в него осуществляются путем "всплытия" и "погружения" элементов дерева, которые выполняются за O(log N) и при этом как бы автоматически сохраняется нужный порядок элементов. Т.н. сортирующее дерево. Как красно-черное дерево, только намного проще в реализации за счет того, что и требования к приоритетной очереди более простые. И в этом прелесть этой структуры данных. С одной стороны - она относительно простая. С другой - чрезвычайно эффективна по производительности и ресурсам.

Ответить

36. herfis 513 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);
		Сообщить(СЧ);
		ДобавитьЭлемент(СЧ);
	КонецЦикла;
КонецПроцедуры

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

ПриоритетнаяОчередь = Новый Массив;

Показать

Ответить

37. herfis 513 25.06.19 13:48 Сейчас в теме

Еще одна прикольная особенность такой реализации - расходы на "сортировку" делятся между помещением элемента в очередь и извлечением элемента из очереди. Каждый момент времени гарантируется только, что корневой элемент является максимальным/минимальным. Чтобы получить всю последовательность в отсортированном виде необходимо выполнить процедуру по извлечению всех элементов из очереди (с соответствующей перестройкой дерева в процессе).

45. Alias 176 26.06.19 15:34 Сейчас в теме

(36)
Объясните мне, пожалуйста, ведь это Вы явно не двоичное дерево организовали, верно? Это всё тот же массив. Просто после добавления элемента Вы начинаете всплывать, погружаться и рокироваться элементами чтобы он занял более-менее правильную позицию (первый всегда правильный)?

Но в наше время это называлось просто "методом половинного деления", и выглядело как-то попроще. Вместо погружений-всплытий-рокировок для этого было бы достаточно одной функции, которая будет возвращать номер позиции, куда нужно поместить новый элемент. Как-то так:

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

Показать

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

Вопрос -- зачем тогда сложности? Только ради быстрой инициализации -- в каких-то системах возможно и имеет смысл (ценой общего увеличения времени!). Но для 1С, если смотреть на общее количество кода и общее время выполнения -- лучше как проще и быстрее.

Прикрепленные файлы:

ТестПриоритетнаяОчередь.epf

46. herfis 513 26.06.19 16:17 Сейчас в теме

(45)

ведь это Вы явно не двоичное дерево организовали, верно? Это всё тот же массив.

Нет, это именно двоичное дерево, несмотря на то, что оно в массиве :)
"Всплытие" и "погружение" элементов происходит именно "по дереву", между дочерними и родительскими элементами.
Ессно в 1С это решение не претендует на эффективность. Это просто модель "настоящей" низкоуровневой реализации priority queue, выполненная средствами 1С. Я поэтому и писал в (30) и продублирую здесь:

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

Остальные комментарии

Подписаться на ответы Инфостарт бот

Свернуть все

1. ArchLord42 83 24.06.19 13:20 Сейчас в теме

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

Показать

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

6. RonX01 325 24.06.19 13:57 Сейчас в теме

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

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

Показать

7. TODD22 19 24.06.19 14:16 Сейчас в теме

(6)

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

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

8. RonX01 325 24.06.19 14:27 Сейчас в теме

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

21. for_sale 976 24.06.19 21:14 Сейчас в теме

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

9. for_sale 976 24.06.19 17:19 Сейчас в теме

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

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

12. RonX01 325 24.06.19 20:38 Сейчас в теме

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

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

13. for_sale 976 24.06.19 20:40 Сейчас в теме

(12)

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

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

19. RonX01 325 24.06.19 21:04 Сейчас в теме

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

22. for_sale 976 24.06.19 21:15 Сейчас в теме

(19)

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

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

Показать

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

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

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

// если немогут или неважно
Знч = Стек_Взять(Стек);

Показать

23. RonX01 325 24.06.19 21:23 Сейчас в теме

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

24. leemuar 21 25.06.19 01:11 Сейчас в теме

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

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

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

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

Показать

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

27. RonX01 325 25.06.19 07:29 Сейчас в теме

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

40. ltfriend 25.06.19 19:43 Сейчас в теме

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

Функция Стек_ВзятьБезУдаления(Стек)
   
    Возврат Стек[ИндексПоследнегоЭлемента];

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

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

Показать

41. for_sale 976 25.06.19 20:23 Сейчас в теме

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

42. RonX01 325 26.06.19 06:02 Сейчас в теме

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

11. MikeI 73 24.06.19 20:37 Сейчас в теме

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

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

14. RonX01 325 24.06.19 20:45 Сейчас в теме

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

15. MikeI 73 24.06.19 20:47 Сейчас в теме

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

16. MikeI 73 24.06.19 20:49 Сейчас в теме

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

18. RonX01 325 24.06.19 21:03 Сейчас в теме

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

17. RonX01 325 24.06.19 20:55 Сейчас в теме

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

25. kuzyara 2090 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 325 25.06.19 07:09 Сейчас в теме

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

36. herfis 513 25.06.19 13:29 Сейчас в теме

&НаКлиенте
Перем ПриоритетнаяОчередь;

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

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

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

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

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

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

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

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

ПриоритетнаяОчередь = Новый Массив;

Показать

Ответить

43. RonX01 325 26.06.19 06:09 Сейчас в теме

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

44. herfis 513 26.06.19 09:36 Сейчас в теме

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

45. Alias 176 26.06.19 15:34 Сейчас в теме

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

Показать

Прикрепленные файлы:

ТестПриоритетнаяОчередь.epf

46. herfis 513 26.06.19 16:17 Сейчас в теме

(45)

ведь это Вы явно не двоичное дерево организовали, верно? Это всё тот же массив.

47. Alias 176 26.06.19 16:33 Сейчас в теме

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

48. herfis 513 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 строится поверх неизменяемых массивов (фактически просто непрерывных кусков памяти) и оптимизирован под минимальное количество перестановок и копирований. Реализовывать ее с помощью динамического массива - это уже смешно. Эти алгоритмы и структуры данных как раз и составляют "потроха" реализации библиотечной функциональности высокоуровневых языков.

49. RonX01 325 27.06.19 06:43 Сейчас в теме

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

66. mity1982 20.06.21 18:10 Сейчас в теме

(36)
(45)
В методе поиска есть рекурсия, на вскидку стек может стать достаточно длинным. Вроде как в 1С его длинна ограничена.

2. VmvLer 24.06.19 13:32 Сейчас в теме

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

3. vadim1011985 101 24.06.19 13:44 Сейчас в теме

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

Ответить

51. ValeriVP 1336 27.06.19 14:54 Сейчас в теме

(3)

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

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

52. vadim1011985 101 27.06.19 15:23 Сейчас в теме

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

53. vadim1011985 101 27.06.19 15:25 Сейчас в теме

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

54. ValeriVP 1336 27.06.19 16:55 Сейчас в теме

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

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

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

55. vadim1011985 101 27.06.19 18:11 Сейчас в теме

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

58. ValeriVP 1336 28.06.19 13:03 Сейчас в теме

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

60. RonX01 325 28.06.19 13:48 Сейчас в теме

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

56. RonX01 325 28.06.19 06:33 Сейчас в теме

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

57. ValeriVP 1336 28.06.19 10:23 Сейчас в теме

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

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

59. RonX01 325 28.06.19 13:37 Сейчас в теме

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

4. boln 1041 24.06.19 13:47 Сейчас в теме

(2)

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

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

5. VmvLer 24.06.19 13:56 Сейчас в теме

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

этот код

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

63. RonX01 325 10.07.19 11:37 Сейчас в теме

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

10. acsent 1203 24.06.19 18:20 Сейчас в теме

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

20. RonX01 325 24.06.19 21:11 Сейчас в теме

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

39. acsent 1203 25.06.19 18:12 Сейчас в теме

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

28. Scorpion4eg 434 25.06.19 07:54 Сейчас в теме

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

29. RonX01 325 25.06.19 08:54 Сейчас в теме

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

30. herfis 513 25.06.19 09:06 Сейчас в теме

31. herfis 513 25.06.19 09:35 Сейчас в теме

Ответить

32. RonX01 325 25.06.19 10:01 Сейчас в теме

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

33. herfis 513 25.06.19 10:26 Сейчас в теме

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

34. herfis 513 25.06.19 10:30 Сейчас в теме

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

35. RonX01 325 25.06.19 11:14 Сейчас в теме

(34) Спасибо

37. herfis 513 25.06.19 13:48 Сейчас в теме

38. comol 5107 25.06.19 15:26 Сейчас в теме

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

50. Jimbo 10 27.06.19 12:45 Сейчас в теме

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

61. new_user 08.07.19 16:53 Сейчас в теме

62. RonX01 325 09.07.19 06:25 Сейчас в теме

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

64. memb3r 04.02.20 08:35 Сейчас в теме

Философский вопрос: почему разработчики 1С не добавили реализацию стека и очереди на уровне платформы, ну или хотя бы на уровне БСП ...

65. AnderWonder 27 05.02.20 10:51 Сейчас в теме

Это все прикольно, но за 10 лет автоматизации упр., бух, складского, финансового учета - ни разу не возникла необходимость ни в одной из этих структур данных.

68. kalyaka 1105 17.04.22 19:59 Сейчас в теме

(65)Это свидетельствует только о том, что все ваши задачи решались в рамках возможностей платформы 1С. Платформа 1С ориентирована на решение предметных задач: автоматизация бизнес-процессов, учета, расчета, документооборота, отчетности. Практически все эти задачи платформа может решать просто на основании декларативного описания из конфигурации.

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

67. splxgf 26.01.22 22:11 Сейчас в теме

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

69. kalyaka 1105 17.04.22 20:00 Сейчас в теме

(67)Для потокобезопасности нужно использовать чистые функции, иными словами каждый поток должен работать со своей копией массива, а результат потом должен собираться в финале.

70. nature2002 14 12.05.23 20:04 Сейчас в теме

Особенно интересно будет, когда комп вырубится или сервер.

Оставьте свое сообщение

E-mail:

Автор:

(RonX01)

Рейтинг: 325

Для получения уведомлений о новых публикациях автора подключите телеграм бот: Инфостарт бот

Публикация:

№ 1079893

Создание 24.06.19 12:40

Обновление 24.06.19 12:40

Статистика:

Просмотры 23673

Загрузки 0

Рейтинг 92

Комментарии 70

Характеристики:

Код открыт Да

Рубрики Математика и алгоритмы Универсальные функции

Кому Программист

Тип файла Нет файла

Платформа Платформа 1С v8.3

Конфигурация Конфигурации 1cv8

Операционная система Не имеет значения

Страна Россия

Отрасль Не имеет значения

Налоги Не имеет значения

Вид учета Не имеет значения

Доступ к файлу Бесплатно (free)