使用嵌套类导出 xml 文件

Question

4per

Asked:2024-12-14 17:51:32 +0000 UTC2024-12-14 17:51:32 +0000 UTC 2024-12-14 17:51:32 +0000 UTC

优化位矩阵中非交集的搜索

772

有一个位表，宽度为一千个元素，行数超过一万行。您需要将行分成一到四个元素的组，其中该组中的每一行在与另一行相同的位置上没有 1 位。

嗯，就是这样。如果宽度为 3 并且有 5 行，

，则输出三组

1）

1 0 0
0 1 0
0 0 1

1 0 1

1 1 1

众所周知，最常见的情况是没有不相交的线，这意味着有多少条线就有多少组。

任务是找到不相交的线并将它们分成四组。只有当由于合适的组溢出而无法堆叠不相交的字符串时，才可以将不相交的字符串最终放入一个字符串的组中。

到目前为止，我只是通过详尽的搜索解决了这个问题https://dotnetfiddle.net/k6tBjL，其中每一行都与其他每一行进行比较（好吧，几乎），这给出了令人不快的性能。

有没有办法降低算法的复杂度并加快这个过程？

4 个回答

Voted

DiD · Answer 1 · 2024-12-23T09:24:05Z

对我来说，BitArray 不太适合这项任务。它将 8 个元素打包到 1 个字节中。每次写入时对每个新元素重复编码，因此每次读取时重复解码。这不能不影响算法的性能。

uint在最简单的情况下，32个元素或16个元素的数组可用于存储1000位ulong。也就是说，uint我们在一个元素中放置 32 位数据。比较它们的不相交非常简单：

我们还按顺序迭代元素。检查可以在任何方向进行，直到找到交叉点。两个数如果其位不相交，则a & b运算时返回0，如果a & b大于0，则可以完成顺序检查。

if ((a[i] & b[i]) != 0) return true;

在单线程测试中，uint它比ulong.根据随机数据，这是单线程中的最佳结果。

但对于有机数据，通过逻辑 OR 使用组的总价值有可能提高生产率。也就是说，首先将字符串与组掩码进行比较，然后与其余字符串进行比较。

最初按汉明权重对字符串进行排序也可能有所帮助。一些非常善良的人从俄语维基百科中删除了一个页面。

Alexander Petrov 在评论中提供了文档的链接。

Также можно подключить параллельную обработку данных с помощью Parallel.ForEach. Тогда для хранения Bucket следует использовать ConcurrentBag. Но по тестам на dotnetfiddle это, очевидно, не даёт никакого прироста к скорости выполнения. По всей видимости, выполнение идёт также в один процесс, но с многопоточным оверхедом.

Так что самый производительный вариант беглых тестов https://dotnetfiddle.net/YuZD30

Скопирую код также сюда.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.Linq;

namespace ConsoleApp16
{
    internal class Program
    {
        static long _comparisons;

        static void Main(string[] args)
        {
            Console.WriteLine("Start Data creation");
            uint[][] data = CreateData();
            Console.WriteLine("Data created");

            Console.WriteLine("Start looking for non-intersected");
            var stopwatch = Stopwatch.StartNew();
            var buckets = GetBuckets(data);
            Console.WriteLine($"Completed looking for non-intersected in {stopwatch.Elapsed}");

            var checkCount = buckets.Sum(x => x.Items.Count());
            Console.WriteLine($"Packed {checkCount} items");

            var grouped = buckets
                .GroupBy(x => x.Items.Count())
                .Select(g => $"{g.Key}-item: {g.Count()} buckets");

            foreach (var g in grouped)
            {
                Console.WriteLine(g);
            }

            var comparisons = _comparisons.ToString("N0", new CultureInfo("en-us"));
            Console.WriteLine($"{comparisons} comparisons");
        }

