[.net] उनमें वस्तुओं के क्रम के बावजूद समानता के लिए दो संग्रहों की तुलना करना


Answers

एक सरल और काफी कुशल समाधान दोनों संग्रहों को क्रमबद्ध करना है और फिर समानता के लिए उनकी तुलना करना है:

bool equal = collection1.OrderBy(i => i).SequenceEqual(
                 collection2.OrderBy(i => i));

यह एल्गोरिदम ओ (एन * लॉगएन) है, जबकि ऊपर आपका समाधान ओ (एन ^ 2) है।

यदि संग्रह में कुछ गुण हैं, तो आप एक तेज समाधान को लागू करने में सक्षम हो सकते हैं। उदाहरण के लिए, यदि आपके दोनों संग्रह हैंश सेट हैं, तो उनमें डुप्लीकेट नहीं हो सकते हैं। साथ ही, यह जांच कर रहा है कि हैश सेट में कुछ तत्व बहुत तेज़ है या नहीं। उस स्थिति में आपके जैसा एक एल्गोरिदम संभवतः सबसे तेज़ होगा।

Question

मैं दो संग्रहों (सी # में) की तुलना करना चाहता हूं, लेकिन मुझे यह कुशलतापूर्वक कार्यान्वित करने का सबसे अच्छा तरीका नहीं है।

मैंने Enumerable.SequenceEqual बारे में अन्य धागा पढ़ा है। Enumerable.SequenceEqual , लेकिन यह वही नहीं है जो मैं ढूंढ रहा हूं।

मेरे मामले में, दो संग्रह बराबर होंगे यदि दोनों में एक ही वस्तुएं हों (कोई फर्क नहीं पड़ता)।

उदाहरण:

collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};

collection1 == collection2; // true

मैं आमतौर पर एक संग्रह के प्रत्येक आइटम के माध्यम से लूप करना चाहता हूं और देख सकता हूं कि यह अन्य संग्रह में मौजूद है या नहीं, फिर दूसरे संग्रह के प्रत्येक आइटम के माध्यम से लूप करें और देखें कि यह पहले संग्रह में मौजूद है या नहीं। (मैं लंबाई की तुलना करके शुरू)।

if (collection1.Count != collection2.Count)
    return false; // the collections are not equal

foreach (Item item in collection1)
{
    if (!collection2.Contains(item))
        return false; // the collections are not equal
}

foreach (Item item in collection2)
{
    if (!collection1.Contains(item))
        return false; // the collections are not equal
}

return true; // the collections are equal

हालांकि, यह पूरी तरह से सही नहीं है, और संभवतः समानता के लिए दो संग्रहों की तुलना करने का यह सबसे प्रभावी तरीका नहीं है।

एक उदाहरण मैं सोच सकता हूं कि यह गलत होगा:

collection1 = {1, 2, 3, 3, 4}
collection2 = {1, 2, 2, 3, 4}

जो मेरे कार्यान्वयन के बराबर होगा। क्या मुझे बस प्रत्येक आइटम को मिलने की संख्या की गणना करनी चाहिए और यह सुनिश्चित करना चाहिए कि गणना दोनों संग्रहों में बराबर हो?

उदाहरण किसी प्रकार के सी # में हैं (चलो इसे छद्म-सी # कहते हैं), लेकिन अपनी इच्छा जो भी चाहें उसमें अपना उत्तर दें, इससे कोई फर्क नहीं पड़ता।

नोट: मैंने सादगी के उदाहरणों में पूर्णांक का उपयोग किया, लेकिन मैं संदर्भ-प्रकार की वस्तुओं का भी उपयोग करने में सक्षम होना चाहता हूं (वे कुंजी के रूप में सही तरीके से व्यवहार नहीं करते हैं क्योंकि केवल वस्तु का संदर्भ तुलना की जाती है, सामग्री नहीं)।




प्रकार की एक डुप्लिकेट पोस्ट, लेकिन संग्रह की तुलना करने के लिए मेरा समाधान देखें । यह बहुत आसान है:

आदेश के बावजूद यह समानता तुलना करेगा:

var list1 = new[] { "Bill", "Bob", "Sally" };
var list2 = new[] { "Bob", "Bill", "Sally" };
bool isequal = list1.Compare(list2).IsSame;

यह जांचने के लिए जांच करेगा कि आइटम जोड़े / हटा दिए गए हैं या नहीं:

var list1 = new[] { "Billy", "Bob" };
var list2 = new[] { "Bob", "Sally" };
var diff = list1.Compare(list2);
var onlyinlist1 = diff.Removed; //Billy
var onlyinlist2 = diff.Added;   //Sally
var inbothlists = diff.Equal;   //Bob

यह देखेंगे कि शब्दकोश में कौन सी चीजें बदली गईं:

var original = new Dictionary<int, string>() { { 1, "a" }, { 2, "b" } };
var changed = new Dictionary<int, string>() { { 1, "aaa" }, { 2, "b" } };
var diff = original.Compare(changed, (x, y) => x.Value == y.Value, (x, y) => x.Value == y.Value);
foreach (var item in diff.Different)
  Console.Write("{0} changed to {1}", item.Key.Value, item.Value.Value);
//Will output: a changed to aaa

here मूल पोस्ट।




संपादित करें: जैसे ही मैंने देखा कि यह वास्तव में केवल सेट के लिए काम करता है - यह डुप्लिकेट आइटम वाले संग्रहों से ठीक से निपट नहीं पाएगा। उदाहरण के लिए {1, 1, 2} और {2, 2, 1} को इस एल्गोरिदम के परिप्रेक्ष्य से बराबर माना जाएगा। यदि आपके संग्रह सेट हैं (या उनकी समानता को इस तरह मापा जा सकता है), हालांकि, मुझे आशा है कि आपको नीचे उपयोगी लगेगा।

मैं जिस समाधान का उपयोग करता हूं वह है:

return c1.Count == c2.Count && c1.Intersect(c2).Count() == c1.Count;

लिंक कवर के तहत शब्दकोश की बात करता है, इसलिए यह ओ (एन) भी है। (ध्यान दें, यह ओ (1) है यदि संग्रह एक ही आकार के नहीं हैं)।

मैंने डैनियल द्वारा सुझाए गए "SetEqual" विधि का उपयोग करके एक सैनिटी चेक किया, इगोर द्वारा सुझाए गए ऑर्डरबी / अनुक्रम एक्वल्स विधि और मेरे सुझाव। परिणाम नीचे हैं और मेरे और डैनियल के लिए इगोर और ओ (एन) के लिए ओ (एन * लॉगएन) दिखा रहा है।

मुझे लगता है कि लिंक intersect कोड की सादगी इसे बेहतर समाधान बनाता है।

__Test Latency(ms)__
N, SetEquals, OrderBy, Intersect    
1024, 0, 0, 0    
2048, 0, 0, 0    
4096, 31.2468, 0, 0    
8192, 62.4936, 0, 0    
16384, 156.234, 15.6234, 0    
32768, 312.468, 15.6234, 46.8702    
65536, 640.5594, 46.8702, 31.2468    
131072, 1312.3656, 93.7404, 203.1042    
262144, 3765.2394, 187.4808, 187.4808    
524288, 5718.1644, 374.9616, 406.2084    
1048576, 11420.7054, 734.2998, 718.6764    
2097152, 35090.1564, 1515.4698, 1484.223



static bool SetsContainSameElements<T>(IEnumerable<T> set1, IEnumerable<T> set2) {
    var setXOR = new HashSet<T>(set1);
    setXOR.SymmetricExceptWith(set2);
    return (setXOR.Count == 0);
}

समाधान के लिए .NET 3.5 और System.Collections.Generic आवश्यकता होती है। चयन। System.Collections.Generic नेमस्पेस। माइक्रोसॉफ्ट के मुताबिक , SymmetricExceptWith एक ओ (एन + एम) ऑपरेशन है, एन पहले सेट में तत्वों की संख्या का प्रतिनिधित्व करता है और मीटर दूसरे तत्वों की संख्या का प्रतिनिधित्व करता है। यदि आवश्यक हो तो आप हमेशा इस फ़ंक्शन में समानता तुलनाकर्ता जोड़ सकते हैं।




ओहैडसी के उत्तर का मेरा एक्सटेंशन विधि संस्करण यहां दिया गया है, अगर यह किसी के लिए उपयोगी है

static public class EnumerableExtensions 
{
    static public bool IsEquivalentTo<T>(this IEnumerable<T> first, IEnumerable<T> second)
    {
        if ((first == null) != (second == null))
            return false;

        if (!object.ReferenceEquals(first, second) && (first != null))
        {
            if (first.Count() != second.Count())
                return false;

            if ((first.Count() != 0) && HaveMismatchedElement<T>(first, second))
                return false;
        }

        return true;
    }

    private static bool HaveMismatchedElement<T>(IEnumerable<T> first, IEnumerable<T> second)
    {
        int firstCount;
        int secondCount;

        var firstElementCounts = GetElementCounts<T>(first, out firstCount);
        var secondElementCounts = GetElementCounts<T>(second, out secondCount);

        if (firstCount != secondCount)
            return true;

        foreach (var kvp in firstElementCounts)
        {
            firstCount = kvp.Value;
            secondElementCounts.TryGetValue(kvp.Key, out secondCount);

            if (firstCount != secondCount)
                return true;
        }

        return false;
    }

