Наш ответ американским лекторам

Публикация № 272646

Разработка - Практика программирования

граф соответствие

Это спойлер к замечательной публикации «Алгоритмы. Часть 1.1. Динамические соединения». Здесь описывается гораздо более быстрый способ решения задачи динамического связывания при отсутствии ограничений на используемые структуры данных

В статье «Алгоритмы. Часть 1.1. Динамические соединения»  рассмотрена интересная задача уточнения сильно связных компонент графа в процессе добавления новых ребер. Приведено и подробно проанализировано целых четыре разных метода. И может сложиться впечатление, что лучший метод решения этой задачи на 1С определен и дальнейшее ускорение решения уже невозможно. Однако оказывается, что это не так. И если использовать подходящие для данной задачи структуры данных языка 1С, то можно получить еще более быстрое решение, которое, возможно,  и нужно использовать на практике.

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

Впрочем, предисловие затянулось. Лучше сразу привести код. Вот он

Процедура Инициализация(ЧислоВершин) Экспорт
	
	Связи = Новый Массив(ЧислоВершин);
	
	Для Этого = 0 По ЧислоВершин - 1 Цикл 
		Связи[Этого] = Новый Соответствие;	
		Связи[Этого].Вставить(Этого)
	КонецЦикла
	
КонецПроцедуры

Процедура Объединить(Ежа, Ужа) Экспорт
	
	Если Связи[Ежа] <> Связи[Ужа] Тогда
		Если Связи[Ежа].Количество() < Связи[Ужа].Количество() Тогда
			Для Каждого Этого Из Связи[Ежа] Цикл	
				Связи[Ужа].Вставить(Этого.Ключ);
				Связи[Этого.Ключ] = Связи[Ужа]
			КонецЦикла
		Иначе
			Для Каждого Этого Из Связи[Ужа] Цикл	
				Связи[Ежа].Вставить(Этого.Ключ);
				Связи[Этого.Ключ] = Связи[Ежа]
			КонецЦикла
		КонецЕсли
	КонецЕсли
	
КонецПроцедуры

Функция ОбъектыСоединены(Ёж, Уж) Экспорт
	
	Возврат Связи[Ёж] = Связи[Уж]
	
КонецФункции

Как и в исходном решении, объекты идентифицируются числами. Для их обработки используется массив Связи, в котором каждому объекту сопоставлен элемент с соответствующим номером. Каждый элемент массива хранит ССЫЛКУ на соответствие, которое содержит номера объектов, связанных с этим элементом.

Чтобы проверить, что объекты А и Б входят в одну компоненту связности, достаточно убедиться, что Связи[А] = Связи[Б]. – Наглядно, не правда ли?

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

Если нет, то все номера, связанные с "ежом" из левого соответствия Связи[Ежа], добавляются к правому соответствию Связи[Ужа], а перечисленные элементы массива заменяются на элемент Связи[Ужа].

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

Обратите внимание на присваивание соответствий, которое производится не путем создания копии соответствия, а копированием ССЫЛКИ. Для понимания этого процесса попробуйте предположить, что будет выведено в окно сообщений при выполнении вот такого фрагмента кода:

Трус = Новый Соответствие;
	
Трус["Крик"] = "Ой, мама!";
	
Балбес = Трус;
	
Балбес["Крик"] = "Ура!";
	
Сообщить(Трус["Крик"])

Если вашим предположением было «Ура!», то можете читать дальше, поверив, что «this is not a bug, this is a feature», как сказал бы американский преподаватель. Еще один тонкий момент - это подмена коллекции внутри цикла по элементам этой коллекции. В том, что это работает, убедимся, проверив работу следующего фрагмента кода:

ВотЭтоДа = Новый Соответствие;
	
ВотЭтоДа.Вставить("Вот");
ВотЭтоДа.Вставить("это");
ВотЭтоДа.Вставить("да!");
	
Для Каждого Этого Из ВотЭтоДа Цикл
		
	ВотЭтоДа.Очистить();
	Сообщить(Этого.Ключ)
		
КонецЦикла

На Фиг.1 изображена схема метода. Показано, что происходит, если при существующих двух компонентах связности {a, b, c} и {d, e} добавляется связь (a, d). Очевидно, компоненты объединяются, а ссылки в ячейках d и e переопределяются общей ссылкой.

Схема метода 

Проверка быстродействия предлагаемого подхода показывает более чем двукратное ускорение решения задачи. Посмотрите график на Фиг.2.

График быстродействия

Предлагаемый вариант обозначен цифрой 1 и показан на графике красным. Выше него идет самый быстрый метод из исходной статьи.

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

Выводы заключаются в том, что

  1. Если требуется работать с графами, очень удобным и эффективным является использование коллекции "соответствие";
  2. При максимизации быстродействия не стоит забывать о втором слагаемом формулы "программы = алгоритмы + структуры данных".

Скачать файлы

Наименование Файл Версия Размер
НашОтвет.epf

.epf 10,49Kb
6
.epf 10,49Kb 6 Скачать

Специальные предложения

Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. Synoecium 712 14.04.14 16:02 Сейчас в теме
Немного покритикую.
"Посмотрите график на Фиг.2." - где подписи к рисункам по которым можно понять, что это Фиг.2 а не Фиг.3
По графику на Фиг.2, как измерялось быстродействие алгоритмов? Что означает максимальный балл - 700?
Что вообще за варианты 2,3,4,5, с которыми вы сравниваете свой вариант 1? Хотя вы приводите ссылку на статью из которой берутся алгоритмы для анализа, может стоит парой предложений охарактеризовать каждый алгоритм.
На графике отчетливо видны только красная и синяя линии, остальные сливаются в линию цвета морской волны, может хотя бы словами опишите асимптотику кривых, которые не разобрать на рисунке.

