8

我在为我的工作编写的程序中遇到了一堵砖墙。您不需要具体了解上下文,但长话短说,我有两个集合,每个集合大约 65 万条记录。

假设集合 A 是我知道是正确的集合,集合 B 是我知道不正确的集合。

集合 B 包含一个复杂对象,该对象具有与集合 A 中的元素相同类型的属性(换句话说,它看起来有点像这样):

// Where T : IComparable
IEnumerable<DateTime> A = ...; // Collection of T elements
IEnumerable<Complex> B = ...; // Collection of complex elements.
class Complex<DateTime>
{
   public DateTime Time { get; set; }
   .....
}

我的问题是我基本上需要依次枚举 A 并查看 A 的当前元素是否存在于 B 中的 Complex 对象中;如果它不存在,那么我需要创建一个 Complex 对象来封装该元素(除其他外)。

当我意识到两个列表的长度约为 650,000 个元素时,就会出现问题。我无法减少数据集;我必须使用这 650,000 个。现在我已经使用ICollection.Contains()了,并且我尝试了二进制搜索的(天真的)实现,但这需要的时间太长了。

你对我有什么建议吗?

编辑:如果有帮助,T 实现 IComparable。EDIT2:更多上下文:使用 Linq To Objects 从 DataTable 中检索 IEnumerable。

        IEnumerable<Complex> set = set.Tbl
            .Where(dbObject => dbObject.TS.CompareTo(default(DateTime)) != 0)
            .Select(Func<DataRow,Complex>) // Function that wraps the DataRow in a Complex object
            // Just done to make debugging a little easier so we still have a large sample but small enough that it doesn't make me grow a beard
            .Take(100000) 
            .AsEnumerable<Complex>();

为了完整起见,以防此问题被存档并且其他任何人都需要解决此问题,我当前的实现看起来有点像这样

        BDataSet bSet = new BDataSet();
        B_LUTableAdapter adap = new B_LUTableAdapter();
        adap.Fill(bSet.B_LU);
        IEnumerable<Complex> w3 = bSet.B
            .Where(dbObject => dbObject.TS.CompareTo(default(DateTime)) != 0)
            // Function that just wraps datarow into a complex object
            .Select(Func<DataRow, Complex>)
            // Just for sake of debugging speed
            .Take(100000)
            .AsEnumerable<Complex>();

        List<Complex> b = bSet.OrderBy(x => x.Time).ToList<Complex>();
        // Get last & first timestamps
        // Some of the timestamps in b are 01/01/1011 for some reason,
        // So we do this check.
        Complex start = b.Where(x => x.Time != default(DateTime)).First();
        Complex end = b.Last();

        List<DateTime> a = new List<DateTime>();
        // RoundSeconds reduces seconds in a DateTime to 0.
        DateTime current = RoundSeconds(new DateTime(start.Time.Ticks));

        while (current.CompareTo(RoundSeconds(end.Time)) <= 0)
        {
            a.Add(current);
            current = current.Add(TimeSpan.FromMinutes(1));
        }

        IEnumerable<DateTime> times = b.Select(x => x.Time);
        var missing = a.Where(dt => times.Contains(dt));
        foreach (var dt in missing)
        {
            adap.Insert(dt, 0, "", "", "", null, 0, 0);
            // This has since been changed to List.Add()
        }

感谢 Cosmin,这个问题现在得到了解决,完成的实现是这样的: List expected = new List(); 当前日期时间 = RoundSeconds(new DateTime(start.Time.Ticks));

        while (current.CompareTo(RoundSeconds(end.Time)) <= 0)
        {
            expected.Add(current);
            current = current.Add(TimeSpan.FromMinutes(1));
        }

        Console.WriteLine("Expecting {0} intervals.", expected.Count);
        var missing = b.FindAllMissing(expected, x => x.Time);
        if(!missing.Any()) return;
        Console.WriteLine("{0} missing intervals.", missing.Count());
        foreach (var dt in missing)
        {
            b.Add(new Complex() { /* some values */ });
            //Console.WriteLine("\t> Inserted new record at {0}", dt);
        }

        //.....
        public static IEnumerable<Basic> FindAllMissing<Basic, Complex>(this IEnumerable<Complex> complexList,
        IEnumerable<Basic> basicList,
        Func<Complex, Basic> selector)
        {
            HashSet<Basic> inComplexList = new HashSet<Basic>();
            foreach (Complex c in complexList)
                inComplexList.Add(selector(c));
            List<Basic> missing = new List<Basic>();
            foreach (Basic basic in basicList)
                if (!(inComplexList.Contains(basic)))
                    missing.Add(basic);
            return missing;
        }
4

5 回答 5

4

一步步:

  • 使用其中一个O(1)通用集合创建T已在第二个集合中的可快速搜索的 ' 列表。我可以建议吗HashSet<T>
  • 枚举 SECOND 集合并将所有的T' 放入第一步中的集合中。
  • 枚举 FIRST 集合并检查每个项目是否在第一步创建的集合中。由于该操作是O(1)您现在有了O(n)解决方案。
  • 享受。

