Доброе время суток господа. Собственно суть задачи: есть некоторые данные, которые можно представить как набор чисел вида "96959", естественно различные. Чисел этих - может быть - как 10, так и n. В процессе работы - к данным числам по определенному событию добавляться ещё несколько. При запуске программы - мы получаем так сказать - эталонный список данных чисел. Так вот, в процессе работы программы - необходимо получать всю эту кучу чисел по определенному событию, и выискивать числа - которых в эталонном списке нет. Вопрос: каким образом наиболее рационально реализовать данную задачу, чтобы это на отожрало кучу времени, и памяти ? 

Записать эталонный список допустим в массив, и потом сравнивать с новым?

Я уже думал об этом, а если элементов массива будет скажем n, но менее n в десятой степени?

Для новых данных сделать другой массив и ничего не надо сравнивать)))

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

Это сообщение отредактировал(а) Alkash - 24.2.2012, 22:07

Тоесть новые данные поступают несколько раз и нужно узнать только данные которые только что поступили?
Если да, тогда нужно три массива:
{эталонный массив}, {массив неэталонный}, {массив с новыми данными},
причем при каждом добавлении новых чисел, старые числа переходят из {массива с новыми данными} в {массив неэталонный}

Если надо, чтобы массив был один (допустим для рандомного расположения элементов), то можно реализовать как выше, и добавить еще один массив, с ссылками на элементы других массивов

Эта схема понятна. Тут вся беда то вот в чем: мы получаем временный массив - в виде смеси из данных эталонных и данных новых, Поэтому - вопрос по сути заключается в том, как отделить старые данные от новых, с минимальными потерями производительности.

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

#конкретные ссылки показать не могу, боюсь модерация этого не одобрит =)

Это сообщение отредактировал(а) ColdSpirit - 24.2.2012, 22:38

использовать vector





Это сообщение отредактировал(а) Dem_max - 26.2.2012, 07:53

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

коллизии можно разрешать двумя способами: 
1) вводом признака занятости ячейки и увеличением индекса при занятости
2) созданием списка и занесением элемена в список

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

этот способ применяется: 
при поиске процесса в ядре линукса
для нахождения мак-адреса в коммутаторе
вобщем, передовой метод