Bildlaufalgorithmus - Verbessert das Abrufen und Anzeigen von Daten

8

Ich möchte ein theoretisches Problem darlegen.

Angenommen, ich habe eine unendliche Schriftrolle, die wie hier beschrieben implementiert ist: https://medium.com/frontend-journeys/how-virtual-infinite-scrolling-works-239f7ee5aa58 . Es ist nichts Besonderes daran zu genügen, zu sagen, dass es sich um eine Datentabelle handelt, z. B. NxN, und der Benutzer kann wie eine Tabelle nach unten und rechts scrollen, und es werden nur die Daten in der aktuellen Ansicht plus minus a angezeigt Griff.

Nehmen wir nun an, dass das Abrufen und Anzeigen der Daten in dieser Ansicht ungefähr 10 ms dauert, mit einer Funktion wie:

get_data(start_col, end_col, start_row, end_row);

Dies wird sofort geladen, wenn Sie auf eine beliebige Stelle in der Bildlaufleiste klicken oder einen leichten Bildlauf durchführen, um die erforderlichen Daten zu rendern. Nehmen wir jedoch auch an, dass für jedes 'unvollendete Abrufereignis' die doppelte Zeit zum Rendern der erforderlichen Ansichtsdaten benötigt wird (aufgrund von Speicher, gc und einigen anderen Dingen). Wenn ich also langsam und absichtlich von links nach rechts scrolle, kann es sein, dass ich mehr als 100 Bildlaufereignisse generiere, die das Laden von Daten auslösen - zunächst gibt es keine spürbare Verzögerung von Null. Der Abruf erfolgt in weniger als 10 ms, aber bald dauert es 20 ms und dann 40 ms, und jetzt haben wir so etwas wie eine merkliche Verzögerung, bis er über eine Sekunde reicht, um die erforderlichen Daten zu laden. Außerdem können wir so etwas wie eine Entprellung / Verzögerung nicht verwenden.

Welche Überlegungen müsste ich berücksichtigen und wie würde ein Beispielalgorithmus aussehen, um dies zu erreichen? Hier ist ein Beispiel für die Benutzerinteraktion, die ich für die Daten haben möchte, unter der Annahme einer Tabelle mit 10000 x 10000 (obwohl Excel alle Daten gleichzeitig laden kann) - https://gyazo.com/0772f941f43f9d14f884b7afeac9f414 .

samuelbrody1249
quelle
Haben Sie nie mehr als eine Anfrage im Flug? Wenn der Benutzer einen Bildlauf durchführt, senden Sie eine Anfrage nur, wenn keine Anfrage ansteht. Wenn Sie eine Antwort auf die ausstehende Anforderung erhalten und sich der Bildlauf seit dem Senden der letzten Anforderung geändert hat, senden Sie eine neue Anforderung.
Ybungalobill
Ich frage mich, warum Sie die gegebene Antwort nicht akzeptiert haben. Können Sie erklären, warum und was Sie sich als Antwort erhoffen?
Trincot
@ Trincot - Ja, es ist eine großartige Antwort. Jemand hat meinen ursprünglichen Beitrag bearbeitet (siehe Änderungen), in dem ich sagte: "Ich werde ein Kopfgeld vergeben, weil dies eine theoretische Frage ist ..."
samuelbrody1249
1
Das beantwortet meine Frage nicht wirklich ...
Trincot
1
Eine weitere erwägenswerte Strategie ist das Puffern der Tabellendaten basierend auf der Richtung des Bildlaufs. Wenn der Benutzer beispielsweise nach unten scrollt, ruft er nicht nur das ab, was in der Ansicht angezeigt wird, sondern auch beispielsweise weitere 25 bis 50 Zeilen weiter unten, in Erwartung, dass der Benutzer weiter nach unten scrollt. Zusätzlich (und ich denke, Josef spielt darauf an), bevor Ihre Datenansicht die gepufferten Daten verbraucht, puffern Sie mehr Daten (so dass Sie immer 25-50 Zeilen gepuffert haben), während der Benutzer scrollt. Diese zusätzlichen Daten werden wahrscheinlich wenig zu dem Overhead beitragen, der bereits mit dem Roundtrip des Abrufs verbunden ist ...
Jon Trent,

Antworten:

3

Ich denke, Sie sollten bei keinem Scroll-Event eine Anfrage senden. Nur wenn der Benutzer mit dieser Schriftrolle das Ende der Schriftrolle erreicht.

if(e.target.scrollHeight - e.target.offsetHeight === 0) {
    // the element reach the end of vertical scroll
}
if(e.target.scrollWidth - e.target.offsetWidth === 0) {
   // the element reach the end of horizontal scroll
}