А соответствия да, хорошая штука)
адуырщдв; +1 Ответить
2. ildarovich 7194 14.04.14 16:58 Сейчас в теме
(1) Приветствую любую критику, спасибо.
Подписи к рисункам появляются при наведении на них мышкой, но будут сделаны и под рисунками.
Максимальный балл - это 700 миллисекунд. То есть в самом сложном из проверенных случаев массив содержал 1600 вершин и 3200 ребер, алгоритмом 5 из исходной статьи был обработан за примерно 640 миллисекунд, а предлагаемым - за 270 миллисекунд (от 249 до 281, если точнее).
Ссылка на статью приведена в самом начале моей статьи. Это «Алгоритмы. Часть 1.1. Динамические соединения». Оттуда же взята программа построения графика. То есть я просто подставил свой алгоритм на место первого алгоритма в конфигурацию из исходной статьи. Я не рисовал график с нуля, чтобы добиться максимального сходства и возможности сопоставления с графиком из исходной статьи. Оттуда же покрашенная цветом морской волны ось абсцисс и лишние в данном случае элементы легенды.
Алгоритмы 2, 3, 4 в данном случае роли не играют. Они заведомо медленнее алгоритма 5. А алгоритм 5 называется в исходной статье "Быстрое объединение с оценкой веса и сжатием пути".
Все замечания постараюсь исправить при ближайшем обновлении статьи.
Euroset1; адуырщдв; +2 Ответить
5. адуырщдв 28 14.04.14 19:47 Сейчас в теме
(2)
4 в данном случае роли не играют. Они заведомо медленнее алгоритма 5.

В взвешенных алгоритмах выйгрыш благодаря использованию сжатия пути однако спорен, а точнее незаметен. Так что методы 3 и 5 равнозначны. чтоб там не говорили принстонские светилы.
Если измерять время до полной связности, то тут есть элемент случайности и сравнивать методы будет сложнее. Чтобы Вам не нужно было тратить "инфобакс", прилагаю обработку к этому сообщению.

Спасибо. Ну для N 100000, M где то 1,5 лимона будет для взвешенного объединения, независимо от метода сжатия пути. Хотя понятно, что без гарантии.
12. agrustny 19 16.04.14 10:18 Сейчас в теме
(2) Уважаемый профессор, объясните, пожалуйста, почему программа на 1С выполняется в 47 раз медленнее, чем на Си? Ваше мнение: каков вклад в ln(47) различных элементов, фигурирующих между компилятором Си и интерпретатором 1С?
14. ildarovich 7194 16.04.14 12:12 Сейчас в теме
(12) Не возьмусь здесь отвечать на этот вопрос, чтобы не уходить от темы сравнения АЛГОРИТМОВ.
Можно спросить на форуме. Тот, кто изучал работу 1С "изнутри" каким-либо дизассемблером или дебаггером (вообще-то 1С это не приветствует), наверное, сможет точнее определить состав накладных расходов, сопровождающих интерпретацию программы на 1С.
Но если вопрос философский, то можно пройтись по ссылкам типа http://subscribe.ru/archive/hitech.kon.ittechnology/201402/11234715.html или http://habrahabr.ru/post/90942/. Видно, что 1С это не самый "гадкий утенок" среди других языков программирования. Python, Perl, PHP, Ruby так же сильно отстают по быстродействию от Си. Просто используется другой, более высокий, приближенный к предметной области уровень абстракции. За это приходится платить быстродействием.
18. agrustny 19 16.04.14 16:08 Сейчас в теме
(14) Профессор, речь идет об АЛГОРИТМАХ. 1С - это самый гадкий утенок, хуже него, согласно предложенному Вами источнику http://subscribe.ru/archive/hitech.kon.ittechnology/201402/11234715.html, только Ruby, но он в танкена рельсах. Вы считаете великим достижением двукратное увеличение скорости за счет использования "правильных" структур данных? А Вы не задумывались о том, что в другой системе, производительность которой может быть на порядок больше или меньше 1С, "правильными" окажутся другие структуры? Если Вы хотите доказать производительность - доказывайте ее параметрически, или же конкретно рассчитывая флопы. А еще лучше - не морочьте людям голову, поскольку время исполнения любой программы 1С, написанной для дела, а не для развлечения, упирается в семиэтажные запросы, в которых используются составные типы данных, неявные соединения через точку и "виртуальные" таблицы регистров накопления, которые сами являются вложенными запросами (на фоне нехилого объема регистров, содержащих всю историю, часть из которой может быть нужна лишь теоретически). В таких условия оптимизировать интерпретатор с ln(47) до ln(7), конечно, никто не будет. Все равно придет Вася, сделает запрос в каждом ПриВыводеСтроки(), и все будут балдеть;). Ну, по минималке итоги ДинамоСписка в УФ через СКД дублированием запроса. Короче, страшно далеки они от народа...
19. ildarovich 7194 16.04.14 16:43 Сейчас в теме
(18) Уважаемый agrustny, я не считаю великими достижениями двукратное увеличение скорости за счет использования "правильных" структур данных. Но если в 1С Вам потребуется решать задачу на графах, благодаря этой статье Вы, возможно, вспомните о соответствиях. При их использовании при решении этих задач на 1С (а такая необходимость встречается даже в типовых) получается гибкий, выразительный и быстрый код. Я лишь хотел это еще раз показать. Меня насторожило то, что один из читателей в комментарии http://forum.infostart.ru/forum24/topic108120/message1113541/#message1113541 захотел применить массивы в задаче определения множества аналогов номенклатуры, когда соответствие подходят лучше и решают задачу быстрее. Разницу в отклике 700 или 250 миллисекунд оператор уже чувствует.
Я задумывался о том о том, что в другой системе, производительность которой может быть на порядок больше или меньше 1С, "правильными" окажутся другие структуры, о том, каковы потребности в памяти моего алгоритма, о том, какова идеальная структура данных для решения этой задачи, об измерении производительности в количестве операций чтения и записи и о много чем еще, но в статью поместить всего этого не получилось. Не счел эту задачу на сейчас достаточно актуальной, чтобы тратить время.
Морочить людям головы я не стремился, и что оптимизировать нужно только то, что реально плохо (APDEX) я из своей практики знаю. И вот, например, в работе Неоплаченные долги при распределении оплаты по правилу ФИФО одним запросом и намного быстрее, чем Вы думали я именно так и делал. А почему этого никто не сделал (привел к линейной зависимости эти вычисления) раньше? Как Вы думаете?
Redokov; agrustny; +2 Ответить
20. agrustny 19 17.04.14 10:51 Сейчас в теме
(19) Я думаю, что никто этого не сделал раньше из-за отсутствия в персональной БД следующих документов:
1) ЗаказНаПроизводство
2) ИнтересКПроблеме
3) ВыдающийсяТалант
In other words, Вася, безжалостный и беспощадный, рулит вовсю.
Профессор, если уж такое дело, не дадите на опохмелиться посмотрите мою студенческую работу http://infostart.ru/public/273699/
21. agrustny 19 18.04.14 10:00 Сейчас в теме
(19) Благодарю за пиво без водки деньги на ветер высокую оценку студенческой работы! Пришла вот еще какая-мысль в голову: на обсуждаемых графиках быстродействия http://subscribe.ru/archive/hitech.kon.ittechnology/201402/11234715.html отсутствует очень важный инструмент! Да-да, SQL как таковой. Ведь это же язык-интерпретатор, и в этом смысле действительно любопытно, где он на этой шкале между Си (=1 by definition) и 1С (\approx 50 from estimation (9)).
3. адуырщдв 28 14.04.14 17:16 Сейчас в теме
1) Synoecium, рисунок непонятный как и в предыдущей теме, наверное чтоб понять надо скачать обработку за инфобакс. Видать авторы так задумали :)
Была б интересна, и наглядней, просто цифра(-ы), оценка времени затрачиваемого на решение "случайных" задач. Например, для N=100000, случайные (M их кол-во) соединения генерируются до тех пор пока все N объектов не оказываются связанными. Соотвественно в сравнении. :)
4. ildarovich 7194 14.04.14 17:36 Сейчас в теме
(3) Прилагаемая к статье обработка именно что для заданного числа вершин генерирует СЛУЧАЙНЫЕ дуги, но в конце концов определяет компоненты сильной связности (можно нажать Проверка, чтобы их увидеть). Определяет в зависимости от выбранного метода (0 - исходный, 1 - предлагаемый). Если измерять время до полной связности, то тут есть элемент случайности и сравнивать методы будет сложнее. Чтобы Вам не нужно было тратить "инфобакс", прилагаю обработку к этому сообщению.
Прикрепленные файлы:
НашОтвет.epf
starik-2005; адуырщдв; +2 Ответить
6. dyak84 15.04.14 12:55 Сейчас в теме
Все хорошо все понятно все наглядно, но название не по феншую причем здесь политика. Если человек умный и говорит по существу то какая разница кто он по национальности?????????????
7. адуырщдв 28 15.04.14 13:17 Сейчас в теме
(6) dyak84, Думаю автор как бы намекает Роберту Сэджвику и компании.... В первых (80-е годы) его "Алгоритмах...." был (если не изменяет память) использован для написания программ паскаль, потом были издания где использовались кресты, а сейчас принстонцы используют жабу . А надо бы использовать внутренний язык 1С Предприятия. ;)
16. dyak84 16.04.14 12:19 Сейчас в теме
(7)Спасибо за детальное обяснение, а то на фоне последних собитиий везде черты мерещатся
8. ildarovich 7194 15.04.14 13:22 Сейчас в теме
(6) Задиристое название выбрано специально для привлечение внимания. Это юмор. Юмор в стиле "А в Москве все эти штаты уж разбиты на квадраты/Кнопка красная одна/Лишь нажмешь и им хана/Это обороны меры/Это наши инженеры/Постарались для ребят/Для мышат и медвежат". Из этой же серии фотография Дианы Вишневой в качестве картинки к анонсу ("а также в области балета мы впереди планеты всей").
Очень удачно получилось, что в нашем отечественном 1С есть средства, позволяющие решить задачу быстрее, чем показано в этой не нашей лекции.
Кстати, в Java вообще-то тоже есть HashMap - аналог нашего соответствия (правда, в данной задаче соответствие скорее используется как HashSet). И вполне возможно, когда-то позже по тексту лекций разговор может вернуться к этой задаче с использованием других структур данных.
9. адуырщдв 28 15.04.14 15:17 Сейчас в теме
(8)
И вполне возможно, когда-то позже по тексту лекций разговор может вернуться к этой задаче с использованием других структур данных.

