Насколько я понимаю, поиск индекса растровый будет возвращать массив 0 и 1, как показано ниже:Растровый массив результатов поиска растровых изображений: поиск индексов ненулевых элементов в постоянное время?
[0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0]
Каждый индекс в массиве сопоставляется с некоторой записью в базе данных в другом массиве, поэтому для получения результатов вам нужно найти индексы ненулевых элементов в массиве результатов ,
Я не понимаю, как вы находите эти индексы в постоянное время? Лучший алгоритм, который я могу придумать, - это пройти через каждый элемент массива, проверить, отличен ли он от него, и если он отличен от нуля, тогда напишите индекс этого элемента где-нибудь еще. Однако это означало бы последовательно смотреть на каждый элемент массива, который является линейным временем. Таким образом, время, затрачиваемое на возврат результатов, будет пропорционально размеру массива результатов, что совпадает с общим количеством строк в таблице.
Однако документы с растровым индексом, которые я прочитал, похоже, предполагают, что время запроса пропорционально числу обращений, а не к общему количеству строк в таблице. Справка:
http://crd-legacy.lbl.gov/~kewu/ps/LBNL-59952.pdf
ли я что-то неправильно? Является ли результат поиска индекса растрового изображения не представленным как массив, а какой-либо другой структурой данных, которая позволяет постоянный поиск времени для ненулевых элементов?
Ну, чтобы быть пропорциональным количеству ударов, возможно, они хранят ненулевые индексы вместо фактического растрового изображения (например, '[6, 7, 11]' в вашем случае). Поиск, который по-прежнему будет линейным, но «менее линейным», чем поиск растрового изображения. Или, возможно, комментарий «постоянное время» относится к тестированию того, загрязнен ли какой-то конкретный индекс, который представляет собой только один доступ к массиву в растровом изображении, в отличие от поиска всех грязных индексов ... – twalberg