Эффективный способ вставить число в сортированный массив чисел?
Если Вы только сделаете это для одного управления, то подход таймера будет хорошо работать. Более устойчивый подход, поддерживающий несколько средств управления и типов событий, выглядит примерно так:
class Event
{
public DateTime StartTime { get; set; }
public Action Method { get; set; }
public Event(Action method)
{
Method = method;
StartTime = DateTime.Now + TimeSpan.FromSeconds(1);
}
}
Поддерживают Queue<Event> в Вашей форме и имеют события UI, которые должны быть отложены, добавляют их к очереди, например:
void onButtonClick( ..)
{
EventQueue.Enqueue(new Event(MethodToCall));
}
Заставляют Ваш таймер отсчитать 10 раз приблизительно в секунду, и иметь его обработчик событий Галочки похожи на это:
void onTimerTick()
{
if (EventQueue.Any() && EventQueue.First().StartTime >= DateTime.Now)
{
Event e = EventQueue.Dequeue();
e.Method;
}
}
2 ответа
Your insertion function assumes that the given array is sorted, it searches directly for the location where the new element can be inserted, usually by just looking at a few of the elements in the array.
The general sort function of an array can't take these shortcuts. Obviously it at least has to inspect all elements in the array to see if they are already correctly ordered. This fact alone makes the general sort slower than the insertion function.
A generic sort algorithm is usually on average O(n ⋅ log(n)) and depending on the implementation it might actually be the worst case if the array is already sorted, leading to complexities of O(n2). Directly searching for the insertion position instead has just a complexity of O(log(n)), so it will always be much faster.
Вот несколько мыслей: Во-первых, если вы действительно беспокоитесь о времени выполнения вашего кода, обязательно знайте, что происходит, когда вы вызываете встроенные функции! Я не знаю сверху вниз в javascript, но быстрый поиск функции splice вернул this , что, кажется, указывает на то, что вы создаете совершенно новый массив при каждом вызове! Не знаю, действительно ли это имеет значение, но, безусловно, связано с эффективностью. Я вижу, что Бретон в комментариях уже указывал на это, но это определенно справедливо для любой функции управления массивами, которую вы выберете.
В любом случае, на решение проблемы.
Когда я прочитал, что вы хотели отсортировать , моя первая мысль - использовать сортировку вставкой ! . Это удобно, потому что он работает в линейное время в отсортированных или почти отсортированных списках . Поскольку в ваших массивах будет только 1 элемент, вышедший из строя, это считается почти отсортированным (за исключением, ну, массивов размера 2 или 3 или чего-то еще, но в этот момент давай). Теперь реализация сортировки не так уж и плоха, но это проблема, с которой вы, возможно, не захотите иметь дело, и, опять же, я ничего не знаю о javascript и будет ли это легко или сложно или еще много чего. Это устраняет необходимость в вашей функции поиска, и вы просто нажимаете (как предложил Бретон).
Во-вторых, ваша функция поиска в стиле быстрой сортировки, похоже, представляет собой алгоритм двоичного поиска ! Это очень хороший алгоритм, интуитивно понятный и быстрый, но с одной загвоздкой: его, как известно, сложно реализовать правильно. Я не осмелюсь сказать, верна ваша или нет (я надеюсь, что это так, конечно! :)), но будьте осторожны, если хотите ее использовать.
В любом случае, резюме: использование "push" со вставкой sort будет работать за линейное время (при условии, что остальная часть массива отсортирована) и позволит избежать каких-либо запутанных требований алгоритма двоичного поиска. Я не знаю, лучший ли это способ (базовая реализация массивов, возможно, сумасшедшая встроенная функция делает это лучше, кто знает), но мне это кажется разумным. :) - Агор.