gifts2017

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

Опубликовал Сергей (ildarovich) в раздел Программирование - Практика программирования

Это спойлер к замечательной публикации «Алгоритмы. Часть 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 7
.epf 10,49Kb
11.04.14
7
.epf 10,49Kb Скачать

См. также

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

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

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

Спасибо. Ну для N 100000, M где то 1,5 лимона будет для взвешенного объединения, независимо от метода сжатия пути. Хотя понятно, что без гарантии.
6. andrey dyak (dyak84) 15.04.14 12:55
Все хорошо все понятно все наглядно, но название не по феншую причем здесь политика. Если человек умный и говорит по существу то какая разница кто он по национальности?????????????
7. адуырщдв (адуырщдв) 15.04.14 13:17
(6) dyak84, Думаю автор как бы намекает Роберту Сэджвику и компании.... В первых (80-е годы) его "Алгоритмах...." был (если не изменяет память) использован для написания программ паскаль, потом были издания где использовались кресты, а сейчас принстонцы используют жабу . А надо бы использовать внутренний язык 1С Предприятия. ;)
8. Сергей (ildarovich) 15.04.14 13:22
(6) Задиристое название выбрано специально для привлечение внимания. Это юмор. Юмор в стиле "А в Москве все эти штаты уж разбиты на квадраты/Кнопка красная одна/Лишь нажмешь и им хана/Это обороны меры/Это наши инженеры/Постарались для ребят/Для мышат и медвежат". Из этой же серии фотография Дианы Вишневой в качестве картинки к анонсу ("а также в области балета мы впереди планеты всей").
Очень удачно получилось, что в нашем отечественном 1С есть средства, позволяющие решить задачу быстрее, чем показано в этой не нашей лекции.
Кстати, в Java вообще-то тоже есть HashMap - аналог нашего соответствия (правда, в данной задаче соответствие скорее используется как HashSet). И вполне возможно, когда-то позже по тексту лекций разговор может вернуться к этой задаче с использованием других структур данных.
9. адуырщдв (адуырщдв) 15.04.14 15:17
(8) ildarovich,
И вполне возможно, когда-то позже по тексту лекций разговор может вернуться к этой задаче с использованием других структур данных.

Вполне, обычно возвращаются в виде задач, типа перепишите. Алгоритм то трёхкопеечный, не стоит включения тяжелой артилерии. К тому ж, в Си 1600 вершин и 3200 ребер у меня отработало 16 миллисекунд с инициализацией (в отличии от "нашего ответа" который крутился аж 750 мс).
Прикрепленные файлы:
main.c
10. адуырщдв (адуырщдв) 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) 15.04.14 16:34
(10) А смысл? - Ведь в статьях сравнивались не языки, платформы и прочее, а алгоритмы. Ясно, что на ассемблере будет еще быстрее. На Си можно еще битовые строки попробовать. Можно и на графическом ускорителе эту же задачу решать.
Мне было бы интереснее сравнить эти алгоритмы в Java на массивах с Java на HashSet. Хотя пример и задача довольно абстрактные и рыть тут в глубину, наверное, не стоит.
12. анд гру (agrustny) 16.04.14 10:18
(2) Уважаемый профессор, объясните, пожалуйста, почему программа на 1С выполняется в 47 раз медленнее, чем на Си? Ваше мнение: каков вклад в ln(47) различных элементов, фигурирующих между компилятором Си и интерпретатором 1С?
13. адуырщдв (адуырщдв) 16.04.14 11:15
(11) ildarovich,
А смысл?

