пересечение массивов - алгоритм #532950

Уважаемые коллеги! Есть ли в 1С метод (или можно ли его придумать?), позволяющий получить "пересечение массивов" - т.е. оставить в первом массиве только те элементы. которые имеются во втором БЕЗ перебора  каждого из масивов? Задачка такая -- есть 1 массив строк (5-10) и есть 2 массив строк (~1000). Можно ли как-нить удалить из первого массива строки, которых нет во втором, без того, чтобы писать два цикла? В каком-нить RUBY это стандартный оператор языка...

запросом.

левое соединение

тогда уж внутреннее? значения уникальны в массивах?

да, внутренее.

Можно В Тогда только первый в ТЗ преобразовывать...

а как массивы в запрос передать?

да, уникальны

В запрос можно ТаблицуЗначений передать

а таблицуЗначений как?

Преобразовать в ТЗ. ТЗ параметром. Поместить во временную таблицу. Далее пакетным запросом. Если соединением - так обе. Если В(&Второймассив) - второй массив передать параметром, преобразовывать в ТЗ не надо.

мдя... сомнительное решение: гонять массив стачала в ТЗ, потом - на сервер во врем.таблицу, потом обратно, быстрее циклом перебрать

Вот как "поместить во временную таблицу"? Ну тупой,я тупой... Как пакетный запрос писать я понимаю. Как в одном из запросов пакета выбрать значения из параметра?

ВЫБРАТЬ

+ ВЫБРАТЬ    ТЗ1.Счет

просто наверняка массив тоже не изниоткуда взялся.

Спасибо большое. К сожалению, никогда так не делал и даже не знал, что так можно... Все заработало...

В конфигураторе: Справка - Поиск по справке - внешнийисточник

Для каждого Эл из М1 Цикл

всё зависит от железа и от того что вы хотите "нагрузить" сервер или клиент

Интересное решение... Щас проверю, что будет работать быстрее или запрос. Проверю на тех параметрах, что я указал вначале -1 массив 5-10 элементов, 2 массив - 900-1000

На таких количествах ставлю на .

+ чуть-чуть быстрее. должно быть

сортировка и бинарный поиск. Поиск в большем массиве элементов из меньшего.

Хотя если в меньшем массиве строк заведомо меньше Log2 количества строк в большем массиве - тогда без сортировки, и поиск перебором.

О, гуру подтягиваются... Сергей, при каких объемах массивов есть смысл замарачиваться с бинарным поиском?

Для ЗагрузитьКолонку пустые строки всё равно создавать надо. Так что спорно...

Да, быстрее в 2,5 раза. Видимо запрос начнет обгонять при десятках тысяч во втором и сотнях в первом массиве

А какой запрос использовал?

На сортировку тратится О(N*LN(N)) операций, полсе этого на проверку бинарным поиском О(K*LN(N)) операций, К - размер меньшего массива, то есть сложность алгоритма с сортировкой N*LN(N). Если отсортируем меньший массив, то на сортировку K*LN(К), на бинарный поиск поиск N*LN(К), то есть я ошибся - лучше сортировать меньший массив, тогда сложность (N*LN(K)) Без сортировки сложность алгоритма N*K, то есть даже если в меньшем массиве меньше 10 элементов, то лучше его отсортировать и бинарным. Все выкладки сделаны без перевода массива в ТЗ. В случае ТЗ - встроенный поиск работает весьма быстро, и тут уже надо проводить тесты.

а если индекс добавить?

да. правда Ваша. выигрыша по времени похоже не будет.

Добавление индекса равносильно сортировке с последующим бинарным поиском. Вообще самое быстрое - Xbase с добавленным индексом по меньшему массиву. Могу накидать код на 7.7 (восьмерки нет под рукой)

На ПОМЕСТИТЬ это не повлияет. На этом потери в основном.

а не что нить вроде хэш-таблиц?

Сергей, а накидай, а? На восьмерку я уж как-нить и сам перепишу...

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

еще

ты мне щас теорию рассказываешь или как это на самом деле реализовано в 1Ске? =)

проблема в том, что создание ДБФ-а занимает времени больше 20 мс., которые уходят на поиск перебором... Тебе нужно чтоб стало быстрее, перебора?! Именно на значениях 10 и 1000?

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

Вариант с запросом проигрывает по той же причине. Помещение во временную таблицу занимает время...

43+ разумеется, только для уникальных значений внутри каждого массива

Если взять 100 и 10000 тогда тупой перебор 1349 мс. индекс 223 мс. А если массивы как указано в 10 и 1000 тогда тупой перебор 14 мс. индекс 155 мс. Причем Индекс - практически всё потраченное время это создание файла.

Нет, реальные значения будут *10 = т.е сотни и десятки тысяч. Это пока тестовая задачка. Да, скорость очень важна. А на чем можно написать такую ВК? На ПИТОНе  или ПРОЛОГе ведь ВК для 1с-ки не напишешь...

Я вот не понимаю - все вышеперечисленные извращения находят быстрее тупого перебора?

Тогда см.

а откуда массивы взялись?

Потестить на реальных данных надо. Соотношение времён здесь озвученных решений могут существенно поменяться.

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

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

В восьмерке быстро работает "соответсвие" - оно индексировано. Работает быстрее XBase. Никакого ВК не нужно, ибо время тратится только на поиск в индексированной структуре.

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

Очень нехорошо сравнивать строки неограниченной длины.

ТЗ1 и ТЗ2. ТЗ1 колонку "количество" заполняешь 1 ТЗ2 колонку "количество" заполняешь 2 сливаешь обе ТЗ в одну. сворачиваешь и суммируешь по колонке "количество". там где "количество" равно 3, значит это значение существует в обоих. там где "количество" равно 1, значит это значение существует только в первом массиве. там где "количество" равно 2, значит это значение существует только во втором массиве.

тупой перебор 1363 мс. индекс 92 мс. ТЗ 183 мс. Это если 100 и 10000, без времени создания XBase и ТЗ. Если использовать структуру, то будет быстрее второго варианта. То есть код получится быстрее чем свернуть - и понятно почему - свернуть работает за N LN N А второй вариант это N LN K

смотри

+ Не структуру, а соответсвие. Я несколько лет назад проводил тесты - "соответствие" заметно быстрее XBase, то есть работать будет просто влет, быстрее не напишешь и на языках высокого уровня.