Сравнение массивов

@taancer · Регистрация: 18.01.2014

Студворк — интернет-сервис помощи студентам

Здравствуйте.

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

Пример:
Коллекция 1: А В С А
Коллекция 2: С А А Е
Результат: (в скобках указан для простоты порядковый номер элемента из соответствующей коллекции)
Коллекция 1: А(2,3) В() С(1) А(2,3)
Коллекция 2: С(3) А(1,4) А(1,4) Е()

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

@Shamil1 · 02.01.2016, 04:05

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

@taancer · 02.01.2016, 18:33 **[ТС]**

Сообщение от Shamil1

Для каждой из коллекций заполняем словарь "ключ"-"список позиций", где ключ - критерии сравнения.

Спасибо

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

@Shamil1 · 03.01.2016, 03:29

Сообщение от taancer

получается очень ресурсоемко по памяти

Ресурсоёмко - это сколько гигабайт?

@taancer · 03.01.2016, 04:59 **[ТС]**

Сообщение от Shamil1

Ресурсоёмко - это сколько гигабайт?

По предварительным оценкам на гигабайты счет не идет.

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

Действительно, чего на спичках то экономить?...
Что мне еще нравится, что можно обойтись одним словарем, привязав к ключу значения обоих коллекций. думаю, это как раз будет то, что нужно.

echs · 03.01.2016, 11:04

Ребята. Я может что не так понял.
Почему бы в данном случае не составить два множества?
Пересечение этих множеств сразу выделит общие элементы.

@taancer · 11.01.2016, 00:18 **[ТС]**

Сообщение от geh

Пересечение этих множеств сразу выделит общие элементы.

Я немного слабоват в математике множеств...
Как это можно реализовать на С# ?

echs · 11.01.2016, 10:44

taancer
Задаем массив А() и заполняем его так.
Пример
А(1) здесь может быть только символ А
А(2) здесь ... только символ В
А(3) ... только С
И так далее
Итак у нас есть два массива A() и B(). Мы в цикле проверяем
Если А(i)=B(i), то это общий элемент принадлежащий обоим
множествам (заданным в виде массивов). Этот элемент
автоматически идет в массив C(i). Иными словами массив С()
будет содержать общие элементы А() и В(). И далее вам нужно
будет лишь смотреть на С()
Если элемент не принадлежит С() то его и рассматривать не надо
А если принадлежит, то он точно входит в коллекцию.
PS.
Язык С# мне неизвестен и я не могу предложить на нем код.

@Shamil1 · 11.01.2016, 10:53

Сообщение от geh

Почему бы в данном случае не составить два множества?
Пересечение этих множеств сразу выделит общие элементы.

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

Добавлено через 1 минуту

Сообщение от taancer

Как это можно реализовать на С# ?

C#
1
var intersection = col1.Intersect(col2);

echs · 11.01.2016, 11:33

Shamil1
А если параллельно провести подсчет?
Или овчинка выделки не стоит?
Мое предложение удобно тем, что если общих элементов
мало, то оно позволяет сильно сократить перебор.
Есть еще вопрос
А нельзя ли для этой задачи использовать
строку? И лишние символы можно выбросить
и сохранить позиции существующих и их количество?

@Shamil1 · 11.01.2016, 11:52

Сообщение от geh

А нельзя ли для этой задачи использовать
строку?

Строку использовать нельзя - там сложный ключ, насколько я понял (A, B, ... - это объекты с большим количеством полей, значения которых используются при сравнении).

Сообщение от geh

А если параллельно провести подсчет?

Не понял, что именно считать параллельно.

@Igor3D · 11.01.2016, 12:42

С точки зрения экономии можно хранить в самих эл-тах указатель на следующий такой же эл-т (возможно + номер коллекции). Тогда ассоциативный контейнер нужен только для построения списков.

@taancer · 11.01.2016, 14:09 **[ТС]**

Сообщение от Shamil1

не будем знать, сколько раз и на каких позициях.

Да. значит чистое пересечение множеств не подходит.

но спасибо за подсказку, буду знать.

Сообщение от geh

А(i)=B(i)

