Skip to main content

Return to Answer

Post Timeline

added 31 characters in body
Source Link
Ivan Petrov
Ivan Petrov
  • 7.7k
  • 2
  • 16
  • 32

This can be addressed if we introduce some caching on our side with e.g. ConditionalWeakTable<TKey,TValue> for self-cleaning / not causing memory leaks if TSource is reference-type.

This can be addressed if we introduce some caching on our side with e.g. ConditionalWeakTable<TKey,TValue> for self-cleaning / not causing memory leaks.

This can be addressed if we introduce some caching on our side with e.g. ConditionalWeakTable<TKey,TValue> for self-cleaning / not causing memory leaks if TSource is reference-type.

added 2044 characters in body
Source Link
Ivan Petrov
Ivan Petrov
  • 7.7k
  • 2
  • 16
  • 32

EDIT:

As mentioned in the comments - we will necessarily invoke the keySelectors multiple times if there are 3 or more elements that need comparing. See fiddle by T. N.

This can be addressed if we introduce some caching on our side with e.g. ConditionalWeakTable<TKey,TValue> for self-cleaning / not causing memory leaks.

public static class Extensions {
    public static IOrderedEnumerable<TSource> ThenByCustom<TSource, TKey>(
        this IOrderedEnumerable<TSource> source,
        Func<TSource, TKey> keySelector)
        where TSource : class {
        var cache = new ConditionalWeakTable<TSource, StrongBox<TKey>>();
        var customComparer = new KeyComparer<TSource, TKey>(keySelector, cache);
        return source.ThenBy(x => x, customComparer);
    }

    private class KeyComparer<TSource, TKey> : IComparer<TSource>
        where TSource : class {
        private readonly Func<TSource, TKey> _keySelector;
        private readonly IComparer<TKey> _keyComparer;
        private readonly ConditionalWeakTable<TSource, StrongBox<TKey>> _cache;

        public KeyComparer(
            Func<TSource, TKey> keySelector,
            ConditionalWeakTable<TSource, StrongBox<TKey>> cache) {
            _keySelector = keySelector;
            _cache = cache;
            _keyComparer = Comparer<TKey>.Default;
        }

        public int Compare(TSource x, TSource y) {
            var keyX = GetCachedKey(x);
            var keyY = GetCachedKey(y);
            return _keyComparer.Compare(keyX, keyY);
        }

        private TKey GetCachedKey(TSource obj) {
            if (_cache.TryGetValue(obj, out var boxed))
                return boxed.Value;

            var key = _keySelector(obj);
            _cache.Add(obj, new StrongBox<TKey>(key));
            return key;
        }
    }
}

Fiddle with caching

EDIT:

As mentioned in the comments - we will necessarily invoke the keySelectors multiple times if there are 3 or more elements that need comparing. See fiddle by T. N.

This can be addressed if we introduce some caching on our side with e.g. ConditionalWeakTable<TKey,TValue> for self-cleaning / not causing memory leaks.

public static class Extensions {
    public static IOrderedEnumerable<TSource> ThenByCustom<TSource, TKey>(
        this IOrderedEnumerable<TSource> source,
        Func<TSource, TKey> keySelector)
        where TSource : class {
        var cache = new ConditionalWeakTable<TSource, StrongBox<TKey>>();
        var customComparer = new KeyComparer<TSource, TKey>(keySelector, cache);
        return source.ThenBy(x => x, customComparer);
    }

    private class KeyComparer<TSource, TKey> : IComparer<TSource>
        where TSource : class {
        private readonly Func<TSource, TKey> _keySelector;
        private readonly IComparer<TKey> _keyComparer;
        private readonly ConditionalWeakTable<TSource, StrongBox<TKey>> _cache;

        public KeyComparer(
            Func<TSource, TKey> keySelector,
            ConditionalWeakTable<TSource, StrongBox<TKey>> cache) {
            _keySelector = keySelector;
            _cache = cache;
            _keyComparer = Comparer<TKey>.Default;
        }

        public int Compare(TSource x, TSource y) {
            var keyX = GetCachedKey(x);
            var keyY = GetCachedKey(y);
            return _keyComparer.Compare(keyX, keyY);
        }

        private TKey GetCachedKey(TSource obj) {
            if (_cache.TryGetValue(obj, out var boxed))
                return boxed.Value;

            var key = _keySelector(obj);
            _cache.Add(obj, new StrongBox<TKey>(key));
            return key;
        }
    }
}

Fiddle with caching

Source Link
Ivan Petrov
Ivan Petrov
  • 7.7k
  • 2
  • 16
  • 32

I don't claim that this is production-ready, but you can hack it a bit by introducing an extension method such as ThenByCustom which just saves the keySelector and replaces it with x => x. The actual keySelector is used only when comparing values that have the same primary key in a custom comparer.

This is the idea:

public static class Extensions {
    public static IOrderedEnumerable<TSource> ThenByCustom<TSource, TKey>(
        this IOrderedEnumerable<TSource> source,
        Func<TSource, TKey> keySelector) {
        var customComparer = new KeyComparer<TSource, TKey>(keySelector);
        return source.ThenBy(x => x, customComparer);
    }

    private class KeyComparer<TSource, TKey> : IComparer<TSource> {
        private readonly Func<TSource, TKey> _keySelector;
        private readonly IComparer<TKey> _keyComparer;

        public KeyComparer(Func<TSource, TKey> keySelector) {
            _keySelector = keySelector;
            _keyComparer = Comparer<TKey>.Default;
        }

        public int Compare(TSource x, TSource y) {
            return _keyComparer.Compare(_keySelector(x), _keySelector(y));
        }
    }
}

Your (slightly modified) example then:

static void Main() {
    var data = new[]
    {
            new { Name = "Alice", Age = 30 },
            new { Name = "Charlie", Age = 25 },
            new { Name = "Bob", Age = 25 },
        };

    var sorted = data
        .OrderBy(x => Tracer("First criterion", x.Age))
        .ThenByCustom(x => Tracer("Second criterion", x.Name));

    foreach (var item in sorted) {
        Console.WriteLine($"{item.Name} - {item.Age}");
    }
}

static T Tracer<T>(string label, T value) {
    Console.WriteLine($"Computing {label} key: {value}");
    return value;
}

outputs

Computing First criterion key: 30
Computing First criterion key: 25
Computing First criterion key: 25
Computing Second criterion key: Charlie
Computing Second criterion key: Bob
Bob - 25
Charlie - 25
Alice - 30

if you make the age different, you'd see no Tracer calls for the second criterion.