Что касается массива, содержащего много повторяющихся элементов, существуют ли какие-либо операции для повышения производительности обычного двоичного поиска? - PullRequest
4 голосов
/ 08 июля 2010

Что касается массива, содержащего много повторяющихся элементов, существуют ли какие-либо операции для повышения производительности обычного двоичного поиска?

Ответы [ 3 ]

9 голосов
/ 08 июля 2010

Вы можете создать два массива. Один для значений, а другой для повторений. Затем вы можете искать массив значений с помощью бинарного поиска.

1 голос
/ 08 июля 2010

Как и в случае ответа AraK, вы можете использовать массив кортежей размера 2 на языках, которые их поддерживают, причем первый элемент каждого кортежа является искомым значением, а второй - числом повторений, или вы можетеиспользуйте двумерный массив для аналогичных целей.

Некоторые языки даже имеют функции, которые позволяют вам брать массив элементов и создавать подсчитанный список.Например, Python 3.1+ имеет класс Counter, который делает именно это, хотя, к сожалению, возвращаемый тип данных, подкласс встроенного в Python dict, представляет собой неупорядоченную коллекцию, хотя вы можете просто использоватьl = list(Counter([collection of values]).items()); l.sort() для создания отсортированного списка кортежей, подобного тому, который я впервые упомянул.Я уверен, что другие языки имеют аналогичные конструкции.

РЕДАКТИРОВАТЬ: обратите внимание, что, поскольку тип dict реализован как hashtable / hashmap, на самом деле может быть проще проверить элементы (если вы, скажем,проверка наличия или отсутствия элемента в списке) с использованием самого объекта Counter, поскольку это позволит избежать затрат на преобразование и сортировку и будет стоить лишь немного больше для каждого поиска / проверки.Если у вас есть счетчик (назовем его «c»), вы можете сделать c[value] > 0, который вернет True, если значение находится в вашем исходном списке, и False, если его нет.

1 голос
/ 08 июля 2010

Ответ Арака - «единственный» ответ.В общем, вы не можете улучшить производительность в худшем случае на любом массиве с дубликатами.Допустим, ваши дубликаты имеют тенденцию концентрироваться в конце массива.Теперь вы ищете элемент в начале: ваш поиск должен выполняться как обычно.

Если вы знаете , что дубликаты, как правило, появляются на одной стороне чаще, вы можете искажатьразделение для улучшения средней производительности.Если они появляются ближе к концу, например, вы можете сделать first split в 1/3 вместо 1 / 2.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...