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 लिए धन्यवाद।)

लेकिन यदि संभव हो तो मैं खुद को अंतर्निर्मित या अधिक पाइथोनिक मुहावरे का लाभ उठाना चाहता हूं।

संबंधित प्रश्न: पायथन में, सूची से डुप्लीकेट हटाने के लिए सबसे तेज़ एल्गोरिदम क्या है ताकि आदेश को संरक्षित करते समय सभी तत्व अद्वितीय हों?


MizardX का जवाब कई दृष्टिकोणों का एक अच्छा संग्रह देता है।

जोर से सोचते समय मैं यही आया:

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

आप एक बदसूरत सूची समझ हैक कर सकते हैं।

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

आप एक सूची समझ का संदर्भ दे सकते हैं क्योंकि यह प्रतीक '_ [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]

एक और बहुत पुराने सवाल के लिए बहुत देर से जवाब के लिए:

itertools व्यंजनों में एक ऐसा फ़ंक्शन होता है जो seen सेट तकनीक का उपयोग करके करता है, लेकिन:

  • मानक key फ़ंक्शन को संभालता है।
  • कोई असामान्य हैक्स का उपयोग नहीं करता है।
  • लूप को पूर्व-बाध्यकारी द्वारा देखा गया है। इसे बार बार seen.add बजाय। ( f7 यह भी करता है, लेकिन कुछ संस्करण नहीं करते हैं।)
  • ifilterfalse का उपयोग करके लूप को अनुकूलित करता है, इसलिए आपको केवल उन सभी के बजाय पाइथन में अद्वितीय तत्वों पर लूप करना होगा। (आप अभी भी उन सभी पर ifilterfalse अंदर ifilterfalse से शुरू करते हैं, लेकिन यह सी में है, और बहुत तेज़ है।)

क्या यह वास्तव में f7 से तेज़ है? यह आपके डेटा पर निर्भर करता है, इसलिए आपको इसका परीक्षण करना होगा और देखना होगा। यदि आप अंत में एक सूची चाहते हैं, तो f7 एक listcomp का उपयोग करता है, और यहां ऐसा करने का कोई तरीका नहीं है। (आप सीधे yield बजाय append कर सकते हैं, या आप जेनरेटर को list फ़ंक्शन में खिला सकते हैं, लेकिन कोई भी list अंदर LIST_APPEND जितना तेज़ नहीं हो सकता है।) किसी भी दर पर, आमतौर पर, कुछ माइक्रोसेकंड को निचोड़ना नहीं जा रहा है आसानी से समझने योग्य, पुन: प्रयोज्य, पहले से लिखे गए फ़ंक्शन के रूप में महत्वपूर्ण होने के लिए, जब आप सजाने के लिए डीएसयू की आवश्यकता नहीं होती है।

सभी व्यंजनों के साथ, यह 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

एक मृत घोड़े को मारने के लिए नहीं (यह सवाल बहुत पुराना है और पहले से ही बहुत अच्छे जवाब हैं), लेकिन यहां पांडों का उपयोग करने का एक समाधान है जो कई परिस्थितियों में काफी तेज़ है और उपयोग करने में आसान है।

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]

क्योंकि मैं एक dup देख रहा था और कुछ संबंधित लेकिन अलग, संबंधित, उपयोगी जानकारी एकत्र करता था जो कि अन्य उत्तरों का हिस्सा नहीं है, यहां दो अन्य संभावित समाधान हैं।

.get (True) XOR .setdefault (झूठा)

सबसे पहले स्वीकृत seen_add तरह बहुत अधिक है, लेकिन शब्दकोश के get(x,<default>) और setdefault(x,<default>) का उपयोग करके स्पष्ट साइड इफेक्ट्स के साथ:

# Explanation of d.get(x,True) != d.setdefault(x,False)
#
# x in d | d[x]  | A = d.get(x,True) | x in d | B = d.setdefault(x,False) | x in d | d[x]    | A xor B
# False  | None  | True          (1) | False  | False                 (2) | True   | False   | True
# True   | False | False         (3) | True   | False                 (4) | True   | False   | False
#
# Notes
# (1) x is not in the dictionary, so get(x,<default>) returns True but does __not__ add the value to the dictionary
# (2) x is not in the dictionary, so setdefault(x,<default>) adds the {x:False} and returns False
# (3) since x is in the dictionary, the <default> argument is ignored, and the value of the key is returned, which was
#     set to False in (2)
# (4) since the key is already in the dictionary, its value is returned directly and the argument is ignored
#
# A != B is how to do boolean XOR in Python
#
def sort_with_order(s):
    d = dict()
    return [x for x in s if d.get(x,True) != d.setdefault(x,False)]

