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

Обратный путь будет тривиально принимать O (n), поэтому было бы лучше отсортировать его в том порядке, в котором вы хотите, чтобы они отображались (в вашем случае по убыванию)

@JClassic Можете ли вы уточнить, почему это O (n)? Возможно ли, что JS использует двусвязный список за кулисами для списков?

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

Даже если это так, для этого все равно потребуется O(n) (проходя через каждый узел и меняя местами указатели next и prev). Вы практически не можете избежать O (n) для обратного, если только вы не используете странную структуру данных.

Я думаю, что вы оптимизируете преждевременно.

Единственный окончательный ответ: создайте тестовый пример с вашими данными на вашем устройстве, запустите его несколько тысяч раз и измерьте время, которое это занимает.

Две операции больше, чем одна. Просто отсортируйте по убыванию.

@coffee_mug .reverse() используется не так часто. Не имеет смысла использовать двусвязные списки для всех массивов в JS, если только некоторые из них перевернуты (кстати, интересная мысль)

@lux, если вы игнорируете все эти абстракции, происходящие под капотом, все (слишком) просто.

@JonasWilms, вы подразумеваете, что сортировка неупорядоченного списка (либо по возрастанию, либо по убыванию), а затем его обращение более эффективно, чем просто выполнение одной операции противоположной сортировки?

@lux Да, я думаю, что это может произойти во многих случаях. Возьмем, к примеру, [1, 3, 4, 5, 2].

@lux Я согласен, что этот вопрос может быть придирчивым, но бритва Оккама не универсальна, особенно в информатике. :)

@JonasWilms Таким образом, вы должны сначала 1) выполнить итерацию по элементам массива 2) выполнить логику, чтобы определить, будет ли asc / desc наиболее оптимальным 3) выполнить операцию сортировки 4) при необходимости отменить ее, а не 1) отсортировать способ, которым вам нужны предметы. В списке из 100 пунктов? Если бы когда-либо был случай преждевременной оптимизации/перепроектирования, это был бы он.

Всем спасибо за наблюдения и мысли. Как кто-то сказал, единственный окончательный способ проверить это - это... проверить. Я прогоню обе сортировки с разным количеством элементов и опубликую результаты. Жаль, что у меня не было достаточно очков, чтобы проголосовать за всех.

@lux нет, я просто говорю, что мы не можем сказать наверняка. Может быть, данные уже как-то отсортированы

Поэтому я провел несколько тестов сортировки массива по убыванию, а затем по возрастанию с обратным. Результаты довольно интересные: Запуск в хроме: — 1000 элементов в случайном порядке, нормальная сортировка по убыванию, 10000 попыток: 0,36810249999671213 мс — 1000 элементов в случайном порядке, сортировка по возрастанию, затем обратная, 10000 попыток: 0,36508599999770014 мс — 1000 элементов в порядке возрастания, нормальная сортировка по убыванию , 10000 попыток: 0,02824799999525567 мс - 1000 элементов в порядке возрастания, сортировка по возрастанию, затем в обратном порядке, 10000 попыток: 0,024710499998855086 мс

Хм. Что делать, если массив уже отсортирован по возрастанию? Тогда сортировка + реверс может быть быстрее...

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

@JonasWilms отличная мысль. dandavis, я бы не стал заострять на этом внимание, потому что это трудно измерить, так как это действительно зависит от интерпретатора. Обычно вы сосредотачиваетесь на количестве операций, когда говорите о временной сложности.