Cách tốt nhất để sắp xếp hồ sơ 1M bằng Python

Question

Tôi đã một dịch vụ chạy mà phải mất một danh sách khoảng 1.000.000 từ điển và thực hiện những điều sau

myHashTable = {} 
myLists = { 'hits':{}, 'misses':{}, 'total':{} } 
sorted = { 'hits':[], 'misses':[], 'total':[] } 
for item in myList: 
    id = item.pop('id') 
    myHashTable[id] = item 
    for k, v in item.iteritems(): 
    myLists[k][id] = v 

Vì vậy, nếu tôi đã có danh sách sau đây của các từ điển:

[ {'id':'id1', 'hits':200, 'misses':300, 'total':400}, 
    {'id':'id2', 'hits':300, 'misses':100, 'total':500}, 
    {'id':'id3', 'hits':100, 'misses':400, 'total':600} 
] 

tôi kết thúc với

myHashTable = 
{ 
    'id1': {'hits':200, 'misses':300, 'total':400}, 
    'id2': {'hits':300, 'misses':100, 'total':500}, 
    'id3': {'hits':100, 'misses':400, 'total':600} 
} 

và

myLists = 

    { 
     'hits': {'id1':200, 'id2':300, 'id3':100}, 
     'misses': {'id1':300, 'id2':100, 'id3':400}, 
     'total': {'id1':400, 'id2':500, 'id3':600} 
    } 

Sau đó, tôi cần sắp xếp tất cả dữ liệu trong mỗi từ điển myLists.

Những gì tôi đang làm là một cái gì đó như sau:

def doSort(key): 
    sorted[key] = sorted(myLists[key].items(), key=operator.itemgetter(1), reverse=True) 

which would yield, in the case of misses: 
[('id3', 400), ('id1', 300), ('id2', 200)] 

này hoạt động tuyệt vời khi tôi đã lên đến 100.000 hồ sơ hoặc lâu hơn, nhưng với 1.000.000 nó được tham gia ít nhất 5 - 10 phút để sắp xếp mỗi tổng cộng 16 (danh sách ban đầu của tôi về từ điển thực sự có 17 lĩnh vực bao gồm id được popped)

* EDIT * dịch vụ này là một ThreadingTCPServer trong đó có một phương pháp cho phép một khách hàng để kết nối và thêm 01.dữ liệu mới. Các dữ liệu mới có thể bao gồm kỷ lục mới (có nghĩa là từ điển với độc đáo 'id của những gì đã có trong bộ nhớ ) hoặc hồ sơ sửa đổi (nghĩa cùng 'id' với dữ liệu khác nhau cho các cặp giá trị quan trọng khác

Vì vậy, , lần này đang chạy tôi sẽ vượt qua trong

[ 
    {'id':'id1', 'hits':205, 'misses':305, 'total':480}, 
    {'id':'id4', 'hits':30, 'misses':40, 'total':60}, 
    {'id':'id5', 'hits':50, 'misses':90, 'total':20 
] 

tôi đã được sử dụng từ điển để cửa hàng dữ liệu vì vậy mà tôi không kết thúc với bản sao. Sau khi điển được cập nhật với dữ liệu mới/sửa đổi Tôi sử dụng mỗi chúng.

* END EDIT *

Vì vậy, cách tốt nhất đối với tôi để sắp xếp này là gì? Có phương pháp nào tốt hơn không?

Answer 1

Bạn có thể tìm thấy câu trả lời liên quan này từ Guido: Sorting a million 32-bit integers in 2MB of RAM using Python

Answer 2

sorted(myLists[key], key=mylists[key].get, reverse=True) 

sẽ giúp bạn tiết kiệm thời gian, mặc dù không nhiều.

Answer 3

Thành thật mà nói, cách tốt nhất là không sử dụng Python. Nếu hiệu suất là một mối quan tâm lớn cho điều này, sử dụng một ngôn ngữ nhanh hơn.

Answer 4

Điều bạn thực sự muốn là một vùng chứa có thứ tự, thay vì vùng chứa không có thứ tự. Điều đó sẽ ngầm sắp xếp kết quả khi chúng được chèn vào. Cấu trúc dữ liệu chuẩn cho điều này là một cái cây.

Tuy nhiên, dường như không có một trong số này trong Python. Tôi không thể giải thích điều đó; đây là một loại dữ liệu cơ bản, cốt lõi trong bất kỳ ngôn ngữ nào. Lệnh và tập lệnh của Python là cả hai vùng chứa không có thứ tự, ánh xạ tới cấu trúc dữ liệu cơ bản của bảng băm.Nó chắc chắn sẽ có cấu trúc dữ liệu cây được tối ưu hóa; có nhiều thứ bạn có thể làm với chúng, điều đó là không thể với một bảng băm, và chúng khá phức tạp để thực hiện tốt, vì vậy mọi người thường không muốn tự làm nó.

(Ngoài ra còn có bản đồ không có gì để một danh sách liên kết, mà còn phải là một kiểu dữ liệu cốt lõi. Không, một deque không tương đương.)

Tôi không có một thực hiện chứa lệnh hiện có để chỉ cho bạn (và nó có lẽ nên được thực hiện nguyên bản, không phải trong Python), nhưng hy vọng điều này sẽ chỉ cho bạn đi đúng hướng.

Việc triển khai cây tốt sẽ hỗ trợ lặp qua phạm vi theo giá trị ("lặp tất cả giá trị từ [2.100] theo thứ tự"), tìm giá trị tiếp theo/trước từ bất kỳ nút nào khác trong O (1), khai thác dải hiệu quả (" xóa tất cả các giá trị trong [2.100] và trả về chúng trong một cây mới "), v.v. Nếu có ai có cấu trúc dữ liệu được tối ưu hóa tốt như thế này cho Python, tôi rất muốn biết về nó. (Không phải tất cả các hoạt động đều phù hợp với mô hình dữ liệu của Python, ví dụ, để có được giá trị tiếp theo/trước từ một giá trị khác, bạn cần tham chiếu đến một nút chứ không phải chính giá trị đó.)

Answer 5

Nếu bạn có một số trường cố định , sử dụng các bộ dữ liệu thay vì từ điển. Đặt trường bạn muốn sắp xếp ở vị trí đầu tiên và chỉ cần sử dụng mylist.sort()

Answer 6

Tôi sẽ xem xét sử dụng thuật toán phân loại khác. Một cái gì đó giống như một Merge Sort có thể hoạt động. Chia danh sách thành các danh sách nhỏ hơn và sắp xếp chúng riêng lẻ. Sau đó lặp lại.

Pseudo code:

list1 = [] // sorted separately 
list2 = [] // sorted separately 

// Recombine sorted lists 
result = [] 
while (list1.hasMoreElements || list2.hasMoreElements): 
    if (! list1.hasMoreElements): 
     result.addAll(list2) 
     break 
    elseif (! list2.hasMoreElements): 
     result.AddAll(list1) 
     break 

    if (list1.peek < list2.peek): 
     result.add(list1.pop) 
    else: 
     result.add(list2.pop) 

Answer 7

Những người khác đã cung cấp một số lời khuyên tuyệt vời, hãy thử chúng ra.

Như một lời khuyên chung, trong các trường hợp như vậy bạn cần phải cấu hình mã của bạn. Biết chính xác phần lớn thời gian được sử dụng. Nút cổ chai ẩn tốt, ở những nơi bạn ít mong đợi nhất.
Nếu có rất nhiều crunching số tham gia sau đó một trình biên dịch JIT như (bây giờ đã chết) psyco cũng có thể giúp đỡ. Khi quá trình xử lý mất vài phút hoặc 2 giờ, tốc độ thực sự sẽ tăng lên.

• http://docs.python.org/library/profile.html
• http://www.vrplumber.com/programming/runsnakerun/
• http://psyco.sourceforge.net/

Answer 8

Glenn Maynard là đúng rằng một ánh xạ được sắp xếp sẽ thích hợp ở đây. Đây là một cho python: http://wiki.zope.org/ZODB/guide/node6.html#SECTION000630000000000000000

Answer 9

Điều này có vẻ khá nhanh.

raw= [ {'id':'id1', 'hits':200, 'misses':300, 'total':400}, 
    {'id':'id2', 'hits':300, 'misses':100, 'total':500}, 
    {'id':'id3', 'hits':100, 'misses':400, 'total':600} 
] 

hits= [ (r['hits'],r['id']) for r in raw ] 
hits.sort() 

misses = [ (r['misses'],r['id']) for r in raw ] 
misses.sort() 

total = [ (r['total'],r['id']) for r in raw ] 
total.sort() 

Có, nó làm cho ba vượt qua dữ liệu thô. Tôi nghĩ rằng nó nhanh hơn kéo dữ liệu trong một lần.

Answer 10

Thay vì cố gắng giữ danh sách của bạn được sắp xếp, có thể bạn có thể nhận được bằng hàng đợi heap. Nó cho phép bạn đẩy bất kỳ mục nào, giữ một mục nhỏ nhất tại h[0] và popping mục này (và 'sủi bọt' nhỏ nhất tiếp theo) là hoạt động O(nlogn).

vậy, chỉ cần tự hỏi mình:

• để tôi cần the whole list ra lệnh tất cả các thời gian? : Sử dụng một cấu trúc lệnh (như gói BTree Zope, như mentioned bởi Ealdwulf)

• hoặc toàn bộ danh sách đặt hàng nhưng chỉ sau một ngày làm việc của chèn ngẫu nhiên ?: sử dụng loại giống như bạn đang làm, hoặc như S.Lott's answer

• hoặc chỉ một vài mục 'nhỏ nhất' vào bất kỳ lúc nào? : sử dụng heapq

Answer 11

Tôi đã thực hiện một số cách nhanh chóng về cả cách ban đầu và đề xuất của SLott. Trong trường hợp không phải mất 5-10 phút cho mỗi lĩnh vực. Việc phân loại thực tế không phải là vấn đề. Dường như phần lớn thời gian được dành cho dữ liệu slinging xung quanh và chuyển đổi nó. Ngoài ra, việc sử dụng bộ nhớ của tôi đang tăng vọt - python của tôi là hơn 350 megabyte! bạn có chắc là bạn không dùng hết ram và phân trang đĩa không? Ngay cả với máy tính xách tay xử lý tiết kiệm điện năng cũ 3 năm của tôi, tôi thấy kết quả cách ít hơn 5-10 phút cho mỗi khóa được sắp xếp cho một triệu mục. Những gì tôi không thể giải thích là sự thay đổi trong các cuộc gọi sắp xếp thực tế(). Tôi biết python sắp xếp là rất tốt tại phân loại một phần được sắp xếp danh sách, vì vậy có lẽ danh sách của mình là nhận được một phần được sắp xếp trong biến đổi từ dữ liệu thô vào danh sách được sắp xếp.

Dưới đây là các kết quả cho phương pháp slott của:

done creating data 
done transform. elapsed: 16.5160000324 
sorting one key slott's way takes 1.29699993134 

đây là đoạn code để có được những kết quả:

starttransform = time.time() 
hits= [ (r['hits'],r['id']) for r in myList ] 
endtransform = time.time() 
print "done transform. elapsed: " + str(endtransform - starttransform) 
hits.sort() 
endslottsort = time.time() 
print "sorting one key slott's way takes " + str(endslottsort - endtransform) 

Bây giờ các kết quả cho các phương pháp ban đầu, hoặc ít nhất là một phiên bản chặt chẽ với một số thiết bị đo đạc đã thêm:

done creating data 
done transform. elapsed: 8.125 
about to get stuff to be sorted 
done getting data. elapsed time: 37.5939998627 
about to sort key hits 
done sorting on key <hits> elapsed time: 5.54699993134 

Đây là mã:

for k, v in myLists.iteritems(): 
    time1 = time.time() 
    print "about to get stuff to be sorted " 
    tobesorted = myLists[k].items() 
    time2 = time.time() 
    print "done getting data. elapsed time: " + str(time2-time1) 
    print "about to sort key " + str(k) 
    mysorted[k] = tobesorted.sort(key=itemgetter(1)) 
    time3 = time.time() 
    print "done sorting on key <" + str(k) + "> elapsed time: " + str(time3-time2)