Программирование, т. 6

Гайз, вопрос назрел. Достаточно стыдно спрашивать такую вещь, но всё же не могу обойтись. С/C++. Задание - сделать максимально эффективную функцию, находящую пересечения массивов A и B. Т.е. при размерах массивов n и k сложность алгоритма не должна превышать n*k. Вот такое забабахал: пришлось на файлообменник кинуть, как даун-аутист не знаю как вставить сюда нормально код https://www.sendspace.com/file/0b4oks Долго думал, как же правильнее будет сделать проверку на повторяющиеся элементы. Разрывался между тем чтоб до C[m]=A; был if(C[m]!=C[m-1]) и вот тем что сделал в итоге. В первом случае, при первом нахождении совпадения, m в этом IFе становился -1, что как по мне нихуя не здорово. Не знаю просто, как правильнее сделать, подскажите

 code /code в таких вот скобках [] 

а вообще в чем проблема если сложность n*k это вообще говоря самый тупой перебор: берем элемент первого массива и сравниваем с каждым элементом второго и получится n*k операций в худшем случае

но используя set (или мапу/хешмапу) можно добиться скорости/сложности n+k

а вообще в чем проблема если сложность n*k это вообще говоря самый тупой перебор: берем элемент первого массива и сравниваем с каждым элементом второго и получится n*k операций в худшем случае

но используя set (или мапу/хешмапу) можно добиться скорости/сложности n+k

сложности добьешься.

с сортированным вектором добьешься скорости.

можешь сам проверить

а вообще в чем проблема если сложность n*k это вообще говоря самый тупой перебор: берем элемент первого массива и сравниваем с каждым элементом второго и получится n*k операций в худшем случае

но используя set (или мапу/хешмапу) можно добиться скорости/сложности n+k

А нет все верно

а вообще в чем проблема если сложность n*k это вообще говоря самый тупой перебор: берем элемент первого массива и сравниваем с каждым элементом второго и получится n*k операций в худшем случае

но используя set (или мапу/хешмапу) можно добиться скорости/сложности n+k

Вся проблема в том, что если массивы будут состоять каждый из 5 элементов, в которых каждый элемент равен, например, 2, то в полученном массиве пересечений будет пять двоек. Усложнение алгоритма происходит именно в тот момент, когда я пытаюсь проверить, не записано ли уже это число как пересечение в этот массив

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

n*k это же вообще брут, не?

for ( ; i < n; i++)
{
for (j = 0; j < k; j++)
{
	if (A[i] == B[j]) C[pos++] = A[i];
}
}

но если нужно тракать дубликаты, то в n*k это уже не впишется

по идее если замутить любую нетривиальную сортировку + потом руками обработать сортированые массивы то можно поиметь что-то типа n*log(n) + k*log(k) + сколько там будет поиск пересечений по сортированым массивам? какие-нибудь n + k? что всяко быстрее n*k при массивах побольше

допустим оба прогнать shell sort-ом которые без оверхеда памяти и довольно быстрый, потом правда хуй знает что с ними делать

какой-нибудь

while (i < n && j < k)
{
if (A[i] > B[j]) j++;
else if (A[i] < B[j]) i++;
else
{
	C[pos++] = A[i];
	i++; j++;
}
}

и дубликаты можно изи отсеять одним if потому что массив пересечений по дефолту будет отсортирован

но всё это надо тестить, мне чот лень щас

n*k это же вообще брут, не?

 

for ( ; i < n; i++)
{
for (j = 0; j < k; j++)
{
	if (A[i] == B[j]) C[pos++] = A[i];
}
}

 

но если нужно тракать дубликаты, то в n*k это уже не впишется

 

по идее если замутить любую нетривиальную сортировку + потом руками обработать сортированые массивы то можно поиметь что-то типа n*log(n) + k*log(k) + сколько там будет поиск пересечений по сортированым массивам? какие-нибудь n + k? что всяко быстрее n*k при массивах побольше

 

допустим оба прогнать shell sort-ом которые без оверхеда памяти и довольно быстрый, потом правда хуй знает что с ними делать

 

какой-нибудь

while (i < n && j < k)
{
if (A[i] > B[j]) j++;
else if (A[i] < B[j]) i++;
else
{
	C[pos++] = A[i];
	i++; j++;
}
}

и дубликаты можно изи отсеять одним if потому что массив пересечений по дефолту будет отсортирован

но всё это надо тестить, мне чот лень щас

Я как раз так и сделал, запилил функцией сортировку, а потом вот эта функция, что на прошлой странице

но прост вместе с сортировкой это всё равно будет больше h*k, я думаю. А если без неё, то меньше. Наверное

int check(int *A, int *B, int *C, int n, int k) // массивы отсортированы отдельной функцией алгоритмом пузырьковой сортировки по возрастанию

пузырьковая по обоим даёт n^2 + k^2, что при любых размерах исходных массивов >>> n*k

а вообще в чем проблема если сложность n*k это вообще говоря самый тупой перебор: берем элемент первого массива и сравниваем с каждым элементом второго и получится n*k операций в худшем случае

но используя set (или мапу/хешмапу) можно добиться скорости/сложности n+k

Вся проблема в том, что если массивы будут состоять каждый из 5 элементов, в которых каждый элемент равен, например, 2, то в полученном массиве пересечений будет пять двоек. Усложнение алгоритма происходит именно в тот момент, когда я пытаюсь проверить, не записано ли уже это число как пересечение в этот массив

 

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

тоесть если у вас

