#c #stl #hashtable #intersection
#c #stl #хэш-таблица #пересечение
Вопрос:
Кто-нибудь знает, возможно ли превратить это из O (m * n) в O (m n)?
vector<int> theFirst;
vector<int> theSecond;
vector<int> theMatch;
theFirst.push_back( -2147483648 );
theFirst.push_back(2);
theFirst.push_back(44);
theFirst.push_back(1);
theFirst.push_back(22);
theFirst.push_back(1);
theSecond.push_back(1);
theSecond.push_back( -2147483648 );
theSecond.push_back(3);
theSecond.push_back(44);
theSecond.push_back(32);
theSecond.push_back(1);
for( int i = 0; i < theFirst.size(); i )
{
for( int x = 0; x < theSecond.size(); x )
{
if( theFirst[i] == theSecond[x] )
{
theMatch.push_back( theFirst[i] );
}
}
}
Комментарии:
1. Чего именно вы пытаетесь достичь? Было бы полезно добавить немного больше текста, а также то, что вы ожидаете в качестве выходных данных в вашем примере.
2. Пересечение массивов, в массивах a и b существует одно и то же число. Могут быть отрицательными или положительными числами. Массив a содержит m элементов, а массив b — n элементов. Не отсортировано, поскольку сортировка влияет на производительность.
Ответ №1:
Поместите содержимое первого вектора в хэш-набор, такой как std::unordered_set
. Это O (m). Просканируйте второй вектор, проверяя, находятся ли значения в unordered_set и ведя подсчет тех, которые есть. Это n поисков хэш-структуры, так что O (n). Итак, O(m n). Если у вас есть l элементов в перекрытии, вы можете посчитать O (l) для добавления их к третьему вектору. std::unordered_set
находится в черновике C 0x и доступна в последних версиях gcc, а также существует реализация в boost.
Отредактировано для использования unordered_set
Использование синтаксиса C 2011:
unordered_set<int> firstMap(theFirst.begin(), theFirst.end());
for (const intamp; i : theSecond) {
if (firstMap.find(i)!=firstMap.end()) {
cout << "Duplicate: " << i << endl;
theMatch.push_back(i);
}
}
Теперь все еще остается вопрос, что вы хотите делать с дубликатами в оригиналах? Явно, сколько раз должно 1
быть в theMatch
, 1, 2 или 4 раза?
Это выводит:
Duplicate: 1
Duplicate: -2147483648
Duplicate: 44
Duplicate: 1
Комментарии:
1. в сопоставлении дубликатов все в порядке, это еще одна оптимизация на потом.
2. и, кстати, что делает const int amp; i : в цикле for?
3. Ну, const intamp; i получает значение каждого элемента вектора по ссылке const. В этом случае, поскольку значение int невелико, в нем нет особой необходимости, вы могли бы получить его по значению
for (int i : theSecond) ...
но если ваш вектор содержал более крупные объекты, копирование которых обходится дорого, вам нужна постоянная ссылка.4. является ли : с другого языка? он не распознается моим компилятором VS2010. хотя я могу обойти это
5. Это черновик C 2011, к которому я не уверен, как получить доступ из VS2010. Это всего лишь простой цикл над вектором, для (vector<int>::const_iterator i=theSecond.begin() ; …` и так далее.
Ответ №2:
Используя это: http://www.cplusplus.com/reference/algorithm/set_intersection /
Я полагаю, вы должны быть в состоянии достичь O(mlogm nlogn)
. set_intersection
требуется, чтобы входные диапазоны были уже отсортированы). Однако это может работать немного иначе, чем ваше решение для повторяющихся элементов.
Комментарии:
1. Да, это потому, что сначала вам нужно их отсортировать. Кроме того, я не совсем понимаю, что вы подразумеваете под максимальным количеством элементов. mlogm nlogm асимметрично лучше, чем m * n.
2. Ах да, давайте учтем время на сортировку массивов, все еще лучше?
3. Да, без учета коэффициента сортировки, это ок. O(m n). Из документации:
At most, performs 2*(count1 count2)-1 comparisons or applications of comp (where countX is the distance between firstX and lastX).
.4. Это почти идеально, но единственная проблема, которую я вижу, заключается в том, что мне приходится сортировать оба массива раньше, потому что использование функции .sort приведет к преформированию O (n ^ 2) в худшем виде. Которое может быть для обоих массивов. cplusplus.com/reference/algorithm/sort
5. Затем используйте сортировку слиянием, чтобы гарантировать наихудший вариант O (nlogn). Кроме того, сортировка O (n ^ 2) крайне маловероятна — это наихудший случай быстрой сортировки, но в большинстве случаев быстрая сортировка выполняется быстрее, чем сортировка слиянием.
Ответ №3:
Пожалуйста, поправьте меня, если я ошибаюсь, вы предлагаете следующее решение проблемы пересечения: отсортируйте два вектора и продолжайте итерацию в обоих отсортированных векторах таким образом, чтобы мы достигли общего элемента, поэтому общая сложность будет (n * log (n) m * log (m)) (n m) Предполагая, что k * log (k) как сложность сортировки
Я прав? Конечно, сложность будет зависеть от сложности сортировки.
Комментарии:
1. Их не нужно сортировать, если есть способ без их сортировки, который мог бы быть намного эффективнее.
Ответ №4:
Я бы отсортировал более длинный массив O (n * log (n)), искал элементы из более короткого массива O (m * log (n)). Тогда итого равно O (n * log(n) m * log (n) )
Ответ №5:
Предполагая, что вы хотите создать theMatch
из двух наборов данных, и вас не волнуют сами наборы данных, поместите один из них в unordered_map
(доступен в настоящее время в Boost и указан в окончательном проекте комитета для C 11), сопоставляя ключ с целым числом, которое увеличивается при добавлении к, и, следовательно, отслеживает количество раз, когда встречается ключ. Затем, когда вы получаете совпадение с другим набором данных, вы push_back
указываете, сколько раз это произошло в первый раз.
Вы можете получить O (n log n m log m), сначала отсортировав векторы, или O (n log n m), создав std::map
один из них.
Предостережение: это операции, не сохраняющие порядок, и theMatch
они будут выполняться в разных порядках с использованием разных методов. Мне кажется, что порядок, скорее всего, считается произвольным. Если порядок, указанный в приведенном выше коде, необходим, я не думаю, что есть алгоритм лучше.
Редактировать:
Возьмем набор данных A и набор данных B типа Type. Создайте unordered_map<Type, int>
.
Просмотрите набор данных A и проверьте каждый элемент, чтобы увидеть, есть ли он на карте. Если нет, добавьте элемент с int
1 на карту. Если это так, увеличьте int
. Каждая из этих операций в среднем равна O (1), поэтому этот шаг равен O (len A).
Просмотрите набор данных B и проверьте каждый элемент, чтобы увидеть, есть ли он на карте. Если нет, переходите к следующему. Если это так, push_back
поместите элемент в очередь назначения. int
— это количество раз, когда это значение встречается в наборе данных A, поэтому сделайте push_back
количество раз, когда элемент в A дублирует заданное поведение. Каждая из этих операций в среднем составляет O (1), поэтому этот шаг равен O (len B).
Это обычное поведение. Если вы всегда сталкиваетесь с наихудшим вариантом, вы возвращаетесь к O (m * n). Я не думаю, что есть способ гарантировать O (m n).
Комментарии:
1. Возможно, вам удастся получить,
O(n log n m)
если вы используетеunordered_map
, ноstd::map
имеетlog n
вставку иlog n
поиск, так что вы получитеO(n log n m log n)
.2. @Джейми Вонг: В черновике, который у меня есть для C 0x,
unordered
среднее время вставки и извлечения составляет O (1). Создайтеunordered_map
(O (n)), прочитайте другой набор данных, найдите его вunordered_map
(O (m)), и вы на месте.3. могу я увидеть пример того, что вы имеете в виду, Дэвид?
4. @Джейми, @Кристофер, это O (n) для n вставок в что-то вроде хэша и O (m) для m поисков в этой структуре с чем-то вроде хэша. Плюс O (l) для l обратных возвратов в вектор перекрытия. Смотрите мое решение, используя
std::unordered_set
.5. @Christopher Peterson Извините, это было бы O (n m) с
unordered_map
, вы правы. Однако мой второй пункт все еще должен оставаться в силе —std::map
этоlog n
для вставки и поиска.
Ответ №6:
Если порядок элементов в результирующем массиве / наборе не имеет значения, то ответ — да.
Для произвольных типов элементов с некоторым определенным порядком наилучшим алгоритмом является O( max(m,n)*log(min(m,n)) )
. Для чисел ограниченного размера лучшим алгоритмом является O(m n)
.
-
Создайте набор элементов меньшего массива — для произвольных элементов допустима просто сортировка, а для чисел ограниченного размера это должно быть что-то похожее на промежуточную таблицу в числовой сортировке.
-
Выполните итерацию по большему массиву и проверьте, находится ли элемент в наборе, созданном ранее — для произвольного элемента двоичный поиск разрешен (что является
O(log(min(n,m))
), а для чисел единственная проверка равна O (1).
Комментарии:
1. Объединение массивов с последующей сортировкой и удалением дубликатов приводит к объединению, а не к пересечению. И что бы вам дало ограничение размера
O(m n)
? Это может дать вамO(max(range of m, range of n))
2. Я все еще не понимаю, как вы получаете O (ы) для ограниченного размера. Если вы предлагаете хеширование / пакетирование, то значение имеет не размер m и n, а размер самих входных значений (который не зависит от размера m и n). Путем хэширования каждого значения, а затем выполнения через хэш-таблицу, вы могли бы получить
O(max(range of m, range of n) m n)
(мой предыдущий комментарий был неправильным). Поскольку OP, похоже, имеет дело с полным целочисленным диапазоном, это будет иметь дело с 4 миллиардами операций.3. @Джейми Вонг: Более подробно отвечу позже (сейчас нет времени). Но принцип аналогичен сортировке по основанию .
4. @Serge Dundich: Сортировка по основанию работает только тогда, когда вы можете выделить идентифицируемые сегменты для каждого значения ключа или каждого значения ключевого компонента. В этом случае, похоже, нет ограничений на возможные значения.
5. @Serge Кроме того, сортировка по радиусу, даже для ограниченных значений, выполняется не O (n), а O (kn), где k — количество цифр (зависит от используемого вами радиуса).