在列表中查询Array或List
本文关键字:List Array 查询 列表 | 更新日期: 2023-09-27 18:10:09
List<byte> lbyte
byte[] searchBytes
我如何搜索lbyte不只是一个字节,但为搜索字节的索引?
如
Int32 index = lbyte.FirstIndexOf(searchBytes);
这是我想出的蛮力。
不是我想要的表现。
public static Int32 ListIndexOfArray(List<byte> lb, byte[] sbs)
{
if (sbs == null) return -1;
if (sbs.Length == 0) return -1;
if (sbs.Length > 8) return -1;
if (sbs.Length == 1) return lb.FirstOrDefault(x => x == sbs[0]);
Int32 sbsLen = sbs.Length;
Int32 sbsCurMatch = 0;
for (int i = 0; i < lb.Count; i++)
{
if (lb[i] == sbs[sbsCurMatch])
{
sbsCurMatch++;
if (sbsCurMatch == sbsLen)
{
//int index = lb.FindIndex(e => sbs.All(f => f.Equals(e))); // fails to find a match
IndexOfArray = i - sbsLen + 1;
return;
}
}
else
{
sbsCurMatch = 0;
}
}
return -1;
}
暴力总是一种选择。虽然与其他一些方法相比速度较慢,但在实践中通常并不算太糟糕。如果lbyte
不是很大,没有病理数据,这是很容易实现的。
与暴力字符串搜索的概念相同。
您可能会发现Boyer-Moore算法在这里很有用。将列表转换为数组并进行搜索。算法代码取自这篇文章。
static int SimpleBoyerMooreSearch(byte[] haystack, byte[] needle)
{
int[] lookup = new int[256];
for (int i = 0; i < lookup.Length; i++) { lookup[i] = needle.Length; }
for (int i = 0; i < needle.Length; i++)
{
lookup[needle[i]] = needle.Length - i - 1;
}
int index = needle.Length - 1;
var lastByte = needle.Last();
while (index < haystack.Length)
{
var checkByte = haystack[index];
if (haystack[index] == lastByte)
{
bool found = true;
for (int j = needle.Length - 2; j >= 0; j--)
{
if (haystack[index - needle.Length + j + 1] != needle[j])
{
found = false;
break;
}
}
if (found)
return index - needle.Length + 1;
else
index++;
}
else
{
index += lookup[checkByte];
}
}
return -1;
}
你可以像这样搜索。如果lbyte
在一段时间后保持不变,您可以将其转换为一个数组并传递它。
//index is returned, or -1 if 'searchBytes' is not found
int startIndex = SimpleBoyerMooreSearch(lbyte.ToArray(), searchBytes);
根据评论更新。这里是IList
的实现,这意味着数组和列表(以及任何其他实现IList
的东西都可以传递)
static int SimpleBoyerMooreSearch(IList<byte> haystack, IList<byte> needle)
{
int[] lookup = new int[256];
for (int i = 0; i < lookup.Length; i++) { lookup[i] = needle.Count; }
for (int i = 0; i < needle.Count; i++)
{
lookup[needle[i]] = needle.Count - i - 1;
}
int index = needle.Count - 1;
var lastByte = needle[index];
while (index < haystack.Count)
{
var checkByte = haystack[index];
if (haystack[index] == lastByte)
{
bool found = true;
for (int j = needle.Count - 2; j >= 0; j--)
{
if (haystack[index - needle.Count + j + 1] != needle[j])
{
found = false;
break;
}
}
if (found)
return index - needle.Count + 1;
else
index++;
}
else
{
index += lookup[checkByte];
}
}
return -1;
}
由于数组和列表实现了IList,所以在您的例子中调用它时不需要进行转换。
int startIndex = SimpleBoyerMooreSearch(lbyte, searchBytes);
另一种使用lambda表达式的方法
int index = lbyte.FindIndex(e => searchBytes.All(i => i.Equals(e));