الحد من ListIterator للعناصر N الأولى (الأمثل)

Question

ما هي وسيلة بسيطة وسريعة للحصول على مكرر التي ترجع في معظم عناصر N من بداية List؟

وأبسط الإصدارات أتمكن من التوصل إلى ما يلي:

و# 1:

import com.google.common.collect.Iterators;

// ...

public static <E> Iterator<E> lengthLimitedIterator(Iterable<E> source, int maxLen) {
    return Iterators.partition(source.iterator(), maxLen).next().iterator();
}

و# 2:

public static <E> Iterator<E> lengthLimitedIterator(List<E> source, int maxLen) {
    return source.subList(0, Math.min(source.size(), maxLen)).iterator();
}

ومما يؤسف له كلا الإصدارين خلق List مؤقت الذي يؤثر بشكل كبير على الأداء كما أدعو هذه الطريقة ملايين المرات في حلقة ضيقة.

هل هناك أية وظائف أخرى مكتبة أتمكن من استخدام لهذا؟

---

ملحوظة: أنا لا يمكن تجنب بالتكرار عبر قائمة وأنا فمررها الى الطريقة التي يأخذ مكرر كما حجتها، وأنا لا يمكن تعديل تلك الفئة

Answer 1

ويبدو كما لو في ميزة ستضاف إلى الجوافة وحاليا (في R06) في بيتا:

public static <T> Iterator<T> limit(Iterator<T> iterator, int limitSize)

Answer 2

وأنت تعرف مسبقا انها قائمة، حتى تتمكن من مجرد دعوة طريقة List.subList(int fromIndex, int toIndex). وفقا للمواصفات، يتم دعم قائمة فرعية من القائمة الأصلية، حتى انها ليست خلق حقا List في مهب كامل، مجرد نوع من الكائن الوكيل.

Answer 3

وهذا هو المكان الذي يوجد فيه ديكور يعمل بشكل جيد جدا: الديكور الخاص بك يحافظ على العد، وهو بمقدار next()، واستخدامها من قبل hasNext() السيطرة.

مثال (غير مكتملة عمدا):

public class LengthLimitedIterator<T>
implements Iterator<T>
{
    private Iterator<T> _wrapped;
    private int _length;
    private int _count;

    public LengthLimitedIterator(Iterator<T> wrapped, int length)
    {
        _wrapped = wrapped;
        _length = length;
    }


    public boolean hasNext()
    {
        if (_count < _length)
            return _wrapped.hasNext();
        return false;
    }

    public T next()
    {
        // FIXME - add exception if count >= length
        _count++;
        return _wrapped.next();
    }

Answer 4

لماذا لا ببساطة

list.subList(0, 42).iterator();

وأنا لست متأكدا لماذا لديك مانع في خلق تلك القائمة المؤقتة. وهي لا تفعل أي شيء كنت تنظر مكلفة. في الواقع، وخلق هذه القائمة هو من أرخص بكثير من بالتكرار أكثر من ذلك، والتي أفترض أنك تفعل.

Answer 5

وطريقة ArrayList.sublist(int,int) لا يخلق نسخة من القائمة الأصلية. وبدلا من ذلك فإنها ترجع مثيل قائمة فرعية التي يلتف ArrayList الأصلي. ومكرر إرجاعها بواسطة قائمة فرعية مستمدة من صفيف لا يجعل نسخة سواء.

ولذا نصيحتي هي محاولة استخدام ArrayList ك نوع قائمة قاعدة وطريقة sublist. إذا لم يكن بالسرعة الكافية وتنفيذ البديل الخاص بك من ArrayList التي تطبق طريقة limitedLengthIterator. على سبيل المثال، يجب أن تكون قادرة على التخلص من التعليمات البرمجية التي بالتحقق من التعديلات المتزامنة.

Answer 6

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

Answer 7

وهذه النسخة تبين أن يكون أسرع من أي من الأمثلة الأخرى:

public static <E> Iterator<E> lengthLimitedIterator(List<E> source, int maxLen) {
    maxLen = Math.min(maxLen, source.size());
    ArrayList<E> tempList = new ArrayList<E>(maxLen);
    for (int i = 0; i < maxLen; ++ i) {
       tempList.add(source.get(i));
    }
    return tempList.iterator();
}

وإذا كانت قائمة مؤقتة لابد من خلق على أي حال، وArrayList أسرع من القوائم زينت إرجاعها بواسطة أساليب مكتبة أخرى.

وتخميني هو أن ArrayList هو الحصول على بعض معاملة خاصة داخل VM.

وربما هذا سيكون غير فعال لقوائم طويلة جدا، ولكن القوائم بلدي هي قصيرة (تقريبا دائما أقل من 50 عناصر.)