get(x,<default>) <default> यदि x शब्दकोश में नहीं है, लेकिन शब्दकोश में कुंजी नहीं जोड़ता है। कुंजी set(x,<default>) कुंजी देता है यदि कुंजी शब्दकोश में है, अन्यथा इसे सेट करता है और <default>

इसके अलावा: a != b पाइथन में एक्सओआर कैसे करें

__ ओवरराइडिंग ___missing_____ ( इस उत्तर से प्रेरित)

दूसरी तकनीक __missing__ विधि को ओवरराइड कर __missing__ है जिसे कुंजी कहा जाता है जब कुंजी एक शब्दकोश में मौजूद नहीं होती है, जिसे केवल d[k] नोटेशन का उपयोग करते समय बुलाया जाता है:

class Tracker(dict):
    # returns True if missing, otherwise sets the value to False
    # so next time d[key] is called, the value False will be returned
    # and __missing__ will not be called again
    def __missing__(self, key):
        self[key] = False
        return True

t = Tracker()
unique_with_order = [x for x in samples if t[x]]

दस्तावेज़ों से :

संस्करण 2.5 में नया: यदि dict का उप-वर्ग एक विधि को परिभाषित करता है _____ अनुपलब्ध _____ (), यदि कुंजी कुंजी मौजूद नहीं है, तो डी [कुंजी] ऑपरेशन तर्क के रूप में कुंजी कुंजी के साथ उस विधि को कॉल करता है। डी [कुंजी] ऑपरेशन तब होता है जब कुंजी मौजूद नहीं होती है तो _____ गायब _____ (कुंजी) कॉल द्वारा जो भी लौटाया जाता है या बढ़ाया जाता है। कोई अन्य ऑपरेशन या विधियां _____ अनुपलब्ध _____ () का आह्वान नहीं करती हैं। यदि _____ गायब _____ () को परिभाषित नहीं किया गया है, तो KeyError उठाया गया है। _____ गायब _____ () एक विधि होना चाहिए; यह एक आवृत्ति चर नहीं हो सकता है। उदाहरण के लिए, collections.defaultdict देखें।


बाहरी मॉड्यूल से ऐसी कार्यक्षमता का एक और (बहुत प्रदर्शन) कार्यान्वयन जोड़ने के लिए 1 : iteration_utilities.unique_everseen :

>>> from iteration_utilities import unique_everseen
>>> lst = [1,1,1,2,3,2,2,2,1,3,4]

>>> list(unique_everseen(lst))
[1, 2, 3, 4]

समय

मैंने कुछ समय (पायथन 3.6) किया और ये दिखाते हैं कि यह परीक्षण किए गए सभी अन्य विकल्पों की तुलना में तेज़ है, जिसमें OrderedDict.fromkeys , f7 और more_itertools.unique_everseen :

%matplotlib notebook

from iteration_utilities import unique_everseen
from collections import OrderedDict
from more_itertools import unique_everseen as mi_unique_everseen

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

def iteration_utilities_unique_everseen(seq):
    return list(unique_everseen(seq))

def more_itertools_unique_everseen(seq):
    return list(mi_unique_everseen(seq))

def odict(seq):
    return list(OrderedDict.fromkeys(seq))

from simple_benchmark import benchmark

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
              {2**i: list(range(2**i)) for i in range(1, 20)},
              'list size (no duplicates)')
b.plot()

और यह सुनिश्चित करने के लिए कि मैंने अधिक डुप्लिकेट के साथ एक परीक्षण भी किया है, यह जांचने के लिए कि क्या इससे कोई फर्क पड़ता है:

import random

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
              {2**i: [random.randint(0, 2**(i-1)) for _ in range(2**i)] for i in range(1, 20)},
              'list size (lots of duplicates)')
b.plot()

और एक केवल एक मान युक्त है:

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
              {2**i: [1]*(2**i) for i in range(1, 20)},
              'list size (only duplicates)')
b.plot()

इन सभी मामलों में iteration_utilities.unique_everseen फ़ंक्शन सबसे तेज़ (मेरे कंप्यूटर पर) है।

यह iteration_utilities.unique_everseen फ़ंक्शन इनपुट में अस्थिर मानों को भी संभाल सकता है (हालांकि मानों को हर्षनीय होने पर O(n*n) प्रदर्शन के बजाय O(n*n) प्रदर्शन के साथ)।

>>> lst = [{1}, {1}, {2}, {1}, {3}]

>>> list(unique_everseen(lst))
[{1}, {2}, {3}]

1 अस्वीकरण: मैं उस पैकेज के लेखक हूं।


मुझे लगता है कि अगर आप आदेश बनाए रखना चाहते हैं,

आप इसे आजमा सकते हैं:

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 

मेरे दोस्त वेस ने मुझे सूची समझ का उपयोग करके यह मीठा उत्तर दिया।

उदाहरण कोड:

>>> l = [3, 4, 3, 6, 4, 1, 4, 8]

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

>>> l = [3, 4, 6, 1, 8]

यदि आपकी स्थिति अनुमति देती है, तो आप लोड होने के दौरान डुप्लिकेट को हटाने पर विचार कर सकते हैं:

मान लें कि आपके पास एक लूप है जो डेटा में खींच रहा है और list1.append (आइटम) का उपयोग करता है ...

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))

... अगर मैं गलत हूं तो काम करना चाहिए लेकिन मुझे सही करना चाहिए


यह तेज़ है लेकिन ...

l = list(set(l))

... यदि आपकी सूची आइटम सक्षम नहीं हैं तो यह काम नहीं करता है।

एक और सामान्य दृष्टिकोण है:

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

... यह सभी मामलों के लिए काम करना चाहिए।


यहां आपके कुछ विकल्प हैं: 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 ? पायथन एक गतिशील भाषा है, और seen.add जा रहा है। स्थानीय वैरिएबल को हल करने से प्रत्येक पुनरावृत्ति अधिक महंगा है। seen.add गया। पुनरावृत्ति के बीच बदल सकता है, और रनटाइम उस पर शासन करने के लिए पर्याप्त स्मार्ट नहीं है। इसे सुरक्षित करने के लिए, इसे हर बार ऑब्जेक्ट की जांच करनी होती है।

यदि आप इस फ़ंक्शन का उपयोग उसी डेटासेट पर बहुत अधिक करने की योजना बना रहे हैं, तो शायद आप एक ऑर्डर किए गए सेट से बेहतर होंगे: http://code.activestate.com/recipes/528878/

(1) प्रति ऑपरेशन, हटाने और सदस्य-जांच प्रति ऑपरेशन।


सूचियों के लिए हास्केल के nub फ़ंक्शन को निर्धारित करने में उपयोग किए गए पुनरावर्ती विचार को उधार लेना, यह एक पुनरावर्ती दृष्टिकोण होगा:

def unique(lst):
    return [] if lst==[] else [lst[0]] + unique(filter(lambda x: x!= lst[0], lst[1:]))

उदाहरण के लिए:

In [118]: unique([1,5,1,1,4,3,4])
Out[118]: [1, 5, 4, 3]

मैंने इसे डेटा आकार बढ़ाने के लिए कोशिश की और उप-रैखिक समय-जटिलता देखी (निश्चित नहीं, लेकिन यह सुझाव देता है कि यह सामान्य डेटा के लिए ठीक होना चाहिए)।

In [122]: %timeit unique(np.random.randint(5, size=(1)))
10000 loops, best of 3: 25.3 us per loop

In [123]: %timeit unique(np.random.randint(5, size=(10)))
10000 loops, best of 3: 42.9 us per loop

In [124]: %timeit unique(np.random.randint(5, size=(100)))
10000 loops, best of 3: 132 us per loop

In [125]: %timeit unique(np.random.randint(5, size=(1000)))
1000 loops, best of 3: 1.05 ms per loop

In [126]: %timeit unique(np.random.randint(5, size=(10000)))
100 loops, best of 3: 11 ms per loop

मुझे यह भी लगता है कि यह दिलचस्प है कि इसे अन्य परिचालनों द्वारा विशिष्टता के लिए आसानी से सामान्यीकृत किया जा सकता है। इस कदर:

import operator
def unique(lst, cmp_op=operator.ne):
    return [] if lst==[] else [lst[0]] + unique(filter(lambda x: cmp_op(x, lst[0]), lst[1:]), cmp_op)

उदाहरण के लिए, आप एक ऐसे फ़ंक्शन में पास हो सकते हैं जो समान पूर्णांक के लिए गोल करने की धारणा का उपयोग करता है जैसे कि यह विशिष्टता उद्देश्यों के लिए "समानता" था, जैसे:

def test_round(x,y):
    return round(x) != round(y)

तो अद्वितीय (some_list, test_round) सूची के अद्वितीय तत्व प्रदान करेगा जहां विशिष्टता का मतलब अब पारंपरिक समानता नहीं है (जो इस समस्या के किसी भी प्रकार के सेट-आधारित या dict-key-based दृष्टिकोण का उपयोग करके निहित है) लेकिन इसके बजाय केवल पहला तत्व जो प्रत्येक संभावित पूर्णांक के लिए के लिए राउंड करता है कि तत्व गोल हो सकते हैं, उदाहरण के लिए:

In [6]: unique([1.2, 5, 1.9, 1.1, 4.2, 3, 4.8], test_round)
Out[6]: [1.2, 5, 1.9, 4.2, 3]

सूची में डुप्लिकेट पॉप करें और स्रोत सूची में यूनिक्स रखें:

>>> 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] उपयोग करता हूं।


2016 संपादित करें

जैसा कि रेमंड ने बताया , पाइथन 3.5+ में जहां OrderedDict सी में लागू किया गया है, सूची समझ दृष्टिकोण OrderedDict की तुलना में धीमा हो जाएगा (जब तक कि आपको वास्तव में अंत में सूची की आवश्यकता न हो - और तब भी, केवल इनपुट बहुत छोटा हो)। तो 3.5+ के लिए सबसे अच्छा समाधान OrderedDict

महत्वपूर्ण संपादन 2015

@abarnert नोट्स के रूप में, more_itertools लाइब्रेरी ( pip install more_itertools ) में एक अद्वितीय_विसेन फ़ंक्शन होता है जो इस समस्या को हल करने के लिए बनाया गया है, बिना किसी अपठनीय ( not seen.add ) उत्परिवर्तन सूची समझ में। यह भी सबसे तेज़ समाधान है:

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

बस एक साधारण पुस्तकालय आयात और कोई हैक्स। यह itertools नुस्खा अद्वितीय_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

पाइथन 2.7+ स्वीकृत सामान्य मुहावरे (जो काम करता है लेकिन गति के लिए अनुकूलित नहीं है, अब मैं अद्वितीय_विसेन का उपयोग करता हूं) इस collections.OrderedDict लिए। unique_everseen :

रनटाइम: ओ (एन)

>>> 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 एक इन-प्लेस विधि है जो हमेशा None लौटाती है, इसलिए not None True मूल्यांकन not None करता है।

ध्यान दें कि हैक समाधान कच्चे गति में तेज़ है हालांकि इसमें एक ही रनटाइम जटिलता ओ (एन) है।


पायथन 2.7 में, मूल क्रम में रखते हुए डुप्लिकेट को पुनरावृत्त करने का नया तरीका यह है:

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

पायथन 3.5 में , ऑर्डर्ड डिक्ट के पास सी कार्यान्वयन है। मेरे समय से पता चलता है कि यह अब पाइथन 3.5 के विभिन्न दृष्टिकोणों में से सबसे तेज़ और सबसे छोटा दोनों है।

पायथन 3.6 में , नियमित नियम दोनों आदेश और कॉम्पैक्ट बन गए। (यह सुविधा सीपीथॉन और पीपीपी के लिए है लेकिन अन्य कार्यान्वयन में मौजूद नहीं हो सकती है)। यह हमें आदेश बनाए रखने के दौरान समर्पण का एक नया सबसे तेज़ तरीका देता है:

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

पायथन 3.7 में , नियमित निर्देशों को सभी कार्यान्वयन में आदेश दिया गया है। तो, सबसे छोटा और सबसे तेज़ समाधान है:

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

@max पर प्रतिक्रिया: एक बार जब आप 3.6 या 3.7 पर जाते हैं और ऑर्डर्ड डिक्ट के बजाए नियमित निर्देश का उपयोग करते हैं, तो आप वास्तव में किसी अन्य तरीके से प्रदर्शन को हरा नहीं सकते हैं। शब्दकोश घना है और आसानी से किसी भी ओवरहेड के साथ एक सूची में परिवर्तित हो जाता है। लक्ष्य सूची लेंस (डी) के लिए पूर्व आकार का है जो सूची समझ में होने वाले सभी आकारों को बचाती है। साथ ही, चूंकि आंतरिक कुंजी सूची घनी है, इसलिए पॉइंटर्स की प्रतिलिपि सूची सूची के रूप में लगभग तेज़ है।


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