Создайте структуру массива в JavaScript, в которой отсутствует индексирование
Индексирование (ведение индексов) в массиве делает Array.prototype.shift а также Array.prototype.unshift O(N) вместо O(1).
Однако, если мы просто хотим использовать pop() / push() / shift() и unshift () и никогда не использовать индексы для поиска, есть ли способ реализовать массив JavaScript, в котором отсутствует индексация?
Я не могу придумать, как это сделать. Единственный способ сделать это - использовать массивы и использовать только pop () / push () (так как это O (1))... но даже с несколькими массивами, не уверен, возможно ли это.
Хотите сделать это без связанного списка, если это возможно. Я реализовал решение для этого с помощью двусвязного списка, но мне было интересно, возможно ли это сделать без связанного списка.
Конечная цель: попытка создать очередь FIFO, в которой все операции выполняются в постоянном времени, без использования связанного списка.
3 ответа
Как насчет ES2015 Map что вы индексируете целыми числами?
Назовем карту myFIFOMap,
Вы держите first а также last целочисленный член как часть вашего класса FIFO. Начните их обоих с нуля.
Каждый раз, когда вы хотите push() в свою очередь FIFO, вы звоните myFIFOMap.set(++last,item), А также pop() выглядит примерно так:
const item = myFIFOMap.get(first);
myFIFOMap.delete(first++);
return item;
Должно быть O(1) нажать или хлопнуть
Не забудьте проверить граничные условия (например, не позволяйте им pop() когда first===last).
Учитывая, что JavaScript на самом деле использует плавающую точку двойной точности, вы должны иметь возможность запустить ~2^53 объектов через FIFO, прежде чем возникнут проблемы с целочисленной точностью. Таким образом, если вы выполняете 10000 элементов через FIFO в секунду, это должно быть хорошо в течение примерно 28 000 лет работы.
Если данные, которые вы храните, являются примитивными (строка, целые числа, числа с плавающей запятой или комбинации примитивов), вы можете использовать JavaScript TypedArray, привести его к соответствующему типизированному представлению массива, загрузить его с данными и затем отслеживать смещение (с) себя.
В вашем примере pop, shift, а также unshift все может быть реализовано путем увеличения / уменьшения целочисленного индекса. push является более сложным, потому что TypedArray имеет фиксированный размер: если ArrayBuffer заполнен, единственными двумя вариантами являются усечение данных или выделение нового типизированного массива, поскольку JS не может хранить указатели.
Если вы храните однородные объекты (они имеют одинаковые свойства), вы можете сохранить каждое значение в TypedArray, используя различные представления и смещения, чтобы имитировать структуру C (см. Пример MDN), а затем использовать функцию JS для сериализации / десериализации их из TypedArray, в основном преобразуя данные из двоичного представления, в полноценный объект JS.
Продолжая с ответом @SomeCallMeTim, который, я думаю, находится на правильном пути, у меня есть это:
export class Queue {
lookup = new Map<number, any>();
first = 0;
last = 0;
length = 0;
elementExists = false; // when first === last, and item exists there
peek() {
return this.lookup.get(this.first);
}
getByIndex(v: number) {
return this.lookup.get(v);
}
getLength() {
return this.length;
}
pop() {
const last = this.last;
if (this.elementExists && this.first === this.last) {
this.length--;
this.elementExists = false;
}
else if (this.last > this.first) {
this.length--;
this.last--;
}
const v = this.lookup.get(last);
this.lookup.delete(last);
return v;
}
shift() {
const first = this.first;
if (this.elementExists && this.first === this.last) {
this.length--;
this.elementExists = false;
}
else if (this.first < this.last) {
this.length--;
this.first++;
}
const v = this.lookup.get(first);
this.lookup.delete(first);
return v;
}
push(v: any) {
this.length++;
if (this.elementExists && this.first === this.last) {
this.last++;
}
else if (this.first === this.last) {
this.elementExists = true;
}
else {
this.last++;
}
return this.lookup.set(this.last, v);
}
enq(v: any) {
return this.push.apply(this, arguments);
}
enqueue(v: any) {
return this.push.apply(this, arguments);
}
deq() {
return this.shift.apply(this, arguments);
}
dequeue() {
return this.shift.apply(this, arguments);
}
unshift(v: any) {
this.length++;
if (this.elementExists && this.first === this.last) {
this.first--;
}
else if (this.first === this.last) {
this.elementExists = true;
}
else {
this.first--;
}
return this.lookup.set(this.first, v);
}
addToFront(v: any){
return this.unshift.apply(this,arguments);
}
removeAll() {
return this.clear.apply(this, arguments);
}
clear(): void {
this.length = 0;
this.elementExists = false;
this.first = 0;
this.last = 0;
this.lookup.clear();
}
}
вынос:
оказывается, можно позвонить
getByIndex(), как указывает предложение Тима.Использование Map на удивление примерно на 10% быстрее, чем POJSO, возможно, только потому, что с POJSO целые числа должны быть преобразованы в строки для поиска.
Реализация Map примерно на 20% быстрее, чем двусвязный список, поэтому двусвязный список не намного медленнее. Вероятно, это медленнее, в основном потому, что мы должны создать контейнерный объект с указателями next/prev для каждого элемента в очереди, тогда как при реализации несвязанного списка мы можем вставить примитивы в очередь и т. Д.
Двусвязный список позволяет нам удалять / вставлять элементы из середины очереди в постоянное время; мы не можем сделать то же самое с реализацией несвязанного списка, как есть.
Все вышеперечисленное на несколько порядков более производительно, чем обычный массив, при работе с массивом, содержащим более 10000 элементов или около того.
У меня есть несколько реализаций очереди с постоянным временем здесь: https://github.com/ORESoftware/linked-queue
У Тима было хорошее предложение, чтобы сделать getByIndex() проще в использовании - мы можем сделать это:
getByIndex(v: number) {
if(!Number.isInteger(v)){
throw new Error('Argument must be an integer.');
}
return this.lookup.get(v + this.first);
}
таким образом, чтобы получить 5-й элемент в очереди, все, что нам нужно сделать, это:
getByIndex(4);