Sie können auch eine Breite angeben, die als nah genug definiert wird, um neue Daten abzurufen (z e.target.scrollHeight - e.target.offsetHeight <= 150 ).

Josef Tukachinsky
quelle
1

Theorie und Praxis: In der Theorie gibt es keinen Unterschied zwischen Theorie und Praxis, in der Praxis jedoch.

  • Theorie: Alles ist klar, aber nichts funktioniert;
  • Übung: Alles funktioniert, aber nichts ist klar;
  • Manchmal trifft Theorie auf Praxis: Nichts funktioniert und nichts ist klar.

Manchmal ist der beste Ansatz ein Prototyp, und als ich das Problem interessant fand, verbrachte ich ein wenig Zeit damit, einen zu kochen, obwohl er als Prototyp zugegebenermaßen viele Warzen hat ...

Kurz gesagt, die einfachste Lösung zur Begrenzung eines Rückstands bei Datenabrufen scheint darin zu bestehen, einfach den Mutex eines armen Mannes innerhalb der Routine einzurichten , die das Abrufen durchführt. (Im folgenden Codebeispiel lautet die simulierte Abruffunktion simulateFetchOfData.) Beim Mutex wird eine Variable außerhalb des Funktionsumfangs so eingerichtet, dass falseder Abruf zur Verwendung geöffnet ist und trueder Abruf gerade ausgeführt wird.

Das heißt, wenn der Benutzer den horizontalen oder vertikalen Schieberegler anpasst, um einen Datenabruf zu initiieren, prüft die Funktion, die die Daten abruft, zuerst, ob die globale Variable mutexwahr ist (dh ein Abruf ist bereits im Gange), und wird in diesem Fall einfach beendet . Wenn dies mutexnicht der Fall ist, wird der Wert mutexauf true gesetzt und der Abruf fortgesetzt. Und natürlich am Ende der Abruffunktion,mutex auf false gesetzt, so dass das nächste Benutzereingabeereignis dann die Mutexprüfung vorne durchläuft und einen weiteren Abruf durchführt ...

Ein paar Anmerkungen zum Prototyp.

  • Innerhalb der simulateFetchOfDataFunktion ist der Schlaf (100) als Versprechen konfiguriert, das die Verzögerung beim Abrufen der Daten simuliert. Dies ist mit etwas Protokollierung an der Konsole eingeklemmt. Wenn Sie die Mutex-Prüfung entfernen, werden Sie bei geöffneter Konsole feststellen, dass beim Verschieben der Schieberegler viele Instanzen vonsimulateFetchOfData initiiert und in Spannung gesetzt werden, während der Mutex-Prüfung auf den Ruhezustand (dh den simulierten Datenabruf) wartet An Ort und Stelle wird jeweils nur eine Instanz initiiert.
  • Die Ruhezeit kann angepasst werden, um eine größere Netzwerk- oder Datenbanklatenz zu simulieren, sodass Sie ein Gefühl für die Benutzererfahrung bekommen. Zum Beispiel haben Netzwerke, auf denen ich bin, eine Latenz von 90 ms für Kommunikation in den kontinentalen USA.
  • Eine andere bemerkenswerte ist, dass beim Beenden eines Abrufs und nach dem Zurücksetzen mutex auf false eine Überprüfung durchgeführt wird, um festzustellen, ob die horizontalen und vertikalen Bildlaufwerte ausgerichtet sind. Wenn nicht, wird ein weiterer Abruf eingeleitet. Dies stellt sicher, dass trotz einer Anzahl von Bildlaufereignissen, die möglicherweise nicht ausgelöst werden, weil der Abruf beschäftigt ist, mindestens die endgültigen Bildlaufwerte durch Auslösen eines endgültigen Abrufs adressiert werden.
  • Die simulierten Zellendaten sind einfach ein Zeichenfolgenwert der Zeilen-Strich-Spalten-Nummer. Beispielsweise gibt "555-333" Zeile 555, Spalte 333 an.
  • Ein spärliches Array mit dem Namen bufferwird verwendet, um die "abgerufenen" Daten zu speichern. Wenn Sie es in der Konsole untersuchen, werden viele "leere x XXXX" -Einträge angezeigt. Die simulateFetchOfDataFunktion ist so eingerichtet, dass, wenn die Daten bereits gespeichert sind buffer, kein "Abrufen" durchgeführt wird.

(Um den Prototyp anzuzeigen, kopieren Sie einfach den gesamten Code und fügen Sie ihn in eine neue Textdatei ein, benennen Sie ihn in ".html" um und öffnen Sie ihn in einem Browser. BEARBEITEN: Wurde auf Chrome und Edge getestet.)

<html><head>

<script>

function initialize() {

  window.rowCount = 10000;
  window.colCount = 5000;

  window.buffer = [];

  window.rowHeight = Array( rowCount ).fill( 25 );  // 20px high rows 
  window.colWidth = Array( colCount ).fill( 70 );  // 70px wide columns 

  var cellAreaCells = { row: 0, col: 0, height: 0, width: 0 };

  window.contentGridCss = [ ...document.styleSheets[ 0 ].rules ].find( rule => rule.selectorText === '.content-grid' );

  window.cellArea = document.getElementById( 'cells' );

  // Horizontal slider will indicate the left most column.
  window.hslider = document.getElementById( 'hslider' );
  hslider.min = 0;
  hslider.max = colCount;
  hslider.oninput = ( event ) => {
    updateCells();
  }

  // Vertical slider will indicate the top most row.
  window.vslider = document.getElementById( 'vslider' );
  vslider.max = 0;
  vslider.min = -rowCount;
  vslider.oninput = ( event ) => {
    updateCells();
  }

  function updateCells() {
    // Force a recalc of the cell height and width...
    simulateFetchOfData( cellArea, cellAreaCells, { row: -parseInt( vslider.value ), col: parseInt( hslider.value ) } );
  }

  window.mutex = false;
  window.lastSkippedRange = null;

  window.addEventListener( 'resize', () => {
    //cellAreaCells.height = 0;
    //cellAreaCells.width = 0;
    cellArea.innerHTML = '';
    contentGridCss.style[ "grid-template-rows" ] = "0px";
    contentGridCss.style[ "grid-template-columns" ] = "0px";

    window.initCellAreaSize = { height: document.getElementById( 'cellContainer' ).clientHeight, width: document.getElementById( 'cellContainer' ).clientWidth };
    updateCells();
  } );
  window.dispatchEvent( new Event( 'resize' ) );

}

function sleep( ms ) {
  return new Promise(resolve => setTimeout( resolve, ms ));
}

async function simulateFetchOfData( cellArea, curRange, newRange ) {

  //
  // Global var "mutex" is true if this routine is underway.
  // If so, subsequent calls from the sliders will be ignored
  // until the current process is complete.  Also, if the process
  // is underway, capture the last skipped call so that when the
  // current finishes, we can ensure that the cells align with the
  // settled scroll values.
  //
  if ( window.mutex ) {
    lastSkippedRange = newRange;
    return;
  }
  window.mutex = true;
  //
  // The cellArea width and height in pixels will tell us how much
  // room we have to fill.
  //
  // row and col is target top/left cell in the cellArea...
  //

  newRange.height = 0;
  let rowPixelTotal = 0;
  while ( newRange.row + newRange.height < rowCount && rowPixelTotal < initCellAreaSize.height ) {
    rowPixelTotal += rowHeight[ newRange.row + newRange.height ];
    newRange.height++;
  }

  newRange.width = 0;
  let colPixelTotal = 0;
  while ( newRange.col + newRange.width < colCount && colPixelTotal < initCellAreaSize.width ) {
    colPixelTotal += colWidth[ newRange.col + newRange.width ];
    newRange.width++;
  }

  //
  // Now the range to acquire is newRange. First, check if this data 
  // is already available, and if not, fetch the data.
  //

  function isFilled( buffer, range ) {
    for ( let r = range.row; r < range.row + range.height; r++ ) {
      for ( let c = range.col; c < range.col + range.width; c++ ) {
        if ( buffer[ r ] == null || buffer[ r ][ c ] == null) {
          return false;
        }
      }
    }
    return true;
  }

  if ( !isFilled( buffer, newRange ) ) {
    // fetch data!
    for ( let r = newRange.row; r < newRange.row + newRange.height; r++ ) {  
      buffer[ r ] = [];
      for ( let c = newRange.col; c < newRange.col + newRange.width; c++ ) {
        buffer[ r ][ c ] = `${r}-${c} data`;
      }
    }
    console.log( 'Before sleep' );
    await sleep(100);
    console.log( 'After sleep' );
  }

  //
  // Now that we have the data, let's load it into the cellArea.
  //

  gridRowSpec = '';
  for ( let r = newRange.row; r < newRange.row + newRange.height; r++ ) {
    gridRowSpec += rowHeight[ r ] + 'px ';
  }

  gridColumnSpec = '';
  for ( let c = newRange.col; c < newRange.col + newRange.width; c++ ) {
    gridColumnSpec += colWidth[ c ] + 'px ';
  }

  contentGridCss.style[ "grid-template-rows" ] = gridRowSpec;
  contentGridCss.style[ "grid-template-columns" ] = gridColumnSpec;

  cellArea.innerHTML = '';

  for ( let r = newRange.row; r < newRange.row + newRange.height; r++ ) {  
    for ( let c = newRange.col; c < newRange.col + newRange.width; c++ ) {
      let div = document.createElement( 'DIV' );
      div.innerText = buffer[ r ][ c ];
      cellArea.appendChild( div );
    }
  }

  //
  // Let's update the reference to the current range viewed and clear the mutex.
  //
  curRange = newRange;

  window.mutex = false;

  //
  // One final step.  Check to see if the last skipped call to perform an update
  // matches with the current scroll bars.  If not, let's align the cells with the
  // scroll values.
  //
  if ( lastSkippedRange ) {
    if ( !( lastSkippedRange.row === newRange.row && lastSkippedRange.col === newRange.col ) ) {
      lastSkippedRange = null;
      hslider.dispatchEvent( new Event( 'input' ) );
    } else {
      lastSkippedRange = null;
    }
  }
}

</script>

<style>

/*

".range-slider" adapted from... https://codepen.io/ATC-test/pen/myPNqW

See https://www.w3schools.com/howto/howto_js_rangeslider.asp for alternatives.

*/

.range-slider-horizontal {
  width: 100%;
  height: 20px;
}

.range-slider-vertical {
  width: 20px;
  height: 100%;
  writing-mode: bt-lr; /* IE */
  -webkit-appearance: slider-vertical;
}

/* grid container... see https://www.w3schools.com/css/css_grid.asp */

.grid-container {

  display: grid;
  width: 95%;
  height: 95%;

  padding: 0px;
  grid-gap: 2px;
  grid-template-areas:
    topLeft column  topRight
    row     cells   vslider
    botLeft hslider botRight;
  grid-template-columns: 50px 95% 27px;
  grid-template-rows: 20px 95% 27px;
}

.grid-container > div {
  border: 1px solid black;
}

.grid-topLeft {
  grid-area: topLeft;
}

.grid-column {
  grid-area: column;
}

.grid-topRight {
  grid-area: topRight;
}

.grid-row {
  grid-area: row;
}

.grid-cells {
  grid-area: cells;
}

.grid-vslider {
  grid-area: vslider;
}

.grid-botLeft {
  grid-area: botLeft;
}

.grid-hslider {
  grid-area: hslider;
}

.grid-botRight {
  grid-area: botRight;
}

/* Adapted from... https://medium.com/evodeck/responsive-data-tables-with-css-grid-3c58ecf04723 */

.content-grid {
  display: grid;
  overflow: hidden;
  grid-template-rows: 0px;  /* Set later by simulateFetchOfData */
  grid-template-columns: 0px;  /* Set later by simulateFetchOfData */
  border-top: 1px solid black;
  border-right: 1px solid black;
}

.content-grid > div {
  overflow: hidden;
  white-space: nowrap;
  border-left: 1px solid black;
  border-bottom: 1px solid black;  
}
</style>


</head><body onload='initialize()'>

<div class='grid-container'>
  <div class='topLeft'> TL </div>
  <div class='column' id='columns'> column </div>
  <div class='topRight'> TR </div>
  <div class='row' id = 'rows'> row </div>
  <div class='cells' id='cellContainer'>
    <div class='content-grid' id='cells'>
      Cells...
    </div>
  </div>
  <div class='vslider'> <input id="vslider" type="range" class="range-slider-vertical" step="1" value="0" min="0" max="0"> </div>
  <div class='botLeft'> BL </div>
  <div class='hslider'> <input id="hslider" type="range" class="range-slider-horizontal" step="1" value="0" min="0" max="0"> </div>
  <div class='botRight'> BR </div>
</div>

</body></html>

Auch dies ist ein Prototyp, um ein Mittel zur Begrenzung eines Rückstands unnötiger Datenanrufe zu beweisen. Wenn dies für Produktionszwecke umgestaltet werden soll, müssen viele Bereiche adressiert werden, einschließlich: 1) Reduzierung der Nutzung des globalen variablen Raums; 2) Hinzufügen von Zeilen- und Spaltenbeschriftungen; 3) Hinzufügen von Schaltflächen zu den Schiebereglern zum Scrollen einzelner Zeilen oder Spalten; 4) möglicherweise verwandte Daten puffern, wenn Datenberechnungen erforderlich sind; 5) etc ...

Jon Trent
quelle
Vielen Dank für diese großartige Antwort und nehmen Sie sich Zeit für diese Antwort.
samuelbrody1249
0

Es gibt einige Dinge, die getan werden könnten. Ich sehe es als eine zweistufige Zwischenschicht zwischen der Datenanforderungsprozedur und dem Benutzer-Scroll-Ereignis.

1. Verzögern Sie die Verarbeitung von Bildlaufereignissen

Sie haben Recht, Debounce ist nicht unser Freund in den Scroll-bezogenen Fragen. Es gibt jedoch den richtigen Weg, um die Anzahl der Schüsse zu verringern.

Verwenden Sie die gedrosselte Version des Scroll-Ereignishandlers, die höchstens einmal pro festem Intervall aufgerufen wird. Sie können Lodash-Gas verwenden oder eine eigene Version [ 1 ], [ 2 ], [ 3 ] implementieren . Stellen Sie 40 - 100 ms als Intervallwert ein. Sie müssen auch die trailingOption festlegen, damit das allerletzte Bildlaufereignis unabhängig vom Timerintervall verarbeitet wird.

2. Intelligenter Datenfluss

Wenn der Scroll-Ereignishandler aufgerufen wird, sollte der Datenanforderungsprozess initiiert werden. Wie Sie bereits erwähnt haben, kann es bei jedem Scroll-Ereignis (auch wenn wir mit dem Drosseln fertig sind) zu Zeitverzögerungen kommen. Möglicherweise gibt es einige gängige Strategien: 1) Fordern Sie die Daten nicht an, wenn eine andere ausstehende Anforderung vorliegt. 2) die Daten nicht mehr als einmal pro Intervall anfordern; 3) vorherige ausstehende Anfrage abbrechen.

Der erste und der zweite Ansatz sind nicht mehr als das Entprellen und Drosseln auf Datenflussebene. Das Entprellen kann mit minimalem Aufwand mit nur einer Bedingung implementiert werden, bevor die Anforderung + eine zusätzliche Anforderung am Ende initiiert wird. Aber ich glaube, dass Gas aus UX-Sicht angemessener ist. Hier müssen Sie eine Logik bereitstellen und die trailingOption nicht vergessen, wie sie im Spiel sein sollte.

Der letzte Ansatz (die Stornierung von Anforderungen) ist ebenfalls UX-freundlich, aber weniger vorsichtig als der drosselnde. Sie starten die Anforderung trotzdem, werfen aber das Ergebnis weg, wenn nach dieser Anforderung eine andere Anforderung gestartet wurde. Sie können auch versuchen, die Anforderung abzubrechen, wenn Sie verwenden fetch.

Meiner Meinung nach besteht die beste Option darin, die Strategien (2) und (3) zu kombinieren. Sie fordern die Daten also nur an, wenn seit dem Initiieren der vorherigen Anfrage ein festes Zeitintervall verstrichen ist, UND Sie brechen die Anfrage ab, wenn danach eine andere initiiert wurde .

Dhilt
quelle
0

Es gibt keinen spezifischen Algorithmus, der diese Frage beantwortet, aber um keine Verzögerung aufzubauen, müssen Sie zwei Dinge sicherstellen:

1. Keine Speicherlecks

Stellen Sie unbedingt sicher, dass nichts in Ihrer App neue Instanzen von Objekten, Klassen, Arrays usw. erstellt. Der Speicher sollte nach 10 Sekunden Scrollen derselbe sein wie nach 60 Sekunden usw. Sie können Datenstrukturen vorab zuweisen, wenn Sie müssen (einschließlich Arrays) und sie dann wiederverwenden:

2. Ständige Wiederverwendung von Datenstrukturen

Dies ist bei unendlichen Bildlaufseiten üblich. In einer unendlichen Bildlaufgalerie, in der höchstens 30 Bilder gleichzeitig auf dem Bildschirm angezeigt werden, werden möglicherweise nur 30-40 <img>Elemente erstellt. Diese werden dann beim Scrollen des Benutzers verwendet und wiederverwendet, sodass keine neuen HTML-Elemente erstellt (oder zerstört und daher mit Müll gesammelt werden müssen). Stattdessen erhalten diese Bilder neue Quell-URLs und neue Positionen, und der Benutzer kann weiter scrollen, aber (ohne dass sie es wissen) sehen sie immer wieder dieselben DOM-Elemente.

Wenn Sie Canvas verwenden, werden Sie keine DOM-Elemente verwenden, um diese Daten anzuzeigen, aber die Theorie ist dieselbe, nur die Datenstrukturen sind Ihre eigenen.

Simon Sarris
quelle