使用枚举限制的按位运算获得反向
Get inverse direction using bitwise operation on enum limits
我觉得我缺少一些对一些看似简单的东西进行位操作的基础知识。
我有一个 1 到 8 之间的整数枚举,表示从网格中的某个位置开始的所有可能的移动向量。
(我想你们中的一些人可能会认识到这个问题)
{
TOP: 1,
TOP_RIGHT: 2,
RIGHT: 3,
BOTTOM_RIGHT: 4,
BOTTOM: 5,
BOTTOM_LEFT: 6,
LEFT: 7,
TOP_LEFT: 8,
}
给定网格上两点之间位置的路径,这些可用于表示沿该路径的移动。
[
{x: 22, y: 30},
{x: 22, y: 29},
{x: 22, y: 28},
{x: 23, y: 27},
{x: 24, y: 26},
{x: 25, y: 25},
{x: 26, y: 25},
{x: 27, y: 24},
{x: 26, y: 23},
{x: 27, y: 22},
{x: 26, y: 22}
]
最终表示为字符串
"1122232827"
如何最好地反转方向?
我一直在尝试不同的按位运算来使它尽可能快,但我无法弄清楚(这是一个很大的瓶颈)。到目前为止,我一直在使用 shorthand if 来检查方向是否超过限制的一半,然后删除或添加一半。但是,我再次感觉到,使用一些按位拼写可以更有效地完成此操作。随意使用下面的代码做任何事情。
注意:查找图、方向向量和获取方向的方法都是常量,不能进行更改。它们实际上是对某个 API 幕后发生的事情的解释,并且可能会更好地实现。
// Enum of vectors
let vectors = {
TOP: 1,
TOP_RIGHT: 2,
RIGHT: 3,
BOTTOM_RIGHT: 4,
BOTTOM: 5,
BOTTOM_LEFT: 6,
LEFT: 7,
TOP_LEFT: 8,
};
_.extend(window, vectors); // Add them to global
// Lookup table for vectors
let dirMap = {
1: { 1: TOP_RIGHT, 0: RIGHT, "-1": BOTTOM_RIGHT },
0: { 1: TOP, "-1": BOTTOM, },
"-1": { 1: TOP_LEFT, 0: LEFT, "-1": BOTTOM_LEFT }
};
// Get the direction key
function getDirection(a, b){
return dirMap[b.x - a.x][a.y - b.y];
}
// Example path
let path = [
{x: 22, y: 30},
{x: 22, y: 29},
{x: 22, y: 28},
{x: 23, y: 27},
{x: 24, y: 26},
{x: 25, y: 25},
{x: 26, y: 25},
{x: 27, y: 24},
{x: 26, y: 23},
{x: 27, y: 22},
{x: 26, y: 22}
];
let strPath = "", strInverted = "";
for(let i = 1, len = path.length; i < len; i++){
let prev = path[i - 1];
let direction = getDirection(prev, path[i]);
let inverse = direction + (direction > 4 ? -4 : 4); // Can I turn this into a bitwise operation?
strPath += direction;
strInverted = inverse + strInverted;
}
console.log("Forward: ", strPath);
console.log("Reverse: ", strInverted);
document.getElementById("forward").innerHTML = strPath;
document.getElementById("reverse").innerHTML = strInverted;
// Just for debugging purposes
function getDirString(dirString){
let arrDir = [];
_.each(dirString, function(c){
let val = parseInt(c), dir = "";
_.find(vectors, function(o, i){ if(o === val){ dir = i; return true; }});
arrDir.push(dir);
});
return arrDir.join(", ");
}
document.getElementById("full_forward").innerHTML = getDirString(strPath);
document.getElementById("full_reverse").innerHTML = getDirString(strInverted);
body{ font-family: Arial, Helvetica, sans-serif; }
#forward:before, #reverse:before, #full_forward:before, #full_reverse:before{
display: inline-block;
margin-right: 1em;
width: 4em;
}
#full_forward, #full_reverse{font-size: 0.7em; white-space: nowrap;}
#forward:before{ content: "Forward:"; }
#reverse:before{ content: "Reverse:"; }
#full_forward:before{ content: "Forward:"; }
#full_reverse:before{ content: "Reverse:"; }
<script src="https://cdn.jsdelivr.net/lodash/2.1.0/lodash.compat.js"></script>
<div id="forward"></div>
<div id="reverse"></div>
<br>
<div id="full_forward"></div>
<div id="full_reverse"></div>
Here's a jsfiddle to play with.
过去一个小时左右我一直盯着白板看
我认为您不需要在这里进行按位运算,实际上我认为一个具有硬编码值的数组可以工作,您只需将其作为索引放入您的值中即可。当然,它的内存效率不高,但您列出的长度只有 8,因此可以忽略不计。
试试这个:
var inverseDirList = [5,6,7,8,1,2,3,4];
var invertedDirection = inverseDirList[direction - 1];
如果你真的不想对方向值做任何算术运算,你可以简单地添加一个存根元素,比如-1,到列表的开头,所以它基本上是从 1 开始的
正如其他人提到的,您可以使用 devTools 来检查性能并进行比较,但是根据这个 Whosebug question/answer JS hash/array 查找具有恒定的时间复杂度
我觉得我缺少一些对一些看似简单的东西进行位操作的基础知识。
我有一个 1 到 8 之间的整数枚举,表示从网格中的某个位置开始的所有可能的移动向量。
(我想你们中的一些人可能会认识到这个问题)
{
TOP: 1,
TOP_RIGHT: 2,
RIGHT: 3,
BOTTOM_RIGHT: 4,
BOTTOM: 5,
BOTTOM_LEFT: 6,
LEFT: 7,
TOP_LEFT: 8,
}
给定网格上两点之间位置的路径,这些可用于表示沿该路径的移动。
[
{x: 22, y: 30},
{x: 22, y: 29},
{x: 22, y: 28},
{x: 23, y: 27},
{x: 24, y: 26},
{x: 25, y: 25},
{x: 26, y: 25},
{x: 27, y: 24},
{x: 26, y: 23},
{x: 27, y: 22},
{x: 26, y: 22}
]
最终表示为字符串
"1122232827"
如何最好地反转方向?
我一直在尝试不同的按位运算来使它尽可能快,但我无法弄清楚(这是一个很大的瓶颈)。到目前为止,我一直在使用 shorthand if 来检查方向是否超过限制的一半,然后删除或添加一半。但是,我再次感觉到,使用一些按位拼写可以更有效地完成此操作。随意使用下面的代码做任何事情。
注意:查找图、方向向量和获取方向的方法都是常量,不能进行更改。它们实际上是对某个 API 幕后发生的事情的解释,并且可能会更好地实现。
// Enum of vectors
let vectors = {
TOP: 1,
TOP_RIGHT: 2,
RIGHT: 3,
BOTTOM_RIGHT: 4,
BOTTOM: 5,
BOTTOM_LEFT: 6,
LEFT: 7,
TOP_LEFT: 8,
};
_.extend(window, vectors); // Add them to global
// Lookup table for vectors
let dirMap = {
1: { 1: TOP_RIGHT, 0: RIGHT, "-1": BOTTOM_RIGHT },
0: { 1: TOP, "-1": BOTTOM, },
"-1": { 1: TOP_LEFT, 0: LEFT, "-1": BOTTOM_LEFT }
};
// Get the direction key
function getDirection(a, b){
return dirMap[b.x - a.x][a.y - b.y];
}
// Example path
let path = [
{x: 22, y: 30},
{x: 22, y: 29},
{x: 22, y: 28},
{x: 23, y: 27},
{x: 24, y: 26},
{x: 25, y: 25},
{x: 26, y: 25},
{x: 27, y: 24},
{x: 26, y: 23},
{x: 27, y: 22},
{x: 26, y: 22}
];
let strPath = "", strInverted = "";
for(let i = 1, len = path.length; i < len; i++){
let prev = path[i - 1];
let direction = getDirection(prev, path[i]);
let inverse = direction + (direction > 4 ? -4 : 4); // Can I turn this into a bitwise operation?
strPath += direction;
strInverted = inverse + strInverted;
}
console.log("Forward: ", strPath);
console.log("Reverse: ", strInverted);
document.getElementById("forward").innerHTML = strPath;
document.getElementById("reverse").innerHTML = strInverted;
// Just for debugging purposes
function getDirString(dirString){
let arrDir = [];
_.each(dirString, function(c){
let val = parseInt(c), dir = "";
_.find(vectors, function(o, i){ if(o === val){ dir = i; return true; }});
arrDir.push(dir);
});
return arrDir.join(", ");
}
document.getElementById("full_forward").innerHTML = getDirString(strPath);
document.getElementById("full_reverse").innerHTML = getDirString(strInverted);
body{ font-family: Arial, Helvetica, sans-serif; }
#forward:before, #reverse:before, #full_forward:before, #full_reverse:before{
display: inline-block;
margin-right: 1em;
width: 4em;
}
#full_forward, #full_reverse{font-size: 0.7em; white-space: nowrap;}
#forward:before{ content: "Forward:"; }
#reverse:before{ content: "Reverse:"; }
#full_forward:before{ content: "Forward:"; }
#full_reverse:before{ content: "Reverse:"; }
<script src="https://cdn.jsdelivr.net/lodash/2.1.0/lodash.compat.js"></script>
<div id="forward"></div>
<div id="reverse"></div>
<br>
<div id="full_forward"></div>
<div id="full_reverse"></div>
Here's a jsfiddle to play with.
过去一个小时左右我一直盯着白板看
我认为您不需要在这里进行按位运算,实际上我认为一个具有硬编码值的数组可以工作,您只需将其作为索引放入您的值中即可。当然,它的内存效率不高,但您列出的长度只有 8,因此可以忽略不计。
试试这个:
var inverseDirList = [5,6,7,8,1,2,3,4];
var invertedDirection = inverseDirList[direction - 1];
如果你真的不想对方向值做任何算术运算,你可以简单地添加一个存根元素,比如-1,到列表的开头,所以它基本上是从 1 开始的
正如其他人提到的,您可以使用 devTools 来检查性能并进行比较,但是根据这个 Whosebug question/answer JS hash/array 查找具有恒定的时间复杂度