Как оптимально сравнить две таблицы значений?

1. Nadushka74 5 10.10.14 15:23 Сейчас в теме
наименование колонок и типы данных в колонках идентичны, обе таблицы отсортированы по данным первой колонке. как оптимально произвести их сравнение?
По теме из базы знаний
Вознаграждение за ответ
Показать полностью
Найденные решения
467. ildarovich 7865 02.02.15 12:13 Сейчас в теме
По результатам текущего обсуждения выпущена статья Лучшие методы сравнения таблиц значений.

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

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

Несколько методов осталось "в запасе". Например, использование нового объекта 8.3, позволяющего рассчитать хэш-функцию. Ну и разные доработки свертки.

Но зато выводы получились очень четкими. Каждому методу нашлось свое место. Буквально таблицу решений по выбору метода можно построить. Посмотрю на результаты обсуждения (если оно будет) и сделаю это.
dj_serega; +1 Ответить
387. ildarovich 7865 05.11.14 23:26 Сейчас в теме
(386) kostyaomsk, причина пояснит приложенная картинка. Это результаты теста при использовании SQL-сервера. Тут есть и запросные (вторая часть строчек) и беззапросные методы. Обратите внимание на последнюю строку. Это время выполнения вот такой процедуры
Функция СравнениеТаблицЗначений(Таблица1, Таблица2, ПрочиеКолонки = "") Экспорт
	
	ИмяКлюча = Таблица1.Колонки[0].Имя;
	
	Для ё = 1 По Таблица1.Колонки.Количество() - 1 Цикл ПрочиеКолонки = ПрочиеКолонки +  ", " + Таблица1.Колонки[ё].Имя
	КонецЦикла;
	
	Запрос = Новый Запрос(
	
	"ВЫБРАТЬ Т.Ключ, -1 КАК Знак
	|ПОМЕСТИТЬ Т1
	|ИЗ	&Таблица1 КАК Т
	|;
	|ВЫБРАТЬ Т.Ключ,  1 КАК Знак
	|ПОМЕСТИТЬ Т2
	|ИЗ	&Таблица2 КАК Т"
	
	);
	
	Запрос.Текст = СтрЗаменить(Запрос.Текст, "Т.Ключ,", ИмяКлюча + " КАК Ключ" + ПрочиеКолонки + ",");
	
	Запрос.УстановитьПараметр("Таблица1", Таблица1);
	Запрос.УстановитьПараметр("Таблица2", Таблица2);
	
	Возврат Запрос.Выполнить().Выгрузить()
	
КонецФункции
Показать
В ней ничего не делается. Никакой обработки. Только производится ввод данных из таблиц значений во временные таблицы. Видите время? - 1896 мс. А за это время - за 1588 мс. свертка уже успела получить и выдать готовый результат!
Конечно, если вычесть это время из времени 2631 самого быстрого запроса полного соединения, то получается, что на обработку SQL потратит меньше времени 735 мс, но вод передача данных в запрос все портит!
Прикрепленные файлы:
411. Никулин Леонид 12.11.14 09:33 Сейчас в теме
У меня была похожая задачка. Могу посоветовать выгрузить ТЗ в табличные части и сравнивать их запросом





// Функция сравнивает ТЧ док "ОприходованиеТоваров" и ТЧ док "ЗаказНаПроизводство" (с учетом всех корректировок)
// Если они одинаковые вернет Истину в противном случае Ложь
Функция ПроверкаЗаполненияОприходования(ОприходованиеТоваров,ЗаказНаПроизводство)

Запрос = Новый Запрос;
Запрос.Текст =
"ВЫБРАТЬ РАЗРЕШЕННЫЕ
| Подсчет.Номенклатура,
| Подсчет.ЕдиницаИзмерения,
| Подсчет.Количество,
| СУММА(Подсчет.Счетчик) КАК СчетчикМин,
| СУММА(Подсчет.Счетчик) КАК СчетчикМакс
|ИЗ
| (ВЫБРАТЬ
| ПотребностиЗаказовНаПроизводство.Номенклатура КАК Номенклатура,
| ПотребностиЗаказовНаПроизводство.ЕдиницаИзмерения КАК ЕдиницаИзмерения,
| ПотребностиЗаказовНаПроизводство.Количество КАК Количество,
| 0.5 КАК Счетчик
| ИЗ
| РегистрНакопления.ПотребностиЗаказовНаПроизводство КАК ПотребностиЗаказовНаПроизводство
| ГДЕ
| ПотребностиЗаказовНаПроизводство.ЗаказНаПроизводство.Ссылка = &ЗаказНаПроизводство
|
| ОБЪЕДИНИТЬ ВСЕ
|
| ВЫБРАТЬ
| ОприходованиеТоваровТовары.Номенклатура,
| ОприходованиеТоваровТовары.ЕдиницаИзмерения,
| ОприходованиеТоваровТовары.Количество,
| 0.5
| ИЗ
| Документ.ОприходованиеТоваров.Товары КАК ОприходованиеТоваровТовары
| ГДЕ
| ОприходованиеТоваровТовары.Ссылка = &ОприходованиеТоваров) КАК Подсчет
|
|СГРУППИРОВАТЬ ПО
| Подсчет.Номенклатура,
| Подсчет.Количество,
| Подсчет.ЕдиницаИзмерения
|ИТОГИ
| МИНИМУМ(СчетчикМин),
| МАКСИМУМ(СчетчикМакс)
|ПО
| ОБЩИЕ";
Запрос.УстановитьПараметр("ОприходованиеТоваров", ОприходованиеТоваров);
Запрос.УстановитьПараметр("ЗаказНаПроизводство", ЗаказНаПроизводство);
Выборка = Запрос.Выполнить().Выбрать();
Выборка.Следующий();

ТЧ_Совпадают = (Выборка.СчетчикМин = Выборка.СчетчикМакс И Выборка.СчетчикМин = 1);

Возврат ТЧ_Совпадают;

КонецФункции
//...-Никулин
Остальные ответы
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
246. awk 741 30.10.14 14:57 Сейчас в теме
(244) Serginio, Прикрутил, но неопртимизированный хэш не порман.
247. Serginio 938 30.10.14 15:30 Сейчас в теме
(244) Главное, что он стал уже на один уровень. При этом оптимизация за счет инлайнинга метода и уменьшения сравнения с числом или увеличение индекса на 1 (инкремент) в 1С дает огромный прирост, что например на компиляторах обрабатывается за такт.
241. awk 741 30.10.14 14:18 Сейчас в теме
Не тестируйте в режиме отладки!!! Данные искажаются!!!
248. YanTsys 12 30.10.14 15:48 Сейчас в теме
А если использовать соответствие и тупой перебор строк?

Чтобы вам скучно не было еще один вариант.
я у себя его проверял как 6 вариант (СравнениеТаблицЗначений6) поправьте номер если у вас иначе
количество строк в коде похоже принципиально сократил насколько совести хватило, но если написать в одну строку будет еще быстрее

//////////////////////////YanTsys (248)////////////////////////////

Функция СравнениеТаблицЗначений6(Т1, Т2) Экспорт
	
	ТЗПК = СравнитьТЗ248(Т1, Т2);	
	ТЗПК.Колонки[0].Имя = "Ключ"; ТЗПК.Колонки[1].Имя = "Знак";	
	Возврат ТЗПК
	
КонецФункции

Функция СравнитьТЗ248( ТЗ1,ТЗ2)
	СоответствиеТЗ1=новый Соответствие; СоответствиеРезультат=новый Соответствие; КоличествоКолонок=ТЗ1.Колонки.Количество(); ТЗРез=ТЗ1.СкопироватьКолонки(ТЗ1.Колонки[0].Имя); ТЗРез.Колонки.Добавить("РезультатСравнения");
	Для каждого СтрокаТЗ1 из ТЗ1 Цикл СоответствиеТЗ1.Вставить(СтрокаТЗ1[0],СтрокаТЗ1); КонецЦикла;
	Для каждого СтрокаТЗ2 из ТЗ2 Цикл СтрокаТЗ1=СоответствиеТЗ1[СтрокаТЗ2[0]]; Если СтрокаТЗ1=неопределено Тогда 	СоответствиеРезультат.Вставить(СтрокаТЗ2[0],1);Иначе РезультатСравнения=0;Для ИндексКолонки=1 по КоличествоКолонок-1 Цикл Попытка Если СтрокаТЗ1[ИндексКолонки]<>СтрокаТЗ2[ИндексКолонки] Тогда РезультатСравнения=2; Прервать; КонецЕсли;Исключение РезультатСравнения=2; КонецПопытки;КонецЦикла;	СоответствиеРезультат.Вставить(СтрокаТЗ2[0],РезультатСравнения); КонецЕсли;КонецЦикла;
	Для каждого ЭлементСоответствиеТЗ1 из СоответствиеТЗ1 Цикл Если СоответствиеРезультат[ЭлементСоответствиеТЗ1.Ключ]=неопределено Тогда	СоответствиеРезультат.Вставить(ЭлементСоответствиеТЗ1.Ключ,-1); КонецЕсли;КонецЦикла;
	Для каждого ЭлементСоответствиеРезультат из СоответствиеРезультат Цикл Если ЭлементСоответствиеРезультат.Значение<>0 Тогда  СтрокаТЗРез=ТЗРез.Добавить();СтрокаТЗРез[0]=ЭлементСоответствиеРезультат.Ключ; СтрокаТЗРез[1]=ЭлементСоответствиеРезультат.Значение; КонецЕсли; КонецЦикла;
	Возврат ТЗРез;
КонецФункции
Показать
250. awk 741 30.10.14 16:04 Сейчас в теме
(248) YanTsys, А у меня как? Мой (134). Только что перебираю по индексу. Убрать индексацию и вуаля...
252. YanTsys 12 30.10.14 16:07 Сейчас в теме
(250) awk, неа, у вас есть "НайтиСтроки" а как я понял она очень все тормозит! Очень прошу проверить скорость варианта из 248 поста :)
253. awk 741 30.10.14 17:06 Сейчас в теме
(252) YanTsys, Приведи результат к Новый Структура("Одинаковые, Т1, Т2, Измененные", Новый Соответствие, Новый Массив, Новый Массив, Новый Соответствие); Я добавил проверку правильности результата. И причесываю все тесты к нему...
254. awk 741 30.10.14 17:07 Сейчас в теме
Может по результатам статью набросать?
255. Serginio 938 30.10.14 17:16 Сейчас в теме
(254) Обязательно и еще с анализом замера производительности, что бы были видны где основные потери.
260. ildarovich 7865 30.10.14 20:30 Сейчас в теме
(254) awk, насчет статьи я уже задумался, но исследование не считаю законченными. Результаты должны быть полными, честными и объективными - вне зависимости от того, чей алгоритм побеждает. Пока результаты не считаю полными: на картинках нет метода из (194), например, и других возможных запросов. Также не хватает данных по типам элементов: числам, датам и ссылкам - это тоже нужно проверить. Также стоит показывать данные не только для трех колонок. То есть вообще не в одном выгодном разрезе % искажения, который НА ПРАКТИКЕ обычно ближе к 0 чем к 100 (могу поспорить). Думаю, 15 колонок встречается гораздо чаще, чем 100% искажения. Однобокая статья (выпячивающая один алгоритм) будет не только бесполезной, но и вредной.
Для начала я хотел предварительно отобрать варианты - для более детального рассмотрения.

Пока предполагаю так:
1) слияние исключаем? она во всех вариантах перекрывается?
2) свертку берем из 194, там будет небольшой тюнинг;
3) сканирование берем через соответствие (хэш), здесь еще можно для сравнения строк ЗначениеВСтрокуВнутр использовать.
4) запросы я пока оставляю - посмотрю, что будет на SQL. Хотя думаю, что свертка ТЗ и группировка таблиц в запросе выполняется в файловой версии платформы одними и теми же методами и похоже даже писал их один разработчик и разница только из-за накладных расходов.

Проблему с соответствием вместо индекса я вижу в том, что при наличие составного ключевого поля этот прием перестанет работать, а свертка и запросы будут.
А на практике такое есть: номенклатура - характеристика, номенклатура - серия, счет - субконто1 и так далее.
262. awk 741 30.10.14 21:50 Сейчас в теме
(260) ildarovich, Надо с результатом определится. (194) есть. Пока самый шустрый - это хэш. Правда иногда его делает оптимизированное слияние.

Предлагаю следующие критерии оценки универсальности алгоритма за каждую опцию +1:

1. Можно получить одинаковые строки
2. Можно получить добавленные строки
3. Можно получить одинаковые строки
4. Можно получить измененные строки
5. Можно получить все строки в одной коллекции с пометкой
6. Входящие таблицы остаются неизменными
7. Таблицы могут быть не упорядоченны
266. awk 741 30.10.14 22:46 Сейчас в теме
(260) ildarovich, Сравнение через ЗначениеВСтрокуВнутр, СравнениеЗначений, Вычислить(Код) проигрывают обходу Для Каждого. Я уже с этим поиграл.
271. ildarovich 7865 30.10.14 23:23 Сейчас в теме
(266) awk, думаю, это зависит от числа колонок, поэтому еще попробую сам.
273. awk 741 30.10.14 23:24 Сейчас в теме
(271) ildarovich, 5 колонок по 33 символа строки. Генерация строк через Строка(Новый УникальныйИдентификатор())
276. ildarovich 7865 30.10.14 23:41 Сейчас в теме
(273) awk, идея интересная (насчет идентификатора), а зависимость от длины я тоже хотел посмотреть, поэтому у себя делаю параметром и то и другое. И - картинку в этом разрезе.
В общем-то я бы за то, чтобы и так и так. Для соревнования нужен один победитель и эти условия подойдут, но для статьи нужно честно показать зависимость. Потому, что если чел выберет победителя, засунет в него таблицу из 25 колонок - будет некрасиво.
278. awk 741 30.10.14 23:46 Сейчас в теме
(276) ildarovich, Да победитель пока Serginio и его оптимизированное слияние. YangTsys проигрывает при приведении результата к Структуре. Причем для него я еще скидку сделал. В коллекции структуры помещаю ключи.
285. ildarovich 7865 31.10.14 00:04 Сейчас в теме
(278) awk, я, честно говоря, против приведения результата к одному виду. Потому, что из запроса в соответствие тоже не быстро выводить - в массив еще куда ни шло.
Поэтому я считаю, что финиш нужно фиксировать, как получена информация в "приемлемом" виде. Пусть он будет у каждого свой. А приведение проводить за рамками дистанции.
Иначе вообще сравнивать нельзя. У вас рабочая структура соответствие. У нас - ТЗ. Либо вы тратите время на приведение, либо мы.
Вообще как-то Яков тут говорил, что ему всем нравится соответствие, кроме возможности загрузки-выгрузки в другие коллекции.
Так что требование загрузки в соответствие - no fair play.
286. awk 741 31.10.14 00:09 Сейчас в теме
(285) ildarovich, У меня запрос прекрасно создал четыре таблицы и не чихнул даже. Массив, Таблица, соответствие - не суть. Это все Коллекции. Их можно перебирать, получать количество.
267. awk 741 30.10.14 22:47 Сейчас в теме
(260) ildarovich, Слияние оставь. Последний способ бъет хеш, правда иногда.
268. awk 741 30.10.14 22:49 Сейчас в теме
(260) ildarovich,
Проблему с соответствием вместо индекса я вижу в том, что при наличие составного ключевого поля


Соответствие[К1][К2][Кn] - я уже писал такое в этом году.. не проблема
ildarovich; +1 Ответить
274. ildarovich 7865 30.10.14 23:32 Сейчас в теме
(268) awk, Соответствие[К1][К2] - интересно, нужно для этих задач попробовать. Такой самодельный индекс. Вообше, вдруг быстрее отбора будет работать? - Для ключевых полей. - Вот это и будет открытие. - Отдельная тема.
288. Serginio 938 31.10.14 09:14 Сейчас в теме
(260) На практике еще из семерки это делается за счет деревьев.
Сначала Соответствие по первому полю, значением которого будет
Для каждого стр из Тз Цикл
Ключ1=стр[поле1];
Ключ2=стр[поле2];
Знач1=соответствие[ключ1];

Если Знач1=Неопределено Тогда
 Знач1=новый соответствие;
 соответствие.Вставить(Ключ1,Знач1)
КонецЕсли;

знач1.ДобавитьЗначение(ключ2,стр);
КонецЦикла;
Показать


Ну и соответственно поиск.
Опять же тут нужно смотреть сколь лишних вычислений будет в 1С. Здесь особо нечего сравнивать алгоритмы конечно если они не отличаются на порядок.
289. Serginio 938 31.10.14 09:33 Сейчас в теме
(288) Вообще конечно 1С ущербный язык. Для хэш таблицы неважно сколько полей. Главное только два метода
GetHashCode и Equals
http://www.forum.mista.ru/topic.php?id=724509&page=1#35
256. YanTsys 12 30.10.14 17:31 Сейчас в теме
Сложно перебирать всю историю ваших вариантов, у вас например проверка на равенство в попытку-исключение не завернуто ведь не все значения 1с дает сравнивать? Части кода в других вариантах вынесены в отдельные функции если речь идет о скорости, то это нелогично, обращение к значениям по именам колонок а не по номерам тоже затраты времени... ну и вообще много лишних действий если смотреть условие задачи...

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

По большому счету последний цикл и формирование возвращаемой ТЗ в моем варианте и так уже лишнее действие, вполне можно было бы вернуть сформированное ранее соответствие.

Если я ничего не напортачил, то скорость моего варианта должна быть повыше...
258. awk 741 30.10.14 18:04 Сейчас в теме
(256) YanTsys, Ну а чего тогда не проверить вариант:


Функция СравнитьТаблицы(Т1,Т2, Колонки, Ключ) КонецФункции



Все остальное - лишнее. Спорим, этот вариант порвет все остальные?

Структура: Одинаковые, Т1,Т2, Измененные - дает полный ответ о сравнении. Все алгоритмы модифицированы так, что бы возвращать данную структуру.

P.S. Не надо со мной спорить, лучше написать свою обработку тестирования и заточить под свой вариант с модификацией алгоритмов.
257. YanTsys 12 30.10.14 17:38 Сейчас в теме
Уточню моего варианта реализации :) , очевидно что использовать соответствие не мне первому пришла идея.
264. IvanAlekseev 77 30.10.14 22:10 Сейчас в теме
Функция ТаблицыНеРавны(Тз1, Тз2)
	
	Количество1 = Тз1.Количество();
	Количество2 = Тз2.Количество();
	Если Количество1 <> Количество2 Тогда
		Возврат Истина;
	КонецЕсли;
	
	МассивИмен = Новый Массив;
	Для Каждого Колонка Из Тз1.Колонки Цикл
		МассивИмен.Добавить(Колонка.Имя);
	КонецЦикла;
	
	ПерваяСтрока1 = Тз1.Получить(0);
	ПерваяСтрока2 = Тз2.Получить(0);
	
	ПоследняяСтрока1 = Тз1.Получить(Количество1-1);
	ПоследняяСтрока2 = Тз2.Получить(Количество1-1);
	
	Для Каждого Имя Из МассивИмен Цикл
		Если ПерваяСтрока1[Имя] <> ПерваяСтрока2[Имя] Тогда
			Возврат Истина;
		КонецЕсли;
		
		Если ПоследняяСтрока1[Имя] <> ПоследняяСтрока2[Имя] Тогда
			Возврат Истина;
		КонецЕсли;
	КонецЦикла;
		
	Если Количество1 <= 2 Тогда
		Возврат Ложь;
	КонецЕсли;
	
	МассивОтложенныхЗадач = Новый Массив;
	МассивОтложенныхЗадач.Добавить(0);
	МассивОтложенныхЗадач.Добавить(Количество1 - 1);
	ИндексОтложенныхЗадач = 1;
	
	Пока Истина Цикл
		
		Если ИндексОтложенныхЗадач < -1 Тогда
			Прервать;
		КонецЕсли;
			
		ПервыйИндекс = МассивОтложенныхЗадач[ИндексОтложенныхЗадач-1];
		ПоследнийИндекс = МассивОтложенныхЗадач[ИндексОтложенныхЗадач];
		ЦентральныйИндекс = Цел( (ПервыйИндекс + ПоследнийИндекс)/2 );
		
		//сравним центальную строку
		ЦентральнаяСтрока1 = Тз1.Получить(ЦентральныйИндекс);
		ЦентральнаяСтрока2 = Тз2.Получить(ЦентральныйИндекс);
		
		Для Каждого Имя Из МассивИмен Цикл
			Если ЦентральнаяСтрока1[Имя] <> ЦентральнаяСтрока2[Имя] Тогда
				Возврат Истина;
			КонецЕсли;
		КонецЦикла;
		
		//удалим текущий кусок
		ИндексОтложенныхЗадач = ИндексОтложенныхЗадач - 2;
		
		//положим новые задачи сравнения
		Если ЦентральныйИндекс - ПервыйИндекс > 1 Тогда
			ИндексОтложенныхЗадач = ИндексОтложенныхЗадач + 2;
			МассивОтложенныхЗадач[ИндексОтложенныхЗадач-1] = ПервыйИндекс; 
			МассивОтложенныхЗадач[ИндексОтложенныхЗадач] = ЦентральныйИндекс;
		КонецЕсли;
		
		Если ПоследнийИндекс - ЦентральныйИндекс > 1 Тогда
			ИндексОтложенныхЗадач = ИндексОтложенныхЗадач + 2;
			МассивОтложенныхЗадач[ИндексОтложенныхЗадач-1] = ЦентральныйИндекс;
			МассивОтложенныхЗадач[ИндексОтложенныхЗадач] = ПоследнийИндекс;
		КонецЕсли;
		
	КонецЦикла;
	
	Возврат Ложь;
		
