遍历 1000 个元素的列表 <Byte[]> 的最快方法

Question

我的数据库中有一千个指纹存储在一个Byte[]数组中，我正在尝试对指纹进行1对N验证，这意味着我需要比较传感器给出的指纹和数组中的那些。

但是这个过程花费的时间太长，我正在使用 forEach 循环遍历数组中的所有指纹并调用验证方法来比较 2 个数组以找到匹配项。

有什么方法可以加快查找匹配项的过程？在最坏的情况下，匹配项是数组中的最后一项。或者接近底部。

指纹列表

List<Huellas> ListaHuellas = new List<Huellas>();
public class Huellas 
{
    public int idUsuario;
    public Byte[] Huella;
}

正在搜索匹配项

foreach (Huellas h in ListaHuellas) {
    // Por cada huella... la almacenamos en un MemoryStream como arreglo de bytes.
     MemoryStream fingerprintData = new MemoryStream(h.Huella);
     // Creamos una plantilla a partir de esos bytes...
     DPFP.Template templateIterando = new DPFP.Template(fingerprintData);
     // Extraemos las caracteristicas de la plantilla
     DPFP.FeatureSet features = ExtractFeatures(Sample, DPFP.Processing.DataPurpose.Verification);
     // Verificamos que las caracteristicas sean buenas
     if (features != null) {
        // Compare the feature set with our template
         DPFP.Verification.Verification.Result result = new DPFP.Verification.Verification.Result();
         Verificator.Verify(features, templateIterando, ref result);
         // Y vemos si el resultado es valido o no, (verified)
         // Si es verified, significa que el dedo escaneado ya existia en la base de datos.
         if (result.Verified) {
             MessageBox.Show(new Form { TopMost = true }, "Usuario encontrado: ID " + h.idUsuario);
             // Por ultimo se cierra el programa.
             this.Invoke(new MethodInvoker(delegate { this.Close(); })); 
         }
     }
 }

抱歉西班牙评论。

Answer 1

您可以使用 'Dictionary< long, List< Huellas>>':

对于每个指纹，您从合适的散列函数计算出一个 'long' 值，并将指纹存储在与散列值相关联的列表中（如果您不能保证没有，则需要一个列表已知指纹之间的碰撞）。

当你想搜索指纹时，你计算哈希，从字典中检索关联列表，然后你可以顺序搜索（或使用 parallel.foreach）。

如果你使用一个合适的散列函数，将很少有冲突，列表将主要包含一个元素或最多包含几个元素，因此顺序搜索不会花费很长时间。

注意：即使未知指纹（的哈希值）的列表只包含一个结果，您仍然必须验证实际的字节数组（或提取的特征）：指纹总是有可能是实际上是一个新的，恰好产生与数据库中的指纹之一相同的哈希值。

Answer 2

通过删除永远不匹配的项来减少必须搜索的项数。有很多方法可以做到这一点，但一个例子可能是：

对目标字节数组（您要查找的那个）上的每个字节进行交互。
在每次迭代中，从源列表中删除项目数组中同一索引上的字节与您正在迭代的字节不匹配的所有条目。
重复此操作，直到您拥有一件商品。

这样，您就不会搜索整个数组，而是从一次搜索一个字节开始，并减少搜索的项目数。

如果你想进一步减少这个时间，首先将列表中的字节数组排序并通过字典搜索它们。也就是说，只与中间的项目进行比较，并将列表分成两半，只取你认为匹配的那一半。这样做直到你只有一个项目的一半。这与您尝试在物理词典上搜索单词时所做的相同。首先，你试着打开字典，找到你想找的单词的第一个字母；当您找到以该字母开头的单词时，您会尝试仅查找也与您单词的第二个字母匹配的单词，依此类推。为此，您需要首先对列表进行排序（开头为 {0, 0, 0, ...} 的字节数组，结尾为 {255, 255, 255, ...} 的字节数组） ;

例如，无论数组的长度如何，此算法最多只需要比较具有 65536 项的列表中的 16 个字节。这会非常快。

这只是一个没有任何代码的谈话示例，但我想您明白了。一种简单的方法是创建一个 class 的代表字节数组的名为 FingerPrint 的 GetHashCode() 和 Equals() 方法，然后只使用 HashTable 实例执行搜索。

Answer 3

我的问题是我在 forEach 循环的每次迭代中提取传感器给出的样本指纹的特征。感谢 ainwood 的评论，我将特征提取移到了循环之外，因为我只需要提取样本的特征一次，然后与列表中的指纹进行比较，将最坏情况的时间从 15 秒减少到 2 秒。

遍历 1000 个元素的列表 <Byte[]> 的最快方法

Fastest way to Iterate through a List<Byte[]> of 1000 elements

c#

optimization

foreach

list

fingerprint