2

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

Соответственно я не знаю, что будет лучше: сначала не учитывая порядок добавлять элементы в массив, а потом уже отсортировать с помощью эффективных алгоритмов сортировок, либо же изначально добавлять, учитывая порядок?

Дело в том, что алгоритм добавления, учитывая порядок, аналогичен сортировке вставками (Insertion Sort), временная сложность которого О(n^2), в то время как сложность алгоритма "вставить и потом отсортировать" будет n + (n * log(n)). n для того чтобы заполнить массив и n log n для того, чтобы отсортировать.

Так вот действительно ли будет на практике решение "заполнить и потом уже отсортировать" более эффективным?

Что вообще из этих двух вариантов будет наиболее эффективным в моем случае? Что мне стоит сделать?

15
  • "в игре 60 раз в секунду проверяется этот массив" - проверяется или заполняется?
    – user176262
    6 июл 2018 в 15:49
  • При инициализации игры массив заполняется. Потом уже в процессе игры координаты игрока сверяются с координатами бомб в массиве. То есть каждую секунду 60 раз линейно проходится этот массив. 6 июл 2018 в 15:54
  • Вариант третий - не сортировать - не рассматривался? Созданный массив обрабатывать без сортировки "с помощью эффективных алгоритмов". Вдруг получится быстрее? 6 июл 2018 в 15:55
  • ну и как вы будете быстро искать элемент в неотсортированном массиве? Линейным поиском? Это я уже пробовал, а теперь хочу оптимизировать. 6 июл 2018 в 15:55
  • 3
    Стоит написать и один, и второй варианты и посмотреть время работы. Ибо Практика - критерий истины. (с) Маркс :) Это единственный реально работающий способ...
    – Harry
    6 июл 2018 в 16:32

1 ответ 1

1

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

5
  • Да, это уже давно понял и так сделал, Вы правы! 10 июл 2018 в 13:58
  • Вставлять каждый раз в отсортированном порядке это больше походит на Insertion Sort. То есть временная сложность будет O(n^2). Когда воспользовавшись встроенной сортировкой сложность будет O(n log n). 10 июл 2018 в 13:59
  • Не совсем. Вставка элемента, это вставка элемента (да, она присутствует в сортировке вставками, но не более). Сортировка это сортировка. Если вы будете вставлять элемент и каждый раз запускать сортировку, то у вас каждый раз будет уходить квадрат от количества элементов. Если вы будете каждый раз вставлять элемент, у вас будет уходить линия от количества элементов. 10 июл 2018 в 14:07
  • Ну так я это и имею ввиду. Если 100 элементов вставлять в отсортированном порядке, уйдет O(n^2) = ~100000 итераций. А вот если я все вставлю и отсортирую то будет 100 + 100 * 6 = 700 итераций. 10 июл 2018 в 14:11
  • O(n^2) = ~10000 * * 10 июл 2018 в 18:23

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.