    private static Dictionary<T, int> GetElementCounts<T>(IEnumerable<T> enumerable, out int nullCount)
    {
        var dictionary = new Dictionary<T, int>();
        nullCount = 0;

        foreach (T element in enumerable)
        {
            if (element == null)
            {
                nullCount++;
            }
            else
            {
                int num;
                dictionary.TryGetValue(element, out num);
                num++;
                dictionary[element] = num;
            }
        }

        return dictionary;
    }

    static private int GetHashCode<T>(IEnumerable<T> enumerable)
    {
        int hash = 17;

        foreach (T val in enumerable.OrderBy(x => x))
            hash = hash * 23 + val.GetHashCode();

        return hash;
    }
}



यदि आप कंधे का उपयोग करते हैं , तो आप ContAllBe का उपयोग कर सकते हैं।

collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};

collection1.ShouldAllBe(item=>collection2.Contains(item)); // true

और अंत में, आप एक एक्सटेंशन लिख सकते हैं।

public static class ShouldlyIEnumerableExtensions
{
    public static void ShouldEquivalentTo<T>(this IEnumerable<T> list, IEnumerable<T> equivalent)
    {
        list.ShouldAllBe(l => equivalent.Contains(l));
    }
}

अद्यतन करें

कंधे विधि पर एक वैकल्पिक पैरामीटर मौजूद है।

collection1.ShouldBe(collection2, ignoreOrder: true); // true



कई मामलों में केवल उपयुक्त उत्तर इगोर ओस्ट्रोव्स्की में से एक है, अन्य उत्तर ऑब्जेक्ट हैश कोड पर आधारित हैं। लेकिन जब आप किसी ऑब्जेक्ट के लिए हैश कोड उत्पन्न करते हैं तो आप केवल अपने IMMUTABLE फ़ील्ड पर आधारित होते हैं - जैसे ऑब्जेक्ट आईडी फ़ील्ड (डेटाबेस इकाई के मामले में) - जब समान विधि ओवरराइड हो जाती है तो GetHashCode को ओवरराइड करना क्यों महत्वपूर्ण है?

इसका अर्थ यह है कि यदि आप दो संग्रहों की तुलना करते हैं, तो परिणाम तुलनात्मक विधि के बारे में भी सही हो सकता है, भले ही विभिन्न वस्तुओं के फ़ील्ड गैर-बराबर हों। गहन तुलना करने के लिए, आपको इगोर की विधि का उपयोग करने और IEqualirity लागू करने की आवश्यकता है।

कृपया मेरी सबसे अधिक पोस्ट की गई पोस्ट पर मेरे और श्रीमान। चेकर्डर की टिप्पणियां पढ़ें।

जेम्स




यह मेरा (डी जेनिंग्स द्वारा अत्यधिक प्रभावित) तुलना विधि (सी # में) के सामान्य कार्यान्वयन है:

/// <summary>
/// Represents a service used to compare two collections for equality.
/// </summary>
/// <typeparam name="T">The type of the items in the collections.</typeparam>
public class CollectionComparer<T>
{
    /// <summary>
    /// Compares the content of two collections for equality.
    /// </summary>
    /// <param name="foo">The first collection.</param>
    /// <param name="bar">The second collection.</param>
    /// <returns>True if both collections have the same content, false otherwise.</returns>
    public bool Execute(ICollection<T> foo, ICollection<T> bar)
    {
        // Declare a dictionary to count the occurence of the items in the collection
        Dictionary<T, int> itemCounts = new Dictionary<T,int>();

        // Increase the count for each occurence of the item in the first collection
        foreach (T item in foo)
        {
            if (itemCounts.ContainsKey(item))
            {
                itemCounts[item]++;
            }
            else
            {
                itemCounts[item] = 1;
            }
        }

        // Wrap the keys in a searchable list
        List<T> keys = new List<T>(itemCounts.Keys);

        // Decrease the count for each occurence of the item in the second collection
        foreach (T item in bar)
        {
            // Try to find a key for the item
            // The keys of a dictionary are compared by reference, so we have to
            // find the original key that is equivalent to the "item"
            // You may want to override ".Equals" to define what it means for
            // two "T" objects to be equal
            T key = keys.Find(
                delegate(T listKey)
                {
                    return listKey.Equals(item);
                });

            // Check if a key was found
            if(key != null)
            {
                itemCounts[key]--;
            }
            else
            {
                // There was no occurence of this item in the first collection, thus the collections are not equal
                return false;
            }
        }

        // The count of each item should be 0 if the contents of the collections are equal
        foreach (int value in itemCounts.Values)
        {
            if (value != 0)
            {
                return false;
            }
        }

        // The collections are equal
        return true;
    }
}



Links