Такой вариант перебора я рассматривал как первый алгоритм перебором.
Очень не хочется так делать.
Хотелось бы сделать декларативно - обработкой данных через запросы.

Сообщение от Shamil1

Строку использовать нельзя - там сложный ключ

Да.

Сообщение от Igor3D

+ номер коллекции

Да. так и требуется.
Но для того, чтобы эту коллекцию добавить, нужно сначала найти ее элементы.
Я хочу это сделать через LINQ
Но вот механизм выборки пока что сообразить не могу.
Поэтому и спросил про алгоритм.

@Shamil1 · 11.01.2016, 15:04

Сообщение от taancer

Коллекция 1: А В С А
Коллекция 2: С А А Е

Если задача позволяет, то можно заменить коллекцию на уникальный массив элементов и коллекцию индексов в этом массиве.

Сообщение от taancer

Я хочу это сделать через LINQ

C#
1
2
3
var results = "adfbfdsa".Select((c,i) => Tuple.Create(c,i+1)).GroupBy(x => x.Item1, x => x.Item2);
foreach(var res in results.OrderBy(x => x.Key))
    Console.WriteLine("{0}: {1}", res.Key, string.Join(",", res.ToArray()));

Выведет:

Code
1
2
3
4
5
a: 1,8
b: 4
d: 2,6
f: 3,5
s: 7

Новые блоги и статьи Все статьи Все блоги /
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .

@taancer 17 / 9 / 2 Регистрация: 18.01.2014 Сообщений: 155

	Сравнение массивов 02.01.2016, 01:26. Показов 1448. Ответов 13 Метки нет (Все метки) Здравствуйте. Есть две коллекции однотипных объектов, объекты в обоих коллекциях могут повторяться по критериям сравнения. Задача: Для каждого объекта из обоих коллекций найти по определенным критериям равный объект и записать это в результат. Пример: Коллекция 1: А В С А Коллекция 2: С А А Е Результат: (в скобках указан для простоты порядковый номер элемента из соответствующей коллекции) Коллекция 1: А(2,3) В() С(1) А(2,3) Коллекция 2: С(3) А(1,4) А(1,4) Е() Хочется использовать какой-то более интересный алгоритм, чем тупой перебор сравнения каждого с каждым. Посоветуете? 0

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,887
	02.01.2016, 04:05
	Для каждой из коллекций заполняем словарь "ключ"-"список позиций", где ключ - критерии сравнения. Для каждого из элементов первой коллекции выводим содержимое второго словаря, и наоборот. 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	03.01.2016, 11:04
	Ребята. Я может что не так понял. Почему бы в данном случае не составить два множества? Пересечение этих множеств сразу выделит общие элементы. 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	11.01.2016, 10:44
	taancer Задаем массив А() и заполняем его так. Пример А(1) здесь может быть только символ А А(2) здесь ... только символ В А(3) ... только С И так далее Итак у нас есть два массива A() и B(). Мы в цикле проверяем Если А(i)=B(i), то это общий элемент принадлежащий обоим множествам (заданным в виде массивов). Этот элемент автоматически идет в массив C(i). Иными словами массив С() будет содержать общие элементы А() и В(). И далее вам нужно будет лишь смотреть на С() Если элемент не принадлежит С() то его и рассматривать не надо А если принадлежит, то он точно входит в коллекцию. PS. Язык С# мне неизвестен и я не могу предложить на нем код. 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	11.01.2016, 11:33
	Shamil1 А если параллельно провести подсчет? Или овчинка выделки не стоит? Мое предложение удобно тем, что если общих элементов мало, то оно позволяет сильно сократить перебор. Есть еще вопрос А нельзя ли для этой задачи использовать строку? И лишние символы можно выбросить и сохранить позиции существующих и их количество? 0

@Igor3D 1972 / 828 / 115 Регистрация: 01.10.2012 Сообщений: 4,977 Записей в блоге: 2
	11.01.2016, 12:42
	С точки зрения экономии можно хранить в самих эл-тах указатель на следующий такой же эл-т (возможно + номер коллекции). Тогда ассоциативный контейнер нужен только для построения списков. 0