Алгоритм прокрутки - улучшение выборки и отображения данных - PullRequest
8 голосов
/ 12 февраля 2020

Я хотел бы изложить некоторую теоретическую проблему.

Предположим, у меня есть бесконечный свиток, реализованный примерно так, как описано здесь: https://medium.com/frontend-journeys/how-virtual-infinite-scrolling-works-239f7ee5aa58. В этом нет ничего особенного, достаточно сказать, что это таблица данных, скажем NxN, и пользователь может прокручивать вниз и вправо, как электронная таблица, и он будет отображать данные только в текущем представлении плюс минус a handle.

Теперь, давайте также скажем, что для «извлечения и отображения» данных в этом представлении требуется примерно 10 мсек с помощью функции, такой как:

get_data(start_col, end_col, start_row, end_row);

Это загружается сразу при нажатии где-то в полосе прокрутки или сделать «небольшую прокрутку», чтобы отобразить необходимые данные. Однако, давайте также предположим, что для каждого «незавершенного события извлечения», что требуется в два раза больше времени для рендеринга необходимых данных представления (из-за памяти, g c и некоторых других вещей). Поэтому, если я медленно и намеренно прокручиваю слева направо, я могу сгенерировать более 100 событий прокрутки, которые будут запускать загрузку данных - сначала заметна нулевая задержка. Выборка происходит менее чем за 10 мс, но вскоре она начинает занимать 20 мс, а затем 40 мс, и теперь у нас есть что-то вроде заметной задержки, пока она не достигнет более секунды, чтобы загрузить необходимые данные. Кроме того, мы не можем использовать что-то вроде debounce / delay, поскольку любая задержка будет очевидна - данные должны загружаться мгновенно, когда пользователь щелкает / прокручивает место в сетке.

Какие соображения я должен принять во внимание и как будет выглядеть пример алгоритма для достижения sh этого? Вот пример взаимодействия пользователя с данными, которое я хотел бы иметь при работе с таблицей 10000 x 10000 (хотя Excel может загрузить все данные одновременно) - https://gyazo.com/0772f941f43f9d14f884b7afeac9f414.

Ответы [ 4 ]

3 голосов
/ 16 февраля 2020

Я думаю, что вы не должны отправлять запрос на любое событие прокрутки. только если с помощью этой прокрутки пользователь достигнет конца прокрутки.

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
}

Вы также можете указать ширину, которая будет определена как достаточно близкая для извлечения новых данных (например, e.target.scrollHeight - e.target.offsetHeight <= 150)

1 голос
/ 22 февраля 2020

Теория и практика: в теории нет разницы между теорией и практикой, но на практике есть.

  • Теория: все ясно, но ничего не работает;
  • Практика: все работает, но ничего не ясно;
  • Иногда теория встречается с практикой: ничего не работает и ничего не ясно.

Иногда лучший подход - это прототип, и найдя проблему интересной, я потратил немного времени на ее разработку, хотя в качестве прототипа у нее, по общему признанию, много бородавок ...

Короче говоря, простейшее решение для ограничения отставания выборок данных, по-видимому, просто установка мьютекса бедного человека в рамках процедуры, выполняющей извлечение. (В приведенном ниже примере кода имитируемая функция выборки имеет значение simulateFetchOfData.) Мьютекс включает в себя установку переменной вне области действия функции таким образом, чтобы при false выборка была открыта для использования, а при true выборка была в настоящее время выполняется.

То есть, когда пользователь настраивает ползунок по горизонтали или вертикали, чтобы инициировать выборку данных, функция, которая извлекает данные, сначала проверяет, является ли глобальная переменная mutex истинной (ie извлечение уже началось), и если это так, просто выходит. Если mutex не соответствует истине, то для mutex устанавливается значение true, а затем продолжается выборка. И, конечно же, в конце функции выборки mutex устанавливается в значение false, так что следующее событие пользовательского ввода затем пройдет через проверку мьютекса и выполнит другую выборку ...

Несколько замечаний о прототипе.

  • Внутри функции simulateFetchOfData спящий режим (100) сконфигурирован как Promise, который имитирует задержку при получении данных. Это зажато с некоторым входом в консоль. Если вы удалите проверку мьютекса, вы увидите при открытой консоли, что при перемещении ползунков многие экземпляры simulateFetchOfData запускаются и переводятся в состояние ожидания, ожидающее в спящем режиме (ie, моделируемый выбор данных) для разрешения, в то время как при проверке мьютекса в каждый момент времени запускается только один экземпляр.
  • Время ожидания может быть отрегулировано для имитации большей задержки сети или базы данных, чтобы вы могли почувствовать пользовательский опыт. Например, в сетях с задержкой 90 мс для коммуникаций в континентальной части США.
  • Еще одним примечательным является то, что при завершении выборки и после сброса mutex в false выполняется проверка, чтобы определить, значения горизонтальной и вертикальной прокрутки выровнены. Если нет, инициируется другая выборка. Это гарантирует, что, несмотря на то, что некоторые события прокрутки, возможно, не запускаются из-за того, что выборка занята, минимальные конечные значения прокрутки адресуются путем запуска одной последней выборки.
  • Моделируемые данные ячейки - это просто строковое значение row-da sh -колонный номер. Например, «555-333» указывает на строку 555 столбца 333.
  • Разреженный массив с именем buffer используется для хранения «извлеченных» данных. Изучение его в консоли покажет много «пустых х XXXX» записей. Функция simulateFetchOfData настроена таким образом, что, если данные уже хранятся в buffer, «выборка» не выполняется.

