Некоторое время я работал над проектом iOS, на котором мне пришлось создать пару экранов, которые полностью управляются JSON, возвращаемым из API. Каждое представление и вложенная иерархия представлений управляются JSON. Это кажется интересным, и это то, что я получил от API.
Вот образец JSON,
Вот простое объяснение,
viewType
: Enum представляет различные элементы пользовательского интерфейса, такие как UIView
, UIButton
.. и так далее.
viewID
: Это прямой уникальный идентификатор для каждого элемента.
children
: дочерний элемент, который находится внутри представления
Этот JSON будет преобразован в объект DynamicUIElement
Я не буду объяснять, как преобразовать JSON в UI, эта статья не об этом. Речь идет о конкретном случае, и вот он,
Мы построили это представление и полную иерархию. Теперь, когда пользователь взаимодействует с представлениями, нам нужно выяснить, к какому объекту JSON принадлежит это представление. Вот так! Это то, что мы пытаемся здесь решить.
Перечислим, что у нас есть,
- UIView, который выбран пользователем
- viewID этого представления, который совпадает с
DynamicUIElement.viewID
- Иерархия просмотров
- Иерархия `DynamicUIElement`
Это была моя первая реализация.
Работает, слили PR. Позже, когда я прочитал тот же код пару месяцев назад, я почувствовал, что мы можем улучшить эту логику. Я заметил две вещи,
- Там интерфейс мог бы быть лучше.
- Эта логика кажется грубой силой.
Я начал с улучшения интерфейса. Я обновил приведенную выше логику,
Я провел тест для описанного выше алгоритма. Вот результат.
self.measure { _ = viewModel.viewForID(22651) }
[0.002777, 0.000361, 0.000356, 0.000356, 0.000357, 0.000356, 0.000356, 0.000356, 0.000356, 0.000356]
Теперь я почувствовал, что сделал что-то действительно хорошее. Затем я делюсь этим со своим другом. Он сказал: «Что ж, интерфейс выглядит хорошо, но ваш алгоритм по-прежнему O (n), что хорошо, но теперь отличный алгоритм, потому что мы все еще рекурсивно повторяем дочерние элементы, его дочерние элементы и его дочерние элементы ... и так далее », мы могли бы добиться большего. Производительность поиска по-прежнему оставляет желать лучшего. Затем мы обсудили больше и придумали лучшее решение, воспользовавшись структурой данных HashTable (Hash Map).
Что, если мы создадим хеш-таблицу для индексации адреса памяти объектов DynamicUIElement
?.
Временная сложность хеш-таблицы составляет O (1).
Поэтому я решил пойти по этому пути. Вот так выглядит хеш-таблица,
В этой хэш-таблице будет храниться адрес памяти объекта a DynamicUIElement
напротив его viewID
, независимо от глубины объекта в иерархии. В основном индексная таблица плоская. Имея в руках эту таблицу, мы могли бы избежать написания алгоритма поиска и найти объект, который ищем, за постоянное время O (1).
Все, что нам нужно сделать сейчас, это убедиться, что мы добавляем адрес памяти любого вновь созданного объекта DynamicUIElement
в индексную таблицу во время анализа данных.
Теперь отправьте обратно IndexTable
вместе с проанализированной моделью вызывающей стороне.
Я снова провел тот же тест измерения, но на этот раз производительность алгоритма намного лучше,
[0.000046, 0.000008, 0.000004, 0.000004, 0.000004, 0.000004, 0.000003, 0.000003, 0.000003, 0.000003]
Результаты были впечатляющими. Мы уменьшили время выполнения с 0,000356 до 0,000003.
В подходе HashTable, который я использовал, увеличивается сложность пространства, поскольку нам нужно выделить дополнительную память для IndexTable
, но пространство меня не беспокоило, моей целью было улучшить асимптотическую временную сложность моего алгоритма.
Обратите внимание, что могут быть лучшие алгоритмы, которые хорошо справляются с такими проблемами как во времени, так и в пространстве, если вы его найдете, дайте мне знать в комментариях.