एक अद्वितीय इंडेक्स

Question

के साथ एक सूची इंडेक्स करना मेरे पास एक सूची है l = [10,10,20,15,10,20]। मैं [1,1,2,3,1,2] प्राप्त करने के लिए प्रत्येक अद्वितीय मान को एक निश्चित "अनुक्रमणिका" असाइन करना चाहता हूं।

a = list(set(l)) 
res = [a.index(x) for x in l] 

कौन सा पता चला है बहुत धीमी गति से होने के लिए:

यह मेरा कोड है।

l में 1 एम तत्व हैं, और 100K अद्वितीय तत्व हैं। मैंने लैम्ब्डा और सॉर्टिंग के साथ मानचित्र की भी कोशिश की है, जिसने मदद नहीं की। ऐसा करने का आदर्श तरीका क्या है?

Answer 1

अपने कोड की सुस्ती पैदा होती है क्योंकि a.index(x) एक रेखीय खोज करता है और आप l में तत्वों में से प्रत्येक के लिए कि रैखिक खोज करें। इसलिए 1 एम आइटमों में से प्रत्येक के लिए आप 100K तुलना (प्रदर्शन) करते हैं।

एक मूल्य को दूसरे में बदलने का सबसे तेज़ तरीका इसे मानचित्र में देख रहा है। आपको नक्शा बनाने और मूल मूल्यों और मूल्यों के बीच संबंधों को भरने की आवश्यकता होगी। फिर जब आप अपनी सूची में एक ही मूल्य का सामना करते हैं तो मानचित्र से मूल्य पुनर्प्राप्त करें।

यहां एक उदाहरण है जो l के माध्यम से एक एकल पास बनाता है। इसमें शामिल होने पर res को बार-बार पुन: आवंटित करने की आवश्यकता को खत्म करने के लिए और अनुकूलन के लिए कक्ष हो सकता है।

res = [] 
conversion = {} 
i = 0 
for x in l: 
    if x not in conversion: 
     value = conversion[x] = i 
     i += 1 
    else: 
     value = conversion[x] 
    res.append(value) 

Answer 2

आप एक defaultdict और एक सूची समझ का उपयोग कर O(N) समय में ऐसा कर सकते हैं:

>>> from itertools import count 
>>> from collections import defaultdict 
>>> lst = [10, 10, 20, 15, 10, 20] 
>>> d = defaultdict(count(1).next) 
>>> [d[k] for k in lst] 
[1, 1, 2, 3, 1, 2] 

next अजगर 3 उपयोग __next__ बजाय में।

---

यदि आप सोच रहे हैं कि यह कैसे काम करता है?

default_factory (यानी इस मामले में count(1).next) अगले दस के लिए तो defaultdict के लिए पारित कहा जाता है केवल जब अजगर एक लापता कुंजी का सामना करना पड़ता है, तो 10 के लिए मूल्य 1 होने जा रहा है, यह एक लापता कुंजी नहीं है अब और इसलिए पहले गणना की गई 1 का उपयोग किया जाता है, अब 20 एक लापता कुंजी है और पाइथन default_factory को फिर से अपना मूल्य प्राप्त करने के लिए कॉल करेगा।

d अंत में इस तरह दिखेगा:

>>> d 
defaultdict(<method-wrapper 'next' of itertools.count object at 0x1057c83b0>, 
      {10: 1, 20: 2, 15: 3}) 

Answer 3

आपका समाधान धीमी है क्योंकि इसकी जटिलता m साथ O(nm) है l में अद्वितीय तत्वों की संख्या जा रहा है: a.index()O(m) है और आप l में प्रत्येक तत्व के लिए यह कहते हैं।

बनाने के यह O(n), एक शब्दकोश में index() से छुटकारा पाने और दुकान अनुक्रमित: l एक ज्ञात रेंज में केवल पूर्णांकों शामिल

>>> idx, indexes = 1, {} 
>>> for x in l: 
...  if x not in indexes: 
...   indexes[x] = idx 
...   idx += 1 
... 
>>> [indexes[x] for x in l] 
[1, 1, 2, 3, 1, 2] 

हैं, तो आप भी करने के लिए एक शब्दकोश के बजाय एक सूची में अनुक्रमित संग्रहीत कर सकती है तेज लुकअप

Answer 4

अच्छी तरह से मुझे लगता है कि यह इस बात पर निर्भर करता है कि क्या आप इसे उस विशिष्ट क्रम में इंडेक्स वापस करना चाहते हैं या नहीं। यदि आप उदाहरण वापस लौटना चाहते हैं:

[1,1,2,3,1,2] 

तो आप सबमिट किए गए अन्य उत्तरों को देख सकते हैं।

y = [0,0,2,1,0,2] 

मैं के लिए इस परीक्षण किया: लेकिन यदि आप उसके बाद ही प्रत्येक अद्वितीय संख्या के लिए एक अनूठा सूचकांक हो रही के बारे में परवाह मैं के लिए आप

import numpy as np 
    l = [10,10,20,15,10,20] 
    a = np.array(l) 
    x,y = np.unique(a,return_inverse = True) 

और इस उदाहरण के लिए y के उत्पादन में है एक तेजी से समाधान है 1,000,000 प्रविष्टियां और यह अनिवार्य रूप से तुरंत किया गया था।

Answer 5

completness के लिए, आप भी यह बेसब्री से कर सकते हैं:

from itertools import count 

wordid = dict(zip(set(list_), count(1))) 

यह list_ में अद्वितीय शब्द प्राप्त करने के लिए एक सेट का उपयोग, जोड़े count() से अगले मूल्य के साथ उन अद्वितीय शब्दों में से प्रत्येक (जो ऊपर की गणना करता है), और परिणामों से एक शब्दकोश बनाता है।

Original answer, nneonneo द्वारा लिखित।

Answer 6

आप क्रमशः अद्वितीय वस्तुओं को संरक्षित करने के लिए collections.OrderedDict() का उपयोग कर सकते हैं और वस्तुओं के एक आदेश और उन सूचकांक (उनके आदेश के आधार पर) प्राप्त करने के लिए इस आदेशित अद्वितीय वस्तुओं की गणना के ऊपर लूप का उपयोग कर सकते हैं, फिर इस शब्दकोश को पास करें अंतरिक्ष जटिलता या केवल समय जटिलता के बारे में

>>> from collections import OrderedDict 
>>> from operator import itemgetter 
>>> itemgetter(*lst)({j:i for i,j in enumerate(OrderedDict.fromkeys(lst),1)}) 
(1, 1, 2, 3, 1, 2)