Как разрешить веб-работникам получать новые данные, пока они еще выполняют вычисления?

Question

Я хочу отсортировать массив, используя Web Workers.Но этот массив может со временем получать новые значения, в то время как работник все еще выполняет функцию сортировки.

Поэтому мой вопрос заключается в том, как я могу "остановить" вычисление сортировки на работнике после получения нового элемента, поэтомуон может выполнить сортировку массива с этим элементом, сохраняя при этом уже выполненную сортировку?

Пример:

let worker = new Worker('worker.js');
let list = [10,1,5,2,14,3];
worker.postMessage({ list });
setInterval(() => worker.postMessage({ num: SOME_RANDOM_NUM, list }), 100);

worker.onmessage = event => {
  list = event.data.list;
}

Итак, допустим, что я прошел 50,до этого работник добился определенного прогресса в сортировке, и теперь у меня есть что-то вроде этого: [1, 2, 3, 10, 5, 14, 50].Это означает, что сортировка остановлена ​​на индексе 3.Поэтому я передаю этот массив new обратно работнику, чтобы он мог продолжить сортировку с позиции 3.

Как я могу это сделать, поскольку нет способа приостановить / возобновить работу веб-работника?

Answer 1

Вы можете сделать это с помощью некоторого трюка - с помощью прерывания функции setTimeout.Например, без дополнительного потока невозможно параллельное выполнение 2 функций, но с помощью трюка прерывания функции setTimeout мы можем сделать это следующим образом:

Пример параллельного выполнения функций

var count_0 = 0,
    count_1 = 0;

function func_0()
{
    if(count_0 < 3)
        setTimeout(func_0, 0);//the same: setTimeout(func_0);

    console.log('count_0 = '+count_0);
    count_0++
}

function func_1()
{
    if(count_1 < 3)
        setTimeout(func_1, 0);

    console.log('count_1 = '+count_1)
    count_1++
}

func_0();
func_1();

Вы получите этот вывод:

count_0 = 0
count_1 = 0
count_0 = 1
count_1 = 1
count_0 = 2
count_1 = 2
count_0 = 3
count_1 = 3

Почему это возможно?Потому что для выполнения функции setTimeout требуется некоторое время.И даже этого времени достаточно для выполнения некоторой части из вашего следующего кода.

Решение для вас

Для этого случая вам нужно написать собственную функцию сортировки массива(или вы также можете использовать следующую функцию от меня), потому что мы не можем прервать встроенную функцию sort.И в этой вашей собственной функции вы должны использовать эту setTimeout функцию, которая прерывает трюк.И вы можете получить ваше message уведомление о событии.

В следующем примере у меня есть прерывание на половину длины моего массива, и вы можете изменить его, если хотите.

Пример с прерыванием пользовательской сортировки

var numbers = [4, 2, 1, 3, 5];

// this is my bubble sort function with interruption
/**
 * Sorting an array. You will get the same, but sorted array.
 * @param {array[]} arr – array to sort
 * @param {number} dir – if dir = -1 you will get an array like [5,4,3,2,1]
 *                 and if dir = 1 in opposite direction like [1,2,3,4,5]
 * @param {number} passCount – it is used only for setTimeout interrupting trick.
 */
function sortNumbersWithInterruption(arr, dir, passCount)
{
    var passes = passCount || arr.length,
        halfOfArrayLength = (arr.length / 2) | 0; // for ex. 2.5 | 0 = 2

    // Why we need while loop: some values are on
    // the end of array and we have to change their
    // positions until they move to the first place of array.
    while(passes--)
    {
        if(!passCount && passes == halfOfArrayLength)
        {
            // if you want you can also not write the following line for full break of sorting
            setTimeout(function(){sortNumbersWithInterruption(arr, dir, passes)}, 0);
            /*
                You can do here all what you want. Place 1
            */
            break
        }

        for(var i = 0; i < arr.length - 1; i++)
        {
            var a = arr[i],
                b = arr[i+1];

            if((a - b) * dir > 0)
            {
                arr[i] = b;
                arr[i+1] = a;
            }
        }

        console.log('array is: ' + arr.join());
    }

    if(passCount)
        console.log('END sring is: ' + arr.join());
}

sortNumbersWithInterruption(numbers, -1); //without passCount parameter
/*
    You can do here all what you want. Place 2
*/
console.log('The execution is here now!');

Вы получите следующие выходные данные:

