Algoritmo de rolagem - melhorando a busca e a exibição de dados

Eu gostaria de apresentar um pouco de um problema teórico.

Suponha que eu tenha um rolo infinito, implementado algo como o descrito aqui: https://medium.com/frontend-journeys/how-virtual-infinite-scrolling-works-239f7ee5aa58 . Não há nada sofisticado, basta dizer que é uma tabela de dados, por exemplo, NxN, e o usuário pode rolar para baixo e para a direita, como uma planilha, e ele só mostrará os dados na exibição atual mais menos um lidar com.

Agora, digamos também que são necessários aproximadamente 10 ms para "buscar e exibir" os dados nessa exibição, com uma função como:

get_data(start_col, end_col, start_row, end_row);

Isso carrega instantaneamente quando você clica em algum lugar da barra de rolagem ou faz uma 'rolagem leve' para renderizar os dados necessários. No entanto, vamos supor também que, para cada 'evento de busca inacabada', seja necessário o dobro do tempo para renderizar os dados de exibição necessários (devido à memória, gc e algumas outras coisas). Portanto, se eu rolar da esquerda para a direita de maneira lenta e deliberada, posso gerar mais de 100 eventos de rolagem que acionariam o carregamento de dados - no início, há um atraso visivelmente nulo. A busca ocorre em menos de 10ms, mas logo começa a demorar 20ms e depois 40ms, e agora temos um atraso perceptível, até atingir mais de um segundo para carregar os dados necessários. Além disso, não podemos usar algo como uma rejeição / atraso,

Que considerações eu precisaria levar em consideração e como seria um algoritmo de amostra para fazer isso? Aqui está um exemplo da interação do usuário que eu gostaria de ter nos dados, assumindo uma planilha de 10000 x 10000 (embora o Excel possa carregar todos os dados de uma vez) - https://gyazo.com/0772f941f43f9d14f884b7afeac9f414 .

Acho que você não deve enviar uma solicitação em nenhum evento de rolagem. somente se, com essa rolagem, o usuário chegar ao final da rolagem.

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
}

Você também pode especificar uma largura que será definida como próxima o suficiente para buscar novos dados (ei e.target.scrollHeight - e.target.offsetHeight <= 150)

Teoria e prática: Na teoria, não há diferença entre teoria e prática, mas na prática existe.

• Teoria: tudo é claro, mas nada funciona;
• Prática: tudo funciona, mas nada está claro;
• Às vezes, a teoria encontra a prática: nada funciona e nada é claro.

Às vezes, a melhor abordagem é um protótipo e, achando o problema interessante, passei um pouco de tempo preparando um, embora, como protótipo, ele tenha muitas verrugas ...

Em suma, a solução mais fácil para limitar um acúmulo de buscas de dados parece simplesmente configurar o mutex de um homem pobre dentro da rotina que está realizando a busca. (No exemplo de código abaixo, a função de busca simulada é simulateFetchOfData.) O mutex envolve a configuração de uma variável fora do escopo da função, de modo que false, se a busca estiver aberta para uso e se truea busca estiver em andamento no momento.

Ou seja, quando o usuário ajusta o controle deslizante horizontal ou vertical para iniciar uma busca de dados, a função que busca os dados primeiro verifica se a variável global mutexé verdadeira (ou seja, uma busca já está em andamento) e, nesse caso, simplesmente sai . Se mutexnão for verdadeiro, ele será definido mutexcomo true e continuará a busca. E, é claro, no final da função de busca, mutexé definido como false, de modo que o próximo evento de entrada do usuário passe pela verificação mutex na frente e execute outra busca ...

Algumas notas sobre o protótipo.

• Dentro da simulateFetchOfDatafunção, há sleep (100) configurado como uma promessa que simula o atraso na recuperação dos dados. Isso é imprensado com alguns registros no console. Se você remover a verificação mutex, verá com o console aberto que, ao mover os controles deslizantes, muitas instâncias de simulateFetchOfDatasão iniciadas e colocadas em suspense aguardando o sono (ou seja, a busca simulada de dados) a ser resolvida, enquanto na verificação mutex no lugar, apenas uma instância é iniciada por vez.
• O tempo de suspensão pode ser ajustado para simular uma maior latência da rede ou do banco de dados, para que você possa ter uma ideia da experiência do usuário. Por exemplo, redes com experiência de latência de 90ms para comunicações nos EUA continentais.
• Outro ponto notável é que, ao concluir uma busca e após redefinir mutexpara false, é realizada uma verificação para determinar se os valores de rolagem horizontal e vertical estão alinhados. Caso contrário, outra busca é iniciada. Isso garante que, apesar de vários eventos de rolagem possivelmente não serem disparados devido à busca estar ocupada, que no mínimo os valores finais de rolagem sejam endereçados acionando uma busca final.
• Os dados simulados da célula são simplesmente um valor de sequência do número da linha de traço-coluna. Por exemplo, "555-333" indica a linha 555 da coluna 333.
• Uma matriz esparsa denominada bufferé usada para armazenar os dados "buscados". Examiná-lo no console revelará muitas entradas "vazias x XXXX". A simulateFetchOfDatafunção é configurada de modo que, se os dados já estiverem retidos buffer, nenhuma "busca" seja realizada.

