Indeksowanie (utrzymywanie indeksów) w tablicy sprawia, że Array.prototype.shift i Array.prototype.unshift o (n) zamiast o (1).

Jeśli jednak po prostu chcemy użyć POP () / Push () / Shift () i UNSSIFT () i nigdy nie używać wskaźników do wyszukiwania, czy istnieje sposób na wdrożenie tablicy JavaScript, która pomija indeksowanie?

Nie mogę wymyślić sposobu na to. Jedynym sposobem, w jaki mogę myśleć o tym, że będzie to z tablicami i przy użyciu POP () / Push () (ponieważ są O (1)) ... ale nawet z wieloma tablicami, nie jestem pewien, czy jest to możliwe.

Patrząc, aby wykonać tę listę połączeń, jeśli to możliwe. Wdrożyłem rozwiązanie do tego z podwójnie połączoną listą, ale zastanawiając się, czy możliwe jest wykonanie tego w / o listę połączoną.

Cel końcowy: próbuje utworzyć kolejkę FIFO, gdzie wszystkie operacje są w stałym czasie, bez użycia listy połączonej.

2
Alexander Mills 5 czerwiec 2018, 00:46

3 odpowiedzi

Najlepsza odpowiedź

Co powiesz na ES2015 {x0}} Wskaźnik liczbami całkowitymi?

Zadzwońmy na mapę myFIFOMap.

Utrzymujesz first i last członek integera w ramach klasy FIFO. Rozpocznij je zarówno w zero.

Za każdym razem, gdy chcesz push() do kolejki FIFO, zadzwonisz myFIFOMap.set(++last,item). I pop() wygląda jak:

const item = myFIFOMap.get(first); 
myFIFOMap.delete(first++); 
return item;

Powinien być O(1), aby pchać lub pop.

Nie zapomnij sprawdzić warunków brzegowych (np. Nie pozwól im pop(), gdy first===last).

Biorąc pod uwagę, że JavaScript faktycznie korzysta z podwójnego precyzyjnego punktu zmiennego, powinieneś być w stanie uruchomić ~ 2 ^ 53 Obiekty przez FIFO, zanim będziesz miał problemy z precyzją całkowitą. Więc jeśli prowadzisz 10 000 przedmiotów za pośrednictwem FIFO na sekundę, to powinno być dobre przez około 28 000 lat czasu pracy.

1
SomeCallMeTim 4 czerwiec 2018, 22:34

Idąc z odpowiedzią @somecallmetim, które myślę, jest na właściwym miejscu, mam to:

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();
  }

}

Takeays :

  1. Okazuje się, możesz zadzwonić getByIndex(), ponieważ wskazuje na sugestię Tim.

  2. Korzystanie z mapy jest zaskakująco ~ 10% szybciej niż Posto, prawdopodobnie tylko dlatego, że z Ujso liczby całkowite muszą zostać przekonwertowane na ciągi do wyszukiwania.

  3. Wdrożenie mapy wynosi około 20% szybsze niż podwójnie połączona lista, więc lista podwójnie połączona nie jest tak wolniejsza. Prawdopodobnie jest to przeważnie, ponieważ musimy utworzyć obiekt kontenerowy z następnym / preved wskaźnikami dla każdego elementu w kolejce, podczas gdy w przypadku wdrożenia listy nie połączonej możemy wstawić prymitywy w kolejce itp.

  4. Lista podwójnie połączona pozwala nam usunąć / wkładać elementy z środka kolejki w czasie stałego; Nie możemy zrobić tego samego dzięki niewłaściwym wdrożeniu listy, jak jest.

  5. Wszystkie powyższe są rzędami wielkości bardziej występują niż zwykła tablica podczas pracy na tablicy z więcej niż 10 000 elementów.

Mam tu kilka stałych implementacji kolejki czasu: https://github.com/oresoftware/linked-Sue

Tim miał dobrą sugestię, aby zdobyć GetByindex () łatwiejsze w użyciu - możemy to zrobić:

  getByIndex(v: number) {

    if(!Number.isInteger(v)){
      throw new Error('Argument must be an integer.');
    }

    return this.lookup.get(v + this.first);
  }

W ten sposób uzyskanie piątego elementu w kolejce, wszystko, co musimy zrobić, to:

getByIndex(4);
0
Alexander Mills 7 czerwiec 2018, 23:29

Jeśli przechowywane dane są prymitywne (ciąg, liczby całkowite, pływaki lub kombinacje prymitywy), można użyć javascript Typedarray, rzuć go do odpowiedniej wpisanej tablicy widoku, załaduj go z danymi, a następnie samodzielnie śledzić offset (y).

W twoim przykładzie, pop, shift i unshift może być wdrażana przez zwiększanie / zmniejszanie indeksu całkowitego. push jest trudniejsze, ponieważ typedarray jest stałym rozmiarem: Jeśli arraybuffer jest pełny, tylko dwie opcje mają obcięcie danych lub przydzielić nową tablicę wpisaną, ponieważ JS nie może przechowywać wskaźników.

Jeśli przechowujesz jednorodne obiekty (mają te same właściwości), możesz zapisać każdą wartość w typedarray za pomocą różnych widoków i przesunięć do naśladowania struktury C (patrz Przykład MDN), a następnie użyj funkcji JS, aby serializować / powiadomić je Z typedarraya, w zasadzie konwertowanie danych z reprezentacji binarnej, w pełnoprawny obiekt JS.

0
ouni 4 czerwiec 2018, 22:10