Какова временная сложность Map.prototype.size в JavaScript?

#javascript #dictionary #ecmascript-6 #time-complexity

#javascript #словарь #ecmascript-6 #временная сложность

Вопрос:

Вот ссылка на метод, просто пытаюсь выяснить, какова временная сложность по сравнению с выполнением a .длина массива.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/size

Комментарии:

1. Это удивительно интересный вопрос, спасибо!

Ответ №1:

Согласно спецификации, Array length — это простое свойство данных, доступное только для чтения, но Map size — это свойство доступа, которое вычисляет количество элементов путем перебора списка записей карты.

На самом деле я ожидаю size , что он будет оптимизирован движками JavaScript, поэтому ему не нужно каждый раз перебирать список, но цикл — это то, как его определяет спецификация.

Итак, теоретически ответ на вопрос «Какова временная сложность Map.prototype.size в JavaScript?» равен O (n), но я уверен, что реальность намного лучше, чем это.

Комментарии:

1. Интересно, но при проверке размера созданного пользователем объекта вам нужно будет обязательно перебирать весь объект для каждой проверки размера, верно?

2. @mek24 — Если вы ничего не сделаете, чтобы избежать этого (что возможно, но больно), да, вы бы это сделали. Часть преимущества Map , я думаю, заключается в том, что у вас есть потенциальная / вероятная выгода от оптимизации в движке JS, если это нужная вам информация…