Убрать уникальные значения в List

@belalugoci · Регистрация: 01.06.2018

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

есть

C#
1
2
3
4
5
        public struct S
        {
            public int M;
            public int CRC;
        }

нужно посредством Sort() / foreach / OrderBy() / GroupBy() убрать все уникальные значения по CRC, чтобы остались любые повторяющиеся и можно было прочитать все значения М.
то есть из

C#
1
{ 1, 7, 12, 8, 12, 9, 3, 4, 3, 12, 17, 14, 0 }

нужно получить

C#
1
{ 12, 12, 3, 3, 12 }

я третий день ковыряюсь с Sort() / OrderBy() / GroupBy() и совсем не вкуриваю как они работают.
Из идей была только - сначала с помощью Sort() получить упорядоченную последовательность, а потом в цикле проверять совпадение текущего элемента с предыдущим и если они совпали - обрабатывать их. Но Sort() нет для struct, поэтому пока залип на месте.

@belalugoci · 29.01.2019, 10:39 **[ТС]**

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

Данные обходятся ровно два раза

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

C#
1
int[] A = new int[1000000];

это 4 мегабайта
потом

C#
1
2
.GroupBy(x => x.Hash64)
.Where(g => g.Count() > 1)

это еще 4 мегабайта
потом

C#
1
2
.SelectMany(g => g)
.ToArray();

это еще 4 мегабайта.
Плата за скорость?

@kolorotur · 29.01.2019, 10:41

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

то есть выделяется память для хранения отдельно структуры индексов

Исключительно там, где это необходимо.
В вашем случае — при GroupBy и при ToArray.
Where и SelectMany дополнительной памяти не требуют.

@belalugoci · 29.01.2019, 11:01 **[ТС]**

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

Данные обходятся ровно два раза

пытаюсь придумать как за один проход сделать все группы и ничего не получается.
берём первый элемент, создаем группу, берём второй элемент, проверяем вхождение в предыдущие группы, помещаем в существующую или создаем новую, повторяем. но у меня именно так ранее работал код и это было долго, так как каждый последующий элемент бегает по предыдущим и так много раз. так сказать "каждый с каждым" проверяется. формально по данным один проход, но фактически 1000001*50 итераций. Или я где-то ошибся?

@kolorotur · 29.01.2019, 11:09

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

проверяем вхождение в предыдущие группы

Вот эту часть можно выбросить.

Алгоритм такой:
1. Берем элемент.
2. Смотрим на его хэш (мы ведь по нему группируем).
3. Если нет группы для элементов с этим хэшем, то создаем такую группу.
4. Кладем элемент в эту группу.
5. Если в исходной коллекции еще есть элементы, то goto 1.
6. На выходе получаем набор групп, в каждой из которых лежат элементы с одинаковыми хэшами.

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

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

@belalugoci · 29.01.2019, 11:21 **[ТС]**

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

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

не совсем так, вы в этом примере исходите из предпосылки что групп четыре, я исхожу из предпосылки что число групп равно числу элементов исходных данных.
например для моего случае 8000 групп (для 16152 элементов) но всего в данных 1000000 элементов, то есть всего групп для проверки у нас будет 1000000-16152+8000 - это то число групп, которое будет сформировано, то есть проверяя каждый с каждым в моем случае мы выиграем только 8152 итерации, а это 0,08152% от общего числа.
или всё же я не так всё понимаю?

@kolorotur · 29.01.2019, 11:30

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

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

Суть та же, просто групп будет больше.

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

8000 групп (для 16152 элементов) но всего в данных 1000000

Не понял вот эту часть.
Элементов 16152 или все-таки 1000000?

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

проверяя каждый с каждым

Откуда у вас берется этот "каждый с каждым"?

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

мы выиграем только 8152 итерации, а это 0,08152% от общего числа.

Если вы проверяете каждый элемент с остальными n элементами, то количество проверок у вас будет n².
Если у вас 16152 элементов, то проверка каждого с каждым выльется в 16152² = 260887104 проверок.
Если у вас 1000000 элементов, то проверка каждого с каждым выльется в 1000000² = 1000000000000 проверок.

При "карточном" же подходе у вас количество проверок будет строго n: 16152 для 16152-х элементов и 1000000 для 1000000 элементов.*

* По факту, конечно, немного больше — в зависимости от качества хэш-функции, но количество будет стремиться к n.

@belalugoci · 29.01.2019, 11:44 **[ТС]**

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

Суть та же, просто групп будет больше

1000000 элементов = 1000000 групп, все элементы уникальны (если удобнее с картами, то 1000000 карт разных мастей, не 4 масти, а именно 1000000 мастей)

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

Не понял вот эту часть.
Элементов 16152 или все-таки 1000000?

данные 1000000 штук
после работы GroupBy будет 16152 (это по моим данным уже проверено)
это 8000 групп, то есть почти везде в группе будет по 2 элемента, редко 3.

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

Откуда у вас берется этот "каждый с каждым"?

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

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

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

нет, будет (n+1)*(n/2) так как нет нужды проверять с предыдущими, каждую итерацию мы выполняем на одну проверку меньше.

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

При "карточном" же подходе у вас количество проверок будет строго n: 16152 для 16152-х элементов и 1000000 для 1000000 элементов.*

я и не могу понять как вы умудряетесь не проверяя проверять.
давайте по порядку:
1. групп нет, создаем первую группу, туда кладется первый из 1000000 элемент
2. проверяем со всеми группами, если не совпало, создаем группу и переходим на 1, если совпало - включаем в группу и переходим на 1
Формально мы пройдём по 1000000 элементов, но сделаем 1000001*500000 проверок. Я когда писал свой код, то сразу исключал такой вариант, чтобы не делать лишний проход этих 1000000. Но по факту разница в скорости в несколько сотен раз заставляет меня сильно задуматься о том, что я серьёзно что-то не понимаю.

@kolorotur · 29.01.2019, 11:49

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

проверяем со всеми группами

Да не надо нам проверять со всеми группами!
При группировке очень активно используется хэширование и хэш-таблицы — это когда нужная группа (грубо говоря, индекс нужной группы в массиве групп) находится за одну операцию, без необходимости обхода и проверки всех групп.
Единственный случай, когда будет производиться проверка всех групп — это когда все уникальные ключи будут генерировать одинаковые хэш-коды (вызов GetHashCode на ключе группировки). Но ключом у вас выступает ulong, а значит это исключено.

@belalugoci · 29.01.2019, 11:53 **[ТС]**

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

Да не надо нам проверять со всеми группами!

почему?

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

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

Не понял. Я знаю что такое хэширование и я его использую, именно хэш выступает у меня индексом для группировки. Но какой ещё хэш вы посчитаете чтобы не ходить по всем группам? Что с чем вы будете сравнивать? Я не представляю о чем речь.

@kolorotur · 29.01.2019, 11:59

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

Но какой ещё хэш вы посчитаете чтобы не ходить по всем группам? Что с чем вы будете сравнивать?

Я свой ответ дополнил еще одной ссылкой на хэш-таблицу — почитайте.
Вот они используются в кишках GroupBy.

В качестве хэша для этих таблиц будет использоваться результат вызова GetHashCode на ваших ключах.

@belalugoci · 29.01.2019, 12:56 **[ТС]**

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

Я свой ответ дополнил еще одной ссылкой на хэш-таблицу — почитайте.

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

@kolorotur · 29.01.2019, 16:18

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

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

Именно!

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

но в ряде случаев может понадобиться сравнить только элементы в группе.

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

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

@belalugoci · 29.01.2019, 16:33 **[ТС]**

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

Нет, элементы в группе сравниваться не будут никогда.

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

@belalugoci · 30.01.2019, 06:15 **[ТС]**

Я продолжаю упарываться в тему тут, если кто-то захочет...

Новые блоги и статьи Все статьи Все блоги /
Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .
Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .

@belalugoci 475 / 294 / 29 Регистрация: 01.06.2018 Сообщений: 3,676
	30.01.2019, 06:15 [ТС]
	Я продолжаю упарываться в тему тут, если кто-то захочет... 0