Найти ранг элемента в массиве без сортировки

#algorithm #sorting

#алгоритм #сортировка

Вопрос:

Учитывая массив из n элементов и элемент x в массиве, есть ли быстрый способ найти ранг x без его сортировки?

Поскольку я сейчас имею дело с очень большим массивом, алгоритм с O (n) временной сложностью все равно будет слишком медленным для меня, поэтому я пытаюсь найти другую альтернативу, отличную от сортировки.

Редактировать:

Итак, прямо сейчас мой алгоритм выглядит примерно так:

 for x in list:
    A = x.dot(B) ## return a numpy array
    rank = findRank(a, A) ## find the rank of a in A
    doSomething2(rank)

Итак, здесь моим узким местом является findRank() , в моей текущей реализации я сначала сортирую массив, а затем нахожу ранг элемента в отсортированном массиве.

1. Для этого и нужны базы данных. Например, используя sql orderby. если ваш массив настолько велик, что сортировка происходит так медленно, поместите его в базу данных. Какую технологию вы используете?

2. Вам понадобится алгоритм O (n): если вы не будете смотреть на один элемент, это значение может изменить порядок, который имеет x. Поэтому вам нужно, по крайней мере, проверять каждое значение. Если, конечно, вы не подготовите массив с сортировкой или какой-либо другой структурой данных.

3. Вам нужно несколько запросов для разных x с одним и тем же массивом? Пожалуйста, предоставьте более подробную информацию о проблеме

4. Если вы создаете массив каждый раз, вы уже тратите O (n) времени на создание, поэтому я не понимаю, почему бы вам не посмотреть ранг одновременно или сделать это также в O (n) процессе.

5. В редактировании вы описываете алгоритм, который равен O (nlogn), но вы должны сделать это в O (n) простым сканированием и подсчетом.

Ответ №1:

Без дополнительной подготовки (создания древовидной структуры данных или сортировки), что само по себе потребует по меньшей мере O (n) времени, вы не можете надеяться определить ранг значения в несортированном массиве за сублинейное время: каждое значение в этом массиве потенциально играет определенную рольпри определении этого ранга, таким образом, вам необходимо проверить все значения массива.

Поскольку алгоритм уже имеет линейную временную сложность для выполнения:

 A = x.dot(B) ## return a numpy array

… это не должно быть проблемой.

В комментариях вы упоминаете, что ваша реализация findRank сортирует A. Это неоптимально, так как представляет временную сложность O (nlogn).

Вместо этого просто подсчитайте количество значений в массиве, которые меньше значения, для которого вам нужен ранг. Это будет соответствовать рангу на основе нуля:

 rank = np.sum(A < a)

1. Ваш ответ начинается с «вы не можете надеяться определить ранг значения в несортированном массиве»; затем вы переходите к объяснению, как определить ранг значения в несортированном away.

2. Спасибо, что отметили это, @Stef. Я хотел сказать «… в сублинейное время». Отредактировано.