КонецФункции 
Показать


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

p.s. неплохо было бы отдать вознаграждение...
265. awk 741 30.10.14 22:34 Сейчас в теме
(264) IvanAlekseev, Алгоритм не возвращает количественных показателей. Только Качественные. На если передать две идентичные таблицы работать будет неприемлемо медленно. Для целей узнать разные или нет таблицы самый быстрый способ это свертка.
269. ildarovich 7865 30.10.14 23:18 Сейчас в теме
(264) IvanAlekseev, Иван, я понимаю, сегодня пятница, но ...

Во-первых, в этом коде вы ПЫТАЕТЕСЬ решить ДРУГУЮ задачу: ваш чудо-юдо алгоритм возвращает ИСТИНА или ЛОЖЬ, а здесь требуется возвратить таблицу индексов ВСЕХ отличающихся строк и для каждой отметить (добавлена, изменена, удалена);

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

При сравнении на равенство есть более простой и быстрый способ: отсортируйте строки, сериализуйте таблицы, сравните результат.

В общем, ваш ключ не от нашей двери, но вот есть ли вообще для этого ключа дверь? - Заставили задуматься.
270. awk 741 30.10.14 23:21 Сейчас в теме
(269) ildarovich, Может сортировку из условия убрать? Тогда правда слияние тормозит...
275. ildarovich 7865 30.10.14 23:35 Сейчас в теме
(270) awk, да, можно, а для слияния можно отдельно сортировать - вне замера.
277. awk 741 30.10.14 23:43 Сейчас в теме
(275) ildarovich, Условия должны быть равные. Либо сортированы для всех, либо нет. Кстати есть мысль Т1.Кол() = Т2.Кол()/2; Там хэш и поиск должны порвать всех (по идее).
281. ildarovich 7865 30.10.14 23:54 Сейчас в теме
(277) awk, 100% добавлений? - А не многовато? - Или 50% удалено, с другой стороны. 2/3 - 3/4 еще куда ни шло.
283. awk 741 30.10.14 23:58 Сейчас в теме
(281) ildarovich, Тут размер второй таблицы главное.... Это снизит в два раза затраты на построение бинарного дерева (индекс) и хеша...
290. IvanAlekseev 77 31.10.14 09:55 Сейчас в теме
(269)"Во-первых, в этом коде вы ПЫТАЕТЕСЬ решить ДРУГУЮ задачу: ваш чудо-юдо алгоритм возвращает ИСТИНА или ЛОЖЬ, а здесь требуется возвратить таблицу индексов ВСЕХ отличающихся строк и для каждой отметить (добавлена, изменена, удалена);"

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

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

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

"При сравнении на равенство есть более простой и быстрый способ: отсортируйте строки, сериализуйте таблицы, сравните результат."

По условию задачи строки УЖЕ отсортированы.
291. awk 741 31.10.14 10:14 Сейчас в теме
(290) IvanAlekseev, Я смотрю вы write only.... :)))
dj_serega; IvanAlekseev; +2 Ответить
292. dj_serega 392 31.10.14 10:23 Сейчас в теме
(291) awk, тут много таких. Не у всех есть время фантазировать над алгоритмами. =)
293. awk 741 31.10.14 11:01 Сейчас в теме
(292) dj_serega, Данные "фантазии" сокращают время "боевой" разработки.
272. awk 741 30.10.14 23:23 Сейчас в теме
А есть ли быстрый способ проверки на упорядоченность?
279. ildarovich 7865 30.10.14 23:48 Сейчас в теме
(272) awk, О(N) в худшем случае вроде бы по любому. А в среднем - какие-либо поразрядные. В общем, это разновидность алгоритмов сортировки - а их до фига и новые постоянно открывают.
280. awk 741 30.10.14 23:52 Сейчас в теме
(279) ildarovich, Пузырьковая О(n^2) вроде была, а лучшая пока O(n*Log(n))
282. ildarovich 7865 30.10.14 23:56 Сейчас в теме
(280) awk, для проверки только одна фаза работает, поэтому оценки другие. И это оценки наихудшего, а сейчас оптимизируют "средний" случай. А зачем нам это?
284. awk 741 30.10.14 23:59 Сейчас в теме
(282) ildarovich, Скиена писал, что если он сделает алгоритм и скажет, что тот работает 4с на 5000 строк, а он отработает 1с, то это лучше чем он скажет 1с, а работать будет 4с.
287. antares2010 31.10.14 08:15 Сейчас в теме
Вот отличная обработка сравнения табличных документов http://infostart.ru/public/104596/
294. It-developer 24 31.10.14 12:46 Сейчас в теме
Я знаю правильный ответ на данный вопрос. Оптимально ( С ТОЧКИ ЗРЕНИЯ СКОРОСТИ) будет сравнивать перебором выборкой строк каждой таблицы по ключу и ... УДАЛЯТЬ СОВПАДАЮЩИЕ ЗНАЧЕНИЯ.
Это будет быстрее всего. Я знаю, т. к. это люди уже делали на одном из предприятий, где я работал. Все эти запросы и другое проиграли в производительности
296. ildarovich 7865 31.10.14 13:28 Сейчас в теме
(294) It-developer, словам здесь веры нет - код давайте
298. YanTsys 12 31.10.14 14:55 Сейчас в теме
(294) It-developer, удалять это оптимально? ну это только в том случае если удалять из массива индексов и то не всегда, как правило удаление требует сдвижки элементов находящихся за удаляемым, а при больших объемах такая сдвижка очень затратна по времени... так что НЕ ВЕРЮ :)

А фраза
Я знаю, т. к. это люди уже делали на одном из предприятий, где я работал.

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

