अजगर में सूचियों जहां डुप्लीकेट की आईडी

Question

मैं एक (जो अप करने के लिए 90k तत्व होते हैं कर सकते हैं) सूचियों की सूची है प्राप्त की सूची के लिए अद्वितीय पहचान प्रदान करेगा

[[1,2,3], [1,2,4], [1,2,3], [1,2,4], [1,2,5]] 

मैं प्रत्येक तत्व को एक आईडी असाइन करना चाहते हैं , जहां आईडी अद्वितीय है, सिवाय इसके कि जब आइटम डुप्लिकेट किया जाता है। तो उपर्युक्त सूची के लिए, मुझे इसकी आवश्यकता होगी:

[0,1,0,1,2] 

ऐसा करने का सबसे प्रभावी तरीका क्या है?

Answer 1

संबंधित आईडी के साथ पहले से ही देखे गए तत्वों का मानचित्र रखें।

from itertools import count 
from collections import defaultdict 


mapping = defaultdict(count().__next__) 
result = [] 
for element in my_list: 
    result.append(mapping[tuple(element)]) 

तुम भी एक सूची-समझ इस्तेमाल कर सकते हैं:

result = [mapping[tuple(element)] for element in my_list] 

दुर्भाग्य list रों ताकि आप जब उन्हें मैपिंग की कुंजी के रूप में संग्रहीत करने के लिए उन्हें एक tuple में बदलने के लिए है hashable नहीं कर रहे हैं।

---

नोट defaultdict का उपयोग करने का चाल, और count().__next__ अद्वितीय बढ़ती आईडी प्रदान करने के लिए। Python2 पर आपको को .next के साथ प्रतिस्थापित करना होगा।

defaultdict कोई कुंजी नहीं मिलने पर डिफ़ॉल्ट मान असाइन करेगा। डिफॉल्ट मान कन्स्ट्रक्टर में दिए गए फ़ंक्शन को कॉल करके प्राप्त किया जाता है। इस मामले में __next__count() जनरेटर की संख्या बढ़ती संख्या पैदा करती है।

एक अधिक पोर्टेबल विकल्प तुम कर सकते हो के रूप में:

result = [my_list.index(el) for el in my_list] 

:

from functools import partial 

mapping = defaultdict(partial(next, count())) 

---

एक वैकल्पिक समाधान, के रूप में टिप्पणी में प्रस्तावित है, बस विशिष्ट आईडी के रूप में इंडेक्स का उपयोग करने के लिए है हालांकि यह लागू है:

• यह तों हे (एन^2) हे के बजाय समय (एन)
• आईडी, अद्वितीय हैं बढ़ रही है, लेकिन लगातार नहीं (जो या एक समस्या नहीं हो सकता)

दो समाधान की तुलना के लिए देखें:

In [1]: from itertools import count 
    ...: from collections import defaultdict 

In [2]: def hashing(seq): 
    ...:   mapping = defaultdict(count().__next__) 
    ...:   return [mapping[tuple(el)] for el in seq] 
    ...: 

In [3]: def indexing(seq): 
    ...: return [seq.index(i) for i in seq] 
    ...: 

In [4]: from random import randint 

In [5]: seq = [[randint(1, 20), randint(1, 20), randint(1, 20)] for _ in range(90000)] 

In [6]: %timeit hashing(seq) 
10 loops, best of 3: 37.7 ms per loop 

In [7]: %timeit indexing(seq) 
1 loop, best of 3: 26 s per loop 

नोट कैसे एक 90k तत्व सूची के लिए मानचित्रण समाधान कम 40 मिलीसेकेंड लेता जबकि अनुक्रमण समाधान 26 सेकंड लेता है।

Answer 2

यह मैं इसे कैसे संपर्क किया है:

from itertools import product 
from random import randint 
import time 

t0 = time.time() 
def id_list(lst): 
    unique_set = set(tuple(x) for x in lst) 
    unique = [list(x) for x in unique_set] 
    unique.sort(key = lambda x: lst.index(x)) 

    result = [unique.index(i[1]) for i in product(lst, unique) if i[0] == i[1]] 

    return result 

seq = [[randint(1, 5), randint(1, 5), randint(1, 5)] for i in range(90000)] 

print(id_list(seq)) 

t1 = time.time() 

print("Time: %.4f seconds" % (t1-t0)) 

कौन सा बाहर आईडी के अनुक्रम प्रिंट, एक अनुमानित समय यह और 4 के बीच एक सूची में यादृच्छिक पूर्णांकों का एक अनुक्रम गणना करने के लिए ले लिया के साथ, बार।

Time: 2.3397 seconds # Will slightly differ from computation to computation 

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

मैंने कोड ब्लॉक के प्रारंभ और अंत के बीच समय अंतराल लेबल करने के लिए time लाइब्रेरी का भी उपयोग किया।

import time 

t0 = time.time() 

# code block here 

t1 = time.time() 

# Difference in time: t1 - t0 

product कोड खंड में इस्तेमाल भी गणना तेज़ हो जाएगी साथ itertools पुस्तकालय।

Answer 3

मैं Bakuriu के समाधान की मामूली संशोधन कि NumPy सरणी के साथ ही काम करता है, यह स्मृति पदचिह्न और गणना के मामले में बेहतर काम करता है (के रूप में यह tuples को सरणियों कास्ट करने के लिए की जरूरत है):

from itertools import count 
from collections import defaultdict 
from functools import partial 

def hashing_v1(seq): 
    mapping = defaultdict(partial(next, count())) 
    return [mapping[tuple(el)] for el in seq] 

def hashing_v2(seq): 
    mapping = defaultdict(partial(next, count())) 
    result = [] 
    for le in seq: 
     le.flags.writeable = False 
     result.append(mapping[le.data]) 
    return result 

In [4]: seq = np.random.rand(50000, 2000) 

In [5]: %timeit hashing_v1(seq) 
1 loop, best of 3: 14.1 s per loop 

In [6]: %timeit hashing_v2(seq) 
1 loop, best of 3: 1.2 s per loop