क्या यह संघ सेट के लिए तेज़ है या पूरी सूची को डुप्लिकेट के लिए जांचें?

Question

खराब शब्द वाले शीर्षक के लिए खेद है, लेकिन मैंने दो सूचियों से वस्तुओं की एक अनूठी सूची प्राप्त करने के बारे में पहले एक प्रश्न पूछा था। लोगों ने मुझे सूची बनाने के लिए कहा -> सेट और फिर संघ।

तो अब मैं सोच रहा हूँ अगर यह करने के लिए तेजी से है:

1. एक सूची एक आइटम जोड़ने, डुप्लीकेट की पूरी सूची स्कैन है।
2. उस आइटम को एक सेट बनाएं और फिर संघ सेट करें।

मैं शायद सिर्फ मसा में सेट पर पढ़ना चाहिए ...

अजगर में, जिस तरह से - स्पष्ट नहीं के लिए खेद है।

Answer 1

के रूप में आप एक और अंत तक एक सूची का विस्तार देख सकते हैं तो सेट जिससे सबसे तेज़ तरीका है द्वारा डुप्लिकेट निकालने (कम से कम अजगर में;))

>>> def foo(): 
...  """ 
...  extending one list by another end then remove duplicates by making set 
...  """ 
...  l1 = range(200) 
...  l2 = range(150, 250) 
...  l1.extend(l2) 
...  set(l1) 
... 
>>> def bar(): 
...  """ 
...  checking if element is on one list end adding it only if not 
...  """ 
...  l1 = range(200) 
...  l2 = range(150, 250) 
...  for elem in l2: 
...    if elem not in l1: 
...      l1.append(elem) 
... 
>>> def baz(): 
...  """ 
...  making sets from both lists and then union from them 
...  """ 
...  l1 = range(200) 
...  l2 = range(150, 250) 
...  set(l1) | set(l2) 
... 
>>> from timeit import Timer 
>>> Timer(foo).timeit(10000) 
0.265153169631958 
>>> Timer(bar).timeit(10000) 
7.921358108520508 
>>> Timer(baz).timeit(10000) 
0.3845551013946533 
>>> 

Answer 2

सबसे तेज़ चीज जो आप कर सकते हैं वह सूचियों से दो सेट बनाती है और उनका संघ लेती है। सूची और सेट यूनियन से दोनों सेट निर्माण रनटाइम में बहुत अनुकूलित सी में लागू किए जाते हैं, इसलिए यह बहुत तेज़ है। l2 साथ l1 का विस्तार तेजी से होता है @kriss नोटों के रूप में,:

कोड में, यदि सूचियों l1 और l2 हैं, तो आप

unique_elems = set(l1) | set(l2) 

संपादित कर सकते हैं। हालांकि यह कोड l1 नहीं बदलता है, और l1 और l2 जेनेरिक पुनरावृत्तियों के साथ भी काम करता है।

Answer 3

आप सभी इनपुट के रूप में है और चाहते हैं की निर्भर करता है आउटपुट के रूप में।

आप शुरुआत में एक सूची li है और अंत में एक संशोधित सूची प्राप्त करना चाहते हैं, तो तेजी से विधि समस्या सेट करने के लिए प्रारंभिक सूची परिवर्तित है, तो सूची जो रास्ता बहुत धीमी है वापस करने के लिए परिवर्तित करने if not elt in li: li.append(elt) है।

लेकिन यदि आप किसी भी समय s सेट के साथ काम कर सकते हैं (आपको सूची के आदेश की परवाह नहीं है, और इसे प्राप्त करने के तरीकों को केवल कुछ पुनरावृत्त करने की आवश्यकता है), बस s.add(elt) कर रहा है तेज़ है।

यदि शुरुआत में आपको सूची में सूची से अंतिम रूपांतरण के साथ अंत में एक सूची सूचीबद्ध करना है और चाहते हैं, तो सेट का उपयोग करके वस्तुओं की एकता का प्रबंधन करना तेज़ है, लेकिन आप आसानी से उदाहरण को देख सकते हैं विस्तार के उपयोग से दो सूचियों को संयोजित करने के बजाय @virhilo द्वारा दिए गए उत्तर में प्रदान किया गया है, फिर परिणाम को सेट में परिवर्तित करना दो सूचियों को सेट करने और संघ करने के लिए परिवर्तित करने से तेज़ है।

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

Answer 4

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

यहां मेरा परीक्षण कार्यक्रम है, नीचे उत्पादन होगा।

from timeit import Timer 
from copy import copy 
import random 
import sys 

funcs = [] 

class timeMe(object): 
    def __init__(self, f): 
     funcs.append(f) 
     self.f = f 

    def __call__(self, *args, **kwargs): 
     return self.f(*args, **kwargs) 

@timeMe 
def extend_list_then_set(input1, input2): 
    """ 
    extending one list by another end then remove duplicates by making set 
    """ 
    l1 = copy(input1) 
    l2 = copy(input2) 
    l1.extend(l2) 
    set(l1) 

@timeMe 
def per_element_append_to_list(input1, input2): 
    """ 
    checking if element is on one list end adding it only if not 
    """ 
    l1 = copy(input1) 
    l2 = copy(input2) 
    for elem in l2: 
      if elem not in l1: 
        l1.append(elem) 

@timeMe 
def union_sets(input1, input2): 
    """ 
    making sets from both lists and then union from them 
    """ 
    l1 = copy(input1) 
    l2 = copy(input2) 
    set(l1) | set(l2) 

@timeMe 
def set_from_one_add_from_two(input1, input2): 
    """ 
    make set from list 1, then add elements for set 2 
    """ 
    l1 = copy(input1) 
    l2 = copy(input2) 
    l1 = set(l1) 
    for element in l2: 
     l1.add(element) 

@timeMe 
def set_from_one_union_two(input1, input2): 
    """ 
    make set from list 1, then union list 2 
    """ 
    l1 = copy(input1) 
    l2 = copy(input2) 
    x = set(l1).union(l2) 

@timeMe 
def chain_then_set(input1, input2): 
    """ 
    chain l1 & l2, then make a set out of that 
    """ 
    l1 = copy(input1) 
    l2 = copy(input2) 
    set(itertools.chain(l1, l2)) 

def run_results(l1, l2, times): 
    for f in funcs: 
     t = Timer('%s(l1, l2)' % f.__name__, 
      'from __main__ import %s; l1 = %s; l2 = %s' % (f.__name__, l1, l2)) 
     yield (f.__name__, t.timeit(times))  

test_datasets = [ 
    ('original, small, some overlap', range(200), range(150, 250), 10000), 
    ('no overlap: l1 = [1], l2 = [2..100]', [1], range(2, 100), 10000), 
    ('lots of overlap: l1 = [1], l2 = [1]*100', [1], [1]*100, 10000), 
    ('50 random ints below 2000 in each', [random.randint(0, 2000) for x in range(50)], [random.randint(0, 2000) for x in range(50)], 10000), 
    ('50 elements in each, no overlap', range(50), range(51, 100), 10000), 
    ('50 elements in each, total overlap', range(50), range(50), 10000), 
    ('500 random ints below 500 in each', [random.randint(0, 500) for x in range(500)], [random.randint(0, 500) for x in range(500)], 1000), 
    ('500 random ints below 2000 in each', [random.randint(0, 2000) for x in range(500)], [random.randint(0, 2000) for x in range(500)], 1000), 
    ('500 random ints below 200000 in each', [random.randint(0, 200000) for x in range(500)], [random.randint(0, 200000) for x in range(500)], 1000), 
    ('500 elements in each, no overlap', range(500), range(501, 1000), 10000), 
    ('500 elements in each, total overlap', range(500), range(500), 10000), 
    ('10000 random ints below 200000 in each', [random.randint(0, 200000) for x in range(10000)], [random.randint(0, 200000) for x in range(10000)], 50), 
    ('10000 elements in each, no overlap', range(10000), range(10001, 20000), 10), 
    ('10000 elements in each, total overlap', range(10000), range(10000), 10), 
    ('original lists 100 times', range(200)*100, range(150, 250)*100, 10), 
] 

fullresults = [] 
for description, l1, l2, times in test_datasets: 
    print "Now running %s times: %s" % (times, description) 
    results = list(run_results(l1, l2, times)) 
    speedresults = [x for x in sorted(results, key=lambda x: x[1])] 
    for name, speed in results: 
     finish = speedresults.index((name, speed)) + 1 
     timesslower = speed/speedresults[0][1] 
     fullresults.append((description, name, speed, finish, timesslower)) 
     print '\t', finish, ('%.2fx' % timesslower).ljust(10), name.ljust(40), speed 

print 
import csv 
out = csv.writer(sys.stdout) 
out.writerow(('Test', 'Function', 'Speed', 'Place', 'timesslower')) 
out.writerows(fullresults) 

परिणाम

यहाँ मेरी बात अपने डेटा के साथ परीक्षण करने के लिए प्रोत्साहित करते हैं करने के लिए है, तो मैं बारीकियों पर वीणा नहीं करना चाहती। हालांकि ... पहली विस्तार विधि सबसे तेज़ औसत विधि है, लेकिन set_from_one_union_two (x = set(l1).union(l2)) कुछ बार जीतती है। यदि आप स्वयं स्क्रिप्ट चलाते हैं तो आप अधिक जानकारी प्राप्त कर सकते हैं।

जिन नंबरों की मैं रिपोर्ट कर रहा हूं वे इस कार्य पर सबसे धीमे कार्य की तुलना में धीमे समय की संख्या हैं। यदि यह सबसे तेज़ था, तो यह 1.

          Functions                               
Tests          extend_list_then_set  per_element_append_to_list set_from_one_add_from_two set_from_one_union_two  union_sets  chain_then_set 
original, small, some overlap    1       25.04      1.53      1.18      1.39   1.08 
no overlap: l1 = [1], l2 = [2..100]   1.08      13.31      2.10      1       1.27   1.07 
lots of overlap: l1 = [1], l2 = [1]*100  1.10      1.30      2.43      1       1.25   1.05 
50 random ints below 2000 in each   1       7.76      1.35      1.20      1.31   1 
50 elements in each, no overlap    1       9.00      1.48      1.13      1.18   1.10 
50 elements in each, total overlap   1.08      4.07      1.64      1.04      1.41   1 
500 random ints below 500 in each   1.16      68.24      1.75      1       1.28   1.03 
500 random ints below 2000 in each   1       102.42      1.64      1.43      1.81   1.20 
500 random ints below 200000 in each  1.14      118.96      1.99      1.52      1.98   1 
500 elements in each, no overlap   1.01      145.84      1.86      1.25      1.53   1 
500 elements in each, total overlap   1       53.10      1.95      1.16      1.57   1.05   
10000 random ints below 200000 in each  1      2588.99      1.73      1.35      1.88   1.12 
10000 elements in each, no overlap   1      3164.01      1.91      1.26      1.65   1.02 
10000 elements in each, total overlap  1      1068.67      1.89      1.26      1.70   1.05 
original lists 100 times     1.11      2068.06      2.03      1       1.04   1.17 

           Average 1.04      629.25      1.82       1.19      1.48   1.06 
         Standard Deviation 0.05      1040.76      0.26       0.15      0.26   0.05 
            Max 1.16      3164.01      2.43       1.52      1.98   1.20