Какой самый быстрый поиск может быть выполнен в несортированном массиве?

Question

Как быстро искать в несортированном массиве?Я не могу думать ни о каком другом механизме поиска, кроме линейного поиска.

Любые указатели будут полезны.

Answer 1

Да, без сортировки данных линейный поиск почти так же хорош, как вы можете.

Answer 2

Учитывая действительно случайный несортированный массив, линейный поиск - лучший способ.

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

Answer 3

Линейно. Или сортируйте свой массив и ищите его во время регистрации.

Answer 4

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

Answer 5

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

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

Можно ли вообще сортировать / сортировать данные, чтобы наиболее часто используемые элементы находились рядом с началом массива?

Практично ли хранить ваши данные в двух наборах? Один отсортирован, один не отсортирован? Сортировка, вы должны быть в состоянии быстро найти ваш товар. Если не найден, перейдите к вашему несортированному списку и выполните линейный поиск по нему. Зачем? Хотя вы сказали, что вставлять после каждой вставки непрактично, целесообразно ли / периодически вставлять из несортированного списка в отсортированный список?

Должно ли все это быть в одном несортированном массиве? Можете ли вы поместить свои данные в блоки отсортированных данных? То есть вы можете 1000 отсортированных записей на блок. Поиск по каждому отсортированному блоку может быть быстрее, чем поиск по всему не отсортированному списку.

Просто некоторые идеи. Они могут быть неприменимы к вашей ситуации, но, надеюсь, они полезны.

Answer 6

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

Answer 7

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

Answer 8

После того, как ваш код представлен в несортированном списке, да, вам нужно будет выполнить линейный поиск.

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

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

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

Хотя вам не стоит беспокоиться ни об одном из них, если только список не очень большой и медленный.поиск.В общем, чем меньше кода вы можете написать, тем лучше для всех .