Вход | Регистрация
 
1С:Предприятие :: Математика и алгоритмы

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

пересечение массивов - алгоритм
Я
   Торин
 
11.02.11 - 13:23
Уважаемые коллеги!
Есть ли в 1С метод (или можно ли его придумать?), позволяющий получить "пересечение массивов" - т.е. оставить в первом массиве только те элементы. которые имеются во втором БЕЗ перебора  каждого из масивов?
Задачка такая -- есть 1 массив строк (5-10) и есть 2 массив строк (~1000). Можно ли как-нить удалить из первого массива строки, которых нет во втором, без того, чтобы писать два цикла?
В каком-нить RUBY это стандартный оператор языка...
 
 
   Живой Ископаемый
1 - 11.02.11 - 13:24
запросом.
   Живой Ископаемый
2 - 11.02.11 - 13:25
левое соединение
   Ненавижу 1С
 
3 - 11.02.11 - 13:28
(2) тогда уж внутреннее?
(0) значения уникальны в массивах?
   Живой Ископаемый
4 - 11.02.11 - 13:30
да, внутренее.
   73
 
5 - 11.02.11 - 13:34
Можно
В()

Тогда только первый в ТЗ преобразовывать...
   Торин
 
6 - 11.02.11 - 13:34
а как массивы в запрос передать?
   Торин
 
7 - 11.02.11 - 13:37
(3) да, уникальны
   ReaLg
 
8 - 11.02.11 - 13:39
(6) В запрос можно ТаблицуЗначений передать
   Торин
 
9 - 11.02.11 - 13:39
(8) а таблицуЗначений как?
   73
 
10 - 11.02.11 - 13:39
(6)Преобразовать в ТЗ. ТЗ параметром. Поместить во временную таблицу. Далее пакетным запросом.
Если соединением - так обе.
Если В(&Второймассив) - второй массив передать параметром, преобразовывать в ТЗ не надо.
   Asmody
 
11 - 11.02.11 - 13:43
мдя... сомнительное решение: гонять массив стачала в ТЗ, потом - на сервер во врем.таблицу, потом обратно, быстрее циклом перебрать
   Торин
 
12 - 11.02.11 - 13:45
(10)Вот как "поместить во временную таблицу"? Ну тупой,я тупой... Как пакетный запрос писать я понимаю. Как в одном из запросов пакета выбрать значения из параметра?
   73
 
13 - 11.02.11 - 13:47
ВЫБРАТЬ
    ТЗ1.Счет
ПОМЕСТИТЬ ТЗ1
ИЗ
    &ТЗ1 КАК ТЗ1
;

ВЫБРАТЬ
    ТЗ2.Счет
ПОМЕСТИТЬ ТЗ2
ИЗ
    &ТЗ2 КАК ТЗ2
;
ВЫБРАТЬ
    ТЗ1.Счет,
    ТЗ2.Счет КАК Счет1
ИЗ
    ТЗ1 КАК ТЗ1
        ВНУТРЕННЕЕ СОЕДИНЕНИЕ ТЗ2 КАК ТЗ2
        ПО (ТЗ2.Счет = ТЗ1.Счет)
   73
 
14 - 11.02.11 - 13:49
(13)+
ВЫБРАТЬ
    ТЗ1.Счет
ПОМЕСТИТЬ ТЗ1
ИЗ
    &ТЗ1 КАК ТЗ1
;

ВЫБРАТЬ
   ТЗ1.Счет
ИЗ
    ТЗ1 КАК ТЗ1
ГДЕ    
    ТЗ1.Счет В(&Массив2)
   Живой Ископаемый
15 - 11.02.11 - 13:49
просто наверняка массив тоже не изниоткуда взялся.
   Торин
 
16 - 11.02.11 - 13:52
(13) Спасибо большое. К сожалению, никогда так не делал и даже не знал, что так можно...
Все заработало...
   73
 
17 - 11.02.11 - 13:55
(16) В конфигураторе:
Справка - Поиск по справке - внешнийисточник
   Ненавижу 1С
 
18 - 11.02.11 - 13:55
Для каждого Эл из М1 Цикл
  Стр = ТЗ.Добавить();
  Стр.Элемент = Эл;
  Стр.Флаг = 1;
КонецЦикла;

