Эффективность list.Reverse () в JavaScript?

Question

Кто-нибудь знает, насколько эффективен .reverse () в JS для обращения к списку объектов?

Мне любопытно, будет ли какая-либо значительная потеря производительности для сортировки списка (скажем, 100 объектов) в порядке возрастания и его обращения, а не просто для сортировки списка в порядке убывания.

Edit: Поэтому я провел несколько тестов сортировки массива по убыванию, а затем по возрастанию с обратным. Результаты довольно интересные: (Работает в хроме)

• 1000 элементов в случайном порядке, в порядке убывания, 10000 попыток: 0,3681 мс
• 1000 элементов в случайном порядке, сортировка по возрастанию, затем обратный, 10000 испытаний: 0,3651 мс
• 1000 элементов в порядке возрастания, нормальная сортировка по убыванию, 10000 испытаний: 0,0282 мс
• 1000 элементов в порядке возрастания, сортировка по возрастанию, затем обратный, 10000 попыток: 0,0247 мс

Кажется, что .reverse () не очень дорогая операция, особенно по сравнению с сортировкой.

Answer 1

.reverse () работает в O (n), что видно из связанной спецификации. Это сделает попарно обмен элементов.

Чтобы ответить на ваш вопрос: sort + reverse неизбежно дороже, чем один sort, ярлык не создается (как может быть с двусвязным списком или какой-либо другой структурой данных).

Answer 2

Спецификация Ecma неясна в отношении Array#sort, поэтому ответ зависит от фактической реализации, если предположить, что мы говорим о V8 (Chrome, NodeJS), тогда мы можем сказать, что для списков с >10 элементами времясложность равна O(n log(n)), тогда как временная сложность Array#reverse равна O(n).

. Учитывая это, мы можем с уверенностью сказать, что было бы лучше отсортировать по убыванию напрямую, поскольку sort + reverse, очевидно, большедороже, чем просто sort.

сортировка в порядке убывания равна сортировке в порядке возрастания.

---

ОБНОВЛЕНИЕ :Как заявил Йонас в комментарии ниже, если вы можете заметить шаблон в своем списке (например, список уже отсортирован по asc), то, вероятно, вы можете просто изменить его и сохранить операцию O(n log(n)).Попытка понять форму ваших данных всегда является первым шагом для оптимизации производительности.