Algoritmo de desplazamiento: mejora la recuperación y visualización de datos

Me gustaría plantear un problema teórico.

Supongamos que tengo un desplazamiento infinito, implementado algo como lo descrito aquí: https://medium.com/frontend-journeys/how-virtual-infinite-scrolling-works-239f7ee5aa58 . No tiene nada de lujos, basta con decir que es una tabla de datos, digamos NxN, y el usuario puede desplazarse hacia abajo y hacia la derecha, como una hoja de cálculo, y solo mostrará los datos en la vista actual más menos un encargarse de.

Ahora, digamos también que se necesitan aproximadamente 10 ms para "buscar y mostrar" los datos en esa vista, con una función como:

get_data(start_col, end_col, start_row, end_row);

Esto se carga instantáneamente al hacer clic en algún lugar de la barra de desplazamiento o al hacer un 'ligero desplazamiento' para representar los datos necesarios. Sin embargo, supongamos también que para cada 'evento de recuperación no terminado', se tarda el doble de tiempo en procesar los datos de vista necesarios (debido a la memoria, gc y algunas otras cosas). Entonces, si me desplazo de izquierda a derecha de una manera lenta y deliberada, podría generar más de 100 eventos de desplazamiento que desencadenarían la carga de datos; al principio, no hay un retraso notable. La recuperación ocurre en menos de 10 ms, pero pronto comienza a tardar 20 ms, y luego 40 ms, y ahora tenemos algo así como un retraso notable, hasta que llegue más de un segundo para cargar los datos necesarios. Además, no podemos usar algo como un rebote / retraso,

¿Qué consideraciones necesitaría tener en cuenta y cómo sería un algoritmo de muestra para lograr esto? Aquí hay un ejemplo de la interacción del usuario que me gustaría tener en los datos, suponiendo una hoja de cálculo de 10000 x 10000 (aunque Excel puede cargar todos los datos a la vez): https://gyazo.com/0772f941f43f9d14f884b7afeac9f414 .

Creo que no debe enviar una solicitud en ningún evento de desplazamiento. solo si con este desplazamiento el usuario llega al final del desplazamiento.

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
}

También puede especificar un ancho que se definirá como lo suficientemente cerca como para obtener datos nuevos (ei e.target.scrollHeight - e.target.offsetHeight <= 150)

Teoría y práctica: en teoría no hay diferencia entre teoría y práctica, pero en la práctica sí.

• Teoría: todo está claro, pero nada funciona;
• Práctica: todo funciona, pero nada está claro;
• A veces la teoría se encuentra con la práctica: nada funciona y nada está claro.

A veces, el mejor enfoque es un prototipo, y al encontrar el problema interesante, pasé un poco de tiempo cocinando uno, aunque como prototipo tiene muchas verrugas ...

En resumen, la solución más fácil para limitar la acumulación de datos acumulados parece ser simplemente configurar el mutex de un pobre dentro de la rutina que realiza la recuperación. (En el ejemplo de código a continuación, la función de recuperación simulada es simulateFetchOfData). El mutex implica establecer una variable fuera del alcance de la función, de modo que si falsela recuperación está abierta para su uso y si truela recuperación está actualmente en curso.

Es decir, cuando el usuario ajusta el control deslizante horizontal o vertical para iniciar una búsqueda de datos, la función que busca los datos primero verifica si la variable global mutexes verdadera (es decir, una búsqueda ya está en curso), y si es así, simplemente sale . Si mutexno es verdadero, se establece mutexen verdadero y luego continúa realizando la búsqueda. Y, por supuesto, al final de la función de recuperación, mutexse establece en falso, de modo que el próximo evento de entrada del usuario pasará por el control mutex por adelantado y realizará otra recuperación ...

Un par de notas sobre el prototipo.

• Dentro de la simulateFetchOfDatafunción, hay suspensión (100) configurada como una Promesa que simula el retraso en la recuperación de los datos. Esto se intercala con algunos registros en la consola. Si elimina la verificación de mutex, verá con la consola abierta que, mientras mueve los controles deslizantes, simulateFetchOfDatase inician muchas instancias y se ponen en suspenso esperando el sueño (es decir, la búsqueda simulada de datos) para resolver, mientras que con la verificación de mutex en su lugar, solo se inicia una instancia a la vez.
• El tiempo de suspensión se puede ajustar para simular una mayor latencia de la red o la base de datos, de modo que pueda tener una idea de la experiencia del usuario. Por ejemplo, las redes en las que tengo experiencia tienen una latencia de 90 ms para las comunicaciones en los Estados Unidos continentales.
• Otro aspecto notable es que al finalizar una búsqueda y después de restablecer mutexa falso, se realiza una verificación para determinar si los valores de desplazamiento horizontal y vertical están alineados. Si no, se inicia otra búsqueda. Esto garantiza que, a pesar de que varios eventos de desplazamiento posiblemente no se activen debido a que la búsqueda está ocupada, como mínimo los valores de desplazamiento finales se abordan activando una búsqueda final.
• Los datos de celda simulados son simplemente un valor de cadena de número de fila-guión-columna. Por ejemplo, "555-333" indica la fila 555 columna 333.
• Una matriz dispersa llamada bufferse utiliza para contener los datos "recuperados". Examinarlo en la consola revelará muchas entradas "vacías x XXXX". La simulateFetchOfDatafunción está configurada de tal manera que si los datos ya están almacenados buffer, no se realiza ninguna "búsqueda".

