Проверка 2 массивов на идентичность по свойству
От: e.thrash  
Дата: 06.06.22 09:29
Оценка:
Есть 2 массива вида

List<Parent> a, List<Parent> b

class Parent
int id
List<Child> childs

надо проверить что в массиве a на каждом id идентичный набор на таком же уровне как и в b по ключу id

как это сделать эффективней?
Re: Проверка 2 массивов на идентичность по свойству
От: Sharowarsheg  
Дата: 06.06.22 09:45
Оценка:
Здравствуйте, e.thrash, Вы писали:

ET>Есть 2 массива вида


ET>List<Parent> a, List<Parent> b


ET>class Parent

ET> int id

Они отсортированы по ID или нет?
Re[2]: Проверка 2 массивов на идентичность по свойству
От: e.thrash  
Дата: 06.06.22 09:46
Оценка:
Здравствуйте, Sharowarsheg, Вы писали:

S>Здравствуйте, e.thrash, Вы писали:


ET>>Есть 2 массива вида


ET>>List<Parent> a, List<Parent> b


ET>>class Parent

ET>> int id

S>Они отсортированы по ID или нет?


там ключ сложный, составной. это я так для простоты одно поле написал. но в принципе можно отсортировать по порядку полей из составного ключа
Re[3]: Проверка 2 массивов на идентичность по свойству
От: Sharowarsheg  
Дата: 06.06.22 09:54
Оценка:
Здравствуйте, e.thrash, Вы писали:

S>>Они отсортированы по ID или нет?


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


Это самый интересный вопрос.

Потому что если два массива отсортированы, то сравниваешь сначала число элементов, потом, что все ключи одинаковые (по порядку прямо), и потом детей сравниваешь, тоже по порядку, причём всё это распараллеливается на любой стадии кроме сравнения числа элементов.

Может быть хеш какой-то можно посчитать от этого сложного ID, и по нему сортировать?

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

Еще интересно, результат сравнения чаще "равно" или чаще "не равно", и почему, но вряд-ли тебе нужен такой глум.
Отредактировано 06.06.2022 10:03 Sharowarsheg . Предыдущая версия . Еще …
Отредактировано 06.06.2022 9:57 Sharowarsheg . Предыдущая версия .
Отредактировано 06.06.2022 9:56 Sharowarsheg . Предыдущая версия .
Re: Проверка 2 массивов на идентичность по свойству
От: samius Россия http://sams-tricks.blogspot.com
Дата: 06.06.22 09:57
Оценка:
Здравствуйте, e.thrash, Вы писали:

ET>как это сделать эффективней?

Я думаю, можно все поксорить и сравнить результаты. Пытаюсь убедить себя, что этого достаточно для эквивалентности.
Re[2]: Проверка 2 массивов на идентичность по свойству
От: Sharowarsheg  
Дата: 06.06.22 10:02
Оценка:
Здравствуйте, samius, Вы писали:

ET>>как это сделать эффективней?

S>Я думаю, можно все поксорить и сравнить результаты. Пытаюсь убедить себя, что этого достаточно для эквивалентности.

Поксорить можно, но придётся считать MD5 или вроде того, вместо ксора, а это медленно. Кроме того, когда ты сравниваешь поэлементно, после первого отличающегося можно дальше не сравнивать, а хеши придётся до конца досчитать.
Re[4]: Проверка 2 массивов на идентичность по свойству
От: e.thrash  
Дата: 06.06.22 10:02
Оценка:
Здравствуйте, Sharowarsheg, Вы писали:



S>Может быть хеш какой-то можно посчитать от этого сложного ID, и по нему сортировать?


никогда не делал. надо поискать.

S>Зависит ещё от соотношения, сколько элементов в массиве первого уровня, сколько во втором уровне, и сколько сравнений требуется (а то, может, имеет смысл поддерживать флаг равенства, и проверять при изменении содержимого, если изменения редкие, а сравнения частые).


кол-во +- одинаковое на уровнях
примерно 10 на первом уровне и 15 на втором
Re[5]: Проверка 2 массивов на идентичность по свойству
От: Sharowarsheg  
Дата: 06.06.22 10:07
Оценка:
Здравствуйте, e.thrash, Вы писали:

ET>кол-во +- одинаковое на уровнях

ET>примерно 10 на первом уровне и 15 на втором

Да вроде немного. Если там не миллиарды сравнений, то можно просто все поля ID в строку сшить через разделитель, вот тебе и уникальный ключ. Сортируй по нему, а потом сверяй, что все эти строки одинаковые, и потом, что все дети попарно одинаковые. Да и всё вроде? Параллелить 10 операций бестолку, накладные расходы на параллелизм будут больше, чем само сравнение.
Re[3]: Проверка 2 массивов на идентичность по свойству
От: samius Россия http://sams-tricks.blogspot.com
Дата: 06.06.22 10:16
Оценка:
Здравствуйте, Sharowarsheg, Вы писали:

S>Поксорить можно, но придётся считать MD5 или вроде того, вместо ксора, а это медленно. Кроме того, когда ты сравниваешь поэлементно, после первого отличающегося можно дальше не сравнивать, а хеши придётся до конца досчитать.


