الأداء عند التحقق من التكرارات

Question

لقد كنت أعمل في مشروع حيث أحتاج إلى التكرار من خلال مجموعة من البيانات وإزالة الإدخالات حيث يتم تكرار "المفتاح الأساسي".لقد حاولت استخدام أ

List<int>

و

Dictionary<int, bool>

مع القاموس، وجدت أداءً أفضل قليلاً، على الرغم من أنني لا أحتاج مطلقًا إلى العلامة المنطقية مع كل إدخال.أتوقع أن هذا يرجع إلى أن القائمة تسمح بالوصول المفهرس والقاموس لا يسمح بذلك.ما كنت أتساءل عنه هو هل هناك حل أفضل لهذه المشكلة.لا أحتاج إلى الوصول إلى الإدخالات مرة أخرى، أحتاج فقط إلى تتبع "المفاتيح الأساسية" التي رأيتها والتأكد من أنني أقوم فقط بإجراء أعمال الإضافة على الإدخالات التي تحتوي على مفتاح أساسي جديد.أنا أستخدم C# و.NET 2.0.وليس لدي أي سيطرة على إصلاح بيانات الإدخال لإزالة التكرارات من المصدر (للأسف!).وحتى تتمكن من الشعور بالقياس، بشكل عام، أقوم بالتحقق من التكرارات حوالي 1,000,000 مرة في التطبيق، ولكن في مجموعات فرعية لا تزيد عن 64,000 تقريبًا والتي يجب أن تكون فريدة.

Answer 1

لقد قاموا بإضافة فئة HashSet في .NET 3.5.ولكن أعتقد أنه سيكون على قدم المساواة مع القاموس.إذا كان لديك أقل من 100 عنصر، فمن المحتمل أن يكون أداء القائمة أفضل.

Answer 2

يحرر:لا يهم تعليقي.اعتقدت أنك تتحدث عن C++.ليس لدي أي فكرة عما إذا كانت مشاركتي ذات صلة بعالم C#.

يمكن أن يكون جدول التجزئة أسرع قليلاً.تميل الأشجار الثنائية (هذا ما يستخدم في القاموس) إلى أن تكون بطيئة نسبيًا بسبب طريقة الوصول إلى الذاكرة.هذا صحيح بشكل خاص إذا أصبحت شجرتك كبيرة جدًا.

ومع ذلك، قبل أن تقوم بتغيير بنية البيانات الخاصة بك، هل حاولت استخدام مخصص تجمع مخصص لقاموسك؟أراهن أن الوقت لا يقضيه في عبور الشجرة نفسها، بل في ملايين التخصيصات وإلغاء التخصيص التي سيوفرها لك القاموس.

قد ترى عامل زيادة السرعة بمقدار 10 فقط عن طريق توصيل مُخصص تجمع بسيط في قالب القاموس.يحتوي Afaik Boost على مكون يمكن استخدامه مباشرة.

خيار اخر:إذا كنت تعلم بوجود 64.000 إدخالًا فقط في الأعداد الصحيحة، فيمكنك كتابتها في ملف وإنشاء دالة تجزئة مثالية له.وبهذه الطريقة يمكنك فقط استخدام دالة التجزئة لتعيين الأعداد الصحيحة الخاصة بك في النطاق من 0 إلى 64.000 وفهرسة مصفوفة البت.

ربما هي الطريقة الأسرع، ولكنها أقل مرونة.يجب عليك إعادة وظيفة التجزئة المثالية (يمكن إجراؤها تلقائيًا) في كل مرة تتغير فيها مجموعة الأعداد الصحيحة.

Answer 3

أنا لا أفهم حقًا ما تطلبه.

أولا هو عكس ما تقوله.يتمتع القاموس بإمكانية الوصول المفهرسة (هو جدول تجزئة) بينما لا يتمتع de List بذلك.

إذا كانت لديك البيانات في القاموس بالفعل، فستكون جميع المفاتيح فريدة من نوعها، ولا يمكن أن يكون هناك تكرارات.

أظن أن لديك البيانات المخزنة في نوع بيانات آخر وتقوم بتخزينها في القاموس.إذا كان الأمر كذلك فإن إدخال البيانات سيعمل مع قاموسين.

foreach (int key in keys)
{
  if (!MyDataDict.ContainsKey(key))
  {
    if (!MyDuplicatesDict.ContainsKey(key))
      MyDuplicatesDict.Add(key);
  }
  else
    MyDataDict.Add(key); 
}

Answer 4

إذا كنت تتحقق من تفرد الأعداد الصحيحة، وكان نطاق الأعداد الصحيحة مقيدًا بدرجة كافية، فيمكنك فقط استخدام المصفوفة.

للحصول على تعبئة أفضل، يمكنك تنفيذ بنية بيانات نقطية (مصفوفة بشكل أساسي، ولكن كل int في المصفوفة يمثل 32 int في مساحة المفتاح باستخدام 1 بت لكل مفتاح).بهذه الطريقة، إذا كان الحد الأقصى للعدد هو 1,000,000، فستحتاج فقط إلى 30.5 كيلو بايت تقريبًا من الذاكرة لبنية البيانات.

سيكون أداء الصورة النقطية هو O(1) (لكل فحص) وهو أمر يصعب التغلب عليه.

Answer 5

كان هناك سؤال منذ فترة إزالة التكرارات من مجموعة.لغرض السؤال، لم يكن الأداء محل اهتمام كبير، ولكن قد ترغب في إلقاء نظرة على الإجابات لأنها قد تعطيك بعض الأفكار.أيضًا، قد أكون خارج القاعدة هنا، ولكن إذا كنت تحاول إزالة التكرارات من المصفوفة، فإن أمر LINQ مثل لا يحصى.متميز قد يمنحك أداء أفضل من شيء تكتبه بنفسك.كما اتضح أن هناك طريقة للحصول عليها LINQ يعمل على .NET 2.0 لذلك قد يكون هذا طريقًا يستحق التحقيق.

Answer 6

إذا كنت ستستخدم قائمة، استخدم BinarySearch:

 // initailize to a size if you know your set size
List<int> FoundKeys = new List<int>( 64000 );
Dictionary<int,int> FoundDuplicates = new Dictionary<int,int>();

foreach ( int Key in MyKeys )
{
   // this is an O(log N) operation
   int index = FoundKeys.BinarySearch( Key );
   if ( index < 0 ) 
   {
       // if the Key is not in our list, 
       // index is the two's compliment of the next value that is in the list
       // i.e. the position it should occupy, and we maintain sorted-ness!
       FoundKeys.Insert( ~index, Key );
   }
   else 
   {
       if ( DuplicateKeys.ContainsKey( Key ) )
       {
           DuplicateKeys[Key]++;
       }
       else
       {
           DuplicateKeys.Add( Key, 1 );
       }
   } 
} 

يمكنك أيضًا استخدام هذا لأي نوع يمكنك تعريف IComparer له باستخدام التحميل الزائد:BinarySearch( T item, IComparer< T > );