Búsqueda binaria para identificar nombres de usuarios duplicados -- python campo con reinventing-the-wheel campo con search campo con binary-search camp codereview Relacionados El problema

Binary search to identify duplicate user names


2
vote

problema

Español

Estoy tratando de implementar el código descrito esta publicación sobre cómo reddit identifica los nombres de usuario duplicados (creo que se llama búsqueda binaria). Solo para aclarar, esto es principalmente para mí averiguar cómo funcionan estas cosas; gracias @graipher para señalar bisect ). La forma en que lo entiendo, los pasos son:

  1. Tiene un nuevo nombre de usuario que está comparando con una lista ordenada alfabéticamente de los nombres existentes

  2. Compare ese nuevo nombre al el elemento medio en la lista.

  3. Si no hay ninguna coincidencia, verifique si el nuevo nombre es más alto o más bajo en el alfabeto que el elemento central, y concéntrese en este lado de la lista, de nuevo, comprobar el medio Articulo.

  4. usted repita hasta que haya un nombre de usuario "" tomado ") o ninguno (" Nombre de usuario disponible ") .

a continuación es lo que tengo. Parece que funciona cuando lo pruebo en los nombres en la lista y otros nombres aleatorios. Se enfrió si alguien tuviera algún comentario re:

  • ¿Esto funcionará correctamente o hay algún tipo de error?

  • es el while bucle de la manera correcta de ir? ¿Hay mejores opciones? Especialmente no me gusta el bucle separado para una lista de longitud 1.

  • de rendimiento, ¿hay algún hipo real aquí?

  • ¡Cualquier otro comentario es muy apreciado!

-

  def checker(new_name, old_names):     """     The checker takes a string new_name and checks if it is contained in the list old_names.     It prints out the results.     """      print "***  initializing the checker"     print "searching for ", new_name     print "old names", old_names     old_names= sorted(old_names)     #set the match variable to false     namematch= False     #iterate over list while new_name does not match     while not namematch and len(old_names) > 1:         middle= len(old_names)/2         print "middle item is", old_names[middle], "middle index is", middle         #match         if old_names[middle] == new_name:             namematch= True         #no match         else:             if sorted(list((new_name, old_names[middle])))[0] != new_name:                 print "word is to the right"                 old_names = old_names[middle:]             else:                 print "word is to the left"                 old_names = old_names[:middle]     #check for list of length 1: is it new_name     if (len(old_names)) == 1 and (old_names[0] == new_name):         namematch = True     if not namematch:          print "this name is not taken", new_name     else:         print "this name is taken:", new_name   

Aquí están mis datos de prueba:

-

  names_list= [u'annie', u'max', u'chris', u'11alpha', u'zotti', u'zatti', u'zutti', u'?andy', u'getrxfc', u'zilly']  checker('max', names_list)  # True checker('fail', names_list)  # False   
Original en ingles

I am trying to implement the code described this post about how Reddit identifies duplicate user names (I do believe it is called binary search). Just to clarify, this is mainly for me figuring out how these things work; thanks @Graipher for pointing to bisect). The way I understand it, the steps are:

  1. You have a new user name you are comparing to an alphabetically sorted list of existing names

  2. You compare that new name to the middle item in the list.

  3. If there is no match, you check if the new name is higher or lower in the alphabet than the middle item, and focus on this side of the list, again checking the middle item.

  4. You repeat until there is a match ("User name taken") or none ("User name available").

Below is what I have. It seems to work when I test it on the names in the list and random other names. It'd cool if someone had some feedback re:

  • Will this work correctly or is there some kind of bug?

  • Is the while loop the right way to go? Are there better options? I especially don't like the separate loop for a list of length 1.

  • Performance-wise, are there any real hiccups in here?

  • Any other comments are much appreciated!

-