        private static List<Bucket> GetBuckets(uint[][] data)
        {
            List<Bucket> buckets = new List<Bucket>(data.Length);

            foreach (var item in data)
            {
                bool added = false;

                foreach (var bucket in buckets)
                {
                    if (bucket.IsFull) continue;

                    bool intersected = false;
                    foreach (var other in bucket.Items)
                    {
                        if (AreIntersected(item, other))
                        {
                            intersected = true;
                            break;
                        }
                    }

                    if (!intersected)
                    {
                        bucket.Add(item);
                        added = true;
                        break;
                    }
                }

                if (!added)
                {
                    buckets.Add(new Bucket(item));
                }
            }

            return buckets;
        }

        private static bool AreIntersected(uint[] bitArray, uint[] otherBitArray)
        {
            _comparisons++;

            for (int i = 0; i < bitArray.Length; i++)
            {
                if ((bitArray[i] & otherBitArray[i]) != 0)
                {
                    return true;
                }
            }
            return false;
        }

        private static uint[][] CreateData()
        {
            const int itemCount = 10_000;
            const int bitCount = 1_000;
            const int uintCount = (bitCount + 31) / 32; // 32 uints for 1000 bits

            var result = new uint[itemCount][];
            Random random = new Random();

            for (int i = 0; i < itemCount; i++)
            {
                var uintArray = new uint[uintCount];

                for (int j = 0; j < uintCount; j++)
                {
                    uintArray[j] = (uint)random.Next(0, int.MaxValue);
                }
                result[i] = uintArray;
            }

            return result;
        }
    }

    internal class Bucket
    {
        public bool IsFull => Items.Length == 4;
        public uint[][] Items { get; private set; }

        public Bucket(uint[] firstItem)
        {
            Items = new[] { firstItem };
        }

        public void Add(uint[] nextItem)
        {
            if (Items.Length == 4)
            {
                throw new InvalidOperationException("Bucket is full");
            }

            var newItems = new uint[Items.Length + 1][];
            Items.CopyTo(newItems, 0);
            newItems[^1] = nextItem;
            Items = newItems;
        }
    }
}

4per · Answer 2 · 2024-12-17T16:46:47Z

答案的本质是，即使是完整的搜索也可以通过不同的方式完成。

而提高暴力破解的魔杖就是BitArray（感谢Alexander Petrov的提醒）。

因此我们有 N (10,000) 行和 M (1000) 列。

所以这完全是矫枉过正N*N*M，但有一个细微差别。

解决方案0。由问题中的链接给出。

这里我只使用BitArray来存储行，但没有使用它的操作。我将每一行与每一行进行比较，并且在每次这样的比较中，我用来比较行的单元格。

在我看来， for 更快BitArray.And，但这仅在理想情况下成立，即单元格中的匹配项位于行的开头。

解决方案 1. 使用比较字符串`BitArray.And`。

在一般情况下，我们的生产力得到了提高，因为即使它在这里N*N*M，它*M也很便宜，因为BitArray.And

解决方案 2：添加启发式方法。

如何改进N*N[*M]？

您可以稍微减少第一个因素。我们找到 1 数量最多的列，并立即将带有 1 的行放入组中。

接下来，我们只运行剩余的行，并将每一行与组中的所有内容进行比较。

这就是我们得到的方式(N-X)*N[*M]，如果 X 很大，那么我们就会有明显的增益。

解决方案 3. 如果我们让它更便宜怎么`N`办`M`？

我们转置表并为每一列获取一个 BitArray。我们正在彻底改变算法。我们遍历行，并连接所有具有 1 到的列BitArray.Or。接下来，我们运行生成的 BitArray，并将包含 0 的行添加到组中（直到该组已满）。

这从根本上加快了执行时间。我选择了这个选项。

代码与解决方案https://dotnetfiddle.net/6PzuIr

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Globalization;

namespace ConsoleApp16;

internal class Program
{
    static long _comparisons;