这是一个将该算法实现为通用扩展方法的类,以使其对 LINQ 更加友好。将它的参数作为IEnumerable<T>和 return IEnumerable<T>,对类型 (TComplex) 不做任何假设。在我的测试中,我使用了Tuple<int,int>一个复杂类型的列表和一个简单int的简单类型。控制台应用程序List<Tuple<int,int>>用 600000 个值填充 ,然后将 100000 个值放入使用枚举器计算在;List<int>中找不到的所有简单值的简单值中。List<Tuple<int,int>>它是如此之快,你没有机会看到它在工作,当你点击它时,F5它只会显示结果。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication2
{

    static class FixProblem
    {
        public static IEnumerable<T> FindAllThatNeedCreating<T, Complex>(this IEnumerable<Complex> list_of_complex, IEnumerable<T> list_of_T, Func<Complex, T> extract)
        {
            HashSet<T> T_in_list_of_complex = new HashSet<T>();
            foreach (Complex c in list_of_complex)
                T_in_list_of_complex.Add(extract(c));
            List<T> answer = new List<T>();
            foreach (T t in list_of_T)
                if (!T_in_list_of_complex.Contains(t))
                    answer.Add(t);
            return answer;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            // Test the code
            List<Tuple<int, int>> complex = new List<Tuple<int, int>>();
            List<int> simple = new List<int>();

            // Fill in some random data
            Random rnd = new Random();
            for (int i = 1; i < 600000; i++)
                complex.Add(new Tuple<int, int>(rnd.Next(), rnd.Next()));

            for (int i = 1; i < 100000; i++)
                simple.Add(rnd.Next());

            // This is the magic line of code:
            Console.WriteLine(complex.FindAllThatNeedCreating(simple, x => x.Item1).Count());

            Console.ReadKey();

        }
    }
}
于 2013-10-11T07:56:57.657 回答
0

如果我了解您的要求,那么我认为此代码运行良好。我已将这两个集合的记录提高到 650 万条,并在 11 秒内完成。将其减少到 65 万条记录只需不到一秒钟的时间。

var rnd = new Random();

var xs = Enumerable
    .Range(0, 650000)
    .Select(x => new Complex<int>()
    {
        MyComplex = rnd.Next(0, 100001)
    })
    .ToList();

var ys = Enumerable
    .Range(0, 650000)
    .Select(x => rnd.Next(0, 100001))
    .ToArray();

var xsLookup = xs.ToLookup(x => x.MyComplex);

var newYs = ys.Where(y => !xsLookup[y].Any()).ToArray();

newYs
    .ToList()
    .ForEach(y =>
    {
        xs.Add(new Complex<int>()
        {
            MyComplex = y
        });
    });
于 2013-10-11T08:33:24.093 回答
0

如果您的列表都按相同的键排序,则可以同时遍历两者。这样做我能够将时间缩短到比我看到的 toLookup 时间更少contains甚至except更少的时间。

var A = SimpleCollection; // source of truth
var B = GetComplexOnDemand().ToArray();
var missing = new List<Complex<DateTime>>();
int cpxIx = 0;
int simpleIx = 0;
while (simpleIx < A.Count)
{
    if (cpxIx >= B.Length)
    {
        missing.Add(new Complex<DateTime>() {InnerValue = A[simpleIx]});
        simpleIx++;
        continue;
    }

    if (A[simpleIx] != B[cpxIx].InnerValue)
    {
        missing.Add(new Complex<DateTime>() {InnerValue = A[simpleIx]});
        simpleIx++;
        continue;
    }

    cpxIx++;
    simpleIx++;
}

为了生成测试数据,我执行了以下操作:

private static readonly List<DateTime> SimpleCollection = 
    Enumerable.Range(1, SimpleSize).Select(t => new DateTime(DateTime.Now.Ticks + t)).ToList();
public static IEnumerable<Complex<DateTime>> GetComplexOnDemand()
{
    for (int i = 1; i <= ComplexSize; i+=2)
    {
        yield return new Complex<DateTime>() { InnerValue = SimpleCollection[i] };
    }
}
于 2013-10-11T08:59:50.780 回答
0

我建议将您的复杂对象存储在字典中,使用 A 类型属性作为键。然后您可以非常快速地查看 A 中的任何元素是否存在于 Dictionary 中。每个查找操作将是 O(1),整体性能应该是 O(n)。

或者,您可以在现有的 IEnumerable 上调用 .ToLookup(),并在 lambda 表达式中创建键和值。返回的 ILookup 应该非常适合您的需要(即从 A 中查找值)。此处的另一个优点是,如果您有多个包含 A 的复杂对象,则在使用 Lookup 时将返回它们的集合。

于 2013-10-11T08:02:41.957 回答
0

更新:首先,停止使用数据集。我建议你使用 Linq to SQL 或 Entity Framework。

尝试这个:

        var lookup = B.ToLookup(c => c.MyComplex);

        var noMatch = from a in A
                      where !lookup.Contains(a)
                      select a;

应该更快,但要衡量。

然后尝试

        var lookup = B.AsParallel().ToLookup(c => c.MyComplex);

        var noMatch = from a in A.AsParallel()
                      where !lookup.Contains(a)
                      select a;

并再次测量。

显然,请确保 A 中的对象类型覆盖GetHashCode()Equals(object)正确且有效。特别是GetHashCode()应该有很高的概率不同的对象有不同的哈希码,并且仍然很快。

更新:由于我们现在知道 A 中对象的类型是 DateTime,因此要求GetHashCode()Equals(object)是可以的。

代码变成

        var lookup = B.ToLookup(c => c.Time);

        var noMatch = from a in A
                      where !lookup.Contains(a)
                      select a;
于 2013-10-11T08:10:05.320 回答