Работа с кортежами в Javascript: структура данных контейнера - PullRequest
Новая
       5

Работа с кортежами в Javascript: структура данных контейнера

0 голосов
/ 11 марта 2020

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

// Think of Vector<Tuple<4>>
const vector_of_tuples = [
  [0, 0, 0, 0],
  [0, 1, 4, 6],
  [9, 8, 7, 2],
  [5, 6, 7, 8],
];

Кортежи чисел (фиксированной длины), теперь были моим базовым c типом данных, и я хочу чтобы сделать из них векторы, использовать их в качестве ключей на картах и ​​так далее. (Использование их в качестве ключей в картах - вопрос для другого дня.)

Если мой код много раз создает новые векторы кортежей, он создает много мусора, поскольку каждый кортеж выделяет свое собственное хранилище. Создание вектора с n кортежами приводит к выделению O (n). Очевидной победой на этом фронте было бы «упаковать» кортежи в один вектор (снимите квадратные скобки в приведенном выше примере): 

const packed_vector_of_tuples = [
  0, 0, 0, 0,
  0, 1, 4, 6,
  9, 8, 7, 2,
  5, 6, 7, 8
];

Это большой выигрыш с точки зрения распределения (O ( 1) вместо O (n) для вектора, содержащего n кортежей), но большие потери с точки зрения удобства использования. Очевидно, теперь мне нужно как-то запомнить длину кортежей (не проблема, легко решаемая), но абстракция становится намного сложнее. Предположим, что теперь я хочу перебрать свой упакованный вектор кортежей, подобно тому, как изначально работал vector_of_tuples.forEach(...). Одна идея состоит в том, чтобы сделать это следующим образом: 

function forEach_packed_vector(packed_vector, tuple_length, func) {
  for (let i = 0; i < packed_vector.length; i += tuple_length)
    func(packed_vector.slice(i, i + tuple_length));
}

Однако это означает, что каждый раз, когда я выполняю итерацию, я делаю O (n) распределений, именно то, чего я пытался избежать. (Как V8, так и SpiderMonkey, по-видимому, не могут передать короткий вектор в стеке или, по крайней мере, в достаточный запасной анализ для работы с моим кодом.) пробел: 

function forEach_packed_vector_2(packed_vector, tuple_length, func) {
  const temporary = [];
  for (let i = 0; i < packed_vector.length; i += tuple_length) {
    // Copy packed_vector[i : i + tuple_length] into temporary.
    for (let j = 0; j < tuple_length; j++)
      temporary[j] = packed_vector[i + j];

    // Now call the iteration function.
    func(temporary);
  }
}

На самом деле это работает довольно хорошо, не выделяется более одного раза и невероятно быстро. Тем не менее, я продолжаю сталкиваться с ошибками, где func содержит ссылку на переданный вектор (вместо того, чтобы делать защитную копию, как это должно быть), что приводит к некоторым очень очень странным ошибкам, проявляющимся где-то еще в моем коде. Так что это решение великолепно с точки зрения производительности и довольно ужасно с точки зрения возможности выстрелить себе в ногу.

Вопрос: Как я могу написать качественно, мусорную лампу код, подобный этому, не устанавливая для себя ловушки на потом?

Эта проблема в основном заключается в том, чтобы просить тип среза, например Span<T> в C#, или срезы в Go, et c. Но я был бы открыт для любых предложений о том, как создать эффективные структуры данных, подобные этой, чтобы она прекрасно подходила для абстракции, не оставляя при себе орудий.

1 Ответ

1 голос
/ 11 марта 2020

Как вы, наверное, хорошо знаете, в JavaScript нет "типа среза".

Вы можете создать свой собственный: 

class Slice {
  constructor(array, start, length) {
    this.array = array;
    this.start = start;
    this.length = length;
  }
  get(index) {
    return this.array[this.start + index];
  }
  /* any other methods you want */
}

function func(slice) {
  for (let i = 0; i < slice.length; i++) {
    console.log(slice.get(i));
  }
}

func(new Slice(packed_vector_of_tuples, 4, 4));

Конечно, вы бы выделили любой время, когда вы создаете такой фрагмент, но особенно если ваши кортежи намного больше, чем 4 элемента, это может быть разумным компромиссом между абстракцией и эффективностью - в частности, это O (1) на распределение, тогда как Array.prototype.slice должен выделять , а затем скопируйте n elements .

((EDIT: чтобы расширить это: вы можете еще больше сократить количество выделений, кэшируя фрагменты во внешнем контейнере, примерно так: 

class PackedVector {
  constructor(tuple_length, tuple_count, tuple_data) {
    console.assert(tuple_data.length === tuple_length * tuple_count);
    this.array = tuple_data;
    this.slices = [];
    for (let i = 0; i < tuple_count; i++) {
      this.slices[i] = new Slice(this.array, i * tuple_length, tuple_length);
    }
    this.length = tuple_count;
  }
}

function forEach_packed_vector_3(packed_vector, func) {
  for (let i = 0; i < packed_vector.length; i++)
    func(packed_vector.slices(i));
}

END OF EDIT))

Для максимальной производительности packed_vector_of_tuples - хорошая идея, и любые вспомогательные функции могут использовать «распакованную» версию класса Slice выше , Так что вместо func(temporary) у вас будет func(base_array, start, length). Это защитило бы от ошибок типа «случайная ссылка», но сделало бы сигнатуры функций относительно громоздкими.

Из вашего описания кажется, что наличие идентификатора объекта отдельных кортежей важно для вашего более крупного приложения. Если это действительно так, я бы порекомендовал go с вашим самым первым решением: массивом массивов. Конечно, будет немного накладных расходов; но до тех пор, пока вы не заметите, что это действительно имеет значение, это не имеет значения (и я предсказываю, что это не будет; распределение будет дешевым, и чем длиннее кортеж, тем меньше относительные накладные расходы).

...