Некоторое время я работал над проектом 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, но пространство меня не беспокоило, моей целью было улучшить асимптотическую временную сложность моего алгоритма.

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