множество1 - 1, 2, 2, 3, 3, 4

множество2 - 2,3,3,4,5

то выходное (пересечение) = 2,3,3,4

вы чо

вообще ты бы лучше исходное задание вточности скопировал

а то тут ты наинтерпретировал и не проверил и возможно от тебя совсем не то требуют

int check(int *A, int *B, int *C, int n, int k) // массивы отсортированы отдельной функцией алгоритмом пузырьковой сортировки по возрастанию

пузырьковая по обоим даёт n^2 + k^2, что при любых размерах исходных массивов >>> n*k

Понял, пошёл вздрачивать сортировки

вообще решение норм, но ниже n*k оно будет только если применить сортировку на O(n*logn), любые сортировки по n^2 займут по кол-ву примитивных операций больше n*k ещё не закончив сортировать это дело

да сделай ты просто 2 сортировки, что тебе даст максимум

2*n*logn + 2*k*logk

и std::set_intersection ( в принципе то же, что и дедскин написал в упрощении)

2*(n+k)-1

а вообще в чем проблема если сложность n*k это вообще говоря самый тупой перебор: берем элемент первого массива и сравниваем с каждым элементом второго и получится n*k операций в худшем случае

но используя set (или мапу/хешмапу) можно добиться скорости/сложности n+k

Вся проблема в том, что если массивы будут состоять каждый из 5 элементов, в которых каждый элемент равен, например, 2, то в полученном массиве пересечений будет пять двоек. Усложнение алгоритма происходит именно в тот момент, когда я пытаюсь проверить, не записано ли уже это число как пересечение в этот массив

 

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

пересечение множеств с повторяющимися элементами = множество с повторяющимися элементами.

тоесть если у вас

множество1 - 1, 2, 2, 3, 3, 4

множество2 - 2,3,3,4,5

то выходное (пересечение) = 2,3,3,4

вы чо

 

вообще ты бы лучше исходное задание вточности скопировал

а то тут ты наинтерпретировал и не проверил и возможно от тебя совсем не то требуют

Ебать

Т.е. это же получается тогда

for(int i=0; i<n;i++)

{

while(A!=B[j] && j<k){j++;}

if(j<k)

{

C[m]=A;

m++;

}

j=0;

}

??????

вообще ты бы лучше исходное задание вточности скопировал

а то тут ты наинтерпретировал и не проверил и возможно от тебя совсем не то требуют что ты подумал

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

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

Ебать

Т.е. это же получается тогда

for(int i=0; i<n;i++)

{

while(A!=B[j] && j<k){j++;}

if(j<k)

{

C[m]=A;

m++;

}

j=0;

}

 

??????

for перебор по i

for перебор по j

и если совпало то скипаешь оставшиеся j-од (break или exit - не помню че там в плюсах выход из цикла) и удаляешь из второго массива совпавший элемент.

пересечение множеств с повторяющимися элементами = множество с повторяющимися элементами.

тоесть если у вас

множество1 - 1, 2, 2, 3, 3, 4

множество2 - 2,3,3,4,5

то выходное (пересечение) = 2,3,3,4

вы чо

странная какая-то логика, откуда у тебя взялись какие-то условия на пересечения?

если нужны тупо все пересечения, то вывод вообще будет 2,2,3,3,3,3,4

потому что де факто 3, 3 вс 3, 3 пересекаются колво1 * колво2 раз

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

пересечение мультимножеств = мультимножество

пересечение множеств с повторяющимися элементами = множество с повторяющимися элементами.

тоесть если у вас

множество1 - 1, 2, 2, 3, 3, 4

множество2 - 2,3,3,4,5

то выходное (пересечение) = 2,3,3,4

вы чо

странная какая-то логика, откуда у тебя взялись какие-то условия на пересечения?

если нужны тупо все пересечения, то вывод вообще будет 2,2,3,3,3,3,4

потому что де факто 3, 3 вс 3, 3 пересекаются колво1 * колво2 раз

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

вы че таких элементарных вещей не знаете, выжпрограамисты

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

или как?

или тебе на собесе дали такое задание и ты сейчас думаешь как бы его решил, чисто для себя?

откуда ты приплёл мультимножества, если это совсем другое

да и у нас не математика, а информатика - тут релевантнее комбинаторику использовать, а не теорию множеств, имхо

у нас нет точного определения что такое "пересечение массивов" в даном случае

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

и если они не важны - брут в помощь, цикл в цикле на 3 строчки и вот наш n*k и будь что будет

а если рассматривать массив с повторениями и нам допустим важны все пересечения, даже дубликаты, то по комбинаторике выход будет не 2,3,3,4, а тот что я написал

у нас нет контекста, поэтому ничего конкретного тут особо не скажешь

а блядь, мультимножество это multiset, а не power set

ну там пересечение съедает пару, т.е. min(x,y) а не x*y

в таком случае всё тот же брут даст желаемый результат, хуй знает

Just.doit

При клике на "откликнуться" там кинуло на 4 вопроса сразу, на которые надо прислать ответ вместе с резюме. Вот одним из вопросов было это, в итоге мне приплыл отказ. Я до этого делал 3 цикла, типа цикл по А - цикл по Б - если совпадение, то цикл по С и нахождение повтора, если повтора нет то запись в С. Мне ответили

Добрый день, Виктор!

В 4-ом вопросе тестового задания мы просили "функцию, которая максимально быстро ...", а Вами был применен самый медленный алгоритм из возможных (алгоритмическая сложность более чем N*M)