Javascript: Почему равенство строк занимает больше времени для более длинных строк?

#javascript #string #typescript #equality #string-interning

Вопрос:

В следующем коде создаются 1 миллиметровые строки одинаковой длины. Затем они перебираются, чтобы найти подходящую строку. В первом запуске есть строки, которые в 3 раза длиннее, чем во втором.

Ожидаемый результат заключался в том, что время, необходимое для сравнения строк разной длины на равенство, не будет меняться из-за «интернирования строк». Однако результаты показывают, что для проверки равенства строки, длина которой в 3 раза больше, требуется около 3 раз. Это почему?

 import { v4 as uuidv4 } from 'uuid';

export const uuid = () => {
  return uuidv4();
};

function createSingleId(howManyUuidsInOneId1: number) {
  let id = '';
  for (let j = 0; j < howManyUuidsInOneId1; j  ) {
    id  = uuid();
  }
  return id;
}

function generate(howManyIds: number, howManyUuidsInOneId: number) {
  const ids = [];
  for (let i = 0; i < howManyIds; i  ) {
    ids.push(createSingleId(howManyUuidsInOneId));
  }
  return ids;
}

const main = (howManyIds: number, howManyUuidsInOneId:number) => {

  const ids = generate(howManyIds, howManyUuidsInOneId);

  const toFind = createSingleId(howManyUuidsInOneId);

  console.log(`Sample id being compared: '${toFind}'`);

  const before = new Date().getTime();

  ids.filter(id => id === toFind);

  console.log(`Took '${new Date().getTime() - before}ms' to loop through and equal compare '${howManyIds}' when stacked '${howManyUuidsInOneId}' in single id`);
};

main(1000000, 3);
main(1000000, 1);

Выход:

 Sample id being compared: 'dc03bf00-6f2a-48d9-b3ca-b6ac45782c5cefaa92c0-9372-4f47-bcec-f9fbb41d4625e0c5c278-b574-4a9f-a77e-110cbc6bf601'
Took '64ms' to loop through and equal compare '1000000' when stacked '3' in single id
Sample id being compared: '07e693ce-49a1-4cc6-90e1-0bd99629123b'
Took '19ms' to loop through and equal compare '1000000' when stacked '1' in single id

 > node --version
v15.14.0

1. Ему действительно нужно сравнивать строки символ за символом, и это занимает больше времени для более длинных строк…?! Стажировка просто означает, что у вас не будет нескольких копий строки в памяти. Движок может быть умным и понять, что он пытается сравнить одно и то же место в памяти и тем самым полностью пропустить его, но, по-видимому, он этого не делает, и/или строки не интернируются (почему вы думаете, что они должны быть?).

Ответ №1:

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

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

Какой-нибудь пример, демонстрирующий это:

 function generateString(len) {
  let x = "";
  for (let i=0; i<len; i  ) x = String.fromCharCode(64 id);
  return x;
}
function time(callback, desc) {
  const before = performance.now();
  const res = callback();
  console.log(`Took ${performance.now()-before}ms to ${desc}`);
  return res;
}

const strLen = 5000000;
const a = generateString(strLen);
const b = generateString(strLen);
console.assert(a === b);
const str = a;
time(() => str === a, 'compare a with itself');
time(() => str === b, 'compare a with b');

a и b имеют одинаковое содержимое, но являются разными строковыми объектами (в памяти), потому что они были накоплены в разных generateString вызовах. str ссылается на то же значение, что a и.