On Wed, Nov 20, 2013 at 8:38 PM, Geoffrey Irving <irv...@naml.us> wrote:
> On Wed, Nov 20, 2013 at 6:30 PM, Matthew Knepley <knep...@gmail.com> > wrote: > > On Wed, Nov 20, 2013 at 7:22 PM, Geoffrey Irving <irv...@naml.us> wrote: > >> > >> Was there any particular reason for making DMPlexMarkBoundaryFaces a > >> quadratic time algorithm? I realize it's hard to write a subquadratic > >> time algorithm on top of DMLabelSetValue; maybe PETSc needs some basic > >> integer hash tables? > > > > Why is it quadratic time? I just looked again, and it seems to be linear > > time to me. > > It calls DMLabelSetValue for each boundary face. Each call to > DMLabelSetValue seems to be O(log n) if the value is already set > (binary search) and O(n/2) if the value is missing, since it does a > PetscMemmove to shift roughly half the existing values over by one in > order to insert the new entry in the middle of a sorted list. Yes that is correct. This is fixed in knepley/fix-hash-scaling which is merged to next. Thanks, Matt > > Geoffrey > -- What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead. -- Norbert Wiener