(Para visualizar o protótipo, basta copiar e colar o código inteiro em um novo arquivo de texto, renomeie para ".html" e abra em um navegador. EDIT: Foi testado no Chrome e 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>

Novamente, este é um protótipo para provar um meio de limitar um acúmulo de chamadas de dados desnecessárias. Se isso tiver que ser refatorado para fins de produção, muitas áreas precisarão ser abordadas, incluindo: 1) redução do uso do espaço variável global; 2) adicionando rótulos de linha e coluna; 3) adicionar botões aos controles deslizantes para rolar linhas ou colunas individuais; 4) possivelmente armazenar dados relacionados em buffer, se cálculos de dados forem necessários; 5) etc ...

Há algumas coisas que poderiam ser feitas. Eu o vejo como um intercalar de dois níveis, colocado entre o procedimento de solicitação de dados e o evento de rolagem do usuário.

1. Atraso no processamento do evento de rolagem

Você está certo, a renúncia não é nossa amiga nas questões relacionadas à rolagem. Mas existe o caminho certo para reduzir o número de disparos.

Use a versão otimizada do manipulador de eventos de rolagem, que será invocada no máximo uma vez a cada intervalo fixo. Você pode usar o acelerador lodash ou implementar a própria versão [ 1 ], [ 2 ], [ 3 ]. Defina 40 - 100 ms como um valor de intervalo. Você também precisará definir a trailingopção para que o último evento de rolagem seja processado, independentemente do intervalo do timer.

2. Fluxo de dados inteligente

Quando o manipulador de eventos de rolagem é chamado, o processo de solicitação de dados deve ser iniciado. Como você mencionou, fazer isso sempre que ocorrer um evento de rolagem (mesmo que tenhamos terminado a aceleração) pode causar atrasos no tempo. Pode haver algumas estratégias comuns: 1) não solicite os dados se houver outra solicitação pendente; 2) solicitar os dados não mais de uma vez a cada intervalo; 3) cancelar a solicitação pendente anterior.

A primeira e a segunda abordagens não passam de debouncing e throttling no nível do fluxo de dados. O debounce pode ser implementado com esforços mínimos com apenas uma condição antes de iniciar a solicitação + uma solicitação adicional no final. Mas acredito que o acelerador é mais apropriado do ponto de vista do UX. Aqui você precisará fornecer alguma lógica e não se esqueça da trailingopção, pois ela deve estar no jogo.

A última abordagem (o cancelamento da solicitação) também é amigável ao UX, mas menos cuidadosa do que a otimização. Você inicia a solicitação de qualquer maneira, mas descarta o resultado se outra solicitação tiver sido iniciada após esta. Você também pode tentar abortar a solicitação se estiver usando fetch.

Na minha opinião, a melhor opção seria combinar estratégias (2) e (3), para que você solicite os dados apenas se algum intervalo de tempo fixo tiver passado desde o início da solicitação anterior E você cancele a solicitação se outro tiver sido iniciado após .

Não existe um algoritmo específico que responda a essa pergunta, mas para não haver atraso, é necessário garantir duas coisas:

1. Sem vazamento de memória

Tenha certeza absoluta de que nada no seu aplicativo esteja criando novas instâncias de objetos, classes, matrizes etc. A memória deve ser a mesma depois de rolar por 10 segundos, assim como por 60 segundos, etc. Você pode pré-alocar estruturas de dados se você precisa (incluindo matrizes) e depois as reutiliza:

2. Reutilização constante de estruturas de dados

Isso é comum em páginas de rolagem infinitas. Em uma galeria de imagens de rolagem infinita que mostra no máximo 30 imagens na tela ao mesmo tempo, pode haver apenas de 30 a 40 <img>elementos criados. Eles são usados ​​e reutilizados à medida que os usuários rolam, para que nenhum novo elemento HTML precise ser criado (ou destruído e, portanto, coletado de lixo). Em vez disso, essas imagens recebem novos URLs de origem e novas posições, e o usuário pode continuar rolando, mas (sem o conhecimento delas) sempre vê os mesmos elementos DOM repetidamente.

Se você estiver usando canvas, não usará elementos DOM para exibir esses dados, mas a teoria é a mesma, apenas as estruturas de dados são suas.