И кстати вы должны знать что одни и те же алгоритмы на разных языках программирования и с разными объектами будут исполняться с разной скоростью... В 1с например критично количество строк в коде... Сомневаюсь что у вас там ставился эксперимент именно с таблицами значений.
dj_serega; awk; +2 Ответить
299. Serginio 938 31.10.14 15:26 Сейчас в теме
(298) Обычно индексы построены на Б+ дереве, да и удаление из хэш таблицы не затратная операция.
Почитай на досуге http://rsdn.ru/article/alg/tlsd.xml
300. awk 741 31.10.14 15:33 Сейчас в теме
(299) Serginio, Судя по результатам тестов 1С и использует хэш для соответствия и бинарное дерево для индекса. Но это лишь догадки...
303. Serginio 938 31.10.14 19:03 Сейчас в теме
(300) Ну раз они свою БД сделали там все эти структуры есть. Единственно, что для соответствия можно было бы в качестве ключа принимать массив ключей. Очень не хватает группировок как в (115). Вообще не хватает аналога Linq как для коллекций так и для запросов к БД.
Ну и говоря о Linq не забываем про замыкания/
В том числе работа с ассинхронными методами аля await, и совмещение клиентского и серверного кода опять
http://www.forum.mista.ru/topic.php?id=707805&page=3#275
http://www.forum.mista.ru/topic.php?id=707805&page=2#175
304. awk 741 31.10.14 21:04 Сейчас в теме
(303) Serginio, Я с c# на джаву слез и без линку, там прекрасно живется. Особенно если groovy взять.
305. Serginio 938 31.10.14 21:50 Сейчас в теме
(304) 1С тоже прекрасно без функциональщины живут и думают, что большего и не надо. Однако как только появился LINQ в Net его стали активно использовать. Но кстати с Full Join там немного попотеть нужно http://habrahabr.ru/sandbox/39626/
306. awk 741 31.10.14 22:15 Сейчас в теме
(305) Serginio, да я в 2007 так же думал. и в 2011... Но в 2012 я понял, что на скорость разработки linq не влияет. На читабельность - то же. Приятная фишка - не более того.
308. Serginio 938 31.10.14 23:28 Сейчас в теме
(306) Нескажи. Многие вещи за счет ленивости можно делать намного проще. В том числе и в EF по сравнению с SQL.
Например в 1С приходится писать портянки кода и очень часто либо плодить временные таблицы либо склеивать текст запроса без всякого синтаксического контроля. Ну да ладно, не хочу спорить просто констатирую, что популярность в NET Linq очень высока
(307) Спасибо, часто слышал, но почему то не удостоился посмотреть.
333. Serginio 938 01.11.14 23:31 Сейчас в теме
(308) В том, что там идет в основном поиск и можно оценить эффективность двоичного поиска и поика по хэшу, а так же посмотреть реальную скорость поиска. Ты не нервничай, а слушай дедушку.
(323) Зачем? Я показываю реальные затраты на поиск, и можно посчитать какие затраты идут на интерпретатор 1С
(327) А поиск в массиве?
(324) Уважаемый ildarovich я там комментарии для кого писал?
(329) Ну тогда объясните наивному, по какому алгоритму происходит поиск по индексированному полю?
336. awk 741 01.11.14 23:47 Сейчас в теме
(333) Serginio, Что поиск? Цикл Т1 = н операций, поиск log м операций цикл Т2 m операций получаем n * log m + С*m = n*log m = получение из соответствия и сравнение = C
338. Serginio 938 02.11.14 00:03 Сейчас в теме
(336) Прошу прощения, не заметил, что одинаковые и измененные это Соответствие.
Но тогда зачем в (183) и (224) Нужно соответствие, если достаточно массива. Стоит тогда переписать эти алгоритмы.
340. Serginio 938 02.11.14 08:43 Сейчас в теме
(336) Тогда лучше 135 сделать как 321, сделать Одинаковый и различные массивами и обращение к ним не через точку, а напрямую как в (224)
Либо добавить в 135 отдельно соответствие для запоминания дублей. Тогда алгоритмы будут правильными.
337. ildarovich 7865 01.11.14 23:54 Сейчас в теме
(333) Serginio, у меня нет цели доказывать свою правоту или здесь кого-то учить. Я сам хочу чему-нибудь научиться. Но ваши суждения для меня - это какая-то каша, не связанная с реальностями 1С, которую я никак не могу использовать в улучшении решения обсуждаемой задачи. Поэтому перестаю дискутировать. Да и начинал зря. Для себя делаю вывод, что разных способов три: свертка, слияние, полное соединение (через соответствие или индекс).
339. Serginio 938 02.11.14 01:09 Сейчас в теме
(337) Вообще то слияние это тоже полное соединение.
Читаем ВИКИ Операция соединения (СУБД)

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

Алгоритм соединения вложенными циклами.
Алгоритм соединения хэшированием.
Алгоритм соединения слиянием сортированных списков.
302. Serginio 938 31.10.14 17:00 Сейчас в теме
414. It-developer 24 26.11.14 17:44 Сейчас в теме
(298) YanTsys, да вы просто любители пописать всякую чушь на форумах :))
Ок. Папочка покажет вам код ;)
ТЗ1, ТЗ2 - 2 таблицы. ПолеСравнения - есть в каждой из таблиц.

ТЗ1.Индексы.Добавить(ПолеСравнения );
ТЗ2.Индексы.Добавить(ПолеСравнения );

к1 = ТЗ1.Количество();

Пока к1 > 0 Цикл
ПараметрыОтбора = Новый Структура;
ПараметрыОтбора.Вставить("ПолеСравнения", ТЗ1[к1].ПолеСравнения);
НайденныеСтроки = ТЗ2.НайтиСтроки(ПараметрыОтбора);
Если НайденныеСтроки.Количество() > 0 Тогда
Для каждого НайденнаяСтрока Из НайденныеСтроки Цикл
ТЗ2.Удалить(НайденнаяСтрока)
КонеЦикла;
ТЗ1.Удалить(к1)
КонецЕсли;
к1 = к1 - 1;
КонеЦикла;

// ----
На выходе - отличающиеся таблицы
415. ildarovich 7865 26.11.14 22:54 Сейчас в теме
(414) It-developer, по этому коду минимум четыре замечания:
1) непонятно, зачем создается индекс по полю сравнения в ТЗ1 - он нигде не используется;
2) исходные таблицы не должны меняться, поэтому в замер времени работы программы нужно будет включить время на создание копий таблиц;
3) проверив только поле сравнения, нельзя судить об одинаковости строк. Перед удалением вам потребуется еще пробежаться по элементам строк, чтобы их сравнить;
4) цикл по найденным строкам не нужен - мы договорились, что поле сравнение является ключом, то есть для заданного отбора по полю сравнения никогда не может найтись больше одной строки.
Вообще идея понятная. Вам кажется, что поиск в уменьшающейся таблице ТЗ2 будет идти быстрее и это компенсирует время на удаление строки с перестройкой индекса. Но это, скорее всего, не так. Впрочем, после внесения исправлений по п.1)-4) можно будет провести испытания.
alexscamp; Yashazz; dj_serega; awk; +4 Ответить
417. It-developer 24 27.11.14 18:00 Сейчас в теме
(415) ildarovich,

//ТЗ_1 - таблица начальная 1
//ТЗ_2 - таблица начальная 2

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

// чтобы не портить таблицы начальные
ТЗ1 = ТЗ_1.Скопировать();
ТЗ2 = ТЗ_2.Скопировать();

//ТЗ1.Индексы.Добавить(ПолеСравнения); // Согласен - можно убрать
//ТЗ2.Индексы.Добавить(ПолеСравнения);

