python - كيف تتم إزالة التكرارات من القائمة مع الاحتفاظ بالترتيب؟




list duplicates (20)

5 × أسرع تقليل متغير ولكن أكثر تطورا

>>> l = [5, 6, 6, 1, 1, 2, 2, 3, 4]
>>> reduce(lambda r, v: v in r[1] and r or (r[0].append(v) or r[1].add(v)) or r, l, ([], set()))[0]
[5, 6, 1, 2, 3, 4]

تفسير:

default = (list(), set())
# use list to keep order
# use set to make lookup faster

def reducer(result, item):
    if item not in result[1]:
        result[0].append(item)
        result[1].add(item)
    return result

>>> reduce(reducer, l, default)[0]
[5, 6, 1, 2, 3, 4]

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

def uniq(input):
  output = []
  for x in input:
    if x not in output:
      output.append(x)
  return output

(شكرا على unwind لهذا unwind الكود .)

لكنني أود أن أستفيد من صيغة بديهية أو أكثر من البيثونية إذا أمكن.

سؤال ذو صلة: في Python ، ما هي أسرع خوارزمية لإزالة التكرارات من قائمة بحيث تكون جميع العناصر فريدة أثناء الحفاظ على الطلب ؟


أعتقد أنه إذا كنت تريد الحفاظ على النظام ،

يمكنك تجربة هذا:

list1 = ['b','c','d','b','c','a','a']    
list2 = list(set(list1))    
list2.sort(key=list1.index)    
print list2

أو بالمثل ، يمكنك القيام بذلك:

list1 = ['b','c','d','b','c','a','a']  
list2 = sorted(set(list1),key=list1.index)  
print list2 

يمكنك أيضًا القيام بذلك:

