для некоторых целей, мною был создан сложный алгоритм для поиска значений одного массива в другом. Т.е. проверить содержутся ли во 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 ничего хорошего. он рекурсивный, поменяешь глубину рекурсии и получишь проблемы со скоростью выполнения. Есть более простые способы сортировки, которые пишутся вручную за две минуты...

То что пишется за две минуты иногда отлаживается за пол часа и даже более. 
Гораздо более серьезной проблемой qsort а является то, что он вызывает ф-цию каждый раз для сравнения [std::sort может заinlineить компаратор, а вот qsort очень навряд ли].
Однако в любом случае - не стоит что-либо оптимизировать и переписывать, пока profiler показывает что в этом нет особой нужды.

Это сообщение отредактировал(а) Mayk - 5.9.2006, 18:00

   

Вообще это англ Comparator. "Сравниватель". 

В частности

кхм, ладно, с сортировкой покончили... вот ещё пару вопросов на повестке дня 

"Тогда, может лучше отсортировать 2 массива, и вычёркивать из второго проверенные элементы?.. т.е. сокращать массив... я просто незнаю как это реализовать. (можете помочь то...)

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

и как всё-таки таймингом пользоватся то?? можно примерчик то )) я же всё-таки начинающий кодер...

Это сообщение отредактировал(а) ReGeDiT - 5.9.2006, 20:58

Опять отсортировать, тогда одинаковые элементы будут рядом.
В STL есть алгоритм unique, который убирает дубликаты.

Earnest, а если элементов 200? =)

Может всё-таки кто-нибудь поможет мне..........................?

1) Помогите усовершенствовать мой код выше! У меня такая идея, может лучше отсортировать 2 массива, и вычёркивать из второго проверенные элементы?.. т.е. сокращать второй массив... я просто незнаю как это реализовать.

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

3) Как пользоватся таймингом? можно примерчик то )) я же всё-таки начинающий кодер

-.-

А что 200 - это по-твоему много? Много - это 200 000. А на 200 почти нет разницы - что линейный поиск, что бинарный.
Что именно тебе не понятно? В отсортированном массиве одинаковые элементы стоят рядом: бери и проверяй, за один проход.
Если речь идет о сравнении 2 отсортированных массивов, то там тоже просто: инкрементируй индекс первого, пока его элементы меньше второго. И наоборот. Если элементы совпадают, инкрементируй оба индекса. 
По-моему, кто-то такой код тебе уже писал.

Что значит "не знаю как реализовать"? Пока не попробуешь, не узнаешь.

ИМХО тебе могут подсказать, написать прогу за тебя, но пока сам не напишешь, лучше разбираться в языке не станешь!

я имею в виду то что, вдруг будут 200 одинаковых рядом. Массив состоит примерно из 50 000 элементов ;). откуда я знаю сколько раз проверять массив?

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

На работе была такая же задача: нужно было выбрать из БД все номера ИНН и номера, которые попали на выделение, затем сравнить и получить список тех людей, которые не попали. Вкратце так:Делал без сортировки, работает довольно быстро.

Можно было бы сделать код сортировки на ASM и вставить методом ассемблерной вставки (только метод сортировки должен быть быстрым, а то даже на ASM "пузырек" будет медленнеe qsort на C). Или другую функцию сортировки, используя inline-подстановку. Можно так же было сделать и без сортировки, но (профи сейчас начнут меня ругать  ) это лишний - перебор + цикл в цикле + сравнения flag = true/false, особенно для 50000 элементов.

спасибо!

осталось 2 вопроса 

---

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

Это сообщение отредактировал(а) ReGeDiT - 9.9.2006, 15:44

Библиотека time.h. А вообще поконкретней объясни чего ты хочешь.


Каких? 

Нет.

{1, 99, 9, 3, 0, 34, 654, 34, -345, 3456, 34, -1000, 321, 13244, 0, 654, -100, 1000, -1000, 9};

34 - встречается 3 раза, выводим - два раза 34 - они "лишние".

Хотя, можно еще так: если число встречается > 2 раз, то выводим его столько раз сколько оно встречается в массиве:Для наглядности я здесь поставил число 34 четыре раза.

Я вроде понял что надо найти одинаковые числа в двух массивах, и все их собрать в одном массиве (у меня в связанном списке):

Простите, не туда записал

Всё удалил...  

Это сообщение отредактировал(а) Олег4 - 12.9.2006, 18:02