Вполне, обычно возвращаются в виде задач, типа перепишите. Алгоритм то трёхкопеечный, не стоит включения тяжелой артилерии. К тому ж, в Си 1600 вершин и 3200 ребер у меня отработало 16 миллисекунд с инициализацией (в отличии от "нашего ответа" который крутился аж 750 мс).
Прикрепленные файлы:
main.c
10. адуырщдв 28 15.04.14 16:16 Сейчас в теме
хе, хе быстрый поиск, квадратичный алгоритм, в си, для тех же параметров - 31 мс
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 1600
#define M 3200

int main()
{
int i, p, q, id[N],arM,t ;
srand(time(NULL));
for (i = 0; i < N; i++) id[i] = i;
for (arM=0;arM<M;arM++)
{
p=rand()%N; q=rand()%N;
t = id[p];
if (t == id[q]) continue;
for (i = 0; i < N; i++)
if (id[i] == t) id[i] = id[q];

 }
  return 0;
}
Показать

Кто померяет в Jave?
11. ildarovich 7194 15.04.14 16:34 Сейчас в теме
(10) А смысл? - Ведь в статьях сравнивались не языки, платформы и прочее, а алгоритмы. Ясно, что на ассемблере будет еще быстрее. На Си можно еще битовые строки попробовать. Можно и на графическом ускорителе эту же задачу решать.
Мне было бы интереснее сравнить эти алгоритмы в Java на массивах с Java на HashSet. Хотя пример и задача довольно абстрактные и рыть тут в глубину, наверное, не стоит.
13. адуырщдв 28 16.04.14 11:15 Сейчас в теме
(11)
А смысл?

Обязательно нужен? :) А тогда вообще, есть ли смысл учить алгоритмы "с реализацией примеров на 1С", к тому ж в "вольном" переводе, переводе даже не соответвующей книги, а просто лекций???
15. ildarovich 7194 16.04.14 12:15 Сейчас в теме
(13) Видимо, смысл
учить алгоритмы "с реализацией примеров на 1С", к тому ж в "вольном" переводе, переводе даже не соответвующей книги, а просто лекций???
есть. Об этом говорит высокая популярность исходной статьи у читателей.
17. адуырщдв 28 16.04.14 12:41 Сейчас в теме
(15) Оптимистично. :) Ну чтож, тогда остаётся ждать появления экпертов в algorithm design and analysis, выучившихся таким способом.
22. mikuho 91 20.04.14 07:27 Сейчас в теме
Спасибо! не все конечно понятно, но то что хотел - освоил
23. Yashazz 3636 20.04.14 15:00 Сейчас в теме
Вот всё мне в изложенном нравится, кроме одного: коллекция "Соответствие" не совместима напрямую ни со списками, ни с массивами, ни с таблицами значений, ни тем более с выборками запросов или результатами Построителей/СКД. Поэтому очень многое насчёт соответствий, к сожалению, сферический кодинг в вакууме, т.к. потеря времени на заполнение соответствия иногда бывает трудно соизмерима с выигрышем скорости при его последующем чтении.
А главное, и извратные способы медленны, и заполнение циклом тоже. Вот кабы можно было, например, скопом заполнить всё соответствие из двуколоночной таблицы или из списка, или ещё откуда, но... Увы нам.
artbear; ildarovich; agrustny; +3 Ответить
24. ksuman 21.04.14 15:58 Сейчас в теме
Причем тут алгоритмы и пример использования структуры 1С "Соответствие"?
Алгоритмы - это простейшие операции, которые мы можем наблюдать и контролировать, а когда задача выполняется с помощью библиотек процедур, функций, классов и объектов - это не алгоритм, а иная реализация. Пытаться унизить американцев или блеснуть своим аналитическим мышлением в данном случае - плохая идея. Все равно, что к изобретению колеса добавить открытие каучука: принцип действия не меняется.
Вот, если бы вы для применения к данной задаче использовали открытый массив с индексом с описанием метода поиска в рамках этой задачи, это было бы ответом.
25. ildarovich 7194 21.04.14 16:33 Сейчас в теме
(24) Устал повторять, но не будьте, пожалуйста, так буквальны в понимании названии статьи. Я рассчитывал на читателей с чувством юмора. Вы прочитали комментарий (8)?
В самой статье я говорю не об алгоритмах, а о решении той же задачи. О том, что
При максимизации быстродействия не стоит забывать о втором слагаемом формулы <программы = алгоритмы + структуры данных>.
Я просто-напросто, читая статью, подумал о том, как можно решить эту задачу на 1С. Попробовал использовать соответствие, поскольку применял его раньше в решении задач на графах, и получил в два с половиной раза более быстрое решение задачи, чем у автора исходной статьи. Мне показалось, что это решение будет интересным и поучительным. Вы так не считаете?
26. ЧИА 164 22.11.14 08:54 Сейчас в теме
применение специфики платформы для ускорения - не панацея

