История изменений

На текущий момент план такой: рисую вариацию binary heap (tnx @annulen), который суть дерево (tnx @timdorohin), но в корневом узле минимальный (ближайший) launch time, т.е. время извлечения O(0). При этом, чтобы при добавлении узлов (которое будет весьма частым: периодические запуски нужно заново добавлять сразу после исполнения) не копировать куски дерева туда-сюда:

• организую не в массиве а в {Node* parent; Node* children[2]} (плюс кастомный memory manager);
• разрешаю узлы с 1 потомком.

В худшем случае, если у ВСЕХ узлов будет по 1 потомку, это будет double-linked list, который по слухам (tnx @firkax) мой объём вытянет. Но такое случится только если каждый добавляемый узел будет иметь launch time больше всех предыдущих; в противном случае добавление заполнит пустого второго ребёнка какого-то промежуточного узла (UPD TODO противоречит последнему пункту?).

Ну и чтобы какая-нить заклинившая задача, долго выполняющаяся и постоянно повторно добавляющая себя с delay=0, не заблокировала все остальные задачи в очереди, буду делать так:

• храню в узлах не delay, а launch time (по-другому собственно и никак; к слову – в наносекундах от моего epoch2 = 2025-01-01);
• если при добавлении узла, идя по дереву от корня, я напарываюсь на узел с таким же launch time, то пропускаю его и его потомков с совпадающими launch time и добавляю новую задачу в конец (самым дальним потомком).
• соответственно, у одного узла запрещаю детей с одинаковыми launch time, а для добавления ноды, чей launch time больше чем у обоих детей, выбираю поддерево с бОльшим launch time.

Как-то так. Пока что вроде всё выглядит красиво.

На текущий момент план такой: рисую вариацию binary heap (tnx @annulen), который суть дерево (tnx @timdorohin), но в корневом узле минимальный (ближайший) launch time, т.е. время извлечения O(0). При этом чтобы при добавлении узлов (которое будет весьма частым: периодические запуски нужно заново добавлять сразу после исполнения) не копировать куски дерева туда-сюда:

• организую не в массиве а в {Node* parent; Node* children[2]} (плюс кастомный memory manager);
• разрешаю узлы с 1 потомком.

В худшем случае, если у ВСЕХ узлов будет по 1 потомку, это будет double-linked list, который по слухам (tnx @firkax) мой объём вытянет. Но такое случится только если каждый добавляемый узел будет иметь launch time больше всех предыдущих; в противном случае добавление заполнит пустого второго ребёнка какого-то промежуточного узла (UPD TODO противоречит последнему пункту?).

Ну и чтобы какая-нить заклинившая задача, долго выполняющаяся и постоянно повторно добавляющая себя с delay=0, не заблокировала все остальные задачи в очереди, буду делать так:

• храню в узлах не delay, а launch time (по-другому собственно и никак; к слову – в наносекундах от моего epoch2 = 2025-01-01);
• если при добавлении узла, идя по дереву от корня, я напарываюсь на узел с таким же launch time, то пропускаю его и его потомков с совпадающими launch time и добавляю новую задачу в конец (самым дальним потомком).
• соответственно, у одного узла запрещаю детей с одинаковыми launch time, а для добавления ноды, чей launch time больше чем у обоих детей, выбираю поддерево с бОльшим launch time.

Как-то так. Пока что вроде всё выглядит красиво.

На текущий момент план такой: рисую вариацию binary heap (tnx @annulen), который суть дерево (tnx @timdorohin), но в корневом узле минимальный (ближайший) launch time, т.е. время извлечения O(0). При этом чтобы при добавлении узлов (которое будет весьма частым: периодические запуски нужно заново добавлять сразу после исполнения) не копировать куски дерева туда-сюда:

• организую не в массиве а в {Node* parent; Node* children[2]} (плюс кастомный memory manager);
• разрешаю узлы с 1 потомком.

В худшем случае, если у ВСЕХ узлов будет по 1 потомку, это будет double-linked list, который по слухам (tnx @firkax) мой объём вытянет. Но такое случится только если каждый добавляемый узел будет иметь launch time больше всех предыдущих; в противном случае добавление заполнит пустого второго ребёнка какого-то промежуточного узла (UPD TODO противоречит последнему пункту?).

Ну и чтобы какая-нить заклинившая задача, долго выполняющаяся и постоянно повторно добавляющая себя с delay=0, не заблокировала все остальные задачи в очереди, буду делать так:

• храню в узлах не delay, а launch time (по-другому собственно и никак; к слову – в наносекундах от моего epoch2 = 2025-01-01);
• если при добавлении узла, идя по дереву от корня, я напарываюсь на узел с таким же launch time, то пропускаю его и его потомков с совпадающими launch time и добавляю новую задачу в конец (самым последним потомком).
• соответственно, у одного узла запрещаю детей с одинаковыми launch time, а для добавления ноды, чей launch time больше чем у обоих детей, выбираю поддерево с бОльшим launch time.

Как-то так. Пока что вроде всё выглядит красиво.

На текущий момент план такой: рисую вариацию binary heap (tnx @annulen), который суть дерево (tnx @timdorohin), но в корневом узле минимальный (ближайший) launch time, т.е. время извлечения O(0). При этом чтобы при добавлении узлов (которое будет весьма частым: периодические запуски нужно заново добавлять сразу после исполнения) не копировать куски дерева туда-сюда:

• организую не в массиве а в {Node* parent; Node* children[2]} (плюс кастомный memory manager);
• разрешаю узлы с 1 потомком.

В худшем случае, если у ВСЕХ узлов будет по 1 потомку, это будет double-linked list, который по слухам (tnx @firkax) мой объём вытянет. Но такое случится только если каждый добавляемый узел будет иметь launch time больше всех предыдущих; в противном случае добавление заполнит пустого второго ребёнка какого-то промежуточного узла (UPD TODO противоречит последнему пункту?).

Ну и чтобы какая-нить заклинившая задача, долго выполняющаяся и постоянно повторно добавляющая себя с delay=0, не заблокировала все остальные задачи в очереди, буду делать так:

• храню в узлах не delay, а launch time (по-другому собственно и никак);
• если при добавлении узла, идя по дереву от корня, я напарываюсь на узел с таким же launch time, то пропускаю его и его потомков с совпадающими launch time и добавляю новую задачу в конец (самым последним потомком).
• соответственно, у одного узла запрещаю детей с одинаковыми launch time, а для добавления ноды, чей launch time больше чем у обоих детей, выбираю поддерево с бОльшим launch time.

Как-то так. Пока что вроде всё выглядит красиво.

На текущий момент план такой: рисую вариацию binary heap (tnx @annulen), который суть дерево (tnx @timdorohin), но в корневом узле минимальный (ближайший) launch time, т.е. время извлечения O(0). При этом чтобы при добавлении узлов (которое будет весьма частым: периодические запуски нужно заново добавлять сразу после исполнения) не копировать куски дерева туда-сюда:

• организую не в массиве а в {Node* parent; Node* children[2]} (плюс кастомный memory manager);
• разрешаю узлы с 1 потомком.

В худшем случае, если у ВСЕХ узлов будет по 1 потомку, это будет double-linked list, который по слухам (tnx @firkax) мой объём вытянет. Но такое случится только если каждый добавляемый узел будет иметь launch time больше всех предыдущих – но тут и чистый binary heap сработает не лучше; а в противном случае добавление заполнит пустого второго ребёнка какого-то промежуточного узла (UPD TODO противоречит последнему пункту?).

Ну и чтобы какая-нить заклинившая задача, долго выполняющаяся и постоянно повторно добавляющая себя с delay=0, не заблокировала все остальные задачи в очереди, буду делать так:

• храню в узлах не delay, а launch time (по-другому собственно и никак);
• если при добавлении узла, идя по дереву от корня, я напарываюсь на узел с таким же launch time, то пропускаю его и его потомков с совпадающими launch time и добавляю новую задачу в конец (самым последним потомком).
• соответственно, у одного узла запрещаю детей с одинаковыми launch time, а для добавления ноды, чей launch time больше чем у обоих детей, выбираю поддерево с бОльшим launch time.

Как-то так. Пока что вроде всё выглядит красиво.

На текущий момент план такой: рисую вариацию binary heap (tnx @annulen), который суть дерево (tnx @timdorohin), но в корневом узле минимальный (ближайший) launch time, т.е. время извлечения O(0). При этом чтобы при добавлении узлов (которое будет весьма частым: периодические запуски нужно заново добавлять сразу после исполнения) не копировать куски дерева туда-сюда:

• организую не в массиве а в {Node* parent; Node* children[2]} (плюс кастомный memory manager);
• разрешаю узлы с 1 потомком.

В худшем случае, если у ВСЕХ узлов будет по 1 потомку, это будет double-linked list, который по слухам (tnx @firkax) мой объём вытянет. Но такое случится только если каждый добавляемый узел будет иметь launch time больше всех предыдущих – но тут и чистый binary heap сработает не лучше; а в противном случае добавление заполнит пустого второго ребёнка какого-то промежуточного узла (UPD TODO противоречит последнему пункту?).

Ну и чтобы какая-нить заклинившая задача, долго выполняющаяся и постоянно повторно добавляющая себя с delay=0, не заблокировала все остальные задачи в очереди, буду делать так:

• храню в узлах не delay, а launch time (по-другому собственно и никак);
• если при добавлении узла, идя по дереву от корня, я напарываюсь на узел с таким же launch time, то пропускаю его и его потомков с совпадающими launch time и добавляю новую задачу в конец (самым последним потомком).
• соответственно, у одного узла запрещаю детей с одинаковыми launch time, а для добавления ноды, чей launch time больше чем у обоих детей, выбираю поддерево с БОЛЬШИМ launch time.

Как-то так. Пока что вроде всё выглядит красиво.

На текущий момент план такой: рисую вариацию binary heap (tnx @annulen), который суть дерево (tnx @timdorohin), но в корневом узле минимальный (ближайший) launch time, т.е. время извлечения O(0). При этом чтобы при добавлении узлов (которое будет весьма частым: периодические запуски нужно заново добавлять сразу после исполнения) не копировать куски дерева туда-сюда:

• организую не в массиве а в {Node* parent; Node* children[2]} (плюс кастомный memory manager);
• разрешаю узлы с 1 потомком.

В худшем случае, если у ВСЕХ узлов будет по 1 потомку, это будет double-linked list, который по слухам (tnx @firkax) мой объём вытянет. Но такое случится только если каждый добавляемый узел будет иметь launch time больше всех предыдущих – но тут и чистый binary heap сработает не лучше; а в противном случае добавление заполнит пустого второго ребёнка какого-то промежуточного узла.

Ну и чтобы какая-нить заклинившая задача, долго выполняющаяся и постоянно повторно добавляющая себя с delay=0, не заблокировала все остальные задачи в очереди, буду делать так:

• храню в узлах не delay, а launch time (по-другому собственно и никак);
• если при добавлении узла, идя по дереву от корня, я напарываюсь на узел с таким же launch time, то пропускаю его и его потомков с совпадающими launch time и добавляю новую задачу в конец (самым последним потомком).
• соответственно, у одного узла запрещаю детей с одинаковыми launch time, а для добавления ноды, чей launch time больше чем у обоих детей, выбираю поддерево с БОЛЬШИМ launch time.

Как-то так. Пока что вроде всё выглядит красиво.