Цитата(Rage @ 1.2.2010, 23:12  ) |
| как организовать поиск в упорядоченном массиве длиной, допустим, |
если уж массив отсортирован - однозначно двоичный (бинарный) поиск.
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Поиск в ОЧЕНЬ большом массиве |
| Автор: Rage 1.2.2010, 23:12 |
| Привет, всем! Подскажите, пожалуйста, как организовать поиск в упорядоченном массиве длиной, допустим, 1000000000000. В принципе длина не важна. Суть в том, что она больше чем позволяет long int. Как можно поступить в таком случае? |
| Автор: Alexeis 1.2.2010, 23:53 |
| Бинарный поиск это логорифмическое время. 2^100 = 1 267 650 600 228 229 401 496 703 205 376 Всего 100 итераций. Это больше чем влазит в int64. Добавлено через 2 минуты Это пожалуй больше чем емкость всех жестких дисков которые были произведены на свете. |
| Автор: Rage 2.2.2010, 00:23 |
| хм... очень странно. потому что меня сегодня на собеседовании попросили провести поиск в таком массиве =) ну можт я на пару нулей ошибся... |
| Автор: mrbrooks 2.2.2010, 08:58 | ||
если уж массив отсортирован - однозначно двоичный (бинарный) поиск. |
| Автор: xvr 2.2.2010, 14:25 |
Проблема не в том, как искать в таком массиве, а где его хранить  В память (32х битную) он не влезет, т.е. хранить надо на внешнем носителе, и искать там же.Т.е. вопрос превращыется в другой - как организовать бинарный поиск в (большом) файле на диске. |
| Автор: Alexeis 2.2.2010, 14:35 |
| xvr, тут похоже академическая задача, суть которой оптимизировать поиск. По моему быстрее бинарного поиска, только поиск хеш таблице. Но у хеш таблицы больше расходы памяти. |
| Автор: W4FhLF 2.2.2010, 14:36 |
| Если известен формат хранения файла и есть интерфейс доступа, то в прицнипе какие проблемы? |
| Автор: xvr 2.2.2010, 15:09 | ||
Хэш таблицу сначала надо построить  По моему, эдесь было произнесено 3 ключевые фразы:
|
| Автор: unicuum 3.2.2010, 06:21 | ||
1000000000000 32 бита 4294967296 64 бита 18446744073709551616 то есть вполне можно работать тера гига мега кило 1000'000'000'000 опять же не уточняю окончания, впрочем учитывая как врут современные производители винтов, используя 1000 вместо 1024 и меняя там стандартные системы как вздумается (кстати я по старому считаю и плевал на то, что они там протащили за свои деньги), в общем учитывая это, винты вполне тоже способны хранить такой массив. А дальше двоичный поиск. Делим адресацию на два и проверяем условие сравнения. найти 3 (деление без округления, с отбрасыванием остатка) 01234 56789 01 234 2 34 3 4 3 |
| Автор: Lazin 3.2.2010, 06:36 |
| B tree B+ tree |
| Автор: mes 3.2.2010, 12:05 | ||||||||
я так понимаю это относилось к фразе
но там говорилось не о
а о
 |
| Автор: Alexeis 3.2.2010, 12:11 |
| mes, я как бы определил область эффективности алгоритма. Т.е. сто итераций это верхний предел того что может понадобиться. Раз это производиться быстро даже для невообразимо большого объема данных, то тем более быстро в всех остальных случаях. |
| Автор: Lazin 3.2.2010, 12:50 |
| проблема только в том, что этот массив должен быть предварительно отсортирован, а сортируется он хуже чем за линейное время |
| Автор: mes 3.2.2010, 12:51 | ||||||
я то понял как раз теми цитатами и показывал откуда взялся невообразимо большой объем данных.  Добавлено через 1 минуту и 38 секунд
|
| Автор: jonie 4.2.2010, 02:22 |
| А я бы спросил про память и задачу: надо найти быстро или находить быстро (несколько раз). Если "памяти мало и находить несколько раз", то вероятно с ходу бы я разбил бы массив на N частей, и зная границы (значения на них) частей искал бы уже в частях (массив, напомню, сортированный). Индексация массива таким образом очень быстра, а выигрышь в скорости поиска может быть значительным (считать лениво). И это будет быстрее бинарного поиска (возможно, не при одиночном проходе) и не жрать столько памяти , сколько хеш таблицы или деревья.... |