C++比较向量，更快的方式

如果有更快的方法从向量列表中找到特定向量？我做矢量比较，这需要永远做，我有数百万记录。C++比较向量，更快的方式

我使用OpenMP

这是我迄今为止

#pragma omp parallel for 
          for(int i=0;i<crossed.size();i++){ 
            #pragma omp flush (exit) 
            if(!exit && (crossed[i]== vectors)){ 

              loop = i; 
              found = true; 
              exit = true; 
              #pragma omp flush (exit) 
            } 
          } 

          if(found == false){ 
            crossed.push_back(vectors); 
            cross.push_back(0); 
          } 
          else{ 
            cross[loop] = cross[loop]+1; 
          }

来源

2014-03-03 Hans

什么问题你在解决？也许有一种数据结构或算法比矢量矢量更适合。也许你可以对数据进行排序，然后进行二分搜索？ – Jens

如果您必须比较这样的多个向量，则可以考虑存储每个向量的哈希信息并比较哈希值。您仍然需要将两个向量与哈希值相等进行比较，但是您可以立即清除不同的哈希值 - 这会为您带来很多速度。 –

我想弄清楚图形是否同构。为了做到这一点，我必须乘以阿尔法向量中的每个点，然后检查是否可以找到重复一次。然后我将它们计数并与其他图形进行比较以找到非同构图。如果你们了解数学，那么找出更快的算法会很有帮助 – Hans

是的，如果你愿意改变你的数据结构的位。

加快比较的一个简单方法是使用校验和。我的意思是，从字面上检查总和。在构建矢量时，保持每个矢量的总和（只要符合数据类型，溢出无关紧要）。然后，而不是比较整个向量，只比较总和 - 如果总和匹配，那么只有比较向量。

走得更远，你可以通过你的校验和排序载体...这可能仅仅是值得的，如果你有很多的载体，因为它从n个减少你校验搜索到的log（n）

来源

2014-03-03 22:22:51

+1 /散列虽然会比总数好。而且，不需要“通过校验和对矢量进行排序” - 只需对单个校验和/矢量ID索引进行排序即可。 –

每次将元素添加到矢量中时，都必须重新计算标准哈希......有数百万个元素，我想你会失去很多时间。 –

一个向量散列，它将所有元素散列*与*相和，这对于该场景是合理的方法...散列方面区分总和弱的情况，例如， {10，-10}对{0,0}，{1,9}对{10}，而总和有助于例如{3，3，3}与{3}。 Trickier具有O（1）cpu和mem方式来生成对处理插入/擦除的命令敏感的值，例如{1,3} vs {3,1}或{1,3,5} vs {5,1,3} - 也可能在相邻元素之间的差异散列中异或（例如，对于上述情况{2} vs { -2}，{2,2} vs {-4,2}） - 虽然有：--(。 –

C++比较向量，更快的方式

回答

相关问题