Lập chỉ mục danh sách có chỉ mục duy nhất

Question

Tôi có danh sách có nội dung là l = [10,10,20,15,10,20]. Tôi muốn chỉ định từng giá trị duy nhất cho một "chỉ mục" nhất định để nhận được [1,1,2,3,1,2].

Đây là mã của tôi:

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

Mà hóa ra là rất chậm.

l có 1M yếu tố và 100K yếu tố độc đáo. Tôi cũng đã thử bản đồ với lambda và phân loại, mà không giúp đỡ. Cách lý tưởng để làm điều này là gì?

Answer 1

Các sự chậm chạp của mã của bạn phát sinh do a.index(x) thực hiện tìm kiếm tuyến tính và bạn thực hiện điều đó tìm kiếm tuyến tính cho mỗi người trong số các yếu tố trong l. Vì vậy, đối với mỗi mục 1M bạn thực hiện (tối đa) 100K so sánh.

Cách nhanh nhất để chuyển đổi một giá trị này sang giá trị khác là tìm kiếm nó trên bản đồ. Bạn sẽ cần phải tạo bản đồ và điền vào mối quan hệ giữa các giá trị ban đầu và các giá trị bạn muốn. Sau đó, lấy giá trị từ bản đồ khi bạn gặp một giá trị khác có cùng giá trị trong danh sách của bạn.

Dưới đây là ví dụ tạo một đường chuyền qua l. Có thể có chỗ để tối ưu hóa thêm để loại bỏ sự cần thiết phải liên tục phân bổ lại res khi thêm vào nó.

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

Bạn có thể làm điều này trong O(N) thời gian sử dụng một defaultdict và một danh sách hiểu:

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

Trong Python 3 sử dụng __next__ thay vì next.

---

Nếu bạn đang tự hỏi nó hoạt động như thế nào?

Các default_factory (tức count(1).next trong trường hợp này) truyền cho defaultdict được gọi là chỉ khi Python gặp một chìa khóa bị mất, vì vậy trong 10 giá trị sẽ là 1, sau đó trong mười tiếp theo nó không phải là một chìa khóa bị mất nữa do đó tính toán 1 trước đây được sử dụng, bây giờ 20 lại là một khóa bị thiếu và Python sẽ gọi lại số default_factory để nhận giá trị của nó và cứ thế.

d ở cuối sẽ trông như thế này:

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

Answer 3

giải pháp của bạn là chậm vì sự phức tạp của nó là O(nm) với m là số của các yếu tố độc đáo trong l: a.index() là O(m) và bạn gọi nó cho mọi phần tử trong l.

Để làm cho nó O(n), thoát khỏi index() và lập chỉ mục lưu trữ trong một cuốn từ điển:

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

Nếu l chỉ chứa các số nguyên trong một phạm vi được biết đến, bạn cũng có thể lưu trữ các chỉ số trong một danh sách thay vì một từ điển cho tra cứu nhanh hơn.

Answer 4

Tôi đoán điều đó phụ thuộc vào việc bạn có muốn trả lại các chỉ mục theo thứ tự cụ thể đó hay không. Nếu bạn muốn ví dụ trả lại:

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

thì bạn có thể xem các câu trả lời khác được gửi. Tuy nhiên nếu bạn chỉ quan tâm đến việc một chỉ số duy nhất cho mỗi số duy nhất sau đó tôi có một giải pháp nhanh chóng cho bạn

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

và cho ví dụ này đầu ra của y là:

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

Tôi thử nghiệm này cho 1.000.000 mục và nó đã được thực hiện cơ bản ngay lập tức.

Answer 5

Đối completness, bạn cũng có thể làm điều đó háo hức:

from itertools import count 

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

này sử dụng một thiết lập để có được những lời duy nhất trong list_, cặp mỗi những lời độc đáo với giá trị kế tiếp từ count() (mà đếm ngược) và xây dựng từ điển từ kết quả.

Original answer, được viết bởi nneonneo.

Answer 6

Bạn có thể sử dụng collections.OrderedDict() để duy trì các mục duy nhất theo thứ tự và lặp lại liệt kê các mặt hàng độc đáo đã đặt hàng này để có được một mệnh đề của các mục và các chỉ mục đó (dựa trên thứ tự của chúng). danh sách chính để operator.itemgetter() để nhận chỉ mục tương ứng cho mỗi mục:

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