для некоторых целей, мною был создан сложный алгоритм для поиска значений одного массива в другом. Т.е. проверить содержутся ли во 2м массиве элементы первого. До сих пор у меня есть уверенность что сделать всё можно намного проще  Помоги упростить это. Главный минус моего алгоритма - УЖАСНО МЕДЛЕННАЯ СКОРОСТЬ работы.

Вот мой алгоритм:

Отсортировать оба. 
Если менять нельзя, отсортировать копии, и искать в них. 
Если порядок зачем-то нужно сохранить, заведи структуру {значение, исходный индекс}, отсортируй ее по значению (можно еще флаг добавить - "встречается\не встречается"), проверь, выведи все скопом.
Как искать совпадения в отсортированных массивах надо объяснять?

ЗЫ
И не пиши так ужасно код: чего строчки экономишь? Читать же невозможно...

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

Это сообщение отредактировал(а) maxim1000 - 31.8.2006, 17:40

Про форматирование...
К сожалению, ни в школе, ни в институте не учат правильному форматированию программ. И вот каждый пытается изобрести велосипед... В конце концов, он приходит к одному из общепринятых стилей... Но не сразу.

ReGeDiTКак ты думаешь, код в таком виде читается лучше, чем тот, что дал ты?

Кстати, обрати внимание на использование оператора ++. Если тебе не нужно получать значение до выполнения инкремента, то лучше использовать ++i, так как гарантированно быстрее работает (а скорость работы i++ сильно зависит от качества и степени оптимизации). 

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

Простите за оффтоп - не мог не вступиться за преподавателей 

Это сообщение отредактировал(а) zkv - 31.8.2006, 18:09

Я нечто похожее делал:Здесь "левые" функции, которые русский текст выводят.

по поводу форматирования: программа пишется для себя и никуда здаватся не будет. важна только работа.

спасибо за подсказки с сортировкой и ++i;


а какие есть способы сортировки? я что-то слышал о Quick Sort... Ведь массивы довольно большие... а всякие сортировки дедовским методом пузырька не будут быстрыми...)

а если через месяц (год, два) захочешь подправить свой код?


простыми включениями, простым выбором, простым обменом (пузырек), сложным выбором (двоичное дерево),  сложными вставками (Шелла),  сложным обменом (Хоора или Quick Sort)

что то из этого есть на этом же форуме в разделе "алгоритмы" если я не ошибаюсь

Зачем, если мы ищем элементы первого массива во втором? Остортировать только второй массив, а потом перебитрать элементы первого и бинарным поиском искать их во втором.

пожалуй, этот вариант ещё лучше, получатся n*log n+m*log n
а в случае двух сортировок - n*log n+m*log m [ну ещё+m+n, но это не так важно]
преимущества 2:
1. если размеры массивов разные, то мы можем, как захотим, выбирать, что m, а что n, тогда при сортировке меньшенго массива m*log n будет меньше m*log m
2. быстрая сортировка не гарантирует n*log n, так что сортируя только один массив мы уменьшаем риск (бинарный поиск даёт log n гарантированно), а сортировка слиянием, которая гарантирует n*log n, требует n памяти, так что сортировать только меньший массив тоже выгодно
впрочем, на небольших массивах эти различия могут быть незаметны...

Это сообщение отредактировал(а) maxim1000 - 1.9.2006, 12:01

Помойму там "быстрая"(так называется) сортировка.

гмммммммммммммммммм.......................

ладно. допустим сортировка 1го массива будет эффективней сортировки 2х сразу.

тогда, может лучше отсортировать 2 массива, и вычёркивать из второго проверенные элементы?.. т.е. сокращать массив... я просто незнаю как это реализовать. И может ли кто написать какой-нибудь быстрый алгоритм сортировки на C (НЕ C++!!)

ТАКЖЕ! допустим имеется 1 массив, как проверить его на повторяющиеся элементы, т.е. допустим есть ли в нём одинаковые... они могут быть совершенно в разных местах? в голову ничего не лезет...

З.Ы.: Какие в Microsoft Visual C++ 7.0 есть средства тайминга программ (засекать скорость работы..).

В разделе "Алгоритмы" поищи...

DWORD GetTickCount(void);

qsort из стандартной библиотеки си (не с++)

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