Каков самый быстрый способ проверить, не пересекаются ли два набора в C#?
Я нашел много ответов в интернете о том, как проверить, не пересекаются ли два массива, которые включали использование перечисляемых.Пересекаются и Перечислимы.Однако мне было интересно, есть ли более быстрый способ сделать то, что мне нужно. Мне просто нужно проверить, не содержат ли два массива каких-либо общих элементов. У меня есть три миллиона массивов, которые мне нужно проверить друг с другом, поэтому мне нужно сделать много звонков, и мне было интересно, есть ли какой-нибудь более быстрый способ выполнить следующую функцию:
private static bool checkIfDisjoint(int[] a, int[] b) { for(int i = 0; i < a.Length; i++) { for (int j = 0; j < b.Length; j++) { if (a[i] == b[j]) return false; } } return true; }
Мне нужно сделать много звонков, и каждый из моих массивов меньше длины 4. Поэтому мне было интересно, есть ли более быстрый способ достичь этого.
Что я уже пробовал:
Я пробовал LINQ и кодовый блок выше, и мне было интересно, если учесть тот факт, что длина моих массивов никогда не превышает 4, а у меня есть только 180 различных символов, которые могут содержать массивы, было бы что-то, что я мог бы сделать, чтобы сделать эту операцию быстрее.
Peter_in_2780
Таким образом, массив может быть повторно выражен в виде 180-битного растрового изображения, содержащего не более 4 единиц. Если вы сделаете это преобразование один раз для каждого из ваших 3 миллионов массивов, то непересекающийся тест будет простой и простой операцией. Я предполагаю, что 3 длинных Инта были бы подходящей структурой для хранения растровых изображений.
Peter_in_2780
В дополнение к моему предыдущему комментарию вы захотите сделать все возможное, чтобы оптимизировать тест. Чтобы проверить 3 x 10^6 элементов попарно, требуется 4,5 x 10^12 операций, поэтому каждая наносекунда, которую вы можете сбрить тестовый цикл, сэкономит вам час с четвертью времени выполнения.
PIEBALDconsult
Как о построении словаря&ЛТ;инт поиска HashSet И Л;int[]&ГТ;&ГТ; ?
Затем перечислите каждый массив, поместив элементы в словарь.
Затем, учитывая элемент из массива X, вы можете посмотреть, содержит ли набор массивов, содержащих этот элемент, массив Y.
Maciej Los
Мой виртуальный 5!
Patrice T
Для наилучшего решения нам нужно подробно знать о том, каким может быть каждый список, их содержащий.
Realhermit123
Каждый массив имеет длину 2 или 4 и может содержать целое число в диапазоне от 1 до 200