    static void Main(string[] args)
    {
        Console.WriteLine("Start Data creation");
        BitArray[] data = CreateData();
        Console.WriteLine("Data created");

        Console.WriteLine("Start looking for non-intersected");
        var stopwatch = Stopwatch.StartNew();
        var buckets = GetBuckets_ColumnMode(data);
        Console.WriteLine($"Completed looking for non-intersected in {stopwatch.Elapsed}");

        var checkCount = buckets.Sum(x => x.Items.Count());
        Console.WriteLine($"Packed {checkCount} items");

        var grouped = buckets
            .GroupBy(x => x.Items.Count())
            .Select(g => $"{g.Key}-item: {g.Count()} buckets");

        foreach (var g in grouped)
        {
            Console.WriteLine(g);
        }

        var comparisons = _comparisons.ToString("N0", new CultureInfo("en-us"));
        Console.WriteLine($"{comparisons} comparisons");

        Console.ReadKey();
    }

    private static List<Bucket> GetBuckets(BitArray[] data)
    {
        List<Bucket> buckets = new List<Bucket>(data.Length);

        foreach (var bitArray in data)
        {
            bool added = false;
            foreach (var bucket in buckets)
            {
                if (bucket.IsFull) continue;

                bool intersected = false;
                foreach (var otherBitArray in bucket.Items)
                {
                    if (AreIntersected(bitArray, otherBitArray))
                    {
                        intersected = true;
                        break;
                    }
                }

                if (!intersected)
                {
                    bucket.Add(bitArray);
                    added = true;
                    break;
                }
            }

            if (!added)
            {
                buckets.Add(new Bucket(bitArray));
            }
        }

        return buckets;
    }

    private static bool AreIntersected(BitArray bitArray, BitArray otherBitArray)
    {
        _comparisons++;

        var clone = new BitArray(bitArray);
        clone = clone.And(otherBitArray);
        return clone.HasAnySet();

        //for loop is better in edge cases only, when intersections are placed in the very left columns
        //
        //for (int i = 0; i < bitArray.Length; i++)
        //{
        //    if (bitArray[i] && otherBitArray[i])
        //    {
        //        return true;
        //    }
        //}
        //
        //return false;
    }

    private static List<Bucket> GetBuckets_WithHeuristic(BitArray[] data)
    {
        HashSet<int> knownIntersected = GetMaxColumn(data);

        List<Bucket> buckets = new List<Bucket>(data.Length);

        buckets.AddRange(data
            .Select((x, i) => (x, i))
            .Where(y => knownIntersected.Contains(y.i))
            .Select(y => new Bucket(y.x)));

        for (int bitArrayIndex = 0; bitArrayIndex < data.Length; bitArrayIndex++)
        {
            if (knownIntersected.Contains(bitArrayIndex))
            {
                continue;
            }

            bool added = false;
            foreach (var bucket in buckets)
            {
                if (bucket.IsFull) continue;

                bool crossed = false;
                foreach (var otherBitArray in bucket.Items)
                {
                    if (AreIntersected(data[bitArrayIndex], otherBitArray))
                    {
                        crossed = true;
                        break;
                    }
                }

                if (!crossed)
                {
                    bucket.Add(data[bitArrayIndex]);
                    added = true;
                    break;
                }
            }

            if (!added)
            {
                buckets.Add(new Bucket(data[bitArrayIndex]));
            }
        }

        return buckets;
    }

    private static HashSet<int> GetMaxColumn(BitArray[] data)
    {
        HashSet<int>[] columns = new HashSet<int>[data[0].Length];
        for (int col = 0; col < data[0].Length; col++)
        {
            columns[col] = new HashSet<int>(data.Length);
            for (int row = 0; row < data.Length; row++)
            {
                if (data[row][col])
                {
                    columns[col].Add(row);
                }
            }
        }

        return columns.MaxBy(x => x.Count)!;
    }