к1 = ТЗ1.Количество();

Пока к1 > 0 Цикл

ПараметрыОтбора = Новый Структура;
Для Каждого Кол Из ТЗ1.Колонки Цикл
ПараметрыОтбора.Вставить(Кол.Имя, ТЗ1[к1][Кол.Имя]);
КонецЦикла;

НайденныеСтроки = ТЗ2.НайтиСтроки(ПараметрыОтбора);
Если НайденныеСтроки.Количество() > 0 Тогда
ТЗ2.Удалить(НайденныеСтроки[0])
ТЗ1.Удалить(к1)
КонецЕсли;

к1 = к1 - 1;
КонеЦикла;
416. awk 741 27.11.14 14:12 Сейчас в теме
(414) It-developer, + к (415) Оформляйте код нормально. Его не машины читают.
301. Serginio 938 31.10.14 16:04 Сейчас в теме
(294) На самом деле (136) (183) (224) на одном уровне. Просто по условию задачи нужно выводить не только разные но и одинаковые значения.
А так да на индексированной таблице с учетом реалий интерпретатора 1С будет оптимальным. Хотя с по алгоритмам соответствие и быстрее, но затраты на засовывание строк в соответствие будет затратнее, чем одна операция индексирования.
295. awk 741 31.10.14 13:25 Сейчас в теме
Запросы на серверной версии в 1000 раз медленнее работают. 100 строк
Прикрепленные файлы:
297. ildarovich 7865 31.10.14 13:35 Сейчас в теме
(295) awk, у меня другие данные. Там запросы также не выигрывают, но и не проигрывают так много.

Нумерация и сами методы пока в первых вариантах. Все еще не переделал обработку тестирования (
Прикрепленные файлы:
315. Serginio 938 01.11.14 15:43 Сейчас в теме
314 + Вот нетовская стандартная функция хэширования для строк

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail), SecuritySafeCritical, __DynamicallyInvokable]
public override unsafe int GetHashCode()
{
    if (HashHelpers.s_UseRandomizedStringHashing)
    {
        return InternalMarvin32HashString(this, this.Length, 0L);
    }
    fixed (char* str = ((char*) this))
    {
        char* chPtr = str;
        int num = 0x15051505;
        int num2 = num;
        int* numPtr = (int*) chPtr;
        int length = this.Length;
        while (length > 2)
        {
            num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
            num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
            numPtr += 2;
            length -= 4;
        }
        if (length > 0)
        {
            num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
        }
        return (num + (num2 * 0x5d588b65));
    }
}
Показать
316. ildarovich 7865 01.11.14 16:05 Сейчас в теме
(315) Serginio, есть очень подходящий случаю анекдот:
Дедушка-программист внуку: внучек, возьми мои скрипты.
Внук отвечает: да не нужны они нам, у нас своих полный дом.
А дедушка: так у вас скачанные, а я сам писал
Не стоит здесь грузить людей результатами своих давних изысканий, если они ПРЯМО не относятся к теме. Я лучше Сэджвика почитаю, чем в доморощенных методах разбираться, которые не прошли серьезную апробацию, не признаны научным сообществом или не лежат в основе всеми используемых библиотек. Я не понаслышке представляю, как издаются журналы типа Хакер или RSDN и кто туда пишет. Но, если бы это имело отношение к делу - с удовольствием почитал, а это не так!
Когда вы говорите
На самом деле всего 3 алгоритма сложности O(n log n), O(n) и существует
(136) Это двоичный поиск по индексу O(n log n)
(183) Это поиск по хэшу в массиве O(n)
(224) Это слияние O(n)
1) избегайте слов "на самом деле"
2) уточняйте о каких КОНКРЕТНО алгоритмах вы говорите. О поиске в отсортированном списке, о слиянии отсортированных массивов, или о чем еще.
3) уточняйте, какое место занимают эти алгоритмы в нашей задаче.
Пожалуйста.
Иначе непонятно, как применять эти сведения в нашей задаче.
317. Serginio 938 01.11.14 16:31 Сейчас в теме
(316) Внучёк ну давай тебе растолкую. Раз ты Сэджвика еще не читал.

(136) Поиск по индексу в ТЗ Это двоичный поиск по индексу O(n log n)
(183) Поиск в соответствие по Хэшу Это поиск по хэшу в массиве O(n)
(224) Это слияние O(n)
Если что то непонятно, то задавай конкретные вопросы.
А насчет алгоритмов, то они построены уже на известных и изученных алгоритмов. Единственно, что для нет из-за GC лучше использовать массивы структур, а не массивы классов. Все алгоритмы давно известны, иногда просто нужно правильно их сочетать.

Ну и Сэджвика и Бакнелл Д. каждому программисту нужно не просто прочитать, но и понять
318. ildarovich 7865 01.11.14 17:59 Сейчас в теме
(317) Serginio,
Поиск по индексу в ТЗ Это двоичный поиск по индексу O(n log n)
n - это число строчек в ТЗ?
"Поиск" - это одна операция ТЗ.Найти(Значение, "ПолеИндекса")?
Получается, что если для 10 000 строк время поиска (индекс создан заранее) будет 1 мсек, то для 20 000 строк - 2 мсек, 40 000 - 8 мсек, 80 000 - 24 мсек, 160 000 - 64 мсек и так далее?
Или "Это" нужно по другому понимать? Или правильнее написать O(n log m), где n - число строк в ведущей таблице (из которой берутся ключи), а m - в ведомой (где производится поиск). Или имеется ввиду, что алгоритм (136) основан на операции двоичного поиска и поэтому его быстродействие в можно оценить числом операций поиска n и временем одного поиска, которое оценивается как O(log m). - Так?
То есть под двоичным поиском вы понимали именно это? - А я было подумал про какое-то хитрое быстрое слияние, экономящее операции сравнения, основанное на дихотомии. И даже думать над ним начал.
Но если так, тогда ХэшМатч по вашим формулам будет всегда перекрывать двоичный поиск (начиная с некоторого m, которое и 1 может быть равно) и зачем его вообще рассматривать?
Итак, в вашем изложении название способа сравнения ТЗ "двоичный поиск" - это всего лишь использование операции ТЗ.Найти(Значение, "ПолеИндекса")? И вы рекомендуете его также исследовать наряду с ХэшМатч? - Все так?

