需要有关算法的帮助

Question

我需要一个算法的帮助.我随机生成了6位数字.喜欢;

123654 109431

它们中大约有100万个逐行保存在文件中.我必须根据我在下面尝试描述的规则对它们进行过滤.

拿一个数字,逐个数字地与其他数字进行比较.如果一个数字出现一个比较数字值大一的数字,则将其删除.让我用数字来表示.

我们的号码是:123456用1增加第一个数字,所以数字变为:223456.从文件中删除所有223456.将第二个数字增加1,数字变为:133456.从文件中删除所有133456,依此类推......

我可以像我描述的那样做,但我需要它是"快".

所以有人可以帮我吗？

谢谢.

Answer 1

首先,由于它大约有1M亿,你最好在RAM中执行算法,而不是在磁盘上,即首先将内容加载到数组中,然后修改数组,然后将结果粘贴回文件中.

我会建议以下算法 - 一个简单的算法.预先计算所有目标数字,在本例中为223456,133456,124456,123556,123466,123457.现在传递数组,如果数字不是其中任何一个,则将其写入另一个数组.或者,如果它是这些数字之一删除它(建议如果您的数据结构有O(1)删除)

Answer 2

该算法将在内存中保留大量数字，但它会一次处理一个数字，因此您实际上不需要一次将其全部读入。您只需要提供一个IEnumerable<int>即可运行。

    public static IEnumerable<int> FilterInts(IEnumerable<int> ints)
    {
        var removed = new HashSet<int>();

        foreach (var i in ints)
        {
            var iStr = i.ToString("000000").ToCharArray();

            for (int j = 0; j < iStr.Length; j++)
            {
                var c = iStr[j];

                if (c == '9')
                    iStr[j] = '0';
                else
                    iStr[j] = (char)(c + 1);

                removed.Add(int.Parse(new string(iStr)));

                iStr[j] = c;
            }

            if (!removed.Contains(i))
                yield return i;
        }
    }

IEnumerable<int>您可以使用此方法从文件创建：

    public static IEnumerable<int> ReadIntsFrom(string path)
    {
        using (var reader = File.OpenText(path))
        {
            string line;
            while ((line = reader.ReadLine()) != null)
                yield return int.Parse(line);
        }
    }