Câu hỏi Cách nhanh nhất để thêm dữ liệu vào danh sách mà không cần sao chép trong python (2.5)


Tôi có khoảng nửa triệu vật cần phải được đặt trong một danh sách, tôi không thể có bản sao, và nếu một món đồ đã có sẵn, tôi cần lấy chỉ mục của nó. Cho đến nay tôi có

if Item in List:
    ItemNumber=List.index(Item)
else:
    List.append(Item)
    ItemNumber=List.index(Item)

Vấn đề là khi danh sách phát triển nó được dần dần chậm hơn cho đến một lúc nào đó nó chỉ là không có giá trị làm. Tôi bị giới hạn ở python 2.5 vì nó là một hệ thống nhúng.


17
2017-09-20 17:29


gốc




Các câu trả lời:


Bạn có thể sử dụng bộ (trong CPython kể từ phiên bản 2.4) để tìm kiếm các giá trị trùng lặp một cách hiệu quả. Nếu bạn thực sự cần một hệ thống được lập chỉ mục, bạn có thể sử dụng cả tập hợp và danh sách.

Thực hiện tra cứu của bạn bằng cách sử dụng một bộ sẽ loại bỏ chi phí của if Item in List, nhưng không phải của List.index(Item)

Xin lưu ý ItemNumber=List.index(Item) sẽ rất không hiệu quả để làm sau List.append(Item). Bạn biết độ dài của danh sách, vì vậy chỉ mục của bạn có thể được truy xuất với ItemNumber = len(List)-1.

Để loại bỏ hoàn toàn phí trên List.index (bởi vì phương pháp đó sẽ tìm kiếm trong danh sách - rất không hiệu quả trên các tập lớn hơn), bạn có thể sử dụng một ánh xạ dict Các mục trở lại chỉ mục của chúng.

Tôi có thể viết lại nó như sau:

# earlier in the program, NOT inside the loop
Dup = {}

# inside your loop to add items:
if Item in Dup:
    ItemNumber = Dup[Item]
else:
    List.append(Item)
    Dup[Item] = ItemNumber = len(List)-1

15
2017-09-20 17:32





Nếu bạn thực sự cần giữ dữ liệu trong một mảng, tôi sẽ sử dụng một từ điển riêng để theo dõi các bản sao. Điều này đòi hỏi nhiều gấp đôi bộ nhớ, nhưng sẽ không làm chậm đáng kể.

existing = dict()
if Item in existing:
    ItemNumber = existing[Item]
else:
    ItemNumber = existing[Item] = len(List)
    List.append(Item)

Tuy nhiên, nếu bạn không cần lưu thứ tự các mục, bạn chỉ nên sử dụng set thay thế. Điều này sẽ chiếm hầu như không gian như một danh sách, nhưng sẽ nhanh như một từ điển.

Items = set()
# ...
Items.add(Item) # will do nothing if Item is already added

Cả hai đều yêu cầu đối tượng của bạn là có thể băm. Trong Python, hầu hết các kiểu có thể băm trừ khi chúng là một vùng chứa có nội dung có thể được sửa đổi. Ví dụ: lists không được băm vì bạn có thể sửa đổi nội dung của chúng, nhưng tuples có thể băm vì bạn không thể.

Nếu bạn đang cố gắng lưu trữ các giá trị không băm, thì không có giải pháp chung nhanh nào.


7
2017-09-20 17:32





Bạn có thể cải thiện séc rất nhiều:

check = set(List)

for Item in NewList:
    if Item in check: ItemNumber = List.index(Item)
    else:
        ItemNumber = len(List)
        List.append(Item)

Hoặc, thậm chí tốt hơn, nếu thứ tự không quan trọng bạn có thể làm điều này:

oldlist = set(List)
addlist = set(AddList)
newlist = list(oldlist | addlist)

Và nếu bạn cần lặp lại các mục đã được sao chép:

for item in (oldlist & addlist):
    pass # do stuff

5
2017-09-20 17:32





Phạm vi của nửa triệu mặt hàng của bạn là bao nhiêu? Bạn có thể sử dụng bộ nhớ rất kém hiệu quả nếu bạn có thể đưa ra một vài câu lệnh về phạm vi của các mục này. Tôi tin rằng một cách tiếp cận dọc theo dòng này sẽ là nhanh nhất có thể, nhưng có thể không thực tế cho một ứng dụng nhúng trừ khi bạn có thể thực hiện một số bảo đảm rất nghiêm ngặt.

Câu trả lời này có giúp bạn hướng tới việc giao dịch thời gian / bộ nhớ mà tôi đang ám chỉ không? Tôi có thể giúp làm rõ thêm nếu bạn muốn.


0
2017-09-20 17:39