Обязательно нужен? :) А тогда вообще, есть ли смысл учить алгоритмы "с реализацией примеров на 1С", к тому ж в "вольном" переводе, переводе даже не соответвующей книги, а просто лекций???
14. Сергей (ildarovich) 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 так же сильно отстают по быстродействию от Си. Просто используется другой, более высокий, приближенный к предметной области уровень абстракции. За это приходится платить быстродействием.
15. Сергей (ildarovich) 16.04.14 12:15
(13) Видимо, смысл
учить алгоритмы "с реализацией примеров на 1С", к тому ж в "вольном" переводе, переводе даже не соответвующей книги, а просто лекций???
есть. Об этом говорит высокая популярность исходной статьи у читателей.
16. andrey dyak (dyak84) 16.04.14 12:19
(7)Спасибо за детальное обяснение, а то на фоне последних собитиий везде черты мерещатся
17. адуырщдв (адуырщдв) 16.04.14 12:41
(15) ildarovich, Оптимистично. :) Ну чтож, тогда остаётся ждать появления экпертов в algorithm design and analysis, выучившихся таким способом.
18. анд гру (agrustny) 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) 16.04.14 16:43
(18) Уважаемый agrustny, я не считаю великими достижениями двукратное увеличение скорости за счет использования "правильных" структур данных. Но если в 1С Вам потребуется решать задачу на графах, благодаря этой статье Вы, возможно, вспомните о соответствиях. При их использовании при решении этих задач на 1С (а такая необходимость встречается даже в типовых) получается гибкий, выразительный и быстрый код. Я лишь хотел это еще раз показать. Меня насторожило то, что один из читателей в комментарии http://forum.infostart.ru/forum24/topic108120/message1113541/#message1113541 захотел применить массивы в задаче определения множества аналогов номенклатуры, когда соответствие подходят лучше и решают задачу быстрее. Разницу в отклике 700 или 250 миллисекунд оператор уже чувствует.
Я задумывался о том о том, что в другой системе, производительность которой может быть на порядок больше или меньше 1С, "правильными" окажутся другие структуры, о том, каковы потребности в памяти моего алгоритма, о том, какова идеальная структура данных для решения этой задачи, об измерении производительности в количестве операций чтения и записи и о много чем еще, но в статью поместить всего этого не получилось. Не счел эту задачу на сейчас достаточно актуальной, чтобы тратить время.
Морочить людям головы я не стремился, и что оптимизировать нужно только то, что реально плохо (APDEX) я из своей практики знаю. И вот, например, в работе Неоплаченные долги при распределении оплаты по правилу ФИФО одним запросом и намного быстрее, чем Вы думали я именно так и делал. А почему этого никто не сделал (привел к линейной зависимости эти вычисления) раньше? Как Вы думаете?
Redokov; agrustny; +2 Ответить 2
20. анд гру (agrustny) 17.04.14 10:51
(19) Я думаю, что никто этого не сделал раньше из-за отсутствия в персональной БД следующих документов:
1) ЗаказНаПроизводство
2) ИнтересКПроблеме
3) ВыдающийсяТалант
In other words, Вася, безжалостный и беспощадный, рулит вовсю.
Профессор, если уж такое дело, не дадите на опохмелиться посмотрите мою студенческую работу http://infostart.ru/public/273699/
21. анд гру (agrustny) 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)).
22. Миклухо Маклай (mikuho) 20.04.14 07:27
Спасибо! не все конечно понятно, но то что хотел - освоил
23. Яков Коган (Yashazz) 20.04.14 15:00
Вот всё мне в изложенном нравится, кроме одного: коллекция "Соответствие" не совместима напрямую ни со списками, ни с массивами, ни с таблицами значений, ни тем более с выборками запросов или результатами Построителей/СКД. Поэтому очень многое насчёт соответствий, к сожалению, сферический кодинг в вакууме, т.к. потеря времени на заполнение соответствия иногда бывает трудно соизмерима с выигрышем скорости при его последующем чтении.
А главное, и извратные способы медленны, и заполнение циклом тоже. Вот кабы можно было, например, скопом заполнить всё соответствие из двуколоночной таблицы или из списка, или ещё откуда, но... Увы нам.
artbear; ildarovich; agrustny; +3 Ответить
24. Станислав Копылов (ksuman) 21.04.14 15:58
Причем тут алгоритмы и пример использования структуры 1С "Соответствие"?
Алгоритмы - это простейшие операции, которые мы можем наблюдать и контролировать, а когда задача выполняется с помощью библиотек процедур, функций, классов и объектов - это не алгоритм, а иная реализация. Пытаться унизить американцев или блеснуть своим аналитическим мышлением в данном случае - плохая идея. Все равно, что к изобретению колеса добавить открытие каучука: принцип действия не меняется.
Вот, если бы вы для применения к данной задаче использовали открытый массив с индексом с описанием метода поиска в рамках этой задачи, это было бы ответом.
25. Сергей (ildarovich) 21.04.14 16:33
(24) Устал повторять, но не будьте, пожалуйста, так буквальны в понимании названии статьи. Я рассчитывал на читателей с чувством юмора. Вы прочитали комментарий (8)?
В самой статье я говорю не об алгоритмах, а о решении той же задачи. О том, что
При максимизации быстродействия не стоит забывать о втором слагаемом формулы <программы = алгоритмы + структуры данных>.
Я просто-напросто, читая статью, подумал о том, как можно решить эту задачу на 1С. Попробовал использовать соответствие, поскольку применял его раньше в решении задач на графах, и получил в два с половиной раза более быстрое решение задачи, чем у автора исходной статьи. Мне показалось, что это решение будет интересным и поучительным. Вы так не считаете?
26. Игорь Чайкин (ЧИА) 22.11.14 08:54
применение специфики платформы для ускорения - не панацея

в бытность свою студентом (80-90-е)
писал на турбопаскале программу рендзю, в ЧМ участвовала
а для увеличения производительности делал ассемблерные вставки, ручками данные между регистрами распределял
так вот -
1. муть это все. ибо при переделки базовых алгоритмов приходилось смотреть на эти вставки и думать - выкинуть или написать новые. не продуктивно, особенно если есть другие занятия
2. а переделки именно алгоритмов и структур хранения данных о позициях давала ускорение в 5-20 раз, тогда как применение ухищрений - раза в 2-4
3. так что мой совет - читайте Кнута, это полезнее
27. Сергей (ildarovich) 22.11.14 14:43
(26) ЧИА, кажется, вы слишком поверхностно отнеслись к содержанию статьи и в итоге "отгадали все буквы, но не смогли назвать слова".
Ассемблерные вставки это совсем не то же самое, что использование соответствия. Ассемблерные вставки не меняют вид зависимости в оценке трудоемкости программы, а только меняют коэффициент в формуле этой оценки. Они здесь не при чем.
Использование соответствия проходит по пункту "переделки алгоритмов и структур хранения данных". По второй части этого пункта.
Если еще помните работы Дональда Кнута, то у него там была такая машина MIX. В томе 1 в разделе 1.3.1 на странице 180 советского издания (оно сейчас стоит у меня на полке) написано, что каждой операции машины MIX приписывается время выполнения, типичное для современных машин. Современность там - 1968 год. Это наш перевод вышел в 1976 году.
У нас сейчас 2014 год и не MIX, а 1С. У нее своя таблица времени выполнения отдельных операций. И моя мысль в том, что при реализации и сравнительном анализе алгоритмов на 1С нужно использовать именно эту таблицу, которая вовсе не mixed.
28. Игорь Чайкин (ЧИА) 22.11.14 20:35
(27)
Если еще помните работы Дональда Кнута
то у него есть четкое разделение, и не в 1, а в 3 томе
глава 6.2 поиск путем сравнения ключей
ваш метод, как я думаю, относится к 6.2.4, Сильноветвящиеся деревья
и именно к конкретной оптимизации под реализацию в 1с
перечитайте
29. Игорь Чайкин (ЧИА) 22.11.14 20:41
Современность там - 1968 год
у меня на полке издание 2000 года
алгоритмы и источники, те, что я заметил, до 1997г (SODA 8), 1998г (SODA 9)
30. Игорь Чайкин (ЧИА) 22.11.14 20:54
Современность там - 1968 год.

и, да, в 3 томе многое минимум от 1970(80,90)+
так что ваши книги немного устарели
31. Игорь Чайкин (ЧИА) 22.11.14 21:13
(27)
Ассемблерные вставки это совсем не то же самое, что использование соответствия. Ассемблерные вставки не меняют вид зависимости в оценке трудоемкости программы, а только меняют коэффициент в формуле этой оценки. Они здесь не при чем.
Использование соответствия проходит по пункту "переделки алгоритмов и структур хранения данных". По второй части этого пункта.

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

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

по моему - одного поля ягоды
33. Сергей (ildarovich) 25.11.14 14:43
(28) ЧИА, попробую пояснить свою мысль.
Я совсем не против изучения книг Кнута, Сэджвика и прочих. Тем более, что сам большой любитель этой литературы. Я против делания из этого культа и бездумного применения рекомендаций и оценок из этих книг. Нужно понимать, что оценки производительности алгоритмов в книгах делались с оговорками. В расчете на определенную модель вычислителя. Если бы в этом вычислителе применялся, например, какой-нибудь "квантовый сопроцессор", который делал бы сортировку любого массива за один такт работы процессора, то оценки алгоритмов, опирающихся на сортировку, были бы другими. Есть целое направление исследования быстродействия параллельных алгоритмов, где те же классические задачи имеют другие оценки временной сложности.
Так вот, платформа 1С предлагает нам иную модель вычислителя, где оценки относительного времени выполнения элементарных операций отличаются от используемых при анализе классических алгоритмов. Это нужно обязательно учитывать при реализации алгоритмов на 1С. Иначе полученные время выполнения программы на 1С и зависимость времени от размерности задачи просто не совпадет с действительностью, которая одна и является критерием истины, а вовсе не бездумное следование заветам какого-либо классика.
(31) Если идеология менялась - непонятно почему был маленький выигрыш - вы же сами это отметили. Значит, неправильно менялась. Бывает. В случае, описанном в данной статье, это было не так.
(32) Все, что сказано Яковом, совершенно верно, но к данному законченному решению не применимо.
...
Что вы называете муторным? - Посмотрите на текст программы в статье! - Там десяток строчек. Использование соответствия позволило получить и быстрый и выразительный код. Мне кажется, в данном случае вы не стараетесь вникнуть в суть решения, а просто рассуждаете по шаблону.
адуырщдв; +1 Ответить
34. Максим Хлыстов (max1c) 23.01.15 18:21
Алгоритм – слегка улучшенный алгоритм «Быстрый поиск». Вместо кода подмножества, используется ссылка на соответствие. При объединении все так же требуется скопировать часть подмножества (улучшение состоит в том, что не нужно сканировать весь массив).
Если объединять (худший случай) два подмножества в каждом из которых N/2 элементов, то это потребует:
- N/2 операций чтения из соответствия (Для Каждого Этого Из Связи[Ежа] Цикл);
- N/2 операций вставки в соответствие (Связи[Ужа].Вставить(Этого.Ключ));
- N/2 операций чтения из массива (…= Связи[Ужа]);
- N/2 операций записи в массив (Связи[Этого.Ключ] =…).

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

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