list1 = ['b','c','d','b','c','a','a']    
list2 = []    
for i in list1:    
    if not i in list2:  
        list2.append(i)`    
print list2

ويمكن أيضا أن تكون مكتوبة على النحو التالي:

list1 = ['b','c','d','b','c','a','a']    
list2 = []    
[list2.append(i) for i in list1 if not i in list2]    
print list2 

إذا كان موقفك يسمح بذلك ، يمكنك التفكير في إزالة العناصر المكررة أثناء التحميل:

لنفترض أن لديك حلقة تسحب البيانات وتستخدم list1.append (item) ...

list1 = [0, 2, 4, 9]
for x in range(0, 7):
  list1.append(x)

يمنحك هذا بعض التكرارات: [0 ، 2 ، 4 ، 9 ، 0 ، 1 ، 2 ، 3 ، 4 ، 5 ، 6]

لكن إذا فعلت:

list1 = [0, 2, 4, 9]
for x in range(0, 7)
  if x not in list1:
    list1.append(x)

لم تحصل على نسخ مكررة وتم الحفاظ على الطلب: [0 ، 2 ، 4 ، 9 ، 1 ، 3 ، 5 ، 6]


إذا كنت بحاجة إلى بطانة واحدة ، فربما يساعد ذلك في:

reduce(lambda x, y: x + y if y[0] not in x else x, map(lambda x: [x],lst))

... يجب أن تعمل ولكن تصحيح لي إذا كنت مخطئا


الإجابة MizardX يعطي مجموعة جيدة من الأساليب المتعددة.

هذا ما توصلت إليه أثناء التفكير بصوت عالٍ:

mylist = [x for i,x in enumerate(mylist) if x not in mylist[i+1:]]

حل بدون استخدام الوحدات أو المجموعات المستوردة:

text = "ask not what your country can do for you ask what you can do for your country"
sentence = text.split(" ")
noduplicates = [(sentence[i]) for i in range (0,len(sentence)) if sentence[i] not in sentence[:i]]
print(noduplicates)

يعطي الإخراج:

['ask', 'not', 'what', 'your', 'country', 'can', 'do', 'for', 'you']

سيؤدي هذا إلى الحفاظ على النظام وتشغيله في وقت O (n). في الأساس ، الفكرة هي إنشاء ثقب في المكان الذي توجد فيه نسخة مكررة وتغسله للأسفل. يجعل استخدام مؤشر القراءة والكتابة. كلما تم العثور على تكرار فقط يتقدم مؤشر القراءة ويظل مؤشر الكتابة على الإدخال المكرر للكتابة فوقه.

def deduplicate(l):
    count = {}
    (read,write) = (0,0)
    while read < len(l):
        if l[read] in count:
            read += 1
            continue
        count[l[read]] = True
        l[write] = l[read]
        read += 1
        write += 1
    return l[0:write]

طريقة فعالة نسبيًا مع numpy صفيفات numpy :

b = np.array([1,3,3, 8, 12, 12,12])    
numpy.hstack([b[0], [x[0] for x in zip(b[1:], b[:-1]) if x[0]!=x[1]]])

المخرجات:

array([ 1,  3,  8, 12])

في Python 3.7 وأعلى ، يتم guaranteed القواميس لتذكر ترتيب الإدراج الرئيسي. الجواب على this السؤال يلخص الوضع الحالي للأمور.

وبذلك يصبح حل OrderedDict عفا عليه الزمن وبدون أي بيانات استيراد ، يمكننا ببساطة إصدار:

>>> list(dict.fromkeys([1, 2, 1, 3, 3, 2, 4]).keys())
[1, 2, 3, 4]

قم برث النسخة المكررة في قائمة وأمسك uniques في قائمة المصادر:

>>> list1 = [ 1,1,2,2,3,3 ]
>>> [ list1.pop(i) for i in range(len(list1))[::-1] if list1.count(list1[i]) > 1 ]
[1, 2, 3]

أستخدم [::-1] لقائمة القراءة بترتيب عكسي.


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

import pandas as pd

my_list = range(5) + range(5)  # [0, 1, 2, 3, 4, 0, 1, 2, 3, 4]
>>> pd.Series(my_list).drop_duplicates().tolist()
# Output:
# [0, 1, 2, 3, 4]

للحصول على إجابة متأخرة أخرى لسؤال قديم جدًا:

itertools صفات itertools على وظيفة تقوم بذلك ، باستخدام تقنية المجموعة seen ، ولكن:

  • يتعامل مع وظيفة key القياسي.
  • لا يستخدم أي قرصان غير لائق
  • يحسن حلقة من قبل ملزمة مسبقا seen.add بدلا من النظر في ذلك N مرات. (كما يفعل f7 هذا ، ولكن بعض الإصدارات لا تفعل ذلك).
  • يحسن الحلقة باستخدام ifilterfalse ، بحيث لا تحتاج إلا إلى ifilterfalse الحلقات عبر العناصر الفريدة في Python ، بدلاً من كلها. (أنت لا تزال تتكرر على كل منهم داخل ifilterfalse ، بالطبع ، ولكن هذا في C ، وأسرع بكثير.)

هل هو في الواقع أسرع من f7 ؟ يعتمد ذلك على بياناتك ، لذا سيتعين عليك اختبارها ومشاهدتها. إذا كنت تريد قائمة في النهاية ، يستخدم f7 listcomp ، ولا توجد طريقة للقيام بذلك هنا. (يمكنك append مباشرة بدلاً من yield على دخل ، أو يمكنك تغذية المولد في وظيفة list ، ولكن لا يمكن لأحد أن يكون بنفس سرعة LIST_APPEND داخل قائمة.) وعلى أي حال ، عادةً ما يتم الضغط على بضعة أجزاء من microseconds أن تكون مهمًا مثل وجود وظيفة سهلة الفهم وقابلة لإعادة الاستخدام ومكتوبة مسبقًا ولا تتطلب DSU عندما تريد تزيينها.

كما هو الحال مع جميع الوصفات ، فإنه متاح أيضًا في more-iterools .

إذا كنت ترغب فقط في حالة عدم وجود key ، فيمكنك تبسيطها على النحو التالي:

def unique(iterable):
    seen = set()
    seen_add = seen.add
    for element in itertools.ifilterfalse(seen.__contains__, iterable):
        seen_add(element)
        yield element

هذا سريع ولكن ...

l = list(set(l))

... لا يعمل إذا كانت عناصر القائمة غير قابلة للغسل.

نهج أكثر عامة هو:

l = reduce(lambda x, y: x if y in x else x + [y], l, [])

... يجب أن تعمل في جميع الحالات.


هل يمكن أن تفعل نوعا من الاختراق القبيح فهم الإختراق.

[l[i] for i in range(len(l)) if l.index(l[i]) == i]

هنا لديك بعض البدائل: http://www.peterbe.com/plog/uniqifiers-benchmark

أسرع واحد:

def f7(seq):
    seen = set()
    seen_add = seen.add
    return [x for x in seq if not (x in seen or seen_add(x))]

لماذا تم تعيين seen.add إلى seen_add بدلاً من مجرد الاتصال بـ seen.add ؟ بايثون هي لغة ديناميكية ، وحلها. كل عملية تكرار أكثر تكلفة من حل متغير محلي. seen.add يمكن أن يكون قد تغيّر بين التكرارات ، ووقت التشغيل ليس ذكيًا بما يكفي لاستبعاد ذلك. لتشغيلها بشكل آمن ، يجب عليها فحص الكائن في كل مرة.

إذا كنت تخطط لاستخدام هذه الوظيفة كثيرًا في نفس مجموعة البيانات ، فربما تكون أفضل حالًا باستخدام مجموعة مرتبة: http://code.activestate.com/recipes/528878/

O (1) الإدراج والحذف وفحص الأعضاء لكل عملية.


هنا نسخة عودية O (N 2 ) للمتعة:

def uniquify(s):
    if len(s) < 2:
        return s
    return uniquify(s[:-1]) + [s[-1]] * (s[-1] not in s[:-1])

يمكنك الإشارة إلى فهم القائمة لأنه يتم إنشاؤه بواسطة الرمز "_ [1]".
على سبيل المثال ، الدالة التالية فريدة - ifies قائمة العناصر دون تغيير ترتيبها عن طريق الرجوع إلى فهم القائمة الخاصة به.

def unique(my_list): 
    return [x for x in my_list if x not in locals()['_[1]']]

عرض:

l1 = [1, 2, 3, 4, 1, 2, 3, 4, 5]
l2 = [x for x in l1 if x not in locals()['_[1]']]
print l2

انتاج:

[1, 2, 3, 4, 5]

تحرير 2016

كما أشار رايموند ، في python OrderedDict حيث يتم تنفيذ OrderedDict في C ، سيكون أسلوب فهم القائمة أبطأ من OrderedDict (إلا إذا كنت في حاجة بالفعل إلى القائمة في النهاية - وحتى ذلك الحين ، فقط إذا كان الإدخال قصيرًا جدًا). الحل الأفضل لـ 3.5 + هو OrderedDict .

مهم تحرير عام 2015

كما هو @abarnert ، more_itertools مكتبة more_itertools ( pip install more_itertools ) على وظيفة unique_everseen التي تم إنشاؤها لحل هذه المشكلة دون أي طفرات غير قابلة للقراءة ( not seen.add ) في قائمة الفهم. هذا هو أيضًا الحل الأسرع أيضًا:

>>> from  more_itertools import unique_everseen
>>> items = [1, 2, 0, 1, 3, 2]
>>> list(unique_everseen(items))
[1, 2, 0, 3]

واحد فقط استيراد مكتبة بسيطة ولا الخارقة. يأتي هذا من تنفيذ وصفة unique_everseen التي تبدو كالتالي:

def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBCcAD', str.lower) --> A B C D
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in filterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

في Python 2.7+ الشائعة المقبولة (التي تعمل ولكنها غير محسّنة للسرعة ، يمكنني الآن استخدام unique_everseen ) لهذه collections.OrderedDict الاستخدامات.

وقت التشغيل: O (N)

>>> from collections import OrderedDict
>>> items = [1, 2, 0, 1, 3, 2]
>>> list(OrderedDict.fromkeys(items))
[1, 2, 0, 3]

هذا يبدو أجمل بكثير من:

seen = set()
[x for x in seq if x not in seen and not seen.add(x)]

ولا تستخدم الاختراق القبيح :

not seen.add(x)

والتي تعتمد على حقيقة أن set.add هو set.add تعمل دائمًا على إرجاع None حتى not None تقييم not None إلى True .

لاحظ مع ذلك أن حل الاختراق أسرع في سرعة الخام على الرغم من أن له نفس تعقيد وقت التشغيل O (N).


from itertools import groupby
[ key for key,_ in groupby(sortedList)]

لا يلزم حتى فرز القائمة ، الشرط الكافي هو تجميع القيم المتساوية معًا.

تحرير: افترضت أن "الحفاظ على النظام" يعني أن القائمة مرتبة بالفعل. إذا لم تكن هذه هي الحالة ، فإن الحل من MizardX هو الحل الصحيح.

تعديل المجتمع: هذه هي الطريقة الأكثر أناقة "لضغط العناصر المتتالية المتكررة في عنصر واحد".


l = [1,2,2,3,3,...]
n = []
n.extend(ele for ele in l if ele not in set(n))

تعبير المولد الذي يستخدم O (1) يبحث عن مجموعة لتحديد ما إذا كان سيتم تضمين عنصر في القائمة الجديدة أم لا.





unique