Hi, Leo Prikler <leo.prik...@student.tugraz.at> skribis:
> Am Mittwoch, den 06.01.2021, 14:32 +0100 schrieb Ludovic Courtès: >> Hi, >> >> Leo Prikler <leo.prik...@student.tugraz.at> skribis: >> >> > > > + ((first . rest) >> > > > + (if (member first rest =) ; (srfi srfi-1) member >> > > > + (cons first (find-duplicates rest =)) >> > > > + (find-duplicates rest =))))) >> > > >> > > Note that this is quadratic; it’s fine as long as we don’t have >> > > “too >> > > many” users, which may be the case in general. >> > It is indeed quadratic, but would there even be an n log n >> > solution? >> > I've once done an n log n sort+delete-duplicates!, perhaps that'd >> > be a >> > nicer solution here? >> >> You could first build a hash table or vhash or set with all the >> names, >> then traverse again the list of names and check whether they’re in >> that >> table. That’d be linear (assuming the table is well balanced), but >> the >> constant factor would be higher. > Yeah, I think the hash table solution would make the most sense here. > Since VHashes are based on VLists, they're not actually purely > functional, are they? Their implementation is not “purely functional” but it’s inconsequential; it’s a persistent data structure, and that’s what matters (info "(guile) VLists"). >> > > (define (assert-unique-account-names users) >> > > (match (find-duplicates things …) >> > > (() #t) >> > > (lst >> > > (raise (formatted-message (G_ "the following accounts >> > > appear >> > > more than once:~{ ~a~}~%" >> > > lst)))))) >> > > >> > > ? >> > That'd be weird for duplicate duplicates, hence just reporting the >> > first. >> >> You could do (delete-duplicates lst) in the message above? > Sure, but that'd be O(n^2) on top of O(n^2), which is less than ideal. Yes, but it’s a small ‘n’, typically one or two. Ludo’.