| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Для новичков > [Си] Сравнение элементов |
| Автор: Alkash 24.2.2012, 20:50 |
| Доброе время суток господа. Собственно суть задачи: есть некоторые данные, которые можно представить как набор чисел вида "96959", естественно различные. Чисел этих - может быть - как 10, так и n. В процессе работы - к данным числам по определенному событию добавляться ещё несколько. При запуске программы - мы получаем так сказать - эталонный список данных чисел. Так вот, в процессе работы программы - необходимо получать всю эту кучу чисел по определенному событию, и выискивать числа - которых в эталонном списке нет. Вопрос: каким образом наиболее рационально реализовать данную задачу, чтобы это на отожрало кучу времени, и памяти ? |
| Автор: ColdSpirit 24.2.2012, 21:46 |
| Записать эталонный список допустим в массив, и потом сравнивать с новым? |
| Автор: Alkash 24.2.2012, 21:50 |
| Я уже думал об этом, а если элементов массива будет скажем n, но менее n в десятой степени? |
| Автор: ColdSpirit 24.2.2012, 21:51 |
| Для новых данных сделать другой массив и ничего не надо сравнивать))) |
| Автор: Alkash 24.2.2012, 22:06 |
| Эм, так мне надо неким чудным образом - новые появляющиеся данные, отсутствующие в массиве первом - запихивать в массив финальный получается, без элементов эталонного массива. И как я создав новый массив с новыми данными - узнаю, без сравнения,какие из данных новые, если порядок расположения в принципе может быть рандомный?-)) |
| Автор: ColdSpirit 24.2.2012, 22:18 |
| Тоесть новые данные поступают несколько раз и нужно узнать только данные которые только что поступили? Если да, тогда нужно три массива: {эталонный массив}, {массив неэталонный}, {массив с новыми данными}, причем при каждом добавлении новых чисел, старые числа переходят из {массива с новыми данными} в {массив неэталонный} Если надо, чтобы массив был один (допустим для рандомного расположения элементов), то можно реализовать как выше, и добавить еще один массив, с ссылками на элементы других массивов |
| Автор: Alkash 24.2.2012, 22:24 |
| Эта схема понятна. Тут вся беда то вот в чем: мы получаем временный массив - в виде смеси из данных эталонных и данных новых, Поэтому - вопрос по сути заключается в том, как отделить старые данные от новых, с минимальными потерями производительности. |
| Автор: ColdSpirit 24.2.2012, 22:35 |
| Боюсь в таком случае кроме обычного сравнения ничего предложить не могу, но я заметил, что http://www.google.ru/search?q=%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B+%D1%81%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D1%8F+%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2%D0%BE%D0%B2 на этот счет #конкретные ссылки показать не могу, боюсь модерация этого не одобрит =) |
| Автор: Dem_max 26.2.2012, 07:50 | ||
использовать vector
|
| Автор: fish9370 27.2.2012, 00:48 |
| эта задача довольно типична, решается с помощью таблиц с вычисляемым входом: 1) вычисляешь хеш строки (некое число которое можно спроецировть на таблицу определенного размера) 2) по указанному индексу проверяешь не занята ли ячейка (не существует хеш функции, которая бы не порождала бы коллизий) 3) записываешь значение коллизии можно разрешать двумя способами: 1) вводом признака занятости ячейки и увеличением индекса при занятости 2) созданием списка и занесением элемена в список вся сложность алгоритма заключается в написании хорошей хеш-функции (в простом случае это может быть взятие остатка от деления на количество элементов таблицы) этот способ применяется: при поиске процесса в ядре линукса для нахождения мак-адреса в коммутаторе вобщем, передовой метод |