в бытность свою студентом (80-90-е)
писал на турбопаскале программу рендзю, в ЧМ участвовала
а для увеличения производительности делал ассемблерные вставки, ручками данные между регистрами распределял
так вот -
1. муть это все. ибо при переделки базовых алгоритмов приходилось смотреть на эти вставки и думать - выкинуть или написать новые. не продуктивно, особенно если есть другие занятия
2. а переделки именно алгоритмов и структур хранения данных о позициях давала ускорение в 5-20 раз, тогда как применение ухищрений - раза в 2-4
3. так что мой совет - читайте Кнута, это полезнее
27. ildarovich 7194 22.11.14 14:43 Сейчас в теме
(26) ЧИА, кажется, вы слишком поверхностно отнеслись к содержанию статьи и в итоге "отгадали все буквы, но не смогли назвать слова".
Ассемблерные вставки это совсем не то же самое, что использование соответствия. Ассемблерные вставки не меняют вид зависимости в оценке трудоемкости программы, а только меняют коэффициент в формуле этой оценки. Они здесь не при чем.
Использование соответствия проходит по пункту "переделки алгоритмов и структур хранения данных". По второй части этого пункта.
Если еще помните работы Дональда Кнута, то у него там была такая машина MIX. В томе 1 в разделе 1.3.1 на странице 180 советского издания (оно сейчас стоит у меня на полке) написано, что каждой операции машины MIX приписывается время выполнения, типичное для современных машин. Современность там - 1968 год. Это наш перевод вышел в 1976 году.
У нас сейчас 2014 год и не MIX, а 1С. У нее своя таблица времени выполнения отдельных операций. И моя мысль в том, что при реализации и сравнительном анализе алгоритмов на 1С нужно использовать именно эту таблицу, которая вовсе не mixed.
28. ЧИА 164 22.11.14 20:35 Сейчас в теме
(27)
Если еще помните работы Дональда Кнута
то у него есть четкое разделение, и не в 1, а в 3 томе
глава 6.2 поиск путем сравнения ключей
ваш метод, как я думаю, относится к 6.2.4, Сильноветвящиеся деревья
и именно к конкретной оптимизации под реализацию в 1с
перечитайте
33. ildarovich 7194 25.11.14 14:43 Сейчас в теме
(28) ЧИА, попробую пояснить свою мысль.
Я совсем не против изучения книг Кнута, Сэджвика и прочих. Тем более, что сам большой любитель этой литературы. Я против делания из этого культа и бездумного применения рекомендаций и оценок из этих книг. Нужно понимать, что оценки производительности алгоритмов в книгах делались с оговорками. В расчете на определенную модель вычислителя. Если бы в этом вычислителе применялся, например, какой-нибудь "квантовый сопроцессор", который делал бы сортировку любого массива за один такт работы процессора, то оценки алгоритмов, опирающихся на сортировку, были бы другими. Есть целое направление исследования быстродействия параллельных алгоритмов, где те же классические задачи имеют другие оценки временной сложности.
Так вот, платформа 1С предлагает нам иную модель вычислителя, где оценки относительного времени выполнения элементарных операций отличаются от используемых при анализе классических алгоритмов. Это нужно обязательно учитывать при реализации алгоритмов на 1С. Иначе полученные время выполнения программы на 1С и зависимость времени от размерности задачи просто не совпадет с действительностью, которая одна и является критерием истины, а вовсе не бездумное следование заветам какого-либо классика.
(31) Если идеология менялась - непонятно почему был маленький выигрыш - вы же сами это отметили. Значит, неправильно менялась. Бывает. В случае, описанном в данной статье, это было не так.
(32) Все, что сказано Яковом, совершенно верно, но к данному законченному решению не применимо.
...
Что вы называете муторным? - Посмотрите на текст программы в статье! - Там десяток строчек. Использование соответствия позволило получить и быстрый и выразительный код. Мне кажется, в данном случае вы не стараетесь вникнуть в суть решения, а просто рассуждаете по шаблону.
адуырщдв; +1 Ответить
31. ЧИА 164 22.11.14 21:13 Сейчас в теме
(27)
Ассемблерные вставки это совсем не то же самое, что использование соответствия. Ассемблерные вставки не меняют вид зависимости в оценке трудоемкости программы, а только меняют коэффициент в формуле этой оценки. Они здесь не при чем.
Использование соответствия проходит по пункту "переделки алгоритмов и структур хранения данных". По второй части этого пункта.

к сожалению, вы не застали 286 и его приколы
ассемблерные вставки позволяли пропускать чтение данных из памяти если они уже были в регистрах
или не пушить-попить параметры, а читать напрямую из памяти / возвращать (или не возвращать, если дальше был однозначный расчет, все лежало дальше в регистрах)
и т.д. и т.п.
что именно меняло как саму идеологию хранения данных
так и алгоритмы их обработки
просто уж больно это было муторно
29. ЧИА 164 22.11.14 20:41 Сейчас в теме
Современность там - 1968 год
у меня на полке издание 2000 года
алгоритмы и источники, те, что я заметил, до 1997г (SODA 8), 1998г (SODA 9)
30. ЧИА 164 22.11.14 20:54 Сейчас в теме
Современность там - 1968 год.

и, да, в 3 томе многое минимум от 1970(80,90)+
так что ваши книги немного устарели
32. ЧИА 164 22.11.14 21:18 Сейчас в теме
кроме одного: коллекция "Соответствие" не совместима напрямую ни со списками, ни с массивами, ни с таблицами значений, ни тем более с выборками запросов или результатами Построителей/СКД. Поэтому очень многое насчёт соответствий, к сожалению, сферический кодинг в вакууме, т.к. потеря времени на заполнение соответствия иногда бывает трудно соизмерима с выигрышем скорости при его последующем чтении.

и
что именно меняло как саму идеологию хранения данных
так и алгоритмы их обработки
просто уж больно это было муторно

по моему - одного поля ягоды
34. max1c 23.01.15 18:21 Сейчас в теме
Алгоритм – слегка улучшенный алгоритм «Быстрый поиск». Вместо кода подмножества, используется ссылка на соответствие. При объединении все так же требуется скопировать часть подмножества (улучшение состоит в том, что не нужно сканировать весь массив).
Если объединять (худший случай) два подмножества в каждом из которых N/2 элементов, то это потребует:
- N/2 операций чтения из соответствия (Для Каждого Этого Из Связи[Ежа] Цикл);
- N/2 операций вставки в соответствие (Связи[Ужа].Вставить(Этого.Ключ));
- N/2 операций чтения из массива (…= Связи[Ужа]);
- N/2 операций записи в массив (Связи[Этого.Ключ] =…).

Операция «Связи[Ужа].Вставить(Этого.Ключ);» затратна и, если проанализировать алгоритм, нужна только для вычисления размера подмножества. Это бессмысленно. Быстрее работать с массивом.
Соответствие эффективно для поиска значения по ключу. Здесь вообще нет обращений типа «Связи[][]». Для перебора можно было взять список значений (не требуется проверять уникальность при добавлении, мы ее проверяем на этапе: Связи[Ежа] <> Связи[Ужа]).
35. ildarovich 7194 23.01.15 19:32 Сейчас в теме
(34) max1c,
Это бессмысленно. Быстрее работать с массивом
Вот тут нужны не голословные, а реальные доказательства. Обработку для тестирования можно взять из исходной статьи. Ваша задача проста - создать алгоритм и написать программу, не использующий соответствия, работающий быстрее моего. Кода тут всего ничего. - Попробуйте!

Кстати, соответствие здесь действительно можно заменить списком значений (на этапе построения). Вот только будет ли это быстрее?
Оставьте свое сообщение

См. также

FormCodeGenerator Программная доработка форм. Часть 2 (Режим работы "Режим сравнения форм") на примере ERP 2.5 Промо

Практика программирования Адаптация типовых решений Прочие инструменты разработчика v8 1cv8.cf Абонемент ($m)

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

5 стартмани

21.12.2020    2841    14    huxuxuya    11    

Интерактивная справка по объектам 1С (подключаемое расширение)

Практика программирования Работа с интерфейсом v8 ERP2 Абонемент ($m)

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

3 стартмани

29.09.2020    8748    50    sapervodichka    42    

Конвейер проверки качества кода

Инструментарий разработчика Практика программирования Математика и алгоритмы v8 1cv8.cf Абонемент ($m)

Jenkinsfile для выполнения проверки качества кода. Собирает информацию с АПК, EDT и BSL-LS. Сопоставляет ошибки с гит-репозиторием, выгруженным ГитКонвертором. Отправляет в Сонар.

3 стартмани

04.09.2019    28500    23    Stepa86    46    

Алгоритмы поиска пути в графе

Практика программирования Разработка v8 1cv8.cf Абонемент ($m)

Реализуем алгоритмы поиска пути в графе на платформе 1С 8.3, такие как алгоритм А*, поиск в ширину, жадный поиск, алгоритм Дейкстры и вконце волновой.

1 стартмани

09.07.2019    19183    12    RonX01    10    

Вам нравятся запросы в 1С? Промо

Практика программирования Разработка v8 v8::Запросы 1cv8.cf Абонемент ($m)

Речь не только о том, что простейший запрос с "легальным" оформлением растянется на пол-экрана, речь еще обо всем, что нужно написать "в нагрузку" к тексту запроса. Все эти "Новый Запрос", "УстановитьПараметр" и последующие пляски с обработкой результата... Пора с этим заканчивать!

1 стартмани

03.07.2019    22727    6    m-rv    88    

Работа с публикациями "Инфостарт"

Практика программирования О сообществе WEB v8 УУ Абонемент ($m)

Работа с рублевыми публикациями на сайте "Инфостарт": ведение клиентов, заказов, обновление файлов публикации, рассылка обновлений.

1 стартмани

13.09.2018    23432    13    RocKeR_13    16    

HTTP Сервисы: Путь к своему сервису. Часть 3

Инструментарий разработчика Практика программирования v8 1cv8.cf Абонемент ($m)

Продолжение статьи «HTTP Сервисы: Путь к своему сервису. Часть 2». В предыдущих частях мы использовали только Get, в этой части поговорим о других методах и длительных операциях.

1 стартмани

27.08.2018    42390    63    dsdred    17    

Позиционирование в помещении с помощью нейросети по сигналу Wi-Fi. Интерактивная карта склада в 1С с показом позиции

Инструментарий разработчика Практика программирования v8 Абонемент ($m)

Данная публикация содержит в себе редактор и интерактивную карту склада или иного помещения, на которой в реальном времени отображается позиция устройства, координаты которого вычисляются по уровням сигнала нескольких роутеров Wi-Fi. В статье и приложенным к ней разработкам предлагаются инструменты и методика для реализации вычисления точной геопозиции внутри помещений с помощью нейронной сети. Конфигурация написана на релизе 1С:Предприятие 8.3.12.1412, клиентское приложение имеет минимальный уровень совместимости SDK -16.

5 стартмани

09.08.2018    30251    26    informa1555    26    

ВСТАВИТЬ В Справочник.Номенклатура (Код, Наименование) ЗНАЧЕНИЯ ("001", "Новый товар") Промо

Практика программирования v8 v8::Запросы 1cv8.cf Абонемент ($m)

Вас не обманывают ваши глаза, это запрос на изменение данных! И это работает без прямого доступа к БД, регистрации и смс.

1 стартмани

01.06.2018    32021    88    m-rv    57    

Работа с данными выбора

Практика программирования Работа с интерфейсом v8 Россия Абонемент ($m)

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

1 стартмани

17.07.2018    54114    20    kalyaka    16    

Полезные примеры составления схемы компоновки данных #2

