StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I agree with mgilson's analysis. <code>list</code> is a mutable type and <code>list.append</code> is in-place. Here's what that means:</p> <p>There are two types: mutable and immutable. </p> <p>A mutable type lives in the same location on memory, even when you change it. <code>list</code>s and <code>dict</code>s, for example, are mutable types. This means that if you create a <code>list</code> and change it in certain ways, it will still live in the same location in memory. So suppose you create a <code>list</code> called "myList". Let's say this list in memory location 0x9000. Then, doing <code>myList.append(0)</code> will not change the location of the <code>myList</code> in memory. Even if you did <code>myList[0] = 'a'</code>, the location will not change - it will still live at 0x9000.</p> <p>An immutable type will "move" to a different memory location when you attempt to change it in any way. <code>str</code>s and <code>tuple</code>s are immutable. This is why you get the following error:</p> <pre><code>>>> s = 'as' >>> s[0] = 'b' Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: 'str' object does not support item assignment </code></pre> <p>This means that even if you define <code>s = 'as'</code> (and let's say <code>s</code> now lives at memory address 0x5000), and redefine it as <code>s = 'af'</code>, the location of <code>s</code> in memory changes.</p> <p>Now, when you reassign a mutable type, it's location in memory changes. For example,</p> <blockquote> <blockquote> <blockquote> <p>L = [1,2,3] # say memory location 0x4000 L = [5,6,7] # memory location not 0x4000 anymore</p> </blockquote> </blockquote> </blockquote> <p>This is where the property of <code>list.append</code> being "in-place" comes into play. "<code>list.append</code> is in-place" means that the new element is added to the list without creating a new list. This is why <code>list.append</code> has no return value, as demonstrated below:</p> <pre><code>>>> L = [1,2,3] >>> ret = L.append(4) >>> print L [1, 2, 3, 4] >>> print ret None </code></pre> <p>However, if you wanted to create a new list, you can do that as follows:</p> <pre><code>>>> L = [1,2,3] >>> ret = L + [4] >>> print L [1, 2, 3] >>> print ret [1, 2, 3, 4] </code></pre> <p>So what is happening in your case is that in both recursive calls (left and right), <code>point</code> is appended to the list in each recursive call. This is why you get duplicate values.</p> <p>You could circumvent this by doing what mgilson suggests, or if you are a lisp fan (this is a very good lisp question), then you could use the <code>[1,2,3] + [4]</code> principle and do this (untested, but should work):</p> <pre><code>def within_radius(self, point, radius, result=[]): """ Find all items in the tree within radius of point """ d = self.discriminator temp = [] if in_circle(point, radius, self.data): temp = [self.data] # Check whether any of the points in the subtrees could be # within the circle if point[d] - radius < self.data[d] and self.l_child: temp += self.l_child.within_radius(point, radius, result) if point[d] + radius > self.data[d] and self.r_child: temp += self.r_child.within_radius(point, radius, result) return result+temp </code></pre> <p>Hope this helps</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload