Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > С/С++
Перезагрузить страницу Быстрый Алгоритм сравнения двух массивов
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
AcerExtensa AcerExtensa вне форума
Member
 
Сообщений: 79
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 18.11.2007
По умолчанию 17.07.2008, 16:55

Всем привет!,
Пишу программку для КПК и нужна функция которая очень быстренько сравнила бы два uint массива и вернула бы массив с элементами первого массива которые не найдены во втором массиве. Элементов в массивах может быть от 0 до 16000.

нужно как можно быстрый у не толстый алгоритм, т.к. КПК и только по получению результата программа может продолжить свое выполнение так что в Thread засунуть проверку не катит.

сижу туплю.... for.... while ... if... else... do

Может кто нибудь поделится идеей, принципом, ходом выполнения?

Спасибо за ранее!
Ответить с цитированием
  (#2 (permalink)) Старый
Narwal Narwal вне форума
Member
 
Сообщений: 1,039
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 07.10.2003
По умолчанию 17.07.2008, 19:21

Посортировать и потом сравнивать.
Можно использовать это - Сортировка подсчетом, но может понадобиться довольно большой вспомогательный массив
Ответить с цитированием
  (#3 (permalink)) Старый
AcerExtensa AcerExtensa вне форума
Member
 
Сообщений: 79
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 18.11.2007
По умолчанию 17.07.2008, 20:00

Так а сортировать зачем?
Цитата:
потом сравнивать
в смысле == ?
мне нужен обратно массив элементов из напр. массива А которых нет в массиве Б. порядок элементов неинтересен совсем.
Ответить с цитированием
  (#4 (permalink)) Старый
Влад Влад вне форума
Специалист
 
Сообщений: 3,884
Сказал(а) спасибо: 1
Поблагодарили 25 раз(а) в 25 сообщениях
Регистрация: 27.06.2002
Адрес: Санкт-Петербург
По умолчанию 17.07.2008, 23:31

А могут ли повторяться элементы массива? И если могут, то как тогда трактовать "элементы из массива А, которых нет в массиве Б" ? В исходном постинге об этом ничего не сказано...


The difference between theory and practice is that in theory, there is no difference between theory and practice, but in practice, there is.
Ответить с цитированием
  (#5 (permalink)) Старый
Dian Dian вне форума
Member
 
Сообщений: 5,243
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2004
По умолчанию 18.07.2008, 03:58

Цитата:
Так а сортировать зачем?
Чтоб быстрее было
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Narwal Narwal вне форума
Member
 
Сообщений: 1,039
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 07.10.2003
По умолчанию 18.07.2008, 16:25

Цитата:
Так а сортировать зачем?
Если использовать сортировку подсчетом, то понадобиться дополнительный массив, но выбор можно будет сделать за n+k операций.
Если отсортировать один из массивов, то выбор можно будет сделать за n*lg(k) + klg(k).
Если искать напрямую, то получится n*k операций.
Ответить с цитированием
  (#7 (permalink)) Старый
AcerExtensa AcerExtensa вне форума
Member
 
Сообщений: 79
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 18.11.2007
По умолчанию 21.07.2008, 11:38

Цитата:
А могут ли повторяться элементы массива?
Элементы массивов никогда не повторяются.
P.S: например 2 массива:
А 51234 32143 234561 89455 8354239 211111
Б 211111 1 32143 54876 8945



Цитата:
И если могут, то как тогда трактовать "элементы из массива А, которых нет в массиве Б" ? В исходном постинге об этом ничего не сказано...
да как бы сказано:
Цитата:
и вернула бы массив с элементами первого массива которые не найдены во втором массиве
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Утилита сравнения двух каталогов Matematic Офтопик 49 20.12.2013 11:38
Программа для сравнения двух BMP-файлов 5neverthesame94 Вопросы начинающих программистов 9 02.04.2012 22:29
Создание двух динамических массивов qqeeaaddzzcc С/С++ 6 23.05.2008 17:27
универсальный алгоритм для поиска массивов Red1Kk Алгоритмы 23 10.03.2008 13:49
Объединение двух массивов Horror Алгоритмы 6 27.11.2007 18:01
Сравнение двух массивов в Excel'e edgar Visual Basic 2 20.08.2007 17:33
Конкатенация двух численных массивов Amputator Pascal 4 16.04.2006 20:01
Самый быстрый алгоритм сортировки массива RENegade С/С++ 5 01.11.2005 12:14
Алгоритм сравнения двух текстов :shock: rutman Visual Basic 0 28.10.2004 14:41
Быстрый алгоритм градиентной заливки в окне Ril' Visual C++ 0 12.07.2004 00:41
Несовместимость указателей двух- и одномерных массивов EiTRoN С/С++ 18 03.06.2004 13:26
Алгоритм сравнения двух файлов Excel Anonymous Visual Basic 4 07.03.2003 22:09



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов