Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Быстрый поиск элемента массива


Автор: aggressorus 17.1.2009, 18:41
Привет,

Есть такая задачка:

Дан массив целых чисел a.
Размер массива n   0 < n <1kk
Значение элемента массива i 0 < i <1kk

Над данным массивом многократно осуществляется поиск самого близкого элемента i к заданной позиции. На каждом шаге поиска позиция поиска строго увеличивается. Количество шагов поисков < n

Пример:
Код

a: 1,3,4,1,2,4,1,2
п: 0,1,2,3,4,5,6,7
Поиск:
1)  0 (позиция), 3 (элемент) результат 1
2)  1, 1 результат 3
3)  2, 2 результат 4
4)  5, 7 результат эл. не найден
6)  6, 2 результат 7


Моя реализация тривиальная. Для каждого элемента мас. строится список позиций:
1: 0, 3, 6
2: 4, 7
3: 1
4: 2,5

На этапе поиска берется список позиций элемента и бинарным поиском находим позицию.

Есть идеи как можно ускорить такой поиск?

Автор: nworm 18.1.2009, 01:07
Данных мало.

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

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

Ну и, ещё, анализ оптимальности алгоритма сам по себе отнимает много времени.
Если это действительно нужно, надо полностью определить параметры задачи:
1) размер начального массива,
2) количество поисков,
3) что критичней: огромная задержка в 5% случаев или отсутствие вероятности такой задержки, но более долгая работа алгоритма в обычных случаях,
и т.п.

Автор: maxdiver 18.1.2009, 11:57
За линейное время можно.

Сначала линейным проходом для каждого элемента A[i] находим ближайший к нему справа элемент, равный ему (это можно за O(N) одним проходом справа налево сделать). Пусть это массив Next[i] = позиция ближайшего справа элемента, совпадающего с A[i].

Затем идём слева направо, пусть текущая позиция в массиве A это i. Для каждого элемента поддерживаем позицию последней встречи этого элемента (до позиции i включительно), пусть это Last[j] (фактически, позиция ближайшего слева от [i] элемента, совпадающего с j). Чтобы поддерживать этот массив, понятно, нужно по O(1) операции на каждый шаг с i до i+1, собственно, аналогично массиву Next.

Тогда, чтобы найти элемент j, ближайший к позиции i, нужно будет посмотреть на Last[j] и Next[Last[j]]. Здесь мы использовали то, что позиции i по условию не уменьшаются, т.е. мы можем брать текущее значение массива Last[], использовать его, потом пересчитывать его до следующей позиции, обрабатывать следующий запрос, и т.д.

Итого O(N) на всё.

Автор: aggressorus 18.1.2009, 16:15
maxdiver, 
Спасибо, всё понятно smile. Проблема в том, что при следующем поиске некоторое количество элементов j может быть пропущено. 

Автор: maxdiver 18.1.2009, 18:15
Ну на сколько надо, на столько и шагаем. Всё равно мы всегда только вправо движемся, поэтому суммарно будет N шагов.

Автор: maxdiver 19.1.2009, 00:20
От нечего делать кодес накидал:
Код
int n;
cin >> n;
vector<int> a (n);
for (int i=0; i<n; ++i)
    cin >> a[i];
int m = * max_element (a.begin(), a.end()) + 1;

vector<int> next (n),  pos (m, -1);
for (int i=n-1; i>=0; --i) {
    next[i] = pos[a[i]];
    pos[a[i]] = i;
}

vector<int> last (m, -1);
int ptr = -1;

int queries;
cin >> queries;
for (int i=0; i<queries; ++i) {
    int query_pos, query_val;
    cin >> query_pos >> query_val;
    --query_pos;
    while (ptr<query_pos) {
        ++ptr;
        last[a[ptr]] = ptr;
    }
    int ans_left = last[query_val],
        ans_right = ans_left!=-1 ? next[ans_left] : pos[query_val],
        ans = ans_left==-1 ? ans_right : ans_right==-1 ? ans_left
            : (query_pos-ans_left<ans_right-query_pos) ? ans_left : ans_right;
    cout << ans+1 << endl;
}

Автор: maxdiver 19.1.2009, 12:24
Я ещё подумал, что даже если запросы не строго возрастают, но задача в оффлайне (т.е. можно отвечать только после получения сразу всех запросов), то всё равно за линейное время решается - если запросы предварительно отсортировать подсчётом, и потом ту же шнягу повторить.

Автор: aggressorus 19.1.2009, 14:12
maxdiver, 
Огромное спасибо за код smile

Цитата(maxdiver @  19.1.2009,  12:24 Найти цитируемый пост)
Я ещё подумал, что даже если запросы не строго возрастают, но задача в оффлайне (т.е. можно отвечать только после получения сразу всех запросов), то всё равно за линейное время решается - если запросы предварительно отсортировать подсчётом, и потом ту же шнягу повторить. 


Задача в онлайне :(, некоторые позиции определяются на основании результатов предшествующих запросов.
Я уже сам задумался как решить для случайных позиций поиска. Но быстрее бинарного поиска ничего не придумал.

Добавлено через 4 минуты и 35 секунд
Изначально всё решалось матрицей размерности [n][s], s - размер алфавита. В матрице для каждой позиции определялась следующая позиция элемента i.

Автор: maxdiver 19.1.2009, 20:15
aggressorus
Если случайные позиции и в онлайне, то, мне кажется, быстрее бинарного поиска не получится.
Разве что вариант, о котором ты говорил, с таблицей N*S, но всё-таки O(N*S) скорее всего хуже, чем O(N*logN).

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)