(Para ver el prototipo, simplemente copie y pegue todo el código en un nuevo archivo de texto, cambie el nombre a ".html" y ábralo en un navegador. EDITAR: Se ha probado en Chrome y Edge).

<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>

Una vez más, este es un prototipo para demostrar un medio para limitar una acumulación de llamadas de datos innecesarias. Si esto se refactorizara para fines de producción, muchas áreas requerirán abordaje, incluyendo: 1) reducir el uso del espacio variable global; 2) agregar etiquetas de fila y columna; 3) agregar botones a los controles deslizantes para desplazarse por filas o columnas individuales; 4) posiblemente almacenando datos relacionados con el búfer, si se requieren cálculos de datos; 5) etc.

Hay algunas cosas que podrían hacerse. Lo veo como una capa intermedia de dos niveles colocada entre el procedimiento de solicitud de datos y el evento de desplazamiento del usuario.

1. Retraso en el procesamiento del evento de desplazamiento

Tienes razón, debounce no es nuestro amigo en los problemas relacionados con el desplazamiento. Pero existe la manera correcta de reducir el número de disparos.

Utilice la versión acelerada del controlador de eventos de desplazamiento que se invocará como máximo una vez por cada intervalo fijo. Puede usar el acelerador lodash o implementar su propia versión [ 1 ], [ 2 ], [ 3 ]. Establezca 40 - 100 ms como un valor de intervalo. También deberá establecer la trailingopción para que se procese el último evento de desplazamiento independientemente del intervalo del temporizador.

2. Flujo de datos inteligente

Cuando se invoca el controlador de eventos de desplazamiento, se debe iniciar el proceso de solicitud de datos. Como mencionó, hacerlo cada vez que ocurre un evento de desplazamiento (incluso si hemos terminado con la aceleración) puede causar retrasos en el tiempo. Puede haber algunas estrategias comunes: 1) no solicite los datos si hay otra solicitud pendiente; 2) solicitar los datos no más de una vez por algún intervalo; 3) cancelar la solicitud pendiente anterior.

El primer y el segundo enfoque no son más que el rebote y la aceleración en el nivel del flujo de datos. El rebote podría implementarse con un esfuerzo mínimo con una sola condición antes de iniciar la solicitud + una solicitud adicional al final. Pero creo que el acelerador es más apropiado desde el punto de vista de UX. Aquí deberás proporcionar algo de lógica, y no te olvides de la trailingopción, ya que debería estar en el juego.

El último enfoque (la cancelación de la solicitud) también es compatible con UX pero menos cuidadoso que el de estrangulamiento. De todos modos, inicia la solicitud, pero descarta su resultado si se inició otra solicitud después de esta. También puede intentar cancelar la solicitud si está utilizando fetch.

En mi opinión, la mejor opción sería combinar las estrategias (2) y (3), por lo que solicita los datos solo si ha transcurrido un intervalo de tiempo fijo desde el inicio de la solicitud anterior Y cancela la solicitud si se inició otra después de .

No existe un algoritmo específico que responda a esta pregunta, pero para que no se acumule demora, debe asegurarse de dos cosas:

1. No hay fugas de memoria

Asegúrese absolutamente de que nada en su aplicación esté creando nuevas instancias de objetos, clases, matrices, etc. La memoria debe ser la misma después de desplazarse durante 10 segundos como lo es durante 60 segundos, etc. Puede asignar previamente estructuras de datos si necesita (incluidas las matrices) y luego reutilizarlas:

2. Reutilización constante de las estructuras de datos.

Esto es común en las páginas de desplazamiento infinito. En una galería de imágenes de desplazamiento infinito que muestra como máximo 30 imágenes en pantalla al mismo tiempo, en realidad puede haber solo 30-40 <img>elementos que se crean. Estos se usan y se reutilizan a medida que los usuarios se desplazan, de modo que no es necesario crear nuevos elementos HTML (o destruirlos, y por lo tanto recolectar basura). En cambio, estas imágenes obtienen nuevas URL de origen y nuevas posiciones, y el usuario puede seguir desplazándose, pero (sin saberlo) siempre ven los mismos elementos DOM una y otra vez.

Si está utilizando un lienzo, no utilizará elementos DOM para mostrar estos datos, pero la teoría es la misma, solo las estructuras de datos son suyas.