Но если вы на этом уровне классифицируете алгоритмы, то почему не добавляете свертку. К чему она будет относится? Как оценить ее быстродействие? Она будет четвертой? - А вы говорили, что методов всего три?
325. Serginio 938 01.11.14 22:59 Сейчас в теме
(318) Про свертку я уже писал, что внутри могут быть 3 алгоритма, но так как в 1С будет 1 вызов то практически общее время будет зависеть только от заполнения. Если бы ты внимательно посмотрел на результаты данных то понял, что на компиляторах обработка в десятки тысяч строк выполняется очень быстро, по сравнению с выполнение интерпретатора 1С.
В примере ищется количество слов в тексте.
Всего слов 500 000 из них уникальных 22 000. Заполнение и поиск на Хэш таблице на тех компах 0.08 сек.
А тут на 10 000 результаты около секунды
328. ildarovich 7865 01.11.14 23:09 Сейчас в теме
(325) Serginio, ну причем здесь это??? - При чем?
Мы не обсуждаем алгоритм поиска слов в тексте. - А если б обсуждали - вот пример с соответствием (Пример 2):
Эффективная обработка данных в оперативной памяти за счет использования коллекции "соответствие"
А вот пример решения той же задачи ЗАПРОСОМ!
Ну и что? - Какое отношение это имеет к действительно актуальной, но СОВЕРШЕННО ДРУГОЙ задаче сравнения таблиц?
319. ildarovich 7865 01.11.14 19:52 Сейчас в теме
(317) Serginio, я провел эксперименты. Оказалось, что время поиска по индексу, построенному по одному полю таблицы значений, НЕ ЗАВИСИТ от числа строк в таблице.
Для этого я создавал таблицы с одним столбцом и с числом строк от 1 миллиона до 5 миллионов, заполненными числами от 0 до 999999, для единственного столбца строил индекс, а затем выполнял 1000000 поисков случайных чисел. Замерял время. Результаты видны на скриншоте. - Время поиска одно и то же. А должно вырасти с 1 до 4 в два раза. Что скажете? - Может быть, поиск по индексу в таблице значений <> "двоичный поиск"? В связи с этим как теперь понимать все ранее сказанное? И особенно вот это
Внучёк ну давай тебе растолкую
Прикрепленные файлы:
320. ildarovich 7865 01.11.14 21:10 Сейчас в теме
Вот еще информация, которая кое-что объясняет, полученная на базе той-же обработки.
Оказывается, что поиск по соответствию быстрее, чем поиск по индексу в 1,5 - 2 раза.
Но построение индекса примерно в два раза быстрее, чем заполнение соответствия.
Отсюда следует, что, используя соответствие, мы выигрываем в цикле, но проигрываем в подготовке (конечно, за счет того, что заполнение соответствие - не единая операция). Навскидку примерно получается, что использовать соответствие выгоднее, когда число операций поиска больше, чем строк в таблице.
Прикрепленные файлы:
321. Serginio 938 01.11.14 22:31 Сейчас в теме
(320) Об этом я и писал, что увеличение количества операторов 1С сильно тормозит.
По поводу (135) Там есть два алгоритма двоичный поиск и поиск перебором

Функция СравнитьТаблицы(Т1,Т2,Колонки, Ключ)
    Результат = Новый Структура("Одинаковые, Т1, Т2, Измененные", Новый Соответствие, Новый Массив, Новый Массив, Новый Соответствие);
    Т2.Индексы.Добавить(Ключ);
    Для Каждого СтрТ1 Из Т1 Цикл
        СтрТ2 = Т2.Найти(СтрТ1[Ключ], Ключ);
        Если СтрТ2 = Неопределено Тогда
            Результат.Т1.Добавить(СтрТ1);
        Иначе
            Если КолонкиИдентичны(СтрТ1, СтрТ2, Колонки)  Тогда
                Результат.Одинаковые.Вставить(СтрТ2, СтрТ1);
            Иначе 
                Результат.Измененные.Вставить(СтрТ2, СтрТ1);
            КонецЕсли;

         // Добавим удаление найденной строки
         Т2.Удалить(СтрТ2);
        КонецЕсли;
    КонецЦикла;
    Для Каждого СтрТ2 Из Т2 Цикл
// Вот здесь уже сложность O(n в квадрате)
        //Если Результат.Одинаковые[СтрТ2] = Неопределено
        //    И Результат.Измененные[СтрТ2] = Неопределено Тогда
            Результат.Т2.Добавить(СтрТ2);
        //КонецЕсли;
    КонецЦикла;
    Возврат Результат;
КонецФункции
Показать


Правда здесь могут быть утечки памяти из-за циклических ссылок
323. awk 741 01.11.14 22:56 Сейчас в теме
(321) Serginio, Может перейдем на Си? Что бы на 1С не кивать?
324. ildarovich 7865 01.11.14 22:57 Сейчас в теме
(321) Serginio, я готов сильно разочароваться. Возьмем приведенный кусок кода
Функция СравнитьТаблицы(Т1,Т2,Колонки, Ключ)
    Результат = Новый Структура("Одинаковые, Т1, Т2, Измененные", Новый Соответствие, Новый Массив, Новый Массив, Новый Соответствие);
    Т2.Индексы.Добавить(Ключ);
    Для Каждого СтрТ1 Из Т1 Цикл
        СтрТ2 = Т2.Найти(СтрТ1[Ключ], Ключ);
        Если СтрТ2 = Неопределено Тогда
            Результат.Т1.Добавить(СтрТ1);
        Иначе
            Если КолонкиИдентичны(СтрТ1, СтрТ2, Колонки)  Тогда
                Результат.Одинаковые.Вставить(СтрТ2, СтрТ1);
            Иначе 
                Результат.Измененные.Вставить(СтрТ2, СтрТ1);
            КонецЕсли;

         // Добавим удаление найденной строки
         Т2.Удалить(СтрТ2);
        КонецЕсли;
    КонецЦикла;
    Для Каждого СтрТ2 Из Т2 Цикл
// Вот здесь уже сложность O(n в квадрате)
        //Если Результат.Одинаковые[СтрТ2] = Неопределено
        //    И Результат.Измененные[СтрТ2] = Неопределено Тогда
            Результат.Т2.Добавить(СтрТ2);
        //КонецЕсли;
    КонецЦикла;
    Возврат Результат;
КонецФункции
Показать

Покажите, где здесь двоичный поиск и где здесь поиск перебором. Начните с того, двоичный поиск ЧЕГО. Поиск перебором ЧЕГО. Выделите фрагменты кода, где, как вам КАЖЕТСЯ, они есть.
327. awk 741 01.11.14 23:03 Сейчас в теме
(321) Serginio, Там сложность изначального алгоритма: O(n * log(m) + m) = O(n*log(m)) то есть удаление O(n * log(m) + m1) = O(n*log(m))
329. ildarovich 7865 01.11.14 23:20 Сейчас в теме
(327) awk, в (319) я показал, что log(m) выдумал Serginio, наивно полагая, что операция
Т2.Найти(СтрТ1[Ключ], Ключ)
выполняется методом двоичного поиска или эквивалентна ему по трудозатратам. - С чего он это взял?
331. awk 741 01.11.14 23:24 Сейчас в теме
(329) ildarovich, Наверно ассоциировал с SQL где индексы хранятся в B-Tree. В Яве HashSet - это RB Tree... Вопрос у 1С массив - это динамический массив или связанный список?
332. ildarovich 7865 01.11.14 23:30 Сейчас в теме
(331) awk, не знаю, честно говоря. Вряд-ли связный список. Возможно, какая-то комбинированная структура. Судя по замерам скорости.
А вообще, можно было бы замерить скорость вставок и удалений и понять, зависимость от размера. А можно спросить того, кто дебаггером 1С ковырял.
334. Serginio 938 01.11.14 23:35 Сейчас в теме
(331) Динамический это такой http://rsdn.ru/forum/src/450320
Практика показывает, что это аналог List, то есть массив размером больше чем значений в нем и увеличение в 2 раза после полного заполнения