Практика программирования v8 v8::СКД 1cv8.cf Абонемент ($m)

Еще один набор примеров как решить частные задачи в СКД

1 стартмани

22.05.2018    33792    11    SITR-utyos    13    

Печатная форма, сделанная как расширение конфигурации для БП 3.0. Новые возможности БСП

Практика программирования Универсальные печатные формы v8 БП3.0 Абонемент ($m)

Печатные формы на внешних обработках скоро канут в лету. На смену им приходят ПФ, реализованные в виде расширений конфигурации. Не нашел на сайте примеров таких расширений. Привожу пример подобного расширения для БП 3.0.

1 стартмани

06.12.2017    28475    54    kwazi    6    

Заполняем по шаблону (по умолчанию) Промо

Практика программирования v8 v8::УФ 1cv8.cf Абонемент ($m)

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

1 стартмани

08.02.2018    30019    20    mvxyz    17    

Паузы при исполнении кода (Sleep для 1С)

Практика программирования v8 v8::УФ 1cv8.cf Абонемент ($m)

Решил проверить все найденные варианты паузы для 1С. В результате получилась обработка для тестирования и небольшая статья с итогом.

1 стартмани

28.11.2017    52820    13    swimdog    44    

Макет в СКД - пример всех возможных типовых вариантов

Практика программирования Инструментарий разработчика v8 v8::СКД 1cv8.cf Абонемент ($m)

Макет СКД: наглядное представление того, что, как и куда выводится при типовых настройках.

1 стартмани

09.11.2017    23387    77    freelancer    4    

Telegram-боты

Практика программирования v8 Абонемент ($m)

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

1 стартмани

01.09.2017    35685    136    PLAstic    59    

Нечеткий поиск одним запросом Промо

Практика программирования v8 1cv8.cf Абонемент ($m)

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

1 стартмани

28.12.2015    29562    71    vasvl123    9    

Умный дом на 1С + ардуино

Практика программирования v8 Абонемент ($m)

Конфигурация для автоматизации быта программиста 1C и не только. В данной статье будет рассказано, как можно использовать 1С для задач, не входящих в стандартные рамки этой платформы. Например, управление домом. В качестве периферии для подключения будет использован микроконтроллер (МК) Ардуино, но на нём не будет никакой логической нагрузки, весь процесс будет проходить на сервере 1С. Работа с пинами ввода/вывода происходит напрямую из 1С.

1 стартмани

07.08.2017    24433    21    sasha777666    64    

Расширения конфигураций 1С: учимся перехватывать методы

Практика программирования v8 v8::УФ 1cv8.cf Абонемент ($m)

В этой статье я на примерах разберу некоторые механизмы расширений конфигураций 1С. А именно «перехваты» методов модуля объекта и «перехваты» событий формы и элементов формы. Данная статья написана с учебными целями, чтобы показать, как при помощи расширений конфигурации можно делать такие доработки, ради которых раньше приходилось снимать конфигурацию с поддержки.

1 стартмани

30.05.2017    142661    13    signum2009    48    

Регулярные выражения – это просто. Построитель и отладчик регулярных выражений

Инструментарий разработчика Практика программирования v8 1cv8.cf Абонемент ($m)

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

1 стартмани

13.03.2017    33442    117    romasna    49    

1С: Предприятие + корпоративный чат, как наладить оперативные уведомления за 10 минут Промо

Практика программирования v8 Абонемент ($m)

Как сделать автоматические уведомления о разных событиях из 1С в корпоративный чат MyChat для сотрудников компании

1 стартмани

14.08.2016    49974    36    Demanoidos    60    

Распознавание текста с помощью нейросетей Google Cloud Vision и 1С

Практика программирования v8 1cv8.cf Абонемент ($m)

Возможности Google Cloud Vision в распознавании текста.

1 стартмани

08.02.2017    32237    135    kiv1c    18    

Графическая схема. Управление при помощи XDTO.

Практика программирования v8 Абонемент ($m)

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

2 стартмани

16.01.2017    24477    109    Alxby    23    

Простой редактор плана помещения JavaScript

Практика программирования Работа с интерфейсом v8 1cv8.cf Абонемент ($m)

На ресурсе сейчас очень много решений, которые позволяют редактировать карты, используя географические схемы. Так же много решений, которые позволяют редактировать объекты онлайн веб-карт. Мне же нужно было простое решение, для того чтобы расставить квадратные объекты на плане, показать их пользователю. Ну и распечатать, опять же. Я решил написать простенький редактор на JavaScript с использованием библиотеки Raphael.

1 стартмани

23.11.2016    22712    99    igel9780    22    

Быстрое определение интервалов в запросе Промо

Практика программирования v8 Абонемент ($m)

В статье описывается новый метод определения интервалов между данными различных записей в запросе. В отличие от общеизвестного метода, время работы предлагаемого метода зависит от объема данных ЛИНЕЙНО. Это обеспечивает ему значительный выигрыш по быстродействию на больших объемах данных. В качестве иллюстрации возможностей метода приведен отчет, показывающий гистограмму распределения времени между продажами.

1 стартмани

01.10.2015    54399    35    ildarovich    41    

Работа с двоичными данными на примере чтения файлов изображений. Новые возможности 8.3.9

Практика программирования WEB v8 1cv8.cf Россия Абонемент ($m)

В статье приводятся новые функции по работе с двоичными данными, появившимися в версии платформы 8.3.9 , на примере анализа формата и размера изображений. А также пример отправки изображения через API ВКонтакте с помощью новых объектов (без использования ОбъединитьФайлы())