сквозное MD5 и поэлементное сравнение зависит от порядка элементов в массивах, значит, требует сортировки как минимум. Это уже медленнее ксора.
Re[4]: Проверка 2 массивов на идентичность по свойству
От: Sharowarsheg  
Дата: 06.06.22 10:55
Оценка:
Здравствуйте, samius, Вы писали:

S>>Поксорить можно, но придётся считать MD5 или вроде того, вместо ксора, а это медленно. Кроме того, когда ты сравниваешь поэлементно, после первого отличающегося можно дальше не сравнивать, а хеши придётся до конца досчитать.


S>сквозное MD5 и поэлементное сравнение зависит от порядка элементов в массивах, значит, требует сортировки как минимум. Это уже медленнее ксора.


Да, но XOR будет ложные равенства выдавать почти наверняка, и придётся мутить что-то сложнее.
Re[5]: Проверка 2 массивов на идентичность по свойству
От: samius Россия http://sams-tricks.blogspot.com
Дата: 06.06.22 11:04
Оценка: +1
Здравствуйте, Sharowarsheg, Вы писали:

S>Здравствуйте, samius, Вы писали:


S>Да, но XOR будет ложные равенства выдавать почти наверняка, и придётся мутить что-то сложнее.

Да, обязательно. Будет работать как хэш с коллизиями. Полезен лишь для быстрого определения неравенства, когда посчитан для каждого массива.
Re: Проверка 2 массивов на идентичность по свойству
От: Sharov Россия  
Дата: 06.06.22 13:56
Оценка:
Здравствуйте, e.thrash, Вы писали:

ET>Есть 2 массива вида

ET>List<Parent> a, List<Parent> b
ET>class Parent
ET> int id
ET> List<Child> childs
ET>надо проверить что в массиве a на каждом id идентичный набор на таком же уровне как и в b по ключу id
ET>как это сделать эффективней?

В лоб, т.е. сортировать и родителей по id(если надо) и детей. Далее сравниваем сначала кол-во, а затем поэлементно сравниваем id у детей.
Т.е. берем родительское id, находим соотв. эл-ты у List<Parent> a и List<Parent> b, далее сравниваем детей -- сначала общее кол-во,
затем сортируем детей по их id и уже сравниваем детей поэлементно. Как-то так.
Кодом людям нужно помогать!
Re: Проверка 2 массивов на идентичность по свойству
От: Sinclair Россия http://corp.ingrammicro.com/Solutions/Cloud.aspx
Дата: 06.06.22 16:52
Оценка:
Здравствуйте, e.thrash, Вы писали:

ET>Есть 2 массива вида


ET>List<Parent> a, List<Parent> b


ET>class Parent

ET> int id
ET> List<Child> childs

ET>надо проверить что в массиве a на каждом id идентичный набор на таком же уровне как и в b по ключу id


ET>как это сделать эффективней?

Эффективнее хранить в структурах, которые позволяют быстрый поиск. List такой структурой не является.
Полный ответ зависити от того, что такое "идентичный набор" — про класс Child никакой информации нет. В общем случае ничего лучше попарного сравнения вы не сделаете:
bool IsIdentic<T>(List<T> aList, List<T> bList)
{
  foreach(var a in aList)
    if(!bList.Contains(a))
       return false;
  foreach(var b in bList)
    if(!aList.Contains(b))
       return false;
}

Основная идея ускорения — сделать Contains быстрее, чем за O(N), как у List<T>.
Например, можно хранить данные в Set<Сhild> или в ParentCollection: KeyedCollection<int, Parent> { protected override int GetKeyForItem(Parent item) => item.id; }.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
http://rsdn.org/File/5743/rsdnaddict.GIF
Re: Проверка 2 массивов на идентичность по свойству
От: Kolesiki  
Дата: 07.06.22 01:12
Оценка: :)
Здравствуйте, e.thrash, Вы писали:

ET>Есть 2 массива вида

ET>как это сделать эффективней?

Эффективнее ЧЕМ ЧТО?? У тебя какое именно решение?

ET> childs




CHILDREN, ну мать вашу!
Re[2]: Проверка 2 массивов на идентичность по свойству
От: vaa https://www.youtube.com/playlist?list=PLtrvASfI1KW7VOYRKjglcagQzWLoxlncl
Дата: 07.06.22 01:33
Оценка:
Здравствуйте, Kolesiki, Вы писали:


ET>> childs


K>


K>CHILDREN, ну мать вашу!


ChildList
Re[3]: Проверка 2 массивов на идентичность по свойству
От: Sinclair Россия http://corp.ingrammicro.com/Solutions/Cloud.aspx
Дата: 07.06.22 11:37
Оценка: +1
Здравствуйте, vaa, Вы писали:
vaa>ChildList
ChildrenList.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
http://rsdn.org/File/5743/rsdnaddict.GIF
Re[4]: Проверка 2 массивов на идентичность по свойству
От: Mystic Artifact  
Дата: 08.06.22 10:55
Оценка: +1
Здравствуйте, Sinclair, Вы писали:

vaa>>ChildList

S>ChildrenList.
ChildLists тогда уже. Children это существительное мн числа.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.