public void Add(T item)
{
    if (this._size == this._items.Length)
    {
        this.EnsureCapacity(this._size + 1);
    }
    this._items[this._size++] = item;
    this._version++;
}
Показать
335. Serginio 938 01.11.14 23:46 Сейчас в теме
(329) Если бы ты соизволил посмотреть результаты, то увидел бы что скорость Хэш таблицы в 4 раза выше чем бинарный поиск на компиляторе.
И соответственно 1,5-2 раза скорость выше на соответствии как раз и показывает что индекс в таблице это Б+ дерево, соответствие это Хэш таблица, учитывая что большое количество времени уходит на интерпритацию команды, которая и нивелирует скорость Хэш адгоритма.
326. ildarovich 7865 01.11.14 23:00 Сейчас в теме
330. Serginio 938 01.11.14 23:22 Сейчас в теме
Кстати проверь пожалуйста влияние на скорость пароля на форму, на одних и тех же данных сохранив таблицы в файл
351. Serginio 938 05.11.14 10:45 Сейчас в теме
Кстати запаролил модуль дало прирост 10% Но теперь обработка не открывается, конфигуратор вылетает с ошибкой
352. dj_serega 392 05.11.14 11:26 Сейчас в теме
(351) Serginio, Версия 1С какая?
355. Serginio 938 05.11.14 11:59 Сейчас в теме
(352) 1С:Предприятие 8.3 (8.3.5.1098)
357. dj_serega 392 05.11.14 12:03 Сейчас в теме
(355) Serginio, Просто в одной из 8.3 была проблема с запаролеными модулями. Позже это исправили.
Конкретней это вылетало на глобальном поиске если встречался запароленый модуль.
Serginio; +1 Ответить
358. Serginio 938 05.11.14 12:13 Сейчас в теме
Кстати доступ по индексу к полю ТЗ не дает ощутимого премущества перед обращению через имя колонки
Старт = ТекущаяУниверсальнаяДатаВМиллисекундах() ;

	
	Для каждого Стр Из Тз1 Цикл
	
	Значение=стр[0];
	КонецЦикла;

 Сообщить("Доступ по индексу " + (ТекущаяУниверсальнаяДатаВМиллисекундах()  - Старт)+ " мсек.");

Старт = ТекущаяУниверсальнаяДатаВМиллисекундах() ;

Ключ="Поле0";	
	Для каждого Стр Из Тз1 Цикл
	
	Значение=стр[Ключ];

КонецЦикла;
 Сообщить("Доступ по имени " + (ТекущаяУниверсальнаяДатаВМиллисекундах()  - Старт)+ " мсек.");
Показать


Доступ по индексу 56 мсек.
Доступ по имени 59 мсек.

То есть внутри методы выполняются значительно быстрее, чем вызов метода интерпретатором.
385. Serginio 938 05.11.14 20:27 Сейчас в теме
Как то особо не заметил прироста скорости от всё в одну строку.
Посмотри алгоритм для ТЗ
Функция СравнениеТаблицЗначений(Т1, Т2Ориг) Экспорт
	
	Ответ = Новый Соответствие;
	Т2=Т2Ориг.Скопировать();
	ИмяКлюча = Т2.Колонки[0].Имя;
	
	Т2.Индексы.Добавить(ИмяКлюча);
	
	ВГраница = Т1.Колонки.Количество() - 1;
	
	Для Каждого Ведущая Из Т1 Цикл
		Ключ = Ведущая[0]; 
		Ведомая = Т2.Найти(Ключ, ИмяКлюча);
		Если Ведомая = Неопределено Тогда 	
			Ответ[Ключ] = -1 	
		Иначе 	
			Для ё = 1 По ВГраница Цикл 
				Если Ведущая[ё] <> Ведомая[ё] Тогда	
					Ответ[Ключ] = 0; 
					Прервать 
				КонецЕсли КонецЦикла;
				Т2.Удалить(Ведомая) КонецЕсли 
		КонецЦикла;	
		Для Каждого Ведомая Из Т2 Цикл  Ключ = Ведомая[0]; 	Ответ[Ключ] = 1 КонецЦикла;
		
		Результат = Новый ТаблицаЗначений; Результат.Колонки.Добавить("Ключ"); Результат.Колонки.Добавить("Значение");
		
		Для Каждого Элемент Из Ответ Цикл 
			ЗаполнитьЗначенияСвойств(Результат.Добавить(), Элемент) 
		КонецЦикла;
		
		Результат.Колонки[1].Имя = "Знак";
		
		Возврат Результат
		
	КонецФункции
Показать
388. ildarovich 7865 05.11.14 23:42 Сейчас в теме
(385) Serginio, посмотрел - старый вариант выбросил. Быстрее ХэшМап на 10000 строк (что пока проверил), хотя код по структуре один в один.
389. awk 741 05.11.14 23:45 Сейчас в теме
(388) ildarovich, Хэш и должен быть быстрей. Слияние на втором, а поиск по индексу на третьем. Все остальное - это задержки интерпретатора. Если мы это опровергнем, то можем считать себя Резенфордами...
391. ildarovich 7865 06.11.14 00:42 Сейчас в теме
(389) awk, что то я уже начал терять ориентиры. Вот текущие результаты. Не могу понять, почему у меня хэш-мап опустился. Слияние я с подсказками Serginio переписал. Соединение по индексу вроде то же, что и хэш-мап, но он проигрывает, собака. Не пойму, в чем дело - там и кода всего ничего. В общем, вот текущие результаты (было и так, что слияние было вообще на втором месте).
Тут в соседней ветке показали читерский прием, как можно еще быстрее объединение таблиц для свертки делать - если колонок больше 6 и на больших таблицах свертка еще быстрее работать будет. Но пока заканчиваю, надоело. Обработку в текущем состоянии (там все методы) можете брать.
Прикрепленные файлы:
ТестСпособовСравненияТаблицЗначений.erf
392. awk 741 06.11.14 10:11 Сейчас в теме
(391) ildarovich, Надо бы показатели оперативной памяти в динамике снять. Боюсь на 50 000 просто хэш требует увеличения оперативки, а нужный размер вычисляется как удвоенный размер хэша. Теоретически на 75 - 60 тысячах хэш должен опять прийти в норму...
399. ildarovich 7865 06.11.14 23:00 Сейчас в теме
(392) awk, (390) Serginio,
Предлагаю начать все же эту дискуссию заканчивать. Новых идей нет.
- Построитель отчета?
- СКД?
- Совсем не посмотрели "Анализ данных", а вдруг там готовые методы есть?
Нужно какую-то резолюцию подготовить. Потом согласовать ее и отметить как "это лучший ответ" (с помощью ТС).
Другой вариант - все изыскания в одну статью поместить и выводы там сделать (не провалится ли эта статья в прокате?).
- У кого какие предложения?
Труда вложено много, жалко, если пропадет, хотя понимания задачи и смежных вопросов для себя самих сильно прибавилось.
Оставьте свое сообщение

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