(Чтобы просмотреть прототип, просто скопируйте и вставьте все код в новый текстовый файл, переименуйте в «. html» и откройте в браузере. РЕДАКТИРОВАТЬ: Был протестирован на Chrome и 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>

Опять же, это прототип, чтобы доказать средства для ограничения отставания ненужных вызовов данных. Если это должно быть реорганизовано для производственных целей, многие области потребуют адресации, включая: 1) сокращение использования пространства глобальных переменных; 2) добавление меток строк и столбцов; 3) добавление кнопок к ползункам для прокрутки отдельных строк или столбцов; 4) возможно буферизация связанных данных, если требуются вычисления данных; 5) et c ...

0 голосов
/ 21 февраля 2020

Не существует конкретного c алгоритма, который отвечает на этот вопрос, но для того, чтобы не накапливать задержку, вам нужно обеспечить две вещи:

1. Нет утечек памяти

Будьте абсолютно уверены, что ничто в вашем приложении не создает новые экземпляры объектов, классов, массивов и т. Д. c. Память должна быть такой же после прокрутки в течение 10 секунд, как и в течение 60 секунд, и т. Д. c. При необходимости вы можете предварительно выделить структуры данных (включая массивы), а затем повторно использовать их:

2. Постоянное повторное использование структур данных

Это часто встречается на страницах с бесконечной прокруткой. В галерее изображений с бесконечной прокруткой, которая одновременно отображает на экране не более 30 изображений, на самом деле может быть создано только 30-40 <img> элементов. Затем они используются и повторно используются в качестве пользовательских прокруток, поэтому нет необходимости создавать (* уничтожать и, следовательно, собирать мусор) новые элементы HTML. Вместо этого эти изображения получают новые исходные URL-адреса и новые позиции, и пользователь может продолжать прокручивать, но (без ведома) они всегда видят одни и те же элементы DOM снова и снова.

Если вы используете canvas, вы Я не буду использовать элементы DOM для отображения этих данных, но теория та же самая, просто ваши структуры данных принадлежат вам.

0 голосов
/ 13 февраля 2020

Есть некоторые вещи, которые можно сделать. Я вижу его как двухуровневый промежуточный слой, помещенный между процедурой запроса данных и событием прокрутки пользователя.

1. Задержка обработки события прокрутки

Вы правы, debounce не наш друг в вопросах, связанных с прокруткой. Но есть правильный способ уменьшить количество срабатываний.

Используйте дросселированную версию обработчика события прокрутки, которая будет вызываться не чаще одного раза за каждый фиксированный интервал. Вы можете использовать loda sh throttle или реализовать собственную версию [ 1 ], [ 2 ], [ 3 ]. Установите 40 - 100 мс в качестве значения интервала. Вам также необходимо установить параметр trailing, чтобы последнее событие прокрутки обрабатывалось независимо от интервала таймера.

2. Интеллектуальный поток данных

Когда вызывается обработчик события прокрутки, должен быть запущен процесс запроса данных. Как вы упомянули, выполнение этого каждый раз, когда происходит событие прокрутки (даже если мы закончили с регулированием), может привести к задержкам во времени. Могут быть некоторые общие стратегии: 1) не запрашивать данные, если есть другой ожидающий запрос; 2) запрашивать данные не более одного раза за некоторый интервал; 3) отменить предыдущий ожидающий запрос.

Первый и второй подходы - не более, чем устранение неполадок и регулирование на уровне потока данных. Дебадинг может быть реализован с минимальными усилиями с одним условием перед инициацией запроса + один дополнительный запрос в конце. Но я считаю, что газ является более подходящим с точки зрения UX. Здесь вам нужно будет предоставить логи c, и не забывайте о опции trailing, как это должно быть в игре.

Последний подход (отмена запроса) также удобен для UX, но менее осторожен, чем дросселирующий. Вы все равно запускаете запрос, но выкидываете его результат, если после этого был запущен другой запрос. Вы также можете попробовать отменить запрос , если вы используете fetch.

. На мой взгляд, лучшим вариантом будет объединение (2) и (3) стратегий, поэтому вы запрашиваете данные, только если какой-то фиксированный интервал времени прошел с момента инициирования предыдущего запроса, И вы отменяете запрос, если другой был инициирован после.

...