Для каждого Эл из М2 Цикл
  Стр = ТЗ.Добавить();
  Стр.Элемент = Эл;
  Стр.Флаг = -1;
КонецЦикла;

ТЗ.Свернуть("Элемент","Флаг");
М = ТЗ.НайтиСтроки(Новый Структура("Флаг",0));
   Scooter
 
19 - 11.02.11 - 13:59
(0)всё зависит от железа и от того что вы хотите "нагрузить" сервер или клиент

как вариант, ТЗ + НайтиСтроки()
   Торин
 
20 - 11.02.11 - 14:01
(18) Интересное решение...
Щас проверю, что будет работать быстрее (18) или запрос. Проверю на тех параметрах, что я указал вначале -1 массив 5-10 элементов, 2 массив - 900-1000
   73
 
21 - 11.02.11 - 14:03
(20) На таких количествах ставлю на (18).
   НЕА123
 
22 - 11.02.11 - 14:09
(18)+
чуть-чуть быстрее. должно быть

ТЗ.ЗагрузитьКолонку(М2,"Элемент");
ТЗ.ЗаполнитьЗначения(-1,"Флаг");

Для каждого Эл из М1 Цикл
  Стр = ТЗ.Добавить();
  Стр.Элемент = Эл;
  Стр.Флаг = 1;
КонецЦикла;


ТЗ.Свернуть("Элемент","Флаг");
М = ТЗ.НайтиСтроки(Новый Структура("Флаг",0));
   NS
 
23 - 11.02.11 - 14:10
сортировка и бинарный поиск. Поиск в большем массиве элементов из меньшего.
   NS
 
24 - 11.02.11 - 14:11
Хотя если в меньшем массиве строк заведомо меньше Log2 количества строк в большем массиве - тогда без сортировки, и поиск перебором.
   Торин
 
25 - 11.02.11 - 14:13
(23) О, гуру подтягиваются... Сергей, при каких объемах массивов есть смысл замарачиваться с бинарным поиском?
   73
 
26 - 11.02.11 - 14:18
(22) Для ЗагрузитьКолонку пустые строки всё равно создавать надо. Так что спорно...
   Торин
 
27 - 11.02.11 - 14:22
Да, (18) быстрее в 2,5 раза. Видимо запрос начнет обгонять при десятках тысяч во втором и сотнях в первом массиве
   73
 
28 - 11.02.11 - 14:23
(27) А какой запрос использовал?
   NS
 
29 - 11.02.11 - 14:23
(25) На сортировку тратится О(N*LN(N)) операций, полсе этого на проверку бинарным поиском О(K*LN(N)) операций, К - размер меньшего массива, то есть сложность алгоритма с сортировкой N*LN(N). Если отсортируем меньший массив, то на сортировку
K*LN(К), на бинарный поиск поиск N*LN(К), то есть я ошибся - лучше сортировать меньший массив, тогда сложность (N*LN(K))

Без сортировки сложность алгоритма N*K, то есть даже если в меньшем массиве меньше 10 элементов, то лучше его отсортировать и бинарным.

Все выкладки сделаны без перевода массива в ТЗ. В случае ТЗ - встроенный поиск работает весьма быстро, и тут уже надо проводить тесты.
   Stepa86
 
30 - 11.02.11 - 14:24
(13)(14)(22) а если индекс добавить?
 
 Рекламное место пустует
   НЕА123
 
31 - 11.02.11 - 14:25
(26)
да. правда Ваша. выигрыша по времени похоже не будет.
   NS
 
32 - 11.02.11 - 14:26
(30) Добавление индекса равносильно сортировке с последующим бинарным поиском.

Вообще самое быстрое - Xbase с добавленным индексом по меньшему массиву. Могу накидать код на 7.7 (восьмерки нет под рукой)
   73
 
33 - 11.02.11 - 14:26
(30) На ПОМЕСТИТЬ это не повлияет. На этом потери в основном.
   Stepa86
 
34 - 11.02.11 - 14:28
(32) а не что нить вроде хэш-таблиц?
   Торин
 
35 - 11.02.11 - 14:30
(32) Сергей, а накидай, а? На восьмерку я уж как-нить и сам перепишу...
   Торин
 
36 - 11.02.11 - 14:31
(28)
Запрос.Текст = "ВЫБРАТЬ
                   |    таблицаМассива.Значение КАК Значение
                   |ПОМЕСТИТЬ таблицаМассива
                   |ИЗ
                   |    &таблицаМассива КАК таблицаМассива
                   |;
                   |
                   //////////////////////////////////////////////////////////////////////////////// 
                   |ВЫБРАТЬ
                   |    таблицаМассива.Значение
                   |ИЗ
                   |    таблицаМассива КАК таблицаМассива
                   |ГДЕ
                   |    таблицаМассива.Значение В(&массив2)";
   NS
 
37 - 11.02.11 - 14:34
(34) Расчет значения Хеш-функции по большему массиву займет больше времени, чем поиск в меньшем массиве по индексу (бинарный поиск).
   Ненавижу 1С
 
38 - 11.02.11 - 14:39
еще
Для каждого Эл из М1 Цикл
  Стр = ТЗ.Добавить();
  Стр.Элемент = Эл;
КонецЦикла;

Для каждого Эл из М2 Цикл
  Стр = ТЗ.Добавить();
  Стр.Элемент = Эл;
КонецЦикла;

ТЗ.Сортировать("Элемент");
Значение = Неопределено;
М = Новый Массив;
Для каждого Эл из ТЗ Цикл
  Если Значение=Эл.Элемент Тогда
    М.Добавить(Значение);
  КонецЕсли;
  Значение = Эл.Элемент;
КонецЦикла;
   Stepa86
 
39 - 11.02.11 - 14:44
(37) ты мне щас теорию рассказываешь или как это на самом деле реализовано в 1Ске? =)
   NS
 
40 - 11.02.11 - 15:06
проблема в том, что создание ДБФ-а занимает времени больше 20 мс., которые уходят на поиск перебором...
Тебе нужно чтоб стало быстрее, перебора?! Именно на значениях 10 и 1000?
   Stepa86
 
41 - 11.02.11 - 15:09
если массив чисто из строк и прям так нужна скорость, то может написать простенькую компоненту на более низкоуровневом и через нее? или джава скрипт заюзать...
   73
 
42 - 11.02.11 - 15:11
Вариант с запросом проигрывает по той же причине.
Помещение во временную таблицу занимает время...
   Reset
 
43 - 11.02.11 - 15:11
// Еще) ТЗ-таблица с 1 колонкой "Элемент" 
Для каждого Эл из М1 Цикл
  ТЗ.Добавить().Элемент=Эл;
КонецЦикла;
Для каждого Эл из М2 Цикл
  ТЗ.Добавить().Элемент=Эл;
КонецЦикла;

ТЗ.Колонки.Добавить("Флаг");
ТЗ.ЗаполнитьЗначения(1,"Флаг");
ТЗ.Свернуть("Элемент","Флаг");

МассивСовпадающих=Новый массив;
Для каждого Строка из ТЗ.НайтиСтроки(Новый Структура("Флаг",2)) цикл
 МассивСовпадающих.Добавить(Строка.Элемент);
КонецЦикла;
   Reset
 
44 - 11.02.11 - 15:11
43+ разумеется, только для уникальных значений внутри каждого массива
   NS
 
45 - 11.02.11 - 15:13
Процедура Сформировать()
     перем м1[100], м2[10000];
     Для а=1 по 100 цикл
         м1[а]="Алаверды"+а*750;
     Конеццикла;
     Для а=1 по 10000 цикл
         м2[а]="Алаверды"+а;
     КонецЦикла;
     т=_GetPerformanceCounter();                                 
     Для а=1 по 100 цикл
         Для б=1 по 10000 цикл   
             Если м1[а]=м2[б] тогда
                // сообщить(м1[а]); 
                 прервать;
             КонецЕсли;    
         Конеццикла;
     Конеццикла;      
      т=_GetPerformanceCounter();                                 
     Для а=1 по 100 цикл
         Для б=1 по 10000 цикл   
             Если м1[а]=м2[б] тогда
                 // сообщить(м1[а]); 
                 прервать;
             КонецЕсли;    
         Конеццикла;
     Конеццикла;    
     сообщить("тупой перебор "+(_GetPerformanceCounter()-т)+" мс.");   
     т=_GetPerformanceCounter();
     Файл = СоздатьОбъект("Xbase");
     Файл.ДобавитьПоле("Name","C","100",0);
     Файл.ДобавитьИндекс("IdxName","Name",0,0,"");      
     Файл.СоздатьФайл(КаталогИБ()+"find_NS.dbf",КаталогИБ()+"\find_NS.cdx"); 
     Файл.ЗакрытьФайл();    
     Файл.ОткрытьФайл(КаталогИБ()+"find_NS.dbf",КаталогИБ()+"\find_NS.cdx");  
     Файл.Автосохранение(1);   
     Для а=1 по 100 цикл
         Файл.Добавить();
         Файл.Name=м1[а];
     КонецЦикла;        
     Файл.ТекущийИндекс("IdxName");
     Для б=1 по 10000 цикл
         Если Файл.Найти(м2[б],0)>0 тогда
            // сообщить(м2[б]); 
             файл.удалить();
         КонецЕсли;    
     Конеццикла; 
    //файл.закрытьфайл(); 
     сообщить("индекс "+(_GetPerformanceCounter()-т)+" мс.");