def checker(new_name, old_names):     """     The checker takes a string new_name and checks if it is contained in the list old_names.     It prints out the results.     """      print "***\n\ninitializing the checker"     print "searching for ", new_name     print "old names", old_names     old_names= sorted(old_names)     #set the match variable to false     namematch= False     #iterate over list while new_name does not match     while not namematch and len(old_names) > 1:         middle= len(old_names)/2         print "middle item is", old_names[middle], "middle index is", middle         #match         if old_names[middle] == new_name:             namematch= True         #no match         else:             if sorted(list((new_name, old_names[middle])))[0] != new_name:                 print "word is to the right"                 old_names = old_names[middle:]             else:                 print "word is to the left"                 old_names = old_names[:middle]     #check for list of length 1: is it new_name     if (len(old_names)) == 1 and (old_names[0] == new_name):         namematch = True     if not namematch:          print "this name is not taken", new_name     else:         print "this name is taken:", new_name 

Here is my test data:

-

names_list= [u'annie', u'max', u'chris', u'11alpha', u'zotti', u'zatti', u'zutti', u'?andy', u'getr\xfc', u'zilly']  checker('max', names_list)  # True checker('fail', names_list)  # False 
           

Lista de respuestas

2
 
vote
vote
La mejor respuesta
 

La descripción que está proporcionando y su implementación corresponde a una búsqueda binaria de hecho. Como tal, probablemente tenga sentido realizar algunos cambios cosméticos en su función para que este limpiador sea más fácil de usar:

  • Llámelo binary_search (o algo así)
  • hace que la firma (nombres de parámetros y documentación) sea más genérica y no se basa en el concepto de nombre. Los parámetros podrían llamarse item / element / 99887776655443333 / 9988777655544334 > 9988776655544335 / sorted_array .
  • Haz que el valor de retorno sea más claro, por ejemplo, un valor booleano que dice si se encontró el valor o no (o tal vez un índice que le da la posición)
  • Mueva toda la lógica de entrada / salida (excepto quizás para las declaraciones de depuración) fuera de la función.

En cuanto a las actuaciones, estoy un poco preocupado por el hecho de que realmente está realizando copias utilizando el 9988777665544337 Notación de sublist. Por lo tanto, cada paso del algoritmo, en lugar de operar en tiempos constantes, será más grande si el sublista que está copiando se vuelve más grande. Además, está re-ordenando la matriz completa cada vez que se llama la función (e incluso más que esto aparentemente). El punto de uso de la búsqueda binaria es que usted paga el costo de la clasificación ( 9988776655544338 ) Por adelantado Asumirá que lo amortizará realizando muchas búsquedas en O(log(n)) Times. Si tiene que volver a ordenar cada vez, es posible que también pueda usar una búsqueda lineal que iba a través de la matriz y deteniéndose cuando se encuentra el elemento.

 

The description you are providing and your implementation do correspond to binary search indeed. As such, it would probably make sense to perform a few cosmetic changes to your function to make this cleaner and easier to (re)use:

  • call it binary_search (or something like that)
  • makes the signature (parameter names and documentation) more generic and not based on the concept of name. The parameters could be called item/element/x/needle and sorted_list/sorted_array.
  • make the return value clearer, for instance a boolean value telling whether the value was found or not (or maybe an index giving the position)
  • move all the input/output logic (except maybe for the debug statements) out of the function.

As for the performances, I am a bit concerned by the fact that you are actually performing copies by using the [:] sublist notation. Thus, each step of the algorithm, instead of operating in constant times will be bigger if the sublist you are copying gets bigger. Also, you are re-sorting the whole array everytime the function is called (and even more that this apparently). The point of using binary search is that you pay the cost of sorting (O(n*log(n))) upfront assuming you'll amortize it by performing many searches in O(log(n)) times. If you have to re-sort everytime, you might as well use a linear search iterating through the array and stopping when the element is found.

 
 
     
     
2
 
vote

En general, no tiene sentido rodar su propio, si ya hay una solución incorporada. En este caso, existe la 99887766555443310 módulo, que tiene un método item1 que devuelve el índice donde tendría que insertar un elemento para mantener el orden ordenado.

Todo lo que tiene que hacer es verificar si en esa posición ya está el nombre de usuario que está comprobando:

  item2  

Tenga en cuenta que esto supone que su lista de nombres ya está ordenada y que obtiene la lista de usuarios antiguos a través de alguna función item3 .

Alternativamente, puede usar un 99887766655443314 . item5 es $ Mathcal {O} (1) $ y usa Binary Búsqueda en el fondo para ver si el hash ya está en el conjunto (gracias a @ kyrill para sugerir conjuntos en los comentarios):

  item6  
 

In general it does not make sense to roll your own, if there already is a built-in solution. In this case there is the bisect module, which has a method bisect.bisect_left which returns the index where you would have to insert an item to maintain the sorted order.

All you have to do is check if in that position there is already the user name you are checking:

from bisect import bisect_left  old_names = sorted(db_query(...))  def user_name_exists(new_name, old_names):     return old_names[bisect_left(old_names, new_name)] == new_name 

Note that this assumes that your names list is already sorted and that you get the list of old users via some function db_query.

Alternatively, you could use a set. x in set is \$mathcal{O}(1)\$ and uses binary search in the background to see if the hash is already in the set (thanks to @kyrill for suggesting sets in the comments):

old_names = set(db_query(...))  def user_name_exists(new_name, old_names):     return new_name in old_names 
 
 
       
       

Relacionados problema

5  Búsqueda binaria eficiente  ( Efficient binary search ) 
Mi implementación: 157 Implementación normal: 158 La diferencia de ser mi implementación hace una conjetura en el índice del valor en función de l...

2  Búsqueda binaria, usando  ( Binary search using remove ) 
Soy consciente de que existe una función en la biblioteca estándar. Por favor, dame comentarios sobre buenos convenciones y estándares de codificación. fun...

5  BinarySearch Kata en Ruby  ( Binarysearch kata in ruby ) 
Acabo de completar esta búsqueda binaria Kata, que tiene algunos requisitos extraños, y pasé un poco "limpiando" mi código y haciéndolo más compacto. Agradece...

2  Eliminación de un nodo en un árbol de búsqueda binario  ( Deletion of a node in a binary search tree ) 
Estoy buscando ver si mi implementación del método de eliminación / eliminación en un árbol de búsqueda binario es suficiente, legible y se ejecuta en un tiem...

10  Encuentre el duplicado en una matriz ordenada en menos de O (n)  ( Find the duplicate in a sorted array in less than on ) 
suposiciones: La matriz está ordenada. solo hay un duplicado. La matriz solo se rellena con números [0, N], donde n es la longitud de la matriz. Eje...

1  Retroalimentación de búsqueda binaria  ( Binary search feedback ) 
He escrito un algoritmo de búsqueda binario, pero parece ser un poco diferente a otras personas que he visto. Esperaba que la comunidad pudiera darme algunos ...

5  Búsqueda binaria: primera / última / ocurrencia aleatoria  ( Binary search first last random occurrence ) 
He escrito un código para "búsqueda binaria" una lista, y devolver el primera ocurrencia del objetivo: def bsearch(a, left, right, target, first_or_last ...

3  ¿Es esta búsqueda binaria cerca de Idiomatic OCAML?  ( Is this binary search close to idiomatic ocaml ) 
let binsearch ~arr ~cmp x = ( let cmpx = cmp x in (* Assuming arr is ordered according to cmp, then (bs min max) is an *) (* index of a value v...

7  Búsqueda binaria de Java (y obtenga índice si no está allí) Revisión  ( Java binary search and get index if not there review ) 
Quiero hacer una búsqueda binaria y si el objetivo no está allí, obtenga el índice de donde debería haber sido. Este es el código en el que se me ocurrió. P...

2  Encontrar el subconjunto máximo de intervalos no superpuestos  ( Finding the max subset of non overlapping intervals ) 
¿Cómo podría este código ser más limpio? Creo que la forma en que manejo las interfaces y la búsqueda binaria podría mejorarse. Estoy tratando de entender cóm...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos