如何使用可用内存有效地比较 1,000 张图像

这是一个棘手的问题。我的磁盘中存储了大约 1,000 张图像，我想通过成对比较来找到彼此相似的图像。所以我必须做周围1,000 * 999 / 2 https://stackoverflow.com/questions/46958633/generate-unique-combinations-of-integers= 499,500 次比较（“相似”属性不具有传递性）。我的问题与如何比较图像无关，而是与如何在比较过程中有效管理机器的内存有关。我已经实现了比较功能：

static bool AreSimilar(ImageInfo x, ImageInfo y)
{
    // Logic
}

...在哪里ImageInfo是一个保存一张图像信息的类：

class ImageInfo : IDisposable
{
    public string Path { get; init; }
    public System.Drawing.Image Image { get; init; }
    public void Dispose() => Image.Dispose();
}

理想情况下，我想将所有 1,000 个图像加载到内存中，然后执行嵌套循环并调用AreSimilar方法，但一次加载所有它们所需的内存远远超出了我的机器的可用内存。图像文件非常大，并且大小差异很大（大多数大小在 5 到 50 MB 之间）。可用 RAM 为 2 GB，因此我不能同时加载超过 80 个图像。从磁盘加载图像非常慢。实际上，从磁盘加载两个图像比比较它们要慢得多 并找出它们是否相似。

我的问题是如何实现一种方法，该方法负责从磁盘加载/卸载图像，并成对生成它们，同时利用所有可用内存，但不超过内存限制。这是我尝试实现的方法的签名：

static IEnumerable<(TItem, TItem)> GetPairs<TSource, TItem>(
    IReadOnlyList<TSource> source,
    Func<TSource, long> sizeSelector,
    Func<TSource, TItem> itemLoader,
    long maxConcurrentSize) where TItem : IDisposable;

The TSource将是文件的路径，并且TItem将是一个ImageInfo。我打算这样使用它：

string[] paths = Directory.GetFiles(@"C:\Images", "*.jpg");
var pairs = GetPairs(paths,
    path => new FileInfo(path).Length,
    path => new ImageInfo() { Path = path, Image = Image.FromFile(path) },
    2_000_000_000);
foreach (var (x, y) in pairs)
{
    if (AreSimilar(x, y))
        Console.WriteLine($"{x.Path} and {y.Path} are similar!");
}

我目前不知道如何实现这个方法。这看起来是一项严肃的任务。我现在拥有的只是下面的简单版本，它成对加载图像并忽略sizeSelector and maxConcurrentSize参数：

static IEnumerable<(TItem, TItem)> GetPairs<TSource, TItem>(
    IReadOnlyList<TSource> source,
    Func<TSource, long> sizeSelector,
    Func<TSource, TItem> itemLoader,
    long maxConcurrentSize) where TItem : IDisposable
{
    for (int i = 0; i < source.Count; i++)
    {
        using var first = itemLoader(source[i]);
        for (int j = i + 1; j < source.Count; j++)
        {
            using var second = itemLoader(source[j]);
            yield return (first, second);
        }
    }
}

显然，性能很糟糕，因为每个图像平均加载约 500 次。

这是一个适合您的问题的解决方案，其中包含单元测试。不幸的是，在一次只能加载少量图像的情况下，它的性能很差，导致最坏的情况是加载数量是您建议的解决方案的 2 倍。然而，当一次可以加载大量图像时，该算法开始优于您的算法，随着允许的内存大小的增加，每个图像的加载次数限制为 1 次。

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace UnitTest;


[TestClass]
public class TestComparison
{
    [TestMethod]
    public void Test()
    {
        const int imageCount = 10;
        var (totalLoads, max, pairs) = RunTest(1, 5, 1000, imageCount);
        Assert.AreEqual(10, totalLoads);
        Assert.AreEqual(1, max);

        (_, max, var pairs2) = RunTest(5, 5, 12, imageCount);
        Assert.AreEqual(9, max);

        var expectedPairs = (imageCount - 1) * imageCount / 2;
        Assert.AreEqual(expectedPairs, pairs.Count);
        Assert.AreEqual(expectedPairs, pairs2.Count);
    }

    private (int totalLoads, int maxLoads, List<(ImageInfo, ImageInfo)> pairs) RunTest(int minImageSize, int maxImageSize, long memorySize, int imageCount)
    {
        var images = GenerateImages(imageCount, minImageSize, maxImageSize);
        var paths = images.Keys.ToList();
        var imageLoadCounts = new Dictionary<string, int>();
        var pairs = GetPairs(paths,p=>images[p].Size,LoadImage,memorySize).ToList();

        var totalLoads = imageLoadCounts.Values.Sum();
        var maxLoad = imageLoadCounts.Values.Max();
        return new(totalLoads, maxLoad,pairs);

        ImageInfo LoadImage(string path)
        {
            if (!imageLoadCounts.TryGetValue(path, out int count))
            {
                count = 0;
            }

            count++;
            imageLoadCounts[path] = count;

            return images[path];
        }
    }

    private Dictionary<string, ImageInfo> GenerateImages(int imageCount, int minImageSize, int maxImageSize)
    {
        var images = new Dictionary<string,ImageInfo>();
        for (int i = 0; i < imageCount; i++)
        {
            images[RandomString()] = new() { Value = _random.NextSingle(), Size = _random.Next(minImageSize, maxImageSize) };
        }

        return images;
    }

    class ImageInfo:IDisposable
    {
        public int Size { get; set; }
        public float Value { get; set; }

        public void Dispose()
        {
        }
    }

    private static readonly Random _random = new();


    static string RandomString()
    {
        const int length = 10;
        var str = string.Empty;
        for (int i = 0; i < length; i++)
        {
            str += (char)_random.Next(65, 90);
        }

        return str;
    }



    static bool AreSimilar(ImageInfo x, ImageInfo y) => Math.Abs(y.Value-x.Value)<.1f;
    record Comparison<T>(T Path1, T Path2)
    {
        public bool Contains(T path) => Path1.Equals(path) || Path2.Equals(path);


        public T Other(T path)
        {
            if (Path1.Equals(path)) return Path2;
            if (Path2.Equals(path)) return Path1;
            throw new Exception("invalid path");
        }

        public bool IsEquivalentTo(Comparison<T> other) => (other.Path1.Equals(Path1) && other.Path2.Equals(Path2)) ||
                                                           (other.Path2.Equals(Path1) && other.Path1.Equals(Path2));
    }
    static IEnumerable<(TItem, TItem)> GetPairs<TSource, TItem>(
        IReadOnlyList<TSource> source,
        Func<TSource, long> sizeSelector,
        Func<TSource, TItem> itemLoader,
        long maxConcurrentSize) where TItem : IDisposable
    {

        var itemCount = source.Count;
        var comparisons = new List<Comparison<TSource>>(itemCount * itemCount / 2);
        for (int i = 0; i < itemCount - 1; i++)
        {
            for (int j = i + 1; j < itemCount; j++)
            {
                comparisons.Add(new(source[i], source[j]));
            }
        }

        return GetPairs(comparisons,sizeSelector,itemLoader,maxConcurrentSize);
    }

    static IEnumerable<(TItem, TItem)> GetPairs<TSource,TItem>(List<Comparison<TSource>> remainingComparisons,
        Func<TSource, long> sizeSelector,
        Func<TSource, TItem> itemLoader,
        long maxConcurrentSize) where TItem:IDisposable
    {
        if(!remainingComparisons.Any()) yield break;
        var images = LoadImages(remainingComparisons,sizeSelector,itemLoader,maxConcurrentSize);//load as many images as possible from the remaining comparisons
        var imageCount = images.Count;
        for (int i = 0; i < imageCount - 1; i++)
        {
            var (path1, image1) = images[i];
            for (int j = i + 1; j < imageCount; j++)
            {
                var (path2, image2) = images[j];
                yield return new(image1, image2);
                var comparison = new Comparison<TSource>(path1, path2);
                remainingComparisons.RemoveAll(c => c.IsEquivalentTo(comparison));
            }
        }

        //dispose
        foreach (var image in images.Select(i => i.Image))
        {
            image.Dispose();
        }

        images = null;//allow GC
        foreach (var pair in GetPairs(remainingComparisons,sizeSelector,itemLoader,maxConcurrentSize))
        {
            yield return pair;
        }
    }

    /// <summary>
    /// Loads as many images into memory as possible from the remaining comparison list
    /// </summary>
    static List<(TSource Path, TITem Image)> LoadImages<TSource,TITem>(List<Comparison<TSource>> remainingComparisons, Func<TSource, long> sizeSelector,
        Func<TSource, TITem> itemLoader,
        long maxConcurrentSize)
    {
        var availableMemory = maxConcurrentSize;
        remainingComparisons = remainingComparisons.ToList();//copy the list so we can alter it in local scope
        var loadedImages = new List<(TSource Path, TITem Image)>();
        if (!TryGetSeed(out var seed)) throw new Exception("One of the images is too large to load into memory");
        while (remainingComparisons.Any())
        {
            if (!remainingComparisons.TryGetFirst(c => c.Contains(seed),out var comparison ))
            {
                if (!TryGetSeed(out seed)) break;
                continue;
            }

            var other = comparison.Other(seed);
            remainingComparisons.Remove(comparison);
            if (!TryLoad(other)) break;

        }

        return loadedImages;

        bool TryLoad(TSource path)
        {
            var fileSize = sizeSelector(path);
            if (fileSize > availableMemory) return false;
            loadedImages.Add(new(path, itemLoader(path)));
            availableMemory -= fileSize;
            return true;
        }

        bool TryGetSeed(out TSource seed)
        {
            //first, remove any comparisons that are relevant to the current loaded list
            var loadedImageCount = loadedImages.Count;
            for (int i = 0; i < loadedImageCount-1; i++)
            {
                for (int j = 1; j < loadedImageCount; j++)
                {
                    var localComparison = new Comparison<TSource>(loadedImages[i].Path, loadedImages[j].Path);
                    remainingComparisons.RemoveAll(c => c.IsEquivalentTo(localComparison));
                }
            }

            if (!remainingComparisons.TryGetFirst(out var firstRemaining))
            {
                seed = default;
                return false;
            }

            seed = firstRemaining.Path1;
            return TryLoad(seed);
        }

  


    }
}
public static class Extensions
{
    public static bool TryGetFirst<T>(this IEnumerable<T> items, out T value) =>
        items.TryGetFirst(t => true, out value);
    public static bool TryGetFirst<T>(this IEnumerable<T> items, Predicate<T> condition, out T value)
    {
        foreach (var item in items)
        {
            if (condition(item))
            {
                value = item;
                return true;
            }
        }
        value = default;
        return false;
    }
}

为了回答你的问题，忽略了时间复杂度。目前的实施TryGetSeed使得时间复杂度为O(N^3)，但这可以很容易地改进。我怀疑可以在 O(N^2) 时间内编写相同的算法，这是该问题的最佳时间复杂度。