    private static List<Bucket> GetBuckets_ColumnMode(BitArray[] data)
    {
        Stopwatch sw = Stopwatch.StartNew();
        var columns = Transform(data);
        Console.WriteLine($"Transformed in {sw.Elapsed}");

        var used = new BitArray(data.Length);
        var buckets = new List<Bucket>(data.Length);
        for (int itemIndex = 0; itemIndex < data.Length; itemIndex++)
        {
            if (used[itemIndex])
            {
                continue;
            }
            var item = data[itemIndex];

            var mask = new BitArray(data.Length);
            for (int bitIndex = 0; bitIndex < data[0].Length; bitIndex++)
            {
                if (item[bitIndex])
                {
                    mask = mask.Or(columns[bitIndex]);
                    _comparisons++;
                }
                if (mask.HasAllSet())
                {
                    break;
                }
            }

            used[itemIndex] = true;
            var bucket = new Bucket(item);
            buckets.Add(bucket);

            if (!mask.HasAllSet())
            {
                for (int otherItemIndex = 0; otherItemIndex < data.Length && !bucket.IsFull; otherItemIndex++)
                {
                    if (otherItemIndex == itemIndex || used[otherItemIndex] || mask[otherItemIndex])
                    {
                        continue;
                    }

                    bucket.Add(data[otherItemIndex]);
                    used[otherItemIndex] = true;
                }
            }
        }

        return buckets;
    }

    private static BitArray[] Transform(BitArray[] data)
    {
        var result = new BitArray[data[0].Length];
        for (int row = 0; row < data.Length; row++)
        {
            for (int col = 0; col < data[0].Length; col++)
            {
                result[col] ??= new BitArray(data.Length);
                result[col][row] = data[row][col];
            }
        }
        return result;
    }

    private static BitArray[] CreateData()
    {
        const int itemCount = 10_000;
        const int bitCount = 1_000;

        var result = new BitArray[itemCount];
        for (int i = 0; i < itemCount; i++)
        {
            var bitArray = new BitArray(bitCount);
            for (int j = 0; j < bitCount; j++)
            {
                bitArray.Set(j, Random.Shared.Next(0, 2) == 1); // random
                // bitArray.Set(j, false); // all false, uncomment to have all items intersected
            }
            result[i] = bitArray;
        }

        return result;
    }
}

internal class Bucket
{
    public bool IsFull => Items.Length == 4;
    public BitArray[] Items { get; private set; }

    public Bucket(BitArray firstItem)
    {
        Items = [firstItem];
    }

    public void Add(BitArray nextItem)
    {
        if (Items.Length == 4)
        {
            throw new InvalidOperationException("Bucket is full");
        }

        Items = [.. Items, nextItem];
    }
}

maestro · Answer 3 · 2024-12-18T08:52:32Z

当您检查当前组与新元素的交集时，无需将新元素与该组的所有成员进行比较。相反，组可以存储其所有成员的按位或，然后可以将新元素与按位或进行比较。这将减少比较的次数。

但是，在随机生成位序列的特定示例中，所有元素中都会发生交叉，因此组数始终等于元素数，每组中有一个元素。如果您仍然在实际数据上测试算法，其中实际发生不相交的位序列，那么在将每个新成员添加到组中后，后续比较的次数将会减少。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Globalization;

namespace ConsoleApp16;

internal class Program
{
    static long _comparisons;

    static void Main(string[] args)
    {
        Console.WriteLine("Start Data creation");
        BitArray[] data = CreateData();
        Console.WriteLine("Data created");

        Console.WriteLine("Start looking for non-intersected");
        var stopwatch = Stopwatch.StartNew();
        var buckets = GetBuckets(data);
        Console.WriteLine($"Completed looking for non-intersected in {stopwatch.Elapsed}");

        var checkCount = buckets.Sum(x => x.Items.Count());
        Console.WriteLine($"Packed {checkCount} items");

        var grouped = buckets
            .GroupBy(x => x.Items.Count())
            .Select(g => $"{g.Key}-item: {g.Count()} buckets");

        foreach (var g in grouped)
        {
            Console.WriteLine(g);
        }

        var comparisons = _comparisons.ToString("N0", new CultureInfo("en-us"));
        Console.WriteLine($"{comparisons} comparisons");

        Console.ReadKey();
    }

    private static List<Bucket> GetBuckets(BitArray[] data)
    {
        List<Bucket> buckets = new List<Bucket>(data.Length);

        foreach (var bitArray in data)
        {
            bool added = false;
            foreach (var bucket in buckets)
            {
                if (bucket.IsFull) continue;
                var copy = new BitArray(bucket.or_overall);
                bool intersected = copy.And(bitArray).HasAnySet();
                if (!intersected)
                {
                    bucket.Add(bitArray);
                    added = true;
                    break;
                }
            }
            if (!added)
            {
                buckets.Add(new Bucket(bitArray));
            }
        }

        return buckets;
    }

    private static BitArray[] CreateData()
    {
        const int itemCount = 10_000;
        const int bitCount = 1_000;

        var result = new BitArray[itemCount];
        for (int i = 0; i < itemCount; i++)
        {
            var bitArray = new BitArray(bitCount);
            for (int j = 0; j < bitCount; j++)
            {
                bitArray.Set(j, Random.Shared.Next(0, 2) == 1); // random
                // bitArray.Set(j, false); // all false, uncomment to have all items intersected
            }
            result[i] = bitArray;
        }

        return result;
    }
}

internal class Bucket
{
    public bool IsFull => Items.Length == 4;
    public BitArray[] Items { get; private set; }
    public BitArray or_overall;

    public Bucket(BitArray firstItem)
    {
        Items = [firstItem];
        or_overall = new BitArray(firstItem);
    }

    public void Add(BitArray nextItem)
    {
        if (Items.Length == 4)
        {
            throw new InvalidOperationException("Bucket is full");
        }
        or_overall.Or(nextItem);
        Items = [.. Items, nextItem];
    }
}

sibedir · Answer 4 · 2024-12-18T12:02:03Z

sibedir

2024-12-18T12:02:03Z2024-12-18T12:02:03Z

迭代矩阵并对每行的 1 位求和。

!!!比较位总和 1 大于字符串中位数的字符串的交集是没有意义的

if (Sum[i] + Sum[j] > bitCount) continue;

原则上，您可以按 Sum[i] 排序并仅与的行进行比较Sum[j] <= bitCount - Sum[i]。

或者，

我们创建map，其中键是位 1 的总和，值是一个存储不相交字符串的数量及其并集的结构。
在每次迭代中，我们都会获取具有最大键的记录，并尝试将其与其他记录合并，直到这是可能的或达到最大合并次数 (4)。
我们从地图中删除结果值并将其保存在结果向量中。
重复步骤2直到地图为空

1

优化位矩阵中非交集的搜索

解决方案0。由问题中的链接给出。

解决方案 1. 使用比较字符串`BitArray.And`。

解决方案 2：添加启发式方法。

解决方案 3. 如果我们让它更便宜怎么`N`办`M`？

我看不懂措辞

请求的模块“del”不提供名为“default”的导出

"!+tab" 在 HTML 的 vs 代码中不起作用

我正在尝试解决“猜词”的问题。Python

可以使用哪些命令将当前指针移动到指定的提交而不更改工作目录中的文件？

Python解析野莓

问题：“警告：检查最新版本的 pip 时出错。”

帮助编写一个用值填充变量的循环。解决这个问题

尽管依赖数组为空，但在渲染上调用了 2 次 useEffect

数据不通过 Telegram.WebApp.sendData 发送

优化位矩阵中非交集的搜索

4 个回答

解决方案0。由问题中的链接给出。

解决方案 1. 使用 比较字符串BitArray.And。

解决方案 2：添加启发式方法。

解决方案 3. 如果我们让它更便宜怎么*N办*M？

相关问题

解决方案 1. 使用比较字符串`BitArray.And`。

解决方案 3. 如果我们让它更便宜怎么`N`办`M`？