1 стартмани

14.11.2016    28837    16    Anton64    22    

Загрузка файлов на сервер с прогрессом и докачкой

Практика программирования v8 1cv8.cf Россия Абонемент ($m)

Пример использования новых возможностей платформы 8.3.9 по низкоуровневой работе с двоичными данными для инкрементальной передачи файлов на сервер.

1 стартмани

04.10.2016    14479    53    mrstomak    21    

Несколько шаблонов для доработки типовых конфигураций

Практика программирования Инструментарий разработчика v8 v8::УФ Абонемент ($m)

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

1 стартмани

03.10.2016    38282    96    json    25    

HTTP-сервис: отчеты [Расширение]

Практика программирования Работа с интерфейсом v8 1cv8.cf Абонемент ($m)

Это HTTP-сервис, который возвращает почти любой отчет в HTML, XLSX или в JSON. Сохраните вариант отчета, получите на него ссылку и можно получить данные без захода в 1С. Работает в конфигурациях на основе БСП 2.3.3+, для отчетов на СКД и в 1С 8.3.8+

2 стартмани

30.08.2016    28745    143    Stepa86    15    

Недокументированное использование стандартных форм Upd.

Практика программирования v8 v8::УФ 1cv8.cf Абонемент ($m)

Вам не хватает возможностей в платформе 1С или у Вас нет времени на углубленное изучение платформы 1С? Рассмотрены возможности использования стандартных форм, вызываемых из платформы.

1 стартмани

26.07.2016    30032    86    ZhokhovM    60    

Хранение файлов в томах на диске (для УПП 1.3)

Практика программирования v8 УПП1 Абонемент ($m)

Доработка типовой УПП 1.3 в плане хранения присоединенных файлов вне базы данных

2 стартмани

05.06.2016    60518    11    wowik    32    

БСП 2.3 и БСП 3.0: Просто про выполнение внешней обработки в фоне (c индикацией прогресса выполнения)

Инструментарий разработчика Практика программирования БСП (Библиотека стандартных подсистем) v8 1cv8.cf Абонемент ($m)

Простое пояснение о том, как сделать внешнюю обработку с фоновым выполнением и индикацией процесса для любой конфигурации на основе БСП 2.3.2. UPDATE 20/09/19: добавлен вариант обработки с индикацией процента выполнения и статусом выполнения для БСП 3.0.

1 стартмани

18.05.2016    65653    194    rozer    66    

Остатки на каждый день в запросе

Практика программирования Учет ТМЦ Учет ТМЦ v8 1cv8.cf УУ Абонемент ($m)

Запрос формирует остатки товаров на каждый день в пределах выбранного периода.

1 стартмани

26.04.2016    64490    19    arakelyan    20    

Еще один способ расчета остатков на каждый день в запросе

Математика и алгоритмы Практика программирования v8 Абонемент ($m)

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

1 стартмани

24.04.2016    36367    51    ildarovich    23    

Вывод печатных форм с запросом данных в форму "Печать документов" из подсистемы БСП "Печать".

Практика программирования БСП (Библиотека стандартных подсистем) v8 1cv8.cf Абонемент ($m)

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

1 стартмани

29.03.2016    98262    190    lopatin    14    

Выполнение JavaScript кода из 1С в объекте Поле HTML Документа (HTML 5) и вызов события в 1С ПриНажатии

Практика программирования v8 1cv8.cf Россия Абонемент ($m)

Пример выполнения JS кода из 1С в Поле HTML Документа под управляемыми формами, с удобным получением результата в 1С(С помощью вызова привязанного события ПриНажатии к элементу ПолеHTMLДокумента)

1 стартмани

22.03.2016    85658    163    igo1    54    

Количество дней недели (понедельников/вторников/...) в заданном диапазоне одним запросом

Практика программирования v8 Абонемент ($m)

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

1 стартмани

03.03.2016    19528    1    Alexander.Shvets    5    

Простые радости жизни программиста 1С: выбор типа значения

Работа с интерфейсом Практика программирования v8 1cv8.cf Абонемент ($m)

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

1 стартмани

17.02.2016    52723    54    yuraos    18    

Отображение прогресса выполнения длительных операций в БСП и их отладка в текущем сеансе.

Практика программирования БСП (Библиотека стандартных подсистем) v8 1cv8.cf Абонемент ($m)

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

1 стартмани

17.02.2016    59340    194    balanton    23    

Яндекс.Деньги "Благотворительность"

Инструментарий разработчика Практика программирования v8 1cv8.cf Абонемент ($m)

Яндекс.Деньги теперь в 1С. Форма для приема благотворительных взносов. Форму легко сделать и вставить на любую страницу сайта или блога. Платежи будут приходить на ваш кошелек. На форме есть три способа платежа: из кошелька, с банковской карты, с баланса мобильного.

1 стартмани

16.02.2016    24640    8    Tatitutu    5    

Мастер рассылки e-mail 2.2 для управляемых форм

Практика программирования Email v8 v8::УФ ERP2 БП3.0 УТ11 Абонемент ($m)

Для пользователей: переделанный из старый разработки под 8.2 с использованием библиотеки Мастер рассылки e-mail 2.2 (ERP, УТ, БП) (Только управляемые формы), который теперь может запускаться под любой версией платформы с разрешенными или запрещенными модальными/синхронными вызовами в конфигурации. Также удобный выбор e-mail и их владельцев с помощью отбора динамического списка по любым критериям и галочки исключения.

1 стартмани

29.12.2015    40829    20    milkers    4