我有近 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;
}
}
}
}
}
最佳答案
您似乎认为十字路口很慢，但事实并非如此。
对于百万个项目，可能需要几毫秒。
我不能对你的外循环说同样的话，这会很慢:
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健康)状况。
关于.net - 两组 Int32 - 计算交点的最快方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28139974/