Cấu trúc dữ liệu đồ thị hiệu quả nhất trong Python là gì?

Question

Tôi cần để có thể thao tác một đồ thị lớn (10^7 nút) trong python. Các dữ liệu tương ứng với mỗi nút/cạnh là tối thiểu, nói rằng, một số lượng nhỏ các chuỗi. Hiệu quả nhất, về bộ nhớ và tốc độ, cách thực hiện điều này là gì?

Nguyên tắc dicts linh hoạt hơn và đơn giản hơn để triển khai, nhưng tôi trực giác mong đợi danh sách các danh sách sẽ nhanh hơn. Tùy chọn danh sách cũng sẽ yêu cầu tôi giữ dữ liệu riêng biệt với cấu trúc, trong khi dicts sẽ cho phép loại nội dung nào đó:

graph[I][J]["Property"]="value" 

Bạn sẽ đề xuất điều gì?

---

Vâng, tôi phải hiểu rõ hơn về ý nghĩa của hiệu quả. Trong trường hợp cụ thể này, tôi có nghĩa là nó về truy xuất ngẫu nhiên.

Việc tải dữ liệu vào bộ nhớ không phải là vấn đề lớn. Điều đó được thực hiện một lần và cho tất cả. Phần tiêu tốn thời gian là truy cập các nút để tôi có thể trích xuất thông tin và đo các chỉ số mà tôi quan tâm.

Tôi đã không coi việc tạo từng nút là một thuộc tính (giống nhau cho tất cả các nút). như vậy sẽ thêm một lớp chi phí trên không? Tôi đã hy vọng một người nào đó sẽ có một số kinh nghiệm trực tiếp với một trường hợp tương tự mà họ có thể chia sẻ. Sau khi tất cả, đồ thị là một trong những trừu tượng phổ biến nhất trong CS.

Answer 1

Tôi mạnh mẽ sẽ ủng hộ bạn xem NetworkX. Đó là một con ngựa chiến tranh thử nghiệm chiến đấu và công cụ đầu tiên hầu hết các loại 'nghiên cứu' đạt được khi họ cần phân tích dữ liệu dựa trên mạng. Tôi đã thao tác đồ thị với 100 hàng nghìn cạnh mà không gặp vấn đề gì trên sổ ghi chép. Tính năng của nó phong phú và rất dễ sử dụng. Bạn sẽ thấy mình tập trung nhiều hơn vào vấn đề ở bàn tay hơn là các chi tiết trong việc thực hiện bên dưới.

Ví dụ về Erdős-Rényi thế hệ đồ thị ngẫu nhiên và phân tích

""" 
Create an G{n,m} random graph with n nodes and m edges 
and report some properties. 

This graph is sometimes called the Erd##[m~Qs-Rényi graph 
but is different from G{n,p} or binomial_graph which is also 
sometimes called the Erd##[m~Qs-Rényi graph. 
""" 
__author__ = """Aric Hagberg (hagberg@lanl.gov)""" 
__credits__ = """""" 
# Copyright (C) 2004-2006 by 
# Aric Hagberg 
# Dan Schult 
# Pieter Swart 
# Distributed under the terms of the GNU Lesser General Public License 
# http://www.gnu.org/copyleft/lesser.html 

from networkx import * 
import sys 

n=10 # 10 nodes 
m=20 # 20 edges 

G=gnm_random_graph(n,m) 

# some properties 
print "node degree clustering" 
for v in nodes(G): 
    print v,degree(G,v),clustering(G,v) 

# print the adjacency list to terminal 
write_adjlist(G,sys.stdout) 

Visualizations cũng đơn giản:

More trực quan: http://jonschull.blogspot.com/2008/08/graph-visualization.html

Answer 2

Từ điển cũng có thể chứa phí, tùy thuộc vào việc triển khai thực tế. Một hashtable thường chứa một số số nguyên tố của các nút có sẵn để bắt đầu, mặc dù bạn chỉ có thể sử dụng một vài nút.

Đánh giá theo ví dụ của bạn, "Thuộc tính", bạn sẽ tốt hơn với cách tiếp cận lớp học cho cấp độ cuối cùng và thuộc tính thực tế? Hoặc là tên của các thuộc tính thay đổi rất nhiều từ nút đến nút?

Tôi muốn nói rằng những gì "hiệu quả" có nghĩa là phụ thuộc vào rất nhiều thứ, như:

• tốc độ cập nhật (insert, update, delete)
• tốc độ thu hồi truy cập ngẫu nhiên
• tốc độ hồi tuần tự
• bộ nhớ sử dụng

tôi nghĩ rằng bạn sẽ thấy rằng một cấu trúc dữ liệu đó là nhanh chóng sẽ thường c cho phép nhiều bộ nhớ hơn bộ nhớ chậm. Đây không phải lúc nào cũng như vậy, nhưng hầu hết các cấu trúc dữ liệu dường như theo dõi điều này.

Từ điển có thể dễ sử dụng và cung cấp cho bạn khả năng truy cập nhanh tương đối đồng đều, rất có thể sẽ sử dụng nhiều bộ nhớ hơn, như bạn đề xuất, danh sách. Danh sách, tuy nhiên, thường có xu hướng chứa thêm chi phí khi bạn chèn dữ liệu vào nó, trừ khi họ preallocate X nút, trong đó họ sẽ lại sử dụng nhiều bộ nhớ hơn.

Đề xuất của tôi, nói chung sẽ chỉ sử dụng phương pháp có vẻ tự nhiên nhất đối với bạn và sau đó thực hiện "kiểm tra căng thẳng" của hệ thống, thêm một lượng lớn dữ liệu vào đó vấn đề.

Bạn cũng có thể xem xét thêm lớp trừu tượng vào hệ thống của mình, để bạn không phải thay đổi giao diện lập trình nếu sau này bạn cần phải thay đổi cấu trúc dữ liệu nội bộ.

Answer 3

Tạo cấu trúc dựa trên lớp học có thể có nhiều chi phí hơn cấu trúc dựa trên dict, vì trong các lớp python thực sự sử dụng dicts khi chúng được triển khai.

Answer 4

Như tôi đã hiểu, truy cập ngẫu nhiên trong thời gian không đổi cho cả ma thuật và danh sách của Python, sự khác biệt là bạn chỉ có thể truy cập ngẫu nhiên các chỉ số nguyên với danh sách. Tôi giả định rằng bạn cần tra cứu một nút bằng nhãn của nó, vì vậy bạn muốn có một dict của dicts. Tuy nhiên, trên mặt trận hiệu suất, tải nó vào bộ nhớ có thể không phải là một vấn đề, nhưng nếu bạn sử dụng quá nhiều bạn sẽ kết thúc trao đổi vào đĩa, mà sẽ giết hiệu suất của ngay cả dicts thậm chí hiệu quả của Python. Cố gắng giảm mức sử dụng bộ nhớ càng nhiều càng tốt. Ngoài ra, RAM là giá rẻ đáng kinh ngạc ngay bây giờ; nếu bạn làm điều này rất nhiều, không có lý do gì để không có ít nhất 4GB.

Nếu bạn muốn được tư vấn về việc giảm mức sử dụng bộ nhớ, hãy cung cấp thêm một số thông tin về loại thông tin bạn đang theo dõi cho từng nút.

Answer 5

Như đã đề cập, NetworkX là rất đi od, với một tùy chọn khác là igraph. Cả hai mô-đun sẽ có hầu hết (nếu không phải tất cả) các công cụ phân tích bạn có thể cần, và cả hai thư viện thường được sử dụng với các mạng lớn.

Answer 6

Mặc dù câu hỏi này bây giờ là khá cũ, tôi nghĩ rằng nó là đáng giá để đề cập đến mô-đun python của riêng tôi cho thao tác đồ thị được gọi là graph-tool. Nó rất hiệu quả, vì các cấu trúc dữ liệu và các thuật toán được thực hiện trong C++, với metaprograming mẫu, sử dụng Thư viện đồ thị tăng cường. Do đó hiệu suất của nó (cả về sử dụng bộ nhớ và thời gian chạy) có thể so sánh với một thư viện C++ thuần túy, và có thể là các đơn đặt hàng có độ lớn tốt hơn mã python điển hình, mà không bị mất dễ sử dụng. Tôi thường xuyên sử dụng nó để làm việc với các đồ thị rất lớn.

Answer 7

Không có nghi ngờ NetworkX là cấu trúc dữ liệu tốt nhất cho đến bây giờ cho biểu đồ. Nó đi kèm với các tiện ích như chức năng trợ giúp, cấu trúc dữ liệu và thuật toán, trình tạo chuỗi ngẫu nhiên, trang trí, thứ tự Cuthill-Mckee, quản lý ngữ cảnh

NetworkX rất tuyệt vời vì nó gây ấn tượng với đồ thị, đồ họa và nhiều chữ. Nó có thể viết đồ thị với nhiều cách: Danh sách Adjacency, Danh sách Admacity đa cấp, Danh sách cạnh, GEXF, GML. Nó hoạt động với Pickle, GraphML, JSON, SparseGraph6, v.v.

Nó có implimentation các thuật toán radimade khác nhau bao gồm: xấp xỉ, song phương, ranh giới, vị trí trung tâm, bè lũ, Clustering, Tô Màu, Linh kiện, kết nối, Cycles, Đạo mạch hở đồ thị, biện pháp cách, Bộ thống trị, Euler, đẳng cấu, Link Phân tích, Dự đoán liên kết, Kết hợp, Cây Spanning tối thiểu, Câu lạc bộ phong phú, Đường đi ngắn nhất, Traversal, Cây.