Realhermit123 Ответов: 1

Каков самый быстрый способ проверить, не пересекаются ли два набора в 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

1 Ответов

Рейтинг:
1

Valery Possoz

Привет,

Как уже упоминалось в комментарии выше от PIEBALDconsult, вы можете использовать хэш-набор.
Я бы предложил использовать метод Overlaps (), который возвращает логическое значение, указывающее на наличие идентичных элементов.

HashSet<int> set = new HashSet<int>(array1);
bool a = set.Overlaps(array2);


Спасибо.


Realhermit123

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