Чистый, эффективный алгоритм для обертывания целых чисел в C++
Есть много способов придумать работоспособную diff-структуру.
Наивное решение
Один наивный способ - хранить два дерева в кортеже. Затем, когда вам нужно восстановить дерево с учетом другого и различий, вы просто ищете узел, который отличается при сравнении данного дерева с деревом в первой записи кортежа различий. Если найдено, вы возвращаете это дерево из первой записи кортежа. Если не найден, вы возвращаете второй из набора.
Маленькие различия для небольших различий.
Интервьюер, вероятно, попросит альтернативу с меньшим потреблением памяти. Можно попытаться придумать структуру, которая будет небольшой по размеру, когда есть только несколько значений или узлов. В крайнем случае, когда оба дерева равны, такой diff также будет (почти) пустым.
Определения
Я определяю эти термины перед определением структуры diff:
-
Представьте, что деревья получают дополнительные листовые узлы NIL, т.е. пустое дерево будет состоять из 1 NIL узел. Дерево, имеющее только корневой узел, будет иметь два узла NIL в качестве своих прямых потомков и т. Д.
-
Узел является общим для обоих деревьев, когда до него можно добраться по одному и тому же пути от корня (например, слева направо), независимо от того, содержат ли они одно и то же значение или имеют такие же дети. Узел может даже быть общим, когда он является узлом NIL в одном или обоих деревьях (как определено выше).
-
Общие узлы (включая узлы NIL, когда они общие) получают порядковый номер предзаказа (0, 1, 2, ...). Узлы, которые не являются общими, отбрасываются во время этой нумерации.
Различающаяся структура
Разницей может быть список кортежей, где каждый кортеж имеет эту информацию:
- Вышеупомянутый порядковый номер предзаказа, идентифицирующий общий узел
- Значение: когда ни один из узлов не является узлом NIL, это разница значений (например, XOR). Когда один из узлов является узлом NIL, значением является объект другого узла (так эффективно, включая целое поддерево под ним). В типизированных языках любая информация может помещаться в одну и ту же позицию кортежа. В строго типизированных языках вы должны использовать дополнительную запись в кортеже (например, atomicValue, поддерево), где только один из двух будет иметь значительное значение.
Кортеж будет добавлен только для общего узла, и только тогда, когда либо их значения различаются, и по крайней мере один из них является узлом не-NIL.
Алгоритм
Различия могут быть созданы путем предварительного заказа через общие узлы деревьев.
Вот реализация в JavaScript:
class Node {
constructor(value, left, right) {
this.value = value;
if (left) this.left = left;
if (right) this.right = right;
}
clone() {
return new Node(this.value, this.left ? this.left.clone() : undefined,
this.right ? this.right.clone() : undefined);
}
}
// Main functions:
function createDiff(tree1, tree2) {
let i = -1; // preorder sequence number
function recur(node1, node2) {
i++;
if (!node1 !== !node2) return [[i, (node1 || node2).clone()]];
if (!node1) return [];
const result = [];
if (node1.value !== node2.value) result.push([i, node1.value ^ node2.value]);
return result.concat(recur(node1.left, node2.left), recur(node1.right, node2.right));
}
return recur(tree1, tree2);
}
function applyDiff(tree, diff) {
let i = -1; // preorder sequence number
let j = 0; // index in diff array
function recur(node) {
i++;
let diffData = j >= diff.length || diff[j][0] !== i ? 0 : diff[j++][1];
if (diffData instanceof Node) return node ? undefined : diffData.clone();
return node && new Node(node.value ^ diffData, recur(node.left), recur(node.right));
}
return recur(tree);
}
// Create sample data:
let tree1 =
new Node(4,
new Node(3,
new Node(5), new Node(8)
),
new Node(2,
new Node(10), new Node(22)
)
);
let tree2 =
new Node(2,
undefined,
new Node(4,
new Node(11), new Node(12)
)
);
// Demo:
let diff = createDiff(tree1, tree2);
console.log("Diff:");
console.log(diff);
const restoreTree2 = applyDiff(tree1, diff);
console.log("Is restored second tree equal to original?");
console.log(JSON.stringify(tree2)===JSON.stringify(restoreTree2));
const restoreTree1 = applyDiff(tree2, diff);
console.log("Is restored first tree equal to original?");
console.log(JSON.stringify(tree1)===JSON.stringify(restoreTree1));
const noDiff = createDiff(tree1, tree1);
console.log("Diff for two equal trees:");
console.log(noDiff);8 ответов
Знак a % b только определяется если a и b являются оба неотрицательными.
int Wrap(int kX, int const kLowerBound, int const kUpperBound)
{
int range_size = kUpperBound - kLowerBound + 1;
if (kX < kLowerBound)
kX += range_size * ((kLowerBound - kX) / range_size + 1);
return kLowerBound + (kX - kLowerBound) % range_size;
}
Для отрицательного kX можно добавить:
int temp = kUpperBound - kLowerBound + 1;
while (kX < 0) kX += temp;
return kX%temp + kLowerBound;
Я дал бы точку входа наиболее распространенному случаю lowerBound=0, upperBound=N-1. И вызовите эту функцию в общем случае. Никакое ультрасовременное вычисление не сделано, где я уже нахожусь в диапазоне. Это принимает верхний> =lower, или n> 0.
int wrapN(int i,int n)
{
if (i<0) return (n-1)-(-1-i)%n; // -1-i is >=0
if (i>=n) return i%n;
return i; // In range, no mod
}
int wrapLU(int i,int lower,int upper)
{
return lower+wrapN(i-lower,1+upper-lower);
}
Ответ, который имеет некоторую симметрию и также делает ее очевидной что, когда kX находится в диапазоне, он возвращается неизмененный.
int Wrap(int const kX, int const kLowerBound, int const kUpperBound)
{
int range_size = kUpperBound - kLowerBound + 1;
if (kX < kLowerBound)
return kX + range_size * ((kLowerBound - kX) / range_size + 1);
if (kX > kUpperBound)
return kX - range_size * ((kX - kUpperBound) / range_size + 1);
return kX;
}
На самом деле начиная с-1% 4 возврата-1 в каждой системе я даже шел, простое ультрасовременное решение не работает. Я попробовал бы:
int range = kUpperBound - kLowerBound +1;
kx = ((kx - kLowerBound) % range) + range;
return (kx % range) + kLowerBound;
если kx положителен, Вы модификация, добавьте диапазон и модификацию назад, отменив добавление. Если kx отрицателен, Вы модификация, добавьте диапазон, который делает это положительным, то модификация снова, которая ничего не делает.
Я предложил бы это решение:
int Wrap(int const kX, int const kLowerBound, int const kUpperBound)
{
int d = kUpperBound - kLowerBound + 1;
return kLowerBound + (kX >= 0 ? kX % d : -kX % d ? d - (-kX % d) : 0);
}
if-then-else логика ?: оператор удостоверяется это оба операнда % являются неотрицательными.
Следующее должно работать независимо от реализации оператора Mod:
int range = kUpperBound - kLowerBound + 1;
kx = ((kx-kLowerBound) % range);
if (kx<0)
return kUpperBound + 1 + kx;
else
return kLowerBound + kx;
Преимущество перед другими решениями, что оно использует только единственный % (т.е. подразделение), который делает его довольно эффективным.
Отметьте (вне темы):
Это - хороший пример, почему иногда мудро определить интервалы с верхней границей, являющейся первый элемент не в диапазоне (такой что касается итераторов STL...). В этом случае, оба "+1" исчез бы.
Быстрое решение, наименее гибкое: Используйте в своих интересах собственные типы данных, которые сделают обертывание в аппаратные средства.
Абсолютный самый быстрый метод для обертывания целых чисел должен был бы удостовериться, что Ваши данные масштабируются к int8/int16/int32 или безотносительно собственного типа данных. Затем при необходимости в данных для обертывания, собственный тип данных будет сделан в аппаратных средствах! Очень безболезненный и порядки величины быстрее, чем какое-либо программное обеспечение, переносящее реализацию, замеченную здесь.
Как тематическое исследование в качестве примера:
Я нашел, что это очень полезно, когда мне нужно внедрение FAST sin/cos, реализованного с помощью look-up-table для sin/cos реализации. В основном Вы делаете масштаб Вашими данными таким образом, что INT16_MAX является пи, и INT16_MIN - пи. Затем имейте Вас, установлены пойти.
Как примечание стороны, масштабируя Ваши данные добавит некоторую авансовую конечную стоимость вычисления, которая обычно смотрит что-то как:
int fixedPoint = (int)( floatingPoint * SCALING_FACTOR + 0.5 )
Не стесняйтесь обмениваться интервалом для чего-то еще, что Вы хотите как int8_t / int16_t / int32_t.
Следующее быстрое решение, более гибкое: ультрасовременная операция является медленной вместо этого если возможная попытка использовать битовые маски!
Большинство решений, которые я просмотрел, функционально правильно..., но они зависят от ультрасовременной операции.
Ультрасовременная операция является очень медленной, потому что она по существу делает аппаратное деление. laymans объяснение того, почему модификация и подразделение являются медленными, должно приравнять операцию деления к некоторому псевдокоду for(quotient = 0;inputNum> 0;inputNum -= divisor) { quotient++; } (определение частного и делителя). Как Вы видите, аппаратное деление может быть быстрым, если это - небольшое число относительно делителя..., но подразделение может также быть ужасно медленным, если это намного больше, чем делитель.
Если можно масштабировать данные к питанию два затем, можно использовать немного маски, которая выполнится в одном цикле (на 99% всех платформ), и улучшение скорости будет приблизительно одним порядком величины (по крайней мере в 2 или 3 раза быстрее).
C кодируют для реализации обертывания:
#define BIT_MASK (0xFFFF)
int wrappedAddition(int a, int b) {
return ( a + b ) & BIT_MASK;
}
int wrappedSubtraction(int a, int b) {
return ( a - b ) & BIT_MASK;
}
Не стесняйтесь делать #define чем-то, что является временем выполнения. И не стесняйтесь корректировать битовую маску, чтобы быть безотносительно питания два, что Вам нужно. Как 0xFFFFFFFF или питание два Вы выбираете реализацию.
p.s. Я настоятельно рекомендую читать об обработке фиксированной точки при питании с переносящими/переполненными условиями. Я предлагаю читать:
Вычисления с фиксированной точкой: введение Randy Yates 23 августа 2007