python - إزالة التكرارات في القوائم




algorithm list (20)

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

def remove_duplicates():
    t = ['a', 'b', 'c', 'd']
    t2 = ['a', 'c', 'd']
    for t in t2:
        t.append(t.remove())
    return t

أدناه كود بسيط لإزالة مكررة في القائمة

def remove_duplicates(x):
    a = []
    for i in x:
        if i not in a:
            a.append(i)
    return a

print remove_duplicates([1,2,2,3,3,4])

يعود [1،2،3،4]


أرسل أحد الزملاء الإجابة المقبولة كجزء من شفرتي الخاصة بي لإجراء عرض codereview اليوم. بينما أنا معجب بالتأكيد أناقة الإجابة في السؤال ، أنا لست سعيدًا بالأداء. لقد جربت هذا الحل (أستخدم تعيينًا لتقليل وقت البحث)

def ordered_set(in_list):
    out_list = []
    added = set()
    for val in in_list:
        if not val in added:
            out_list.append(val)
            added.add(val)
    return out_list

لمقارنة الكفاءة ، استخدمت عينة عشوائية من 100 عدد صحيح - 62 كانت فريدة

from random import randint
x = [randint(0,100) for _ in xrange(100)]

In [131]: len(set(x))
Out[131]: 62

وهنا نتائج القياسات

In [129]: %timeit list(OrderedDict.fromkeys(x))
10000 loops, best of 3: 86.4 us per loop

In [130]: %timeit ordered_set(x)
100000 loops, best of 3: 15.1 us per loop

حسنًا ، ماذا يحدث إذا تمت إزالة المجموعة من الحل؟

def ordered_set(inlist):
    out_list = []
    for val in inlist:
        if not val in out_list:
            out_list.append(val)
    return out_list

والنتيجة ليست سيئة كما هو الحال مع OrderedDict ، ولكن لا يزال أكثر من 3 مرات من الحل الأصلي

In [136]: %timeit ordered_set(x)
10000 loops, best of 3: 52.6 us per loop

أفضل طريقة لإزالة التكرارات من القائمة هي استخدام وظيفة set () ، المتوفرة في python ، وتحويلها مرة أخرى إلى مجموعة

In [2]: some_list = ['a','a','v','v','v','c','c','d']
In [3]: list(set(some_list))
Out[3]: ['a', 'c', 'd', 'v']

إذا كنت لا تهتم بالطلب ، فافعل ذلك:

def remove_duplicates(l):
    return list(set(l))

set مضمونة لعدم وجود نسخ مكررة.


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

يجب أن يشمل المثال التالي كل ما تحاول القيام به:

>>> t = [1, 2, 3, 1, 2, 5, 6, 7, 8]
>>> t
[1, 2, 3, 1, 2, 5, 6, 7, 8]
>>> list(set(t))
[1, 2, 3, 5, 6, 7, 8]
>>> s = [1, 2, 3]
>>> list(set(t) - set(s))
[8, 5, 6, 7]

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

إذا كان الأمر مهمًا بالنسبة لك ، فسيتعين عليك استخدام آلية مختلفة. حل شائع جدًا لهذا هو الاعتماد على OrderedDict للحفاظ على ترتيب المفاتيح أثناء الإدراج:

>>> from collections import OrderedDict
>>> list(OrderedDict.fromkeys(t))
[1, 2, 3, 5, 6, 7, 8]

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

لاحظ في النهاية أن كلا من set وكذلك حل OrderedDict يتطلبان أن تكون أغراضك قابلة للغسل . هذا يعني عادة أنه يجب أن يكون غير قابل للتغيير. إذا كان عليك التعامل مع العناصر غير القابلة للغسيل (مثل كائنات القائمة) ، فيجب عليك استخدام أسلوب بطيء يجب عليك فيه مقارنة كل عنصر مع كل عنصر آخر في حلقة متداخلة.


انها واحدة من الخطوط: list(set(source_list)) ستفعل الخدعة.

set هي شيء لا يمكن أن يكون مكررًا.

تحديث: نهج حفظ النظام هو سطرين:

from collections import OrderedDict
OrderedDict((x, True) for x in source_list).keys()

هنا نستخدم حقيقة أن OrderedDict يتذكر ترتيب الإدراج من مفاتيح ، ولا يغير ذلك عندما يتم تحديث قيمة في مفتاح معين. نحن نضيف True كقيم ، ولكن يمكننا إدخال أي شيء ، لا يتم استخدام القيم. ( set تعمل مثل الكثير مع القيم المتجاهلة ، أيضا.)


بسيطة وسهلة:

myList = [1, 2, 3, 1, 2, 5, 6, 7, 8]
cleanlist = []
[cleanlist.append(x) for x in myList if x not in cleanlist]

انتاج:

>>> cleanlist 
[1, 2, 3, 5, 6, 7, 8]

تقليل المتغير مع طلب الحفظ:

افترض أن لدينا قائمة:

l = [5, 6, 6, 1, 1, 2, 2, 3, 4]

تقليل المتغير (غير فعال):

>>> reduce(lambda r, v: v in r and r or r + [v], l, [])
[5, 6, 1, 2, 3, 4]

5 × أسرع ولكن أكثر تطورا

>>> 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())
# user 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]

حاول استخدام مجموعات:

import sets
t = sets.Set(['a', 'b', 'c', 'd'])
t1 = sets.Set(['a', 'b', 'c'])

print t | t1
print t - t1

حدد هذا إذا كنت تريد إزالة التكرارات (تعديل في المكان بدلاً من العودة إلى قائمة جديدة) دون استخدام مجموعة مدمجة ، dict.keys ، uniqify ، counter

>>> t = [1, 2, 3, 1, 2, 5, 6, 7, 8]
>>> for i in t:
...     if i in t[t.index(i)+1:]:
...         t.remove(i)
... 
>>> t
[3, 1, 2, 5, 6, 7, 8]

طريقة أخرى للقيام:

>>> seq = [1,2,3,'a', 'a', 1,2]
>> dict.fromkeys(seq).keys()
['a', 1, 2, 3]

في الوقت الحاضر ، قد تستخدم صف مكافحة:

>>> import collections
>>> c = collections.Counter([1, 2, 3, 4, 5, 6, 1, 1, 1, 1])
>>> c.keys()
dict_keys([1, 2, 3, 4, 5, 6])

لإزالة التكرارات ، اجعلها SET ثم أعدها مرة أخرى ثم اطبعها / استخدمها. مجموعة مضمونة لديها عناصر فريدة من نوعها. فمثلا :

a = [1,2,3,4,5,9,11,15]
b = [4,5,6,7,8]
c=a+b
print c
print list(set(c)) #one line for getting unique elements of c

سيكون الناتج كما يلي (تم التحقق في python 2.7)

[1, 2, 3, 4, 5, 9, 11, 15, 4, 5, 6, 7, 8]  #simple list addition with duplicates
[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 15] #duplicates removed!!

لجعل قائمة جديدة تحتفظ بترتيب العناصر الأولى من التكرارات في L

newlist=[ii for n,ii in enumerate(L) if ii not in L[:n]]

على سبيل المثال ، if L=[1, 2, 2, 3, 4, 2, 4, 3, 5] ستكون newlist if L=[1, 2, 2, 3, 4, 2, 4, 3, 5] [1,2,3,4,5]

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


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

def GetListWithoutRepetitions(loInput):
    # return list, consisting of elements of list/tuple loInput, without repetitions.
    # Example: GetListWithoutRepetitions([None,None,1,1,2,2,3,3,3])
    # Returns: [None, 1, 2, 3]

    if loInput==[]:
        return []

    loOutput = []

    if loInput[0] is None:
        oGroupElement=1
    else: # loInput[0]<>None
        oGroupElement=None

    for oElement in loInput:
        if oElement<>oGroupElement:
            loOutput.append(oElement)
            oGroupElement = oElement
    return loOutput

هنا هو أسرع حل pythonic comaring للآخرين المذكورة في الردود.

يسمح استخدام تفاصيل تنفيذ تقييم الدائرة القصيرة باستخدام فهم القائمة ، وهو سريع بما يكفي. visited.add(item) دائمًا يعرض None نتيجة ، والتي يتم تقييمها على أنها False ، لذلك يكون الجانب الأيمن or دائمًا نتيجة لمثل هذا التعبير.

حان الوقت بنفسك

def deduplicate(sequence):
    visited = set()
    adder = visited.add  # get rid of qualification overhead
    out = [adder(item) or item for item in sequence if item not in visited]
    return out

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

def uniqify(iterable):
    seen = set()
    for item in iterable:
        if item not in seen:
            seen.add(item)
            yield item

يعيد هذا المولد / المكرر ، بحيث يمكنك استخدامه في أي مكان يمكنك فيه استخدام المكرّر.

for unique_item in uniqify([1, 2, 3, 4, 3, 2, 4, 5, 6, 7, 6, 8, 8]):
    print(unique_item, end=' ')

print()

انتاج:

1 2 3 4 5 6 7 8

إذا كنت تريد list ، فيمكنك القيام بذلك:

unique_list = list(uniqify([1, 2, 3, 4, 3, 2, 4, 5, 6, 7, 6, 8, 8]))

print(unique_list)

انتاج:

[1, 2, 3, 4, 5, 6, 7, 8]

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

>>> t = [1, 2, 3, 3, 2, 4, 5, 6]
>>> s = [x for i, x in enumerate(t) if i == t.index(x)]
>>> s
[1, 2, 3, 4, 5, 6]

السبب الذي يعمل أعلاه هو أن طريقة index ترجع فقط الفهرس الأول للعنصر. العناصر المكررة تحتوي على مؤشرات أعلى. ارجع إلى here :

list.index (x [، start [، end]])
إرجاع فهرس يستند إلى الصفر في قائمة العنصر الأول الذي قيمته x. رفع ValueError إذا لم يكن هناك عنصر من هذا القبيل.


في Python 2.7 ، الطريقة الجديدة لإزالة التكرارات من iterable مع الاحتفاظ بها في الترتيب الأصلي هي:

>>> from collections import OrderedDict
>>> list(OrderedDict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']

في Python 3.5 ، لدى OrderedDict تطبيق C. توضح مواعيدي أن هذا هو الآن أسرع وأقصر الطرق المختلفة لـ Python 3.5.

في بايثون 3.6 ، أصبح النظام المعتاد مرتبًا وصغيرًا. (هذه الخاصية تحمل لـ CPython و PyPy ولكنها قد لا تكون موجودة في تطبيقات أخرى). يمنحنا ذلك أسرع طريقة جديدة للاختزال بينما نحتفظ بالطلب:

>>> list(dict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']

في بايثون 3.7 ، يتم ضمان الأمر المعتاد لكل من الطلبات عبر جميع التطبيقات. لذا ، فإن الحل الأقصر والأسرع هو:

>>> list(dict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']

>>> t = [1, 2, 3, 1, 2, 5, 6, 7, 8]
>>> t
[1, 2, 3, 1, 2, 5, 6, 7, 8]
>>> s = []
>>> for i in t:
       if i not in s:
          s.append(i)
>>> s
[1, 2, 3, 5, 6, 7, 8]




intersection