c#中嵌套循环中的循环优化

本文关键字：优化 循环 嵌套循环 | 更新日期: 2023-09-27 18:16:49

我正在比较从二进制文件生成的两个数据列表。我很清楚为什么它运行缓慢，当有大量记录时，它会做不必要的冗余工作。

例如:a1 = a1, condition为真。既然2a = 1a，那为什么还要检查呢?我需要从再次检查中消除1a。如果没有，它将在检查第40万条记录时检查第一条记录。我想让第二个for循环foreach，但我不能删除1a，而通过嵌套循环迭代

可以在两个'for循环'中的项的数量是不同的。我不认为使用' I '的单个for循环会起作用，因为匹配可以在任何地方。我正在读取二进制文件

这是我当前的代码。程序已经运行了一个多小时了，还在继续。出于可读性的考虑，我删除了很多迭代代码。

   for (int i = 0; i < origItemList.Count; i++)
    {
        int modFoundIndex = 0;
        Boolean foundIt = false;
        for (int g = 0; g < modItemList.Count; g++)
        {
            if ((origItemList[i].X == modItemList[g].X)
                && (origItemList[i].Y == modItemList[g].Y)
                && (origItemList[i].Z == modItemList[g].Z)
                && (origItemList[i].M == modItemList[g].M))
            {
            foundIt = true;
            modFoundIndex = g;
            break;
            }
            else
            {
                foundIt = false;
            }
        }
        if (foundIt)                         
        {
            /*
             * This is run assumming it finds an x,y,z,m 
             coordinate. It thenchecks the database file.
             * 
             */
            //grab the rows where the coordinates match 
            DataRow origRow = origDbfFile.dataset.Tables[0].Rows[i];
            DataRow modRow = modDbfFile.dataset.Tables[0].Rows[modFoundIndex];
            //number matched indicates how many columns were matched
            int numberMatched = 0;
            //get the number of columns to match in order to detect all changes
            int numOfColumnsToMatch = origDbfFile.datatable.Columns.Count;
            List<String> mismatchedColumns = new List<String>();
            //check each column name for a change
            foreach (String columnName in columnNames)
            {
                //this grabs whatever value is in that field                            
                String origRowValue = "" + origRow.Field<Object>(columnName);
                String modRowValue = "" + modRow.Field<Object>(columnName);
                //check if they are the same
                if (origRowValue.Equals(modRowValue))
                {
                    //if they aren the same, increase the number matched by one
                    numberMatched++;
                    //add the column to the list of columns that don't match
                }
                else
                {
                    mismatchedColumns.Add(columnName);
                }
            }
            /* In the event it matches 15/16 columns, show the change */
            if (numberMatched != numOfColumnsToMatch)
            {
                //Grab the shapeFile in question
                Item differentAttrShpFile = origItemList[i];
                //start blue highlighting
                result += "<div class='turnBlue'>";
                //show where the change was made at
                result += "Change Detected at<br/> point X: " +
                differentAttrShpFile.X + ",<br/> point Y: " +
                    differentAttrShpFile.Y + ",<br/>";
                result += "</div>"; //end turnblue div
                foreach (String mismatchedColumn in mismatchedColumns)
                {
                    //iterate changes here
                }
            }
        }
    }

c#中嵌套循环中的循环优化

你的思路完全错了。你拥有的循环是O(n^2)，当你找到匹配时打破循环会将命中时间缩短一半，这还不够。如果列表中有25万个元素，那么这个循环执行620亿次，即使编译器优化掉了额外的数组查找，你仍然要看至少一万亿条指令。如果可能的话，你不会用O(n^2)来表示大n !

你需要做的是消去它的O(n^2)项。我的建议:

1)定义一个哈希函数，查看x, y, z &M并得到一个整数值，我倾向于使用目标平台的字长。

2)遍历两个列表，计算所有列表的哈希值。

3)建立一个表、哈希和对象的索引。我怀疑字典是这里最好的数据结构，但一个简单的排序数组也可以。

4)遍历没有建立索引的列表，将哈希值与索引中的条目进行比较。如果它是一个哈希值，它是一个O(n)的任务，如果它是一个排序数组，它是O(n log n)。

5)当哈希匹配时，做一个完整的比较来确认命中是真实的，因为你会得到一个好的64位哈希偶尔的碰撞，如果你的哈希是32位的，你会得到一个像样的数字。

这与Loren所说的类似，但下面是。net语言:)
1。重写GetHashCode方法来返回x,y,z和m的总和。重写Equals方法来检查这个总和。
2。在循环之前从modItemList (List)中迭代并创建HashSet。
3。在内部循环中，首先使用YourModHashSet.Contains(MyObject)方法检查HashSet中是否存在origItemList[i]。
4。如果包含返回你的假，携带一个，不匹配。
5。如果. contains返回true，则遍历整个modItemList并应用当前检查整个列表的x,y,z和m的逻辑。请注意，这里应该使用List，因为哈希表可能会吃掉许多哈希码相同的对象。

另外，我会使用Foreach而不是For，因为我看到在这种情况下，Foreach给出了更好的结果(快5到30%)。

更新:


我创建了如下的MyObject类:
 public class MyObject
 {
    public int X, Y, Z, M;
    public override int GetHashCode()
    {
          return X*10000 + Y*100 + Z*10 + M;
    }
    public override bool Equals(object obj)
    {
        return (obj.GetHashCode() == this.GetHashCode());
    }
}

GetHashCode方法在这里很重要。我们不希望有很多误报。当Hash匹配X, Y, Z和m的其他组合时，会出现假阳性。防止假阳性的最佳方法是将每个成员相乘，这样每个成员都会影响HashCode中的一个小数点。注意，您应该考虑不要超过Int。最大价值。如果X,Y,Z和M的期望值很小，你应该是好的。

set2.Clear();
s1 = DateTime.Now;
MyObject matchingElement;
totalmatch = 0;
foreach (MyObject elem in list2)
set2.Add(elem);
foreach (MyObject t1 in list1)
{
if (set2.Contains(t1))
{
    matchingElement = null;
    foreach (MyObject t2 in list2)
    {
        if (t1.X == t2.X && t1.Y == t2.Y && t1.Z == t2.Z && t1.M == t2.M)
        {
            totalmatch++;
            matchingElement = t2;
            break;
        }
    }
    //Do Something on matchingElement if not null
}
}
Console.WriteLine("set foreach with contains: " + (DateTime.Now - s1).TotalSeconds + "'t Total Match: " + totalmatch);

以上是我试图在我的答案中描述的示例代码。

相关文章：