高效的 IP 地址列表

本文关键字：列表 地址 IP 高效 | 更新日期: 2023-09-27 18:20:43

使用IP4地址，显然可以存储32位。我需要跟踪IP列表，这可能是一个相当长的列表，所以希望尽可能保持紧凑。我还需要快速搜索列表，以检查其中是否已加载IP。

我目前正在研究：将 IP 转换为 UInt32，然后将列表存储在 HashSet 中。

我想可能有更好的方法吗？

更新：哈希集当然会生成哈希，这些哈希大于 uint 的 4 个字节。因此，要真正优化这一点，特别是针对IP4地址，需要针对4字节进行优化的类似结构

高效的 IP 地址列表

如果列表相对静态(即不经常更改(，那么数组或List<uint>将是一种非常简单的存储方法。它为您提供 O(log n( 查找与 BinarySearch ，这可能足够快，除非您每秒执行数千次查找。但是，在列表中插入新项是一个 O(n( 操作。如果你必须做很多插入，这不是要走的路。

HashSet<uint>运行良好，查找和插入速度更快。但这会让你付出代价。HashSet<uint>将占用大约 3 倍于List<uint>的内存。

3X 内存使用的理由：

下面的程序分配了一个包含 89,478,457 个项目的List<uint>，这曾经是可以创建的最大大小HashSet。(一直到 .NET 4.0。然后，它用唯一值填充该列表，并从列表中创建一个HashSet<uint>。

程序通过调用 GC.GetTotalMemory(true) 来计算总分配的内存，这会强制垃圾回收。然后，它计算列表和哈希集所需的内存量。

测试使用 .NET 4.5、Visual Studio 2012 运行。在发布模式下运行，无需附加调试器。

我的输出：

Max size = 89,478,457
Starting memory = 53,240
89,000,000
After list populated = 357,967,136
89,478,457 items in the HashSet
After HashSet populated = 1,789,622,704
List occupies 357,913,896
HashSet occupies 1,431,655,568
HashSet occupies 4.00 times the memory of List
Press Enter:

所以我错了...uint是 4 倍.ulong是 3.5 倍.

    private void DoStuff()
    {
        int maxSize = 89478457;
            //89000000;
        Console.WriteLine("Max size = {0:N0}", maxSize);
        var startMem = GC.GetTotalMemory(true);
        Console.WriteLine("Starting memory = {0:N0}", startMem);
        // Initialize a List<long> to hold maxSize items
        var l = new List<uint>(maxSize);
        // now add items to the list
        for (uint i = 0; i < maxSize; i++)
        {
            if ((i % 1000000) == 0)
            {
                Console.Write("'r{0:N0}", i);
            }
            l.Add(i);
        }
        Console.WriteLine();
        var memAfterListAlloc = GC.GetTotalMemory(true);
        Console.WriteLine("After list populated = {0:N0}", memAfterListAlloc);
        // Construct a HashSet from that list
        var h = new HashSet<uint>(l);
        Console.WriteLine("{0:N0} items in the HashSet", h.Count);
        var memAfterHashAlloc = GC.GetTotalMemory(true);
        Console.WriteLine("After HashSet populated = {0:N0}", memAfterHashAlloc);
        var listMem = memAfterListAlloc - startMem;
        var hashMem = memAfterHashAlloc - memAfterListAlloc;
        Console.WriteLine("List occupies {0:N0}", listMem);
        Console.WriteLine("HashSet occupies {0:N0}", hashMem);
        Console.WriteLine("HashSet occupies {0:N2} times the memory of List", (double)hashMem / listMem);
        GC.KeepAlive(l);
        GC.KeepAlive(h);
        Console.Write("Press Enter:");
        Console.ReadLine();
    }
相关文章：