كيفية الحصول على أكبر الأرقام من كمية ضخمة من الأرقام؟

Question

أرغب في الحصول على أكبر 100 عنصر من قائمة تحتوي على 100000000 رقم على الأقل.

يمكنني فرز القائمة بأكملها وأخذ آخر 100 عنصر من القائمة التي تم فرزها، لكن ذلك سيكون مكلفًا للغاية من حيث الذاكرة والوقت.

هل هناك أي طريقة سهلة وبيثونية للقيام بذلك؟

ما أريده هو اتباع الوظيفة بدلاً من النوع النقي.في الواقع لا أريد إضاعة الوقت في فرز العناصر التي لا أهتم بها.

على سبيل المثال، هذه هي الوظيفة التي أرغب في الحصول عليها:

getSortedElements(100, lambda x,y:cmp(x,y))

لاحظ أن هذا المتطلب يتعلق فقط بمنظور الأداء.

Answer 1

وحدة heapq في المكتبة القياسية توفر وظيفة nlargest () للقيام بذلك:

top100 = heapq.nlargest(100, iterable [,key])

وانها لن فرز القائمة بأكملها، لذلك سوف لا تضيعوا الوقت على العناصر التي لا تحتاج إليها.

Answer 2

خوارزميات اختيار أن تساعد هنا.

وهناك حل سهل جدا هو العثور على أكبر عنصر 100th، ثم تشغيلها من خلال قائمة اصطياد العناصر التي هي أكبر من هذا العنصر. والتي تعطيك أكبر 100 عناصر. هذا هو خطي في طول القائمة؛ هذا هو أفضل ما يمكن.

وهناك خوارزميات أكثر تطورا. A كومة ، على سبيل المثال، غير قابلة للغاية لهذه المشكلة. وn log k خوارزمية مقرها كومة حيث n هو طول القائمة وk هو عدد أكبر العناصر التي تريد تحديدها.

ومن هناك مناقشة هذا على صفحة ويكيبيديا عن خوارزمية الاختيار.

وتحرير: وأشار ملصق آخر إلى أن بيثون وقد بنيت في حل لهذه المشكلة. ومن الواضح أن هذا هو أسهل بكثير من المتداول بنفسك، ولكن سوف استمر هذا الرد حتى في حال كنت ترغب في معرفة المزيد عن كيفية عمل هذه الخوارزميات.

Answer 3

ويمكنك استخدام بنية بيانات كومة. وليس بالضرورة أن يؤمر كومة، وإنما هو وسيلة سريعة إلى حد ما للحفاظ على البيانات شبه أمر، ولها مصلحة من أصغر عنصر يجري دائما العنصر الأول في كومة.

وكومة اثنين من العمليات الأساسية التي ستساعدك: إضافة واستبدال

وأساسا ما عليك فعله هو إضافة عناصر إلى أنه حتى تحصل على 100 وحدات (الخاص أعلى عدد N في سؤالك). ثم بعد ذلك، يمكنك استبدال البند الأول مع كل عنصر جديد، طالما أن العنصر الجديد هو أكبر من العنصر الأول.

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

Answer 4

أفضل طريقة للقيام بذلك هي الحفاظ على قائمة انتظار ذات أولوية مرتبة في الكومة والتي تنبثق منها بمجرد أن تحتوي على 100 إدخال.

على الرغم من أنك لا تهتم إذا تم فرز النتائج، فمن الواضح أنك ستحصل على هذا مجانًا.لكي تعرف أن لديك أعلى 100 رقم، تحتاج إلى ترتيب قائمتك الحالية لأعلى الأرقام بالترتيب من خلال بنية بيانات فعالة.ستعرف هذه البنية الحد الأدنى والحد الأقصى والموضع النسبي لكل عنصر بطريقة طبيعية يمكنك من خلالها تأكيد موقعه بجوار جيرانه.

كما ذكرنا في بايثون، ستستخدم heapq.في قائمة انتظار الأولوية جافا:http://java.sun.com/javase/6/docs/api/Java/util/PriorityQueue.html

Answer 5

وهنا هو الحل لقد استخدمت مستقلة عن المكتبات وأن ستعمل في أي لغة البرمجة التي لديها صفائف:

وInitialisation:

Make an array of 100 elements and initialise all elements
with a low value (less than any value in your input list).

Initialise an integer variable to 0 (or any value in
[0;99]), say index_minvalue, that will point to the
current lowest value in the array.

Initialise a variable, say minvalue, to hold the current 
lowest value in the array.

لكل قيمة، ويقول current_value، في قائمة المدخلات:

if current_value > minvalue

  Replace value in array pointed to by index_minvalue
  with current_value

  Find new lowest value in the array and set index_minvalue to
  its array index. (linear search for this will be OK as the array
  is quickly filled up with large values)

  Set minvalue to current_value

else
  <don't do anything!>

وMINVALUE سوف بسرعة الحصول على قيمة عالية، وبالتالي معظم القيم في قائمة المدخلات سوف تحتاج فقط إلى أن مقارنة MINVALUE (نتيجة المقارنة ستكون في الغالب كاذبة).

Answer 6

لوweenies الخوارزميات في الجمهور: يمكنك أن تفعل هذا مع اختلاف بسيط في الخوارزمية توني هور في <لأ href = "http://portal.acm.org/citation.cfm؟id=362489" يختلط = "نوفولو noreferrer "> <م> البحث :

find(topn, a, i, j)
   pick a random element x from a[i..j]
   partition the subarray a[i..j] (just as in Quicksort) 
     into subarrays of elements <x, ==x, >x
   let k be the position of element x
   if k == 0 you're finished
   if k > topn, call find(topn, a, i, k)
   if k < topn, call find(topn-k, k, j)

وهذه الخوارزمية يضع أكبر عناصر topn في عناصر topn الأولى من مجموعة a، <م> بدون فرزها. بالطبع، إذا كنت تريد لهم فرزها، أو لمجرد البساطة، كومة هو أفضل، واستدعاء الدالة المكتبة هو أفضل من ذلك. لكنه خوارزمية باردة.