КонецПроцедуры

Если взять 100 и 10000 тогда

тупой перебор 1349 мс.
индекс 223 мс.

А если массивы как указано в (0) 10 и 1000 тогда
тупой перебор 14 мс.
индекс 155 мс. Причем Индекс - практически всё потраченное время это создание файла.
   Торин
 
46 - 11.02.11 - 15:13
(40) Нет, реальные значения будут *10 = т.е сотни и десятки тысяч. Это пока тестовая задачка.
(41) Да, скорость очень важна. А на чем можно написать такую ВК? На ПИТОНе  или ПРОЛОГе ведь ВК для 1с-ки не напишешь...
   NS
 
47 - 11.02.11 - 15:14
Я вот не понимаю - все вышеперечисленные извращения находят быстрее тупого перебора?
   NS
 
48 - 11.02.11 - 15:14
(46) Тогда см. (45)
   Asmody
 
49 - 11.02.11 - 15:16
(46) а откуда массивы взялись?
   73
 
50 - 11.02.11 - 15:18
(46) Потестить на реальных данных надо.
Соотношение времён здесь озвученных решений могут существенно поменяться.
   Stepa86
 
51 - 11.02.11 - 15:20
(46) только ассемблер, он быстрее!!! а вообще вроде есть шаблоны ВК на дельфях и наверняка есть примеры пересечения массивов на них же в инете... так что собрать из этого компоненту думаю будет просто и быстро
   Торин
 
52 - 11.02.11 - 15:21
первый массив -это массив строк из внешнего файла, второй - это некий справочник внутри базы, значение текстового поля неограниченной длины...
   NS
 
53 - 11.02.11 - 15:31
(46) В восьмерке быстро работает "соответсвие" - оно индексировано. Работает быстрее XBase. Никакого ВК не нужно, ибо время тратится только на поиск в индексированной структуре.
   73
 
54 - 11.02.11 - 15:33
(52) Если там справочник, то в варианте с запросом не надо его поле выгружать в массив чтобы потом назад в запрос передавать...
Возможно быстродействия запроса будет достаточно.
   NS
 
55 - 11.02.11 - 15:42
(52) Очень нехорошо сравнивать строки неограниченной длины.
   _Atilla
 
56 - 11.02.11 - 15:44
ТЗ1 и ТЗ2.
Добавляешь колонку "количество"

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

там где "количество" равно 3, значит это значение существует в обоих.
там где "количество" равно 1, значит это значение существует только в первом массиве.
там где "количество" равно 2, значит это значение существует только во втором массиве.
   NS
 
57 - 11.02.11 - 15:56
(18)
тупой перебор 1363 мс.
индекс 92 мс.
ТЗ 183 мс.
Это если 100 и 10000, без времени создания XBase и ТЗ.
Если использовать структуру, то будет быстрее второго варианта. То есть код получится быстрее чем свернуть - и понятно почему - свернуть работает за N LN N А второй вариант это N LN K
   NS
 
58 - 11.02.11 - 15:56
(56) смотри (57)
   NS
 
59 - 11.02.11 - 16:05
+ (57) Не структуру, а соответсвие.
Я несколько лет назад проводил тесты - "соответствие" заметно быстрее XBase, то есть работать будет просто влет, быстрее не напишешь и на языках высокого уровня.


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Ветка сдана в архив. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.