Однажды в классе (я заканчиваю учебный лагерь в Fullstack Academy) у меня была сессия REACTO, где меня спросили, как внедрить приоритетную очередь (затем пришлось имитировать собеседование с однокурсником), ну, первое. который появился у меня в голове, был разреженным массивом (мы вернемся к этому). Следующей вещью был связанный список.
Итак, мы прошли через это с инструктором, затем возник вопрос, можете ли вы оптимизировать? И вместе пришли кучи. Связанный список имеет временную сложность O(n) для вставки, O(1) для просмотра и извлечения и O(N) для пространственной сложности (запомните это N). Кучи, с другой стороны, имеют O (1) для просмотра, O (log n) для извлечения, что немного медленнее, но все же очень хорошо, но взамен мы также получаем O (log of n) для вставки и тот же O ( N) для пространства, стоит пожертвовать выскакиванием, но в затылке стучали эти разреженные массивы.
Я был собакой с костью, мне нужно было выяснить, почему не разрежены массивы. Поэтому, как любой хороший щенок, я начал копать… Я приглашаю вас спуститься со мной в кроличью нору и посмотреть, где я вышел.
Для начала мы должны поговорить о том, что такое массивы, а затем о том, что Javascript называет массивом.
вебопедия-
В программировании — серия «объектов, все из которых имеют одинаковый размер и тип. Каждый объект в массиве называется элементом массива. Например, у вас может быть массив целых чисел, массив символов или массив всего, что имеет определенный тип данных. . Важными характеристиками массива являются: важные характеристики массива:
- Каждый элемент имеет один и тот же тип данных (хотя они могут иметь разные значения).
- Весь массив хранится непрерывно в памяти (то есть между элементами нет промежутков)».
Кажется, это не подходит для массивов JavaScript, не так ли? ну, это потому, что то, что мы называем массивом в JS, на самом деле не является массивом по определению, это объект с некоторыми уникальными свойствами, такими как длина и т. д., это больше похоже на хеш-таблицу с указателями в ячейке. Еще одна интересная вещь: каждая платформа обрабатывает их по-разному, поэтому производительность JS-массивов сильно различается в разных браузерах (подробнее о производительности).
Следующее, что я хотел знать, это разреженные массивы (массивы с «дырами») в JS, так как в HashTable есть дыры, и это обычное дело. space, и поскольку я хотел посмотреть, будет ли работать мое решение для массива, я решил отдать предпочтение школе мысли, что их можно использовать.
после того, как я провел должную осмотрительность, пришло время, наконец, КОДИТЬ!!!! поэтому я написал простой фрагмент, чтобы проверить свое решение:
class PriorityQueue {
constructor() {
this.queue = [];
}
insert(priority, patient) {
if (!this.queue[priority]) {
this.queue[priority] = [{ patient, priority }];
} else {
this.queue[priority].push({ patient, priority });
}
}
peek() { console.log(this.queue[this.queue.length - 1][0].name);}
popMax() {
this.peek();
if (this.queue[this.queue.length - 1].length === 1) {
this.queue.pop();
} else {
this.queue[this.queue.length - 1].shift();
}
return this.queue;
}
}
проверено с несколькими массивами
let data = [
{ name: 'aj', pri: 1 },
{ name: 'jay', pri: 1 },
{ name: 'zulu', pri: 3 },
{ name: 'alpha', pri:5},
{ name: 'barvo', pri: 9 },
{ name: 'delta', pri: 9 },
{ name: 'charlie', pri: 9 },
];
let data2 = [
{ name: 'aj', pri: 9 },
{ name: 'jay', pri: 9 },
{ name: 'zulu', pri: 9 },
{ name: 'alpha', pri: 9 },
{ name: 'barvo', pri: 9 },
{ name: 'delta', pri: 9 },
{ name: 'charlie', pri: 9 },
];
let data3 = [
{ name: 'aj', pri: 0 },
{ name: 'jay', pri: 1 },
{ name: 'zulu', pri: 2 },
{ name: 'alpha', pri:3},
{ name: 'barvo', pri: 4 },
{ name: 'delta', pri: 5 },
{ name: 'charlie', pri: 6 },
];хорошо, это сработало, НО было ли это лучше, так же или хуже, чем куча?
Вы помните N? Я просил вас хорошо запомнить, что это был мой компромисс. Я определил разреженный массив, у меня были пустые ячейки с указателями, указывающими на неопределенное. Будем надеяться, что это того стоило!
глядя на мой код, я увидел O (1) для вставки и просмотра (победа для меня), но для извлечения я столкнулся с небольшой загвоздкой, и ее имя было SHIFT. в отличие от array.pop (который является O (1) просто должен сократить свойство длины) array.shift должен переиндексировать массив, что в моем случае, когда у меня есть вложенные массивы, означало O (b) (b = количество элементов в мой вложенный массив), что в крайнем случае, когда все имеет одинаковый приоритет, означало O (b = n). но это был крайний случай, поэтому я решил продолжать.
Время проверить мое решение на куче!
Я использовал jsperf.com для проверки своего фрагмента и был шокирован
Я работал на на 93 % медленнее, чем решение с кучей (вы можете поэкспериментировать с тестами @ https://jsperf.com/priorityqueueheapvssparsearray ). Я должен был знать почему или, по крайней мере, иметь какое-то представление (я потерял все тесты, а не только крайний случай, о котором я беспокоился).
поэтому, как хороший щенок, я копал глубже, пока не наткнулся на две вещи:
A. Эти надоедливые константы, которые мы игнорируем при расчете большого O, не могут быть полностью проигнорированы во время фактической реализации. Например, если я реализую тот же массив на языке, который в 3 раза медленнее, чем другой, тогда я получаю O (3n), что равно O (n), но при выполнении вы действительно получаете 3n, что может быть важно, если вы сравниваете фактические времена
B. статья 2010 года Особенности производительности массивов JavaScript, в которой они тестировали массивы в разных сценариях. У них было два независимых предположения о массивах JS:
- Они ведут себя как массивы C/Java. Итерация по содержимому и доступ к данным по индексу выполняются быстро — удаление записей и увеличение размера обходится дорого.
- Они ведут себя как объекты JavaScript. Итерация по содержимому и доступ к данным по индексу выполняются медленно — удаление записей и увеличение размера происходит быстро.
таковы были их выводы:
Оказывается, в зависимости от контекста оба предположения могут быть верными или неверными.
Normal array uses are almost always faster than objects, up to two orders of magnitude in some browser.
- Если вы сомневаетесь, предпочитайте массивы объектам.
- Никогда не рассматривайте массивы как объекты.
- Никогда не инициализируйте массивы в обратном порядке.
- Разреженные массивы ведут себя (с точки зрения производительности) как объекты.
- Необычное использование массива имеет свою цену.
две выделенные жирным шрифтом строки привлекли мое внимание. Мое решение с массивом, вероятно, было медленнее, потому что оно действовало как объект, а не как массив, и всевозможные константы влияли на preformance.
Ну, я спустился в кроличью нору, понюхал, вышел с другой стороны, лучше разбираясь в вещах. В целом, отличный опыт обучения, ничего лучше, чем упасть и испачкаться, чтобы узнать что-то новое.
