Tôi nghĩ mã của bạn không quá đói như bạn mong đợi. Nó phá vỡ và cải cách danh sách, nhưng nó có xu hướng giữ hầu hết các danh sách con còn nguyên vẹn.
Như những người khác đã nhận xét, có thể vẫn làm tốt hơn bằng cách sử dụng các trình bao bọc giữ và/hoặc các thuộc tính HoldXXX, để mô phỏng lời gọi theo tham chiếu.
Đối với một cách tiếp cận lõi khó để một số hiện thực cấu trúc dữ liệu liên quan, xem
http://library.wolfram.com/infocenter/MathSource/7619/
Mã liên quan là trong máy tính xách tay Hemmecke-final.nb (đặt tên như vậy bởi vì nó thực hiện toric Groebner cơ sở thuật toán do R. Hemmecke và đồng tác giả).
Tôi đã đâm vào việc thực hiện lại bằng cách sử dụng các thuộc tính Giữ ... nhưng tôi không giỏi về điều đó và đã từ bỏ khi đoạn mã bị đâm vào tôi (đã bỏ lỡ, nhưng đã giết phiên Mathematica của tôi). Vì vậy, thay vào đó tôi có một triển khai thực hiện sử dụng một kiểu dữ liệu Mathematica "thô" không có giấy tờ, một trong đó là trơ và do đó tuân theo hành vi gọi-by-tham chiếu.
Cấu trúc được đề cập được gọi là "túi expr" vì cấu trúc dữ liệu Mathematica chung là "expr". Nó giống như một Danh sách nhưng (1) Nó có thể phát triển ở một đầu (mặc dù không co lại) và (2) giống như các kiểu biểu thức thô khác (ví dụ: đồ thị trong phiên bản 8). (một API, để nói). "Các yếu tố" cơ bản của nó là trơ theo nghĩa là chúng có thể tham chiếu BẤT CỨ expr (bao gồm cả chính túi) và có thể được thao tác theo cách tôi sẽ chỉ ra dưới đây.
Mục đầu tiên ở trên cung cấp công nghệ cơ bản để thực hiện Sow/Reap. Đây là thứ hai sẽ được quan tâm trong mã dưới đây. Cuối cùng tôi sẽ bao gồm một vài nhận xét dọc theo các dòng giải thích cấu trúc dữ liệu, vì không có tài liệu chính thức cho việc này.
Tôi đã giữ mã nhiều hơn hoặc ít hơn theo kiểu gốc, và đặc biệt nó vẫn là phiên bản trực tuyến (tức là, các yếu tố không cần phải đi ngay từ đầu nhưng có thể được thêm riêng). Đã thay đổi một vài cái tên. Made cấu trúc cơ bản giống như
nút
(hộp, giá trị, bằng không hoặc bốn subnodes bounding) Nếu có subnodes sau đó lĩnh vực giá trị rỗng. Các trường hộp và giá trị được biểu diễn bằng biểu thức Danh sách Mathematica thông thường, mặc dù nó có thể có ý nghĩa để sử dụng các đầu chuyên dụng và có nó giống như một kiểu cấu trúc C. Tôi đã làm một cái gì đó như thế trong việc đặt tên cho các chức năng truy cập/thiết lập trường khác nhau.
Một lưu ý là loại dữ liệu thô này tiêu tốn chi phí bộ nhớ nhiều hơn đáng kể so với ví dụ: một danh sách. Vì vậy, biến thể của tôi dưới đây sẽ sử dụng nhiều bộ nhớ hơn so với mã được đăng ban đầu. Không tiệm cận nhiều hơn, chỉ bằng một yếu tố không đổi. Ngoài ra, nó đòi hỏi một yếu tố không đổi trong chi phí cao hơn, ví dụ, một cấu trúc C so sánh về mặt truy cập hoặc thiết lập giá trị phần tử. Vì vậy, nó không phải là một viên đạn ma thuật, chỉ là một loại dữ liệu với hành vi mà không nên cho những bất ngờ tiệm cận.
AppendTo[$ContextPath, "Internal`"];
makeQuadTreeNode[bounds_] := Bag[{bounds, {}, {}}]
(*is pt inside box?*)
insideBox[pt_, box_] :=
And @@ Thread[box[[1]] <= (List @@ pt) <= box[[2]]]
(*split bounding box into 4 children*)
splitBox[{{xmin_, ymin_}, {xmax_, ymax_}}] :=
Map[makeQuadTreeNode, {{{xmin, (ymin + ymax)/2}, {(xmin + xmax)/2,
ymax}}, {{xmin,
ymin}, {(xmin + xmax)/2, (ymin + ymax)/2}}, {{(xmin + xmax)/2,
ymin}, {xmax, (ymin + ymax)/2}}, {{(xmin + xmax)/
2, (ymin + ymax)/2}, {xmax, ymax}}}]
bounds[qt_] := BagPart[qt, 1]
value[qt_] := BagPart[qt, 2]
children[qt_] := BagPart[qt, 3]
isLeaf[qt_] := value[qt] =!= {}
isSplit[qt_] := children[qt] =!= {}
emptyNode[qt_] := ! isLeaf[qt] && ! isSplit[qt]
(*qtInsert #1-return input if pt is out of bounds*)
qtInsert[qtree_, pt_] /; ! insideBox[pt, bounds[qtree]] := qtree
(*qtInsert #2-empty node (no value,no children)*)
qtInsert[qtree_, pt_] /; emptyNode[qtree] := value[qtree] = pt
(*qtInsert #2-currently a leaf (has a value and no children)*)
qtInsert[qtree_, pt_] /; isLeaf[qtree] := Module[
{kids = splitBox[bounds[qtree]], currval = value[qtree]},
value[qtree] = {};
children[qtree] = kids;
Map[(qtInsert[#, currval]; qtInsert[#, pt]) &, kids];
]
(*qtInsert #4-not a leaf and has children*)
qtInsert[qtree_, pt_] := Map[qtInsert[#, pt] &, children[qtree]];
getBoxes[ee_Bag] :=
Join[{bounds[ee]}, Flatten[Map[getBoxes, children[ee]], 1]]
getPoints[ee_Bag] :=
Join[{value[ee]}, Flatten[Map[getPoints, children[ee]], 1]]
qtDraw[qt_] := Module[
{pts, bboxes},
pts = getPoints[qt] /. {} :> Sequence[];
bboxes = getBoxes[qt];
Graphics[{EdgeForm[Black], Hue[0.2], Map[Disk[#, 0.01] &, pts],
Hue[0.7], EdgeForm[Red],
FaceForm[], (Rectangle @@ #) & /@ bboxes}, Frame -> True]]
Dưới đây là một ví dụ. Tôi sẽ lưu ý rằng việc chia tỷ lệ là hợp lý. Có lẽ O (n log (n)) hay như vậy. Chắc chắn tốt hơn O (n^2).
len = 4000;
pts = RandomReal[{0, 2}, {len, 2}];
qt = makeQuadTreeNode[{{0.0, 0.0}, {2.0, 2.0}}];
Timing[Do[qtInsert[qt, pts[[i]]], {i, 1, len}]]
{1.6, Null}
chung expr túi ghi chú. Đây là những cái cũ vì vậy tôi không tuyên bố rằng tất cả điều này vẫn hoạt động như được chỉ ra.
Các chức năng này nằm trong ngữ cảnh Nội bộ.
Bag Tạo một túi expr, tùy chọn với các yếu tố đặt trước.
BagPart Lấy các bộ phận của túi expr, tương tự như Part cho thông thường exprs. Cũng có thể được sử dụng trên một lhs, ví dụ: để đặt lại giá trị.
StuffBag Gắn các phần tử vào cuối túi.
Chúng tôi cũng có một BagLength. Hữu ích cho việc lặp qua một túi.
Các chức năng này cực kỳ hữu ích vì hai lý do.
Đầu tiên, đây là cách tốt để tạo bảng mở rộng trong Mathematica.
Thứ hai, nội dung của các túi được đánh giá nhưng sau đó được đặt trong một expr thô, do đó được che chắn. Do đó người ta có thể sử dụng như là "con trỏ" (theo nghĩa C) chứ không phải là các đối tượng, và này không đòi hỏi Giữ vv Đây là một số ví dụ:
a = {1,2,a} (* gives infinite recursion *)
Nếu chúng ta thay vì sử dụng túi chúng ta có được một sự tự cấu trúc -referential.
In[1]:= AppendTo[$ContextPath, "Internal`"];
In[2]:= a = Bag[{1,2,a}]
Out[2]= Bag[<3>]
In[3]:= expr1 = BagPart[a, All]
Out[3]= {1, 2, Bag[<3>]}
In[4]:= expr2 = BagPart[BagPart[a, 3], All]
Out[4]= {1, 2, Bag[<3>]}
In[5]:= expr1 === expr2
Out[5]= True
Điều này rất khó để mô phỏng theo bất kỳ cách nào khác trong Mathematica. Một người sẽ cần sử dụng các bảng thưa thớt (băm) ở một số cách không minh bạch.
Đây là ví dụ liên quan, không được gỡ rối hoàn toàn. Chúng tôi về cơ bản thực hiện một danh sách liên kết theo đó một triệt tiêu có thể sửa đổi đuôi, thay thế các danh sách con vv
tail[ll_] := BagPart[ll,2]
settail[ll_, ll2_] := BagPart[ll,2] = ll2
contents[ll_] := BagPart[ll,1]
setcontents[ll_, elem_] := BagPart[ll,1] = elem
createlinkedlist[elems__] := Module[
{result, elist={elems}, prev, el},
result = Bag[{elist[[1]],Bag[]}];
prev = result;
Do [el = Bag[{elist[[j]],Bag[]}];
settail[prev, el];
prev = el,
{j,2,Length[elist]}];
result
]
In[18]:= tt = createlinkedlist[vv,ww,xx]
Out[18]= Bag[<2>]
In[20]:= BagPart[tt,All]
Out[20]= {vv, Bag[<2>]}
Vì vậy, tt là một danh sách liên kết, yếu tố đầu tiên là câu, tiếp theo là bản thân một danh sách liên kết, vv Tôi đã hạn chế sử dụng thuật ngữ Lisp (xe hơi/cdr và các loại tương tự) vì tôi không thể gọi lại các hoạt động danh sách của Lisp có phá hoại hay không. Nhưng bạn sẽ có được ý tưởng chung.
Cùng các dòng tương tự, tôi đã sử dụng túi expr để triển khai nhị phân cây. Điều này rất hữu ích vì chúng ta có thể thực hiện các thay đổi phá hoại trong thời gian không đổi (giả sử chúng ta đã có một "xử lý" trên điểm chèn/xóa), và hơn nữa bản chất "thô" của expr có nghĩa là chúng ta hoàn toàn tránh được đánh giá vô hạn của Mathematica ngữ nghĩa.
Một ứng dụng khác, có thể.
Pointer = Internal`Bag
Contents[aa_Pointer, j_Integer] /;0<j<=Internal`BagLength[aa] :=
Internal`BagPart[aa,j]
SetContents[aa_Pointer, j_Integer, e_] /; 0<j<=Internal`BagLength[aa] :=
Internal`BagPart[aa,j] = e
SetContents[aa_Pointer, j_Integer, e_] /; j>BagLength[aa] :=
(Do[Internal`StuffBag[aa,Null], {k,Internal`BagLength[aa]+1,j-1}];
Internal`StuffBag[aa,e])
Hãy thử với
a = Bag[{1,2,a,6,t,y,99,Bag[{a,q,3,r,a,5,t}]}]
expr1 = BagPart[a, All]
expr2 = BagPart[BagPart[a, 3], All]
Contents[a, 4]
SetContents[a, 7, Contents[a,7]+5]
SetContents[a,11,33]
Daniel Lichtblau Wolfram Research
Tôi không có thời gian để chơi với mã của bạn, nhưng để đáp lại,' ... Tôi vẫn không thoải mái với ý tưởng sao chép toàn bộ cây/biểu thức mỗi khi một điểm mới được thêm vào ...'--- bạn đang tìm cách thêm bộ nhớ vào (các) chức năng của bạn? Nếu có, hãy tìm kiếm 'các hàm nhớ giá trị của chúng'. Nếu không phải những gì bạn đang tìm kiếm, bỏ qua và tôi sẽ chơi với nó sau ngày hôm nay. Trông mát mẻ. :) – telefunkenvf14
Không, ý tôi là, khi tôi thêm một điểm, thay vì các nút được chèn vào một cây thoát, có hiệu lực, chúng tôi đang tạo ra một cây hoàn toàn mới, loại bỏ cái cây cũ. Tôi chỉ tự hỏi về những tác động quản lý bộ nhớ của điều này, khi những biểu hiện đó thực sự rất lớn. Khó có thể thoát khỏi tư duy C++! ;-) Cảm ơn. –
Nếu tôi hiểu bạn một cách chính xác, bạn muốn chuyển qua tham chiếu vì bạn không thích dòng 'Return' trong' qtInsert' để tạo một danh sách lồng nhau mới trong cây có thể lớn và một vài nút mới .Có một cách trong Mathematica để làm một cái gì đó như thế này với 'Attributes [qtInsert] = HoldAll;' với shortcoming, rằng tất cả các đối số của 'qtInsert' sau đó phải là biến, không phải là giá trị theo nghĩa đen. – bbtrb