массив: 4,2,3,5,1
массив: 4,3,5, 2,1
Выполнение здесь! * Массив
: 4,5,3,2,1
Массив: 5,4,3,2,1
END sring:5,4,3,2,1

Answer 2

Вы можете сделать это с помощью сортировки вставок (вид).Вот идея:

1. Запустите вашего работника с внутренним пустым массивом (пустой массив явно отсортирован)

2. Ваш работник получает только элементы, невесь массив

3. Ваш работник вставляет любой полученный элемент в правильное положение в массив

4. Каждые n секунд работник выдает сообщение стекущий массив, если он изменился после последнего события.(Если вы предпочитаете, вы можете отправлять массив при каждой вставке, но более эффективно буферизовать каким-либо образом)

В конце концов, вы получите весь массив, если какой-либо элемент будет добавлен, вы получитеполучите обновленный массив в.

ПРИМЕЧАНИЕ. Поскольку ваш массив всегда сортируется, вы можете вставить его в правильное положение с помощью бинарного поиска.Это очень эффективно.

Answer 3

Несмотря на то, что Worker работает в другом потоке, отличном от основного на вашей странице, и, таким образом, может работать непрерывно, не блокируя пользовательский интерфейс, он все равно работает в одном потоке.

Это означает, что до завершения алгоритма сортировки Worker будет задерживать выполнение обработчика событий сообщения;он заблокирован так же, как и основной поток.

Даже если вы использовали другого работника изнутри этого работника, проблема была бы такой же.

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

Но это резко замедлит ваш алгоритм сортировки.

Чтобы сделать его лучше, вы можете попытаться подключиться к каждому циклу событий, благодаря объекту MessageChannel:Вы говорите в одном порту и получаете сообщение в следующем цикле событий.Если вы снова поговорите с другим портом, то у вас будет свой собственный хук для каждого цикла событий.

Теперь лучше всего запустить хороший пакет в каждом из этих циклов событий, но для демонстрации яЯ вызову только один экземпляр нашей функции генератора (который я позаимствовал у этого Q / A )

const worker = new Worker(getWorkerURL());
worker.onmessage = draw;

onclick = e =>     worker.postMessage(0x0000FF/0xFFFFFF); // add a red pixel

// every frame we request the current state from Worker
function requestFrame() {
  worker.postMessage('gimme a frame');
  requestAnimationFrame(requestFrame);
}
requestFrame();

// drawing part
const ctx = canvas.getContext('2d');
const img = ctx.createImageData(50, 50);
const data = new Uint32Array(img.data.buffer);
ctx.imageSmoothingEnabled = false;

function draw(evt) {
  // converts 0&1 to black and white pixels
  const list = evt.data;
  list.forEach((bool, i) =>
    data[i] = (bool * 0xFFFFFF) + 0xFF000000
  );
  ctx.setTransform(1,0,0,1,0,0);
  ctx.clearRect(0,0,canvas.width,canvas.height);
  ctx.putImageData(img,0,0);
  // draw bigger
  ctx.scale(5,5);
  ctx.drawImage(canvas, 0,0);
}

function getWorkerURL() {
  const script = document.querySelector('[type="worker-script"]');
  const blob = new Blob([script.textContent]);
  return URL.createObjectURL(blob);
}

body{
  background: ivory;
}

// our list
const list = Array.from({length: 2500}).map(_=>+(Math.random()>.5));
// our sorter generator
let sorter = bubbleSort(list);
let done = false;
/* inner messaging channel */
const msg_channel = new MessageChannel();
// Hook to every Event loop
msg_channel.port2.onmessage = e => {
  // procede next step in sorting algo
  // could be a few thousands in a loop
  const state = sorter.next();
  // while running
  if(!state.done) {
    msg_channel.port1.postMessage('');
    done = false;
  }
  else {
    done = true;
  }
}
msg_channel.port1.postMessage("");

/* outer messaging channel (from main) */
self.onmessage = e => {
  if(e.data === "gimme a frame") {
    self.postMessage(list);
  }
  else {
    list.push(e.data);
    if(done) { // restart the sorter
      sorter = bubbleSort(list);
      msg_channel.port1.postMessage('');
    }
  }
};

function* bubbleSort(a) { // * is magic
  var swapped;
  do {
    swapped = false;
    for (var i = 0; i < a.length - 1; i++) {
      if (a[i] > a[i + 1]) {
        var temp = a[i];
        a[i] = a[i + 1];
        a[i + 1] = temp;
        swapped = true;
        yield swapped; // pause here
      }
    }
  } while (swapped);
}

 click to add red pixels