[Freeciv-Dev] Re: (PR#9995) RfP: is_sane_name and user names

["Marko Lindqvist" <marko.lindqvist@xxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=9995 >

Jason Short wrote:
> However also note that under the check_names patch, search_for_city_name 
> has become pretty slow.  O(n^2) at best.  Having it search through for 
> the current nation list and allow any nations for that would make it 
> much slower.
> 
> I think all of this is fixable, but it means changing the data 
> structures to allow a more efficient search.

  It seems to me that there is space for some easy optimizations even 
with current data structures, for instance by avoiding unnecessary 
iterations in common 'special' cases. But if you are going to make real 
structural changes in short/mid-term anyway, I won't bother improving 
current algorithms. O(n^2) is slow even in its fastest.


  - Caz