Блог

Допустим, у меня есть class с fields массивом. Каждое поле имеет name . В основном, как таблица SQL.

  class X {
   foo: String
   bar: String
   ...
 }
  

Каков способ построения структуры данных и алгоритма для извлечения поля по ключу таким образом, чтобы это было (а) быстро с точки зрения количества операций и (б) минимально с точки зрения размера памяти / структуры данных?

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

Теперь количество ключей будет относительно небольшим для каждого класса. В этом примере есть только 2 ключа / поля.

Одним из способов сделать это было бы создать хэш-таблицу, подобную этой, в JS. Вы даете ему ключ, и он перебирает каждый символ в ключе и запускает его через некоторую функцию микширования. Но это, во-первых, зависит от размера ключа. Неплохо для ожидаемых типов имен полей, которые не должны быть слишком большими, скажем, они обычно не длиннее 100 символов.

Другим способом сделать это было бы создать trie. Сначала вам нужно вычислить дерево, затем, когда вы выполняете поиск, каждый узел дерева будет иметь один символ, поэтому для поиска поля потребуется name.length количество шагов.

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

Но все эти 3 метода будут примерно одинаковыми с точки зрения количества итераций.

Есть ли какой-либо другой тип магии, который даст вам наименьшее количество итераций / шагов?

Кажется, что может существовать возможный алгоритм хеширования, который использует в своих интересах тот факт, что количество элементов в хэш-таблице будет небольшим. Вы бы создали новую хеш-таблицу для каждого класса, присвоив ей «размер» (количество полей в конкретном классе, используемом для этой хеш-таблицы). Возможно, каким-то образом он может использовать эту информацию о размере для построения простого алгоритма хеширования, который минимизирует количество итераций.

Возможно ли что-нибудь подобное? Если да, то как бы вы это сделали? Если нет, то было бы интересно узнать, почему невозможно получить более оптимальный вариант, чем этот.

Насколько «мал» список полей?

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

Для очень небольшого числа полей (например, 4) он будет выполнять примерно такое же количество итераций и сравнения ключей, что и линейный поиск, если рассматривать наихудший случай линейного поиска. (Линейный поиск был бы очень эффективным (скорость и память) для этого случая.)

Чтобы превзойти средний случай линейного поиска, вам понадобится больше полей (например, 8).

Это так же эффективно с точки зрения памяти, как и ваше решение линейного поиска. Более эффективное использование памяти, чем решение trie.