ArrayList BinarySearch
Я занят, готовясь к экзамену 70-536 MCTS, согласно книге экзамена (Microsoft Press - Платформа.NET - Основа Разработки приложений Сам Измеренный шагами Учебный Набор 2-й Выпуск), этот пример кода:
ArrayList al = new ArrayList();
al.AddRange(new string[] { "Hello", "world", "this", "is", "a", "test" });
Console.WriteLine(al.BinarySearch("this"));
Производит значение '2' к консоли, потому что объект 'это' в индексе 2. Согласованный это - вывод, который я получаю, когда я выполняю тот код.
Однако, если я работаю
Console.WriteLine(al.BinarySearch("world"));
Я ожидал бы получать значение 1 в консоли, так как 'мир' будет в индексе 1, однако я получаю значение-7?
Кто-либо мог объяснить, как это работает?
Спасибо
3 ответа
Массив, в котором выполняется двоичный поиск не сортируется. Это требование для работы BinarySearch .
Отсутствие сортировки сбивает алгоритм поиска с толку и заставляет его думать, что «мир» должен быть на 7-м месте, но его нет в массиве: результат -7.
Взято непосредственно из документации MSDN ArrayList.BinureSearch ( http ://msdn.microsoft.com/en-us/library/5tzt7yz3% 28VS.85% 29 .aspx )
-121--3133387-Параметр значения и каждый элемент ArrayList должен реализовывать Интерфейс IComparable, который используется для сравнения. Элементы ArrayList уже должен быть отсортирован в увеличение значения в соответствии с сортировкой порядок, определенный IComparable внедрение; в противном случае результат возможно, неверно.
100x100 = 10k, оптимизированная грубая сила не кажется некогерентной, особенно если тест пересечения луча/сферы включает только добавление/умножение. Всегда можно предварительно вычислить весь нормализованный вектор луча перед основным контуром.
Если вы предполагаете, что вы живете в ограниченной Вселенной и пространственная плотность сфер и лучей относительно однородна, вы можете использовать фиксированную пространственную сетку (фиксированное oct-дерево) - что-то вроде сетки ячеек 16x16x16, или более того - и:
- предварительно вычислить для каждой сферы пересекающиеся ячейки (легко вычислить, только включать в себя несколько добавлений и сравнений), сохранить в каждой ячейке список пересекающихся сфер,
- для каждого луча, в цикле:
- вычислить список ячеек, пересекаемых лучом (метод, основанный на алгоритме Бресенхэма, может выполнить трюк)
- выполнить тест пересечения для всех сфер в этом списке ячеек.
Таким образом, вам не нужно хранить лучи ни в одном дереве, только в сферах. Эффективность этого метода зависит от соотношения размер ячейки/размер сферы, если у вас нет слишком большой дисперсии на размер сферы, это может быть хорошим намеком.
Если сферы не пересекаются друг с другом и размер сферы минимален, можно даже привязать список сфер в списке ячеек (соответствующее число оставлено в качестве упражнения для читателя...)
HTH
-121--4067198-Из документации :
Отсчитываемый от нуля индекс значения в отсортированный ArrayList, если значение найдено; в противном случае отрицательное число, которое равно побитовое дополнение индекса следующий элемент, размер которого превышает значение или, если нет большего элемент, побитовое дополнение Граф.
Обратите внимание на отсортированное слово.
Взятый непосредственно из документации MSDN ArrayList. BinarySearch ( http://msdn.microsoft.com/en-us/library/5tzt7yz3%28VS.85%29.aspx)
параметр стоимости и каждый элемент ArrayList должен реализовывать Интерфейс IComparable, который используется для сравнения. Элементы ArrayList уже должен быть отсортирован в увеличение значения в соответствии с сортировкой порядок, определенный IComparable осуществление; в противном случае результат возможно, неверно.