.net - 两组 Int32 - 计算交点的最快方法

Question

我有近 100 万个项目，每个项目都有一组独特的 Int32，我将称之为 idS

每对元素 (1 百万 x (1 百万 -1))
我需要匹配的 idS 计数

这是我现在正在做的

foreach (Item item1 in Items) 
{
    HashSet<Int32> idS1 = item1.idS;
    foreach(Item item2 in Items.Where(x => x.ID > item1.ID)
    {
       HashSet<Int32> idS2 = item2.idS;
       Int32 matchCount = 0;
       if (idS1.Count < idS2.Count)
       {
           foreach(Int32 i1 in idS1) 
               if(idS2.Contains(i1)) matchCount++;
       }
       else 
       {
           foreach(Int32 i2 in idS2) 
               if(idS1.Contains(i2)) matchCount++;
       }
    }
}

有没有更快的方法？
我试过 IntersectWith 并且速度较慢。
我不需要实际的交叉点——只需要计数。

对并行不感兴趣，因为将与生产负载一起运行，因此希望将其限制为单个 CPU

关于排序集还有更多
我对低路口不感兴趣
如果大计数 > 4 * 低计数我不会跳过
当我从 SQL 读入时，我按计数排序
我删除了低计数(我有 3 个滚动组，其中第 2 组是两次计数，第 3 组是计数的 4 倍)
我需要滚动设置只是为了保持在 OOM 下

这就是一切

public void Logon()
{
        sqlCon1 = new SqlConnection(connString);
        sqlCon2 = new SqlConnection(connString);
        sqlCon3 = new SqlConnection(connString);
        try
        {
            sqlCon1.Open();
            sqlCon2.Open();
            sqlCon3.Open();
        }
        catch (SqlException ex)
        {
            MessageBox.Show(ex.Message);
        }
    SqlCommand sqlcmd1 = sqlCon1.CreateCommand();
    SqlCommand sqlcmd2 = sqlCon1.CreateCommand();
    SqlCommand sqlcmd3 = sqlCon1.CreateCommand();
    sqlcmd1.CommandText = "SELECT [FTSindexWordOnce].[sID], [FTSindexWordOnce].[wordID], [docSVsys].[textUniqueWordCount]" + Environment.NewLine +
                          "  FROM [FTSindexWordOnce] with (nolock)" + Environment.NewLine +
                          "  JOIN [docSVsys] with (nolock)" + Environment.NewLine +
                          "    ON [docSVsys].[sID] = [FTSindexWordOnce].[sID] " + Environment.NewLine +
                          " WHERE [docSVsys].[textUniqueWordCount] > 10" + Environment.NewLine +
                          " ORDER BY [docSVsys].[textUniqueWordCount] asc, [FTSindexWordOnce].[sID], [FTSindexWordOnce].[wordID]";
    List<DocUniqueWords> docsA = new List<DocUniqueWords>();
    List<DocUniqueWords> docsB = new List<DocUniqueWords>();
    List<DocUniqueWords> docsC = new List<DocUniqueWords>();
    List<DocUniqueWords> docsActive = docsA;
    List<DocUniqueWords> docs0 = new List<DocUniqueWords>();
    List<DocUniqueWords> docs1 = new List<DocUniqueWords>();
    DocUniqueWords doc = new DocUniqueWords(0);
    Int32 sID;
    Int32 textUniqueWordCount;
    Int32 maxTextUniqueWordCount = 20;
    Int32 ccount = 0;
    byte  textUniqueWordIter = 0;
    System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
    sw.Start();
    try
    {
        SqlDataReader rdr = sqlcmd1.ExecuteReader();
        while (rdr.Read())
        {
            textUniqueWordCount = rdr.GetInt32(2);
            if (textUniqueWordCount > maxTextUniqueWordCount)
            {
                System.Diagnostics.Debug.WriteLine("");
                System.Diagnostics.Debug.WriteLine(maxTextUniqueWordCount.ToString() + " " + ccount.ToString()
                                                   + " " + docsA.Count.ToString() + " " + docsB.Count.ToString() + " " + docsC.Count.ToString());
                maxTextUniqueWordCount = maxTextUniqueWordCount * 2;
                ccount = 0;

                sw.Restart();
                ScoreTwo(docs0, docsActive);
                System.Diagnostics.Debug.WriteLine("  ScoreTwo(docs0, docsActive)       ElapsedMilliseconds = " + sw.ElapsedMilliseconds.ToString("N0") + " ElapsedMinutes = " + (sw.ElapsedMilliseconds / 60000m).ToString("N2") + " ElapsedHours = " + (sw.ElapsedMilliseconds / 3600000m).ToString("N2"));
                //System.Diagnostics.Debug.WriteLine("ElapsedMilliseconds = " + sw.ElapsedMilliseconds.ToString("N0"));
                //System.Diagnostics.Debug.WriteLine("");
                sw.Restart();

                ScoreTwo(docs1, docsActive);
                System.Diagnostics.Debug.WriteLine("  ScoreTwo(docs1, docsActive)       ElapsedMilliseconds = " + sw.ElapsedMilliseconds.ToString("N0") + " ElapsedMinutes = " + (sw.ElapsedMilliseconds / 60000m).ToString("N2") + " ElapsedHours = " + (sw.ElapsedMilliseconds / 3600000m).ToString("N2"));
                //System.Diagnostics.Debug.WriteLine("ElapsedMilliseconds = " + sw.ElapsedMilliseconds.ToString("N0"));
                //System.Diagnostics.Debug.WriteLine("");
                sw.Restart();

                ScoreTwo(docsActive, docsActive);
                System.Diagnostics.Debug.WriteLine("  ScoreTwo(docsActive, docsActive)  ElapsedMilliseconds = " + sw.ElapsedMilliseconds.ToString("N0") + " ElapsedMinutes = " + (sw.ElapsedMilliseconds / 60000m).ToString("N2") + " ElapsedHours = " + (sw.ElapsedMilliseconds / 3600000m).ToString("N2"));
                //System.Diagnostics.Debug.WriteLine("ElapsedMilliseconds = " + sw.ElapsedMilliseconds.ToString("N0"));
                //System.Diagnostics.Debug.WriteLine("");
                sw.Restart();

                switch (textUniqueWordIter)
                {
                    case 0:
                        Console.WriteLine("Case 0");
                        textUniqueWordIter = 1;
                        //docsB.Clear();
                        docs0 = docsC;
                        docs1 = docsA;
                        docsActive = docsB;
                        break;
                    case 1:
                        Console.WriteLine("Case 1");
                        textUniqueWordIter = 2;
                        //docsC.Clear();
                        docs0 = docsA;
                        docs1 = docsB;
                        docsActive = docsC;
                        break;
                    case 2:
                        Console.WriteLine("Case 2");
                        textUniqueWordIter = 0;
                        //docsA.Clear();
                        docs0 = docsA;
                        docs1 = docsC;
                        docsActive = docsC;
                        break;
                    default:
                        Console.WriteLine("Default case");
                        break;
                }
                docsActive.Clear();
            }
            sID = rdr.GetInt32(0);
            if (doc.SID != sID)
            {
                if (doc.SID != 0 && doc.Words.Count > 0 && ccount < 100000) docsActive.Add(doc);
                doc = new DocUniqueWords(sID);
                ccount++;
            }
            doc.Words.Add(rdr.GetInt32(1));
        }
        rdr.Close();
        if (doc.Words.Count > 0) docsActive.Add(doc);

        System.Diagnostics.Debug.WriteLine("docs.Count = " + docsActive.Count.ToString("N0"));

        System.Diagnostics.Debug.WriteLine("done");
    }
    catch (SqlException ex)
    {
        MessageBox.Show(ex.Message);
    }

}
public void ScoreTwo(List<DocUniqueWords> docsOuter, List<DocUniqueWords> docsInner)
{   // docsInner is >= wordcount
    System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
    sw.Start();
    foreach (DocUniqueWords d1 in docsOuter)
    {
        //if (d1.SID % 1000 == 0) 
        //    System.Diagnostics.Debug.WriteLine("  d1.SID = " + d1.SID.ToString() + "  ElapsedMilliseconds = " + sw.ElapsedMilliseconds.ToString("N0"));
        if (docsOuter == docsInner)
        {
            foreach (DocUniqueWords d2 in docsInner.Where(x => x.SID < d1.SID))
            {
                Int32 hashMatchCount = 0;
                if(d1.Words.Count<= d2.Words.Count)
                {                          
                    foreach (Int32 d1sID in d1.Words)
                        if (d2.Words.Contains(d1sID)) hashMatchCount++;
                }
                else
                {
                    foreach (Int32 d2sID in d2.Words)
                        if (d1.Words.Contains(d2sID)) hashMatchCount++;
                }
            }
        }
        else
        {
            foreach (DocUniqueWords d2 in docsInner)
            {
                if (d1.Words.Count * 4 >= d2.Words.Count)
                {
                    Int32 hashMatchCount = 0;
                    foreach (Int32 d1sID in d1.Words)
                        if (d2.Words.Contains(d1sID)) hashMatchCount++;
                }
                else
                {
                    Int32 kkk = 0;
                }
            }
        }
    }
}

Answer 1

您似乎认为十字路口很慢，但事实并非如此。

对于百万个项目，可能需要几毫秒。

我不能对你的外循环说同样的话，这会很慢:

foreach (Item item1 in Items) 
{
    HashSet<Int32> idS1 = item1.idS;
    foreach(Item item2 in Items.Where(x => x.ID > item1.ID)
    ...

根据它的声音，O(n^2) 如果我是对的。这里的技巧是预先排序您的项目列表，因此您不需要 Where健康)状况。