[yt-svn] commit/yt: ngoldbaum: Merged in MatthewTurk/yt (pull request #2411)
commits-noreply at bitbucket.org
commits-noreply at bitbucket.org
Mon Oct 17 14:19:43 PDT 2016
1 new commit in yt:
https://bitbucket.org/yt_analysis/yt/commits/f1929d10804e/
Changeset: f1929d10804e
Branch: yt
User: ngoldbaum
Date: 2016-10-17 21:19:17+00:00
Summary: Merged in MatthewTurk/yt (pull request #2411)
Extract priority queue superclass from distance queue.
Affected #: 2 files
diff -r db097c2981cda61b07abbb087125bb03ea1006a4 -r f1929d10804e6b316a34b74293ca3c7bdebc26b4 yt/utilities/lib/distance_queue.pxd
--- a/yt/utilities/lib/distance_queue.pxd
+++ b/yt/utilities/lib/distance_queue.pxd
@@ -20,6 +20,12 @@
from libc.stdlib cimport malloc, free
from libc.string cimport memmove
+# THESE TWO STRUCTS MUST BE EQUIVALENT
+
+cdef struct ItemList:
+ np.int64_t ind
+ np.float64_t value
+
cdef struct NeighborList:
np.int64_t pn # Particle number
np.float64_t r2 # radius**2
@@ -31,9 +37,14 @@
bint periodicity[3],
np.float64_t max_dist2)
-cdef class DistanceQueue:
+cdef class PriorityQueue:
cdef int maxn
cdef int curn
+ cdef ItemList* items
+ cdef void item_reset(self)
+ cdef int item_insert(self, np.int64_t i, np.float64_t value)
+
+cdef class DistanceQueue(PriorityQueue):
cdef np.float64_t DW[3]
cdef bint periodicity[3]
cdef NeighborList* neighbors # flat array
diff -r db097c2981cda61b07abbb087125bb03ea1006a4 -r f1929d10804e6b316a34b74293ca3c7bdebc26b4 yt/utilities/lib/distance_queue.pyx
--- a/yt/utilities/lib/distance_queue.pyx
+++ b/yt/utilities/lib/distance_queue.pyx
@@ -56,16 +56,68 @@
return -1.0
return r2
+cdef class PriorityQueue:
+ """This class acts as a "priority-queue." It was extracted from the
+ DistanceQueue object so that it could serve as a general-purpose method for
+ storing the N-most "valuable" objects. It's relatively simple, in that it
+ provides storage for a single int64 (which is usually an 'index' into an
+ external array or list) and a single float64 "value" associated with them.
+ You can insert new objects, and then if it's already at maxn objects in it,
+ it'll bump the least valuable one off the end. Of particular note is that
+ *lower* values are considered to be *more valuable* than higher ones; this
+ is because our typical use case is to store radii.
+ """
+ def __cinit__(self, int maxn):
+ cdef int i
+ self.maxn = maxn
+ self.curn = 0
+ self.items = <ItemList *> malloc(
+ sizeof(ItemList) * self.maxn)
+
+ cdef void item_reset(self):
+ for i in range(self.maxn):
+ self.items[i].value = 1e300
+ self.items[i].ind = -1
+ self.curn = 0
+
+ cdef int item_insert(self, np.int64_t ind, np.float64_t value):
+ cdef int i, di
+ if self.curn == 0:
+ self.items[0].value = value
+ self.items[0].ind = ind
+ self.curn += 1
+ return 0
+ # Now insert in a sorted way
+ di = -1
+ for i in range(self.curn - 1, -1, -1):
+ # We are checking if i is less than us, to see if we should insert
+ # to the right (i.e., i+1).
+ if self.items[i].value < value:
+ di = i
+ break
+ # The outermost one is already too small.
+ if di == self.maxn - 1:
+ return -1
+ if (self.maxn - (di + 2)) > 0:
+ memmove(<void *> (self.items + di + 2),
+ <void *> (self.items + di + 1),
+ sizeof(ItemList) * (self.maxn - (di + 2)))
+ self.items[di + 1].value = value
+ self.items[di + 1].ind = ind
+ if self.curn < self.maxn:
+ self.curn += 1
+ return di + 1
+
cdef class DistanceQueue:
"""This is a distance queue object, designed to incrementally evaluate N
positions against a reference point. It is initialized with the maximum
number that are to be retained (i.e., maxn-nearest neighbors)."""
def __cinit__(self, int maxn):
- cdef int i
- self.maxn = maxn
- self.curn = 0
- self.neighbors = <NeighborList *> malloc(
- sizeof(NeighborList) * self.maxn)
+ if sizeof(ItemList) != sizeof(NeighborList):
+ # This should almost never, ever happen unless we do something very
+ # wrong, and must be broken at compile time.
+ raise RuntimeError
+ self.neighbors = <NeighborList *> self.items
self.neighbor_reset()
for i in range(3):
self.DW[i] = 0
@@ -88,7 +140,6 @@
np.float64_t cpos[3]):
# Here's a python+numpy simulator of this:
# http://paste.yt-project.org/show/5445/
- cdef int i, di
cdef np.float64_t r2, r2_trunc
if self.curn == self.maxn:
# Truncate calculation if it's bigger than this in any dimension
@@ -99,36 +150,10 @@
r2 = r2dist(ppos, cpos, self.DW, self.periodicity, r2_trunc)
if r2 == -1:
return
- if self.curn == 0:
- self.neighbors[0].r2 = r2
- self.neighbors[0].pn = pn
- self.curn += 1
- return
- # Now insert in a sorted way
- di = -1
- for i in range(self.curn - 1, -1, -1):
- # We are checking if i is less than us, to see if we should insert
- # to the right (i.e., i+1).
- if self.neighbors[i].r2 < r2:
- di = i
- break
- # The outermost one is already too small.
- if di == self.maxn - 1:
- return
- if (self.maxn - (di + 2)) > 0:
- memmove(<void *> (self.neighbors + di + 2),
- <void *> (self.neighbors + di + 1),
- sizeof(NeighborList) * (self.maxn - (di + 2)))
- self.neighbors[di + 1].r2 = r2
- self.neighbors[di + 1].pn = pn
- if self.curn < self.maxn:
- self.curn += 1
+ self.item_insert(pn, r2)
cdef void neighbor_reset(self):
- for i in range(self.maxn):
- self.neighbors[i].r2 = 1e300
- self.neighbors[i].pn = -1
- self.curn = 0
+ self.item_reset()
def find_nearest(self, np.float64_t[:] center, np.float64_t[:,:] points):
"""This function accepts a center and a set of [N,3] points, and it
Repository URL: https://bitbucket.org/yt_analysis/yt/
--
This is a commit notification from bitbucket.org. You are receiving
this because you have the service enabled, addressing the recipient of
this email.
More information about the yt-svn
mailing list