Gán id duy nhất cho danh sách liệt kê trong python nơi bản sao có được id cùng

Question

Tôi có một danh sách liệt kê (có thể chứa lên đến 90k yếu tố)

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

Tôi muốn chỉ định id cho mỗi yếu tố , trong đó id là duy nhất, ngoại trừ khi mục được sao chép. Vì vậy, để xem danh sách trên, tôi cần trở lại này:

[0,1,0,1,2] 

cách hiệu quả nhất để làm điều này là gì?

Answer 1

Giữ bản đồ các thành phần đã xem với id được liên kết.

from itertools import count 
from collections import defaultdict 


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

bạn cũng có thể sử dụng danh sách-hiểu:

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

Thật không may list s không hashable vì vậy bạn phải chuyển đổi chúng sang một tuple khi lưu trữ chúng như là chìa khóa của việc lập bản đồ.

---

Lưu ý lừa của việc sử dụng defaultdict, và count().__next__ để cung cấp id tăng độc đáo. Trên python2, bạn phải thay thế .__next__ bằng .next.

defaultdict sẽ chỉ định giá trị mặc định khi không tìm thấy khóa. Giá trị mặc định thu được bằng cách gọi hàm được cung cấp trong hàm tạo. Trong trường hợp này, phương pháp __next__ của máy phát điện count() mang lại số lượng ngày càng tăng.

Là một thay thế khả năng di chuyển bạn có thể làm:

from functools import partial 

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

---

Một giải pháp thay thế, như đề xuất trong các ý kiến, là chỉ cần sử dụng các chỉ số như id duy nhất:

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

Tuy nhiên, đây là một ví dụ:

• Nó tak es O (N^2) thời gian thay vì O (N)
• Các id là duy nhất, tăng nhưng không liên tục (có thể hoặc không thể là một vấn đề)

Để so sánh hai giải pháp xem:

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 

Note thế nào để có danh sách các yếu tố 90k giải pháp lập bản đồ mất ít 40 mili giây trong khi các giải pháp lập chỉ mục mất 26 giây .

Answer 2

Đây là cách tôi tiếp cận nó:

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

nào in ra chuỗi các id, cùng với một thời gian xấp xỉ nó mất để tính toán một chuỗi các số nguyên ngẫu nhiên trong danh sách giữa và , lần.

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

Thời gian thực tế sẽ luôn cao hơn một chút, vì nó cần được tính toán trong báo cáo in ở cuối, nhưng không quá chênh lệch.

Tôi cũng đã sử dụng thư viện time để gắn nhãn khoảng thời gian giữa thời gian bắt đầu và kết thúc của khối mã.

import time 

t0 = time.time() 

# code block here 

t1 = time.time() 

# Difference in time: t1 - t0 

Các itertools thư viện cùng với product được sử dụng trong đoạn mã sẽ tăng tốc độ tính toán quá.

Answer 3

tôi sửa đổi chút ít dung dịch Bakuriu rằng chỉ làm việc với mảng NumPy, nó hoạt động tốt hơn về bộ nhớ và tính toán (vì nó không cần phải cast mảng để 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