2008-11-03 16 views
18

Estoy tratando de averiguar si hay una forma razonablemente eficiente de realizar una búsqueda en un diccionario (o un hash, o un mapa, o cualquiera que sea su idioma favorito) donde las teclas son expresiones regulares y las cadenas se buscan contra el conjunto de claves. Por ejemplo (en la sintaxis de Python):Búsqueda de hash/diccionario/mapa con expresiones regulares

>>> regex_dict = { re.compile(r'foo.') : 12, re.compile(r'^FileN.*$') : 35 } 
>>> regex_dict['food'] 
12 
>>> regex_dict['foot in my mouth'] 
12 
>>> regex_dict['FileNotFoundException: file.x does not exist'] 
35 

(Obviamente el ejemplo anterior no funcionará como está escrito en Python, pero ese es el tipo de cosas que me gustaría ser capaz de hacer.)

Puedo pensar en una forma ingenua de implementar esto, en la que iterar sobre todas las claves del diccionario e intentar hacer coincidir la cadena pasada en contra de ellas, pero luego pierdo el tiempo de búsqueda O (1) de un mapa hash y en cambio, tiene O (n), donde n es el número de teclas en mi diccionario. Esto es potencialmente un gran problema, ya que espero que este diccionario crezca mucho, y tendré que buscarlo una y otra vez (en realidad tendré que repetirlo sobre cada línea que leo en un archivo de texto, y los archivos pueden tener cientos de megabytes de tamaño).

¿Hay alguna manera de lograr esto, sin recurrir a la eficiencia O (n)?

Alternativamente, si conoce una forma de realizar este tipo de búsqueda en una base de datos, sería fantástico también.

(cualquier lenguaje de programación está muy bien - Estoy usando Python, pero estoy más interesado en las estructuras de datos y algoritmos aquí.)

Alguien señaló que más de una coincidencia es posible, y eso es absolutamente correcto. Idealmente en esta situación me gustaría devolver una lista o tupla que contenga todas las coincidencias. Me conformaría con el primer partido, sin embargo.

No puedo ver que O (1) sea posible en ese escenario; Me conformaría con algo menos que O (n), sin embargo. Además, la estructura de datos subyacente podría ser cualquier cosa, pero el comportamiento básico que me gustaría es el que he escrito anteriormente: buscar una cadena y devolver los valores que coinciden con las claves de expresión regulares.

+1

Supongo, pero creo que esto es imposible porque hay un número infinito de expresiones regulares que coinciden con su clave, y un número infinito de teclas que coinciden con su expresión regular. –

+0

"esto es imposible porque hay un número infinito de expresiones regulares que coinciden con su clave" - ​​no es adivinar. Esa es una consecuencia de la definición de una expresión regular. –

+0

@jeff ¿Tiene una implementación de ejemplo para la solución aceptada? Será útil, ¡Gracias! – 18bytes

Respuesta

4

Lo que quieres hacer es muy similar a lo que es compatible con xrdb. Sin embargo, solo respaldan una noción bastante mínima de globbing.

Internamente puede implementar una familia de idiomas regulares más grande que la suya almacenando sus expresiones regulares como un carácter trie.

  • caracteres individuales se convierten en nodos trie.
  • . Se convierten en inserciones comodín que cubren todos los elementos secundarios del nodo trie actual.
  • * vuelven enlaces en el trie al nodo al inicio del elemento anterior.
  • Los rangos [a-z] insertan los mismos nodos hijos subsiguientes repetidamente debajo de cada uno de los caracteres del rango. Con cuidado, aunque las inserciones/actualizaciones pueden ser algo costosas, la búsqueda puede ser lineal en el tamaño de la cadena. Con algunas cosas de marcador de posición, los casos comunes de explosión combinatoria pueden mantenerse bajo control.
  • (foo) | (bar) se convierten en nodos múltiples inserciones

Esto no maneja expresiones regulares que se producen en puntos arbitrarios en la cadena, pero que pueden ser modelados envolviendo su expresión regular con * en cada lado. .

Perl tiene un par de módulos similares a Text :: Trie en los que puedes buscar ideas. (Diablos, creo que incluso escribí uno de ellos cuando)

+0

cualquier implementación disponible? – bill

+0

@bill también hay algunos en blogs [mi pregunta sobre la Revisión de Código] (http://codereview.stackexchange.com/questions/24602/readability-and-performance-of-my-trie-implementation). También puede ver [con qué terminé] (https://bitbucket.org/codesparkle/pytrocities/src/27ecee946356a351730889483930d6351a0ddf3a/trie.py?at=default); es solo una Trie básica, pero podría ayudarte a ponerte en marcha. – Adam

0

La suposición fundamental es defectuosa, creo. no puede asignar hashes a expresiones regulares.

+0

Puedes, al menos en Python. Sin embargo, no es muy útil (al menos para mí), ya que solo coincidirán con el mismo objeto regex. – Jeff

4

Esto no es posible con una tabla hash normal en ningún idioma. Deberá iterar a través de todo el conjunto de claves, intentar hacer coincidir la clave con su expresión regular o utilizar una estructura de datos diferente.

Debe elegir una estructura de datos que sea adecuada para el problema que está tratando de resolver. Si tiene que coincidir con cualquier expresión regular arbitraria, no sé de una buena solución. Si la clase de expresiones regulares que utilizará es más restrictiva, es posible que pueda usar una estructura de datos como trie o suffix tree.

0

No creo que sea teóricamente posible. ¿Qué sucede si alguien pasa una cadena que coincide con más de 1 expresión regular?

Por ejemplo, ¿qué pasaría si alguien lo hizo:

>>> regex_dict['FileNfoo'] 

¿Cómo puede algo así, posiblemente, ser O (1)?

2

¿Qué pasa si usted tiene un diccionario como

regex_dict = { re.compile("foo.*"): 5, re.compile("f.*"): 6 } 

En este caso regex_dict["food"] podría volver legítimamente 5 o 6.

Incluso haciendo caso omiso de ese problema, probablemente no hay manera de hacer esto de manera eficiente con el módulo regex En cambio, lo que necesitarías es un gráfico interno dirigido o una estructura de árbol.

4

En el caso general, lo que necesita es un generador lexer. Toma un montón de expresiones regulares y las compila en un reconocedor. "lex" funcionará si está utilizando C. Nunca he usado un generador de lexer en Python, pero parece que hay algunos para elegir. Google muestra PLY, PyGgy y PyLexer.

Si todas las expresiones regulares se parecen entre sí de alguna manera, entonces es posible que pueda tomar algunos accesos directos. Necesitaríamos saber más sobre el problema final que está tratando de resolver para encontrar cualquier sugerencia. ¿Puedes compartir algunas expresiones regulares de muestra y algunos datos de muestra?

Además, ¿con cuántas expresiones regulares está tratando aquí? ¿Estás seguro de que el enfoque ingenuo no funcionará en? Como Rob Pike once said, "Los algoritmos de fantasía son lentos cuando n es pequeño, y n suele ser pequeño". A menos que tengas miles de expresiones regulares y miles de cosas para hacer coincidir con ellas, y esta es una aplicación interactiva en la que un usuario te está esperando, es mejor que lo hagas de la manera más fácil y repitiendo las expresiones regulares.

+0

Anticipamos tener miles de expresiones regulares pronto. En todos los casos, tenemos que hacer coincidir esas expresiones regulares repetidamente, generalmente miles de veces por operación del usuario. Puede estar bien ir con la solución ingenua y luego reescribir el algoritmo cuando el rendimiento se degrada, ya que no es necesario que se ejecute de forma interactiva. – Jeff

1

Como han señalado otros encuestados, no es posible hacer esto con una tabla hash en tiempo constante.

Una aproximación que podría ayudar es usar una técnica llamada "n-grams". Crea un índice invertido de trozos de n caracteres de una palabra a la palabra completa. Cuando se le presente un patrón, divídalo en trozos de n caracteres y use el índice para calcular una lista de palabras coincidentes.

Incluso si no puede aceptar una aproximación, en la mayoría de los casos esto proporcionaría un mecanismo de filtrado preciso para que no tenga que aplicar la expresión regular a cada tecla.

0

puede ser posible obtener el compilador de expresiones regulares para hacer la mayor parte del trabajo para usted mediante la concatenación de las expresiones de búsqueda en una gran expresión regular, separados por "|". Un compilador de expresiones regulares inteligente podría buscar aspectos comunes en las alternativas en ese caso, y diseñar una estrategia de búsqueda más eficiente que simplemente verificar cada una por turno. Pero no tengo idea si hay compiladores que harán eso.

0

Realmente depende de cómo se vean estas expresiones regulares. Si no tenemos un lote expresiones regulares que coincidan con casi cualquier cosa como '.*' o '\d+', y en su lugar tiene expresiones regulares que contiene su mayoría palabras y frases, o cualquier patrón de más de 4 caracteres (por ejemplo, '' a*b*c fijos en ^\d+a\*b\*c:\s+\w+), como en sus ejemplos. Puede hacer este truco común que se adapta bien a millones de expresiones regulares:

Genere un índice invertido para las expresiones regulares (rabin-karp-hash ('patrón fijo') -> lista de expresiones regulares que contienen 'patrón fijo'). Luego, en el tiempo de coincidencia, usando hash Rabin-Karp para calcular hashes deslizantes y buscar el índice invertido, avanzando un carácter a la vez.Ahora tiene O (1) búsqueda de no-coincidencias de índice invertido y un tiempo de O (k) razonable para las coincidencias, k es la longitud promedio de las listas de expresiones regulares en el índice invertido. k puede ser bastante pequeño (menos de 10) para muchas aplicaciones. La calidad (falso positivo significa mayor k, falso negativo significa falta de coincidencia) del índice invertido depende de qué tan bien el indexador entiende la sintaxis de la expresión regular. Si los regexes son generados por expertos humanos, también pueden proporcionar pistas sobre patrones fijos contenidos.

2

Hay un módulo Perl que hace exactamente esto Tie::Hash::Regex.

use Tie::Hash::Regex; 
my %h; 

tie %h, 'Tie::Hash::Regex'; 

$h{key} = 'value'; 
$h{key2} = 'another value'; 
$h{stuff} = 'something else'; 

print $h{key}; # prints 'value' 
print $h{2}; # prints 'another value' 
print $h{'^s'}; # prints 'something else' 

print tied(%h)->FETCH(k); # prints 'value' and 'another value' 

delete $h{k}; # deletes $h{key} and $h{key2}; 
+1

Sí, sé de este módulo, y el comportamiento descrito es exactamente lo que quiero, pero eché un vistazo al código fuente para esto y solo está iterando sobre las claves para cada búsqueda. Entonces, realmente es solo una solución O (n), aunque sea conveniente. – Jeff

1

Un caso especial de este problema surgió en los 70s lenguajes de IA orientados a bases de datos deductivas. Las claves en estas bases de datos podrían ser patrones con variables, como expresiones regulares sin * o | operadores. Tienden a usar extensiones de lujo de las estructuras para los índices. Ver krep * .lisp en Norvig's Paradigms of AI Programming para la idea general.

4

Esto es definitivamente posible, siempre y cuando uses expresiones regulares 'reales'. Una expresión regular de libro de texto es algo que puede ser reconocido por deterministic finite state machine, lo que significa principalmente que no puede tener referencias anteriores allí.

La lengua regular tiene la propiedad de que "la unión de dos idiomas regulares es regular", lo que significa que puede reconocer un número arbitrario de expresiones regulares a la vez con una máquina de estados única. La máquina de estados se ejecuta en O (1) tiempo con respecto al número de expresiones (se ejecuta en O (n) tiempo con respecto a la longitud de la cadena de entrada, pero las tablas hash también).

Una vez que la máquina de estados finaliza, sabrá qué expresiones coinciden, y desde allí es fácil buscar valores en O (1) tiempo.

+0

Recuerdo vagamente haber leído algo sobre esto en Higher Order Perl pero no puedo encontrar la ubicación en este momento. ¿Alguien más recuerda? –

1

Si tiene un conjunto pequeño de entradas posibles, puede almacenar en memoria caché las coincidencias tal como aparecen en un segundo diccionario y obtener O (1) para los valores en caché.

Si el conjunto de entradas posibles es demasiado grande para almacenar en caché pero no infinito, puede mantener las últimas N coincidencias en la memoria caché (busque en Google "LRU maps", menos recientemente utilizado).

Si no puede hacer esto, puede intentar reducir el número de expresiones regulares que tiene que probar marcando un prefijo o un poco.

1

Creé esta estructura de datos exacta para un proyecto una vez. Lo implementé ingenuamente, como sugirió. Hice dos optimizaciones inmensamente útiles, los cuales pueden o no ser factible para usted, dependiendo del tamaño de los datos:

  • Memoizing las búsquedas de hash
  • pre-siembra de la la tabla memoization (no estoy seguro de lo para llamar a esto ... ¿calentar el caché?)

Para evitar el problema de tener varias claves que coincidan con la entrada, le di a cada clave regex una prioridad y se utilizó la más alta prioridad.

3

¿Qué hay de lo siguiente:

class redict(dict): 
def __init__(self, d): 
    dict.__init__(self, d) 

def __getitem__(self, regex): 
    r = re.compile(regex) 
    mkeys = filter(r.match, self.keys()) 
    for i in mkeys: 
     yield dict.__getitem__(self, i) 

Es básicamente una subclase del tipo dict en Python. Con esto puede proporcionar una expresión regular como clave, y los valores de todas las claves que coinciden con esta expresión regular se devuelven de forma iterativa utilizando rendimiento.

Con esto se puede hacer lo siguiente:

>>> keys = ["a", "b", "c", "ab", "ce", "de"] 
>>> vals = range(0,len(keys)) 
>>> red = redict(zip(keys, vals)) 
>>> for i in red[r"^.e$"]: 
...  print i 
... 
5 
4 
>>> 
+0

Funcionalmente, esto está bien, pero en cuanto al rendimiento, sigue siendo O (n) porque filter() es O (n) (bueno, en realidad es peor que O (n) porque tenemos que hacer coincidir la expresión regular con cada clave, que tiene un costo no constante, pero supongo que será parte de cualquier solución). Me gustaría buscar las claves de una mejor manera que la O (n), si es posible. Otros sugirieron estructuras de datos tales como intentos que podrían hacer esto posible. – Jeff

0

Ok, tengo unas necesidades muy similares, tengo una gran cantidad de líneas de sintaxis diferente, básicamente remarcar líneas y líneas con algunos códigos para utilizar en un proceso de formato de tarjeta inteligente, también, líneas descriptivas de claves y códigos secretos, en todos los casos, creo que el patrón/acción "modelo" es el enfoque bestial para reconocer y procesar muchas líneas.
estoy usando C++/CLI para desarrollar mi ensamblaje nombrado LanguageProcessor.dll, el núcleo de esta biblioteca es una clase lex_rule que básicamente contiene:

  • un miembro de expresiones regulares miembro de
  • un evento

El constructor carga la cadena de expresiones regulares y llama a los códigos necesarios para construir el evento sobre la marcha usando DynamicMethod, Emit y Reflexion ... también en el conjunto existe otra clase como meta y objeto que construye y crea una instancia de los objetos con los nombres simples del publicador y la clase receptora, la clase receptora proporciona los controladores de acción para cada regla coincidente.

Tarde, tengo una clase llamada fasterlex_engine que crea un diccionario <Regex, action_delegate> que carga las definiciones de una matriz para ejecutar.

El proyecto está en un punto avanzado pero todavía estoy construyendo, hoy.Voy a tratar de mejorar el rendimiento de funcionamiento que rodea el acceso secuencial a cada entrada de línea par foreach, a través de el uso de algún mecanismo de buscar el diccionario directamente a través de la expresión regular como:

map_rule[gcnew Regex("[a-zA-Z]")]; 

Aquí, algunos de los segmentos de mi código:

public ref class lex_rule: ILexRule 
{ 
private: 
    Exception   ^m_exception; 
    Regex    ^m_pattern; 

    //BACKSTORAGE delegates, esto me lo aprendi asiendo la huella.net de m*e*da JEJE 
    yy_lexical_action ^m_yy_lexical_action; 
    yy_user_action  ^m_yy_user_action; 

public: 
    virtual property String ^short_id; 
private: 
    void init(String ^_short_id, String ^well_formed_regex); 
public: 

    lex_rule(); 
    lex_rule(String ^_short_id,String ^well_formed_regex); 
    virtual event yy_lexical_action ^YY_RULE_MATCHED 
    { 
     virtual void add(yy_lexical_action ^_delegateHandle) 
     { 
      if(nullptr==m_yy_lexical_action) 
       m_yy_lexical_action=_delegateHandle; 
     } 
     virtual void remove(yy_lexical_action ^) 
     { 
      m_yy_lexical_action=nullptr; 
     } 

     virtual long raise(String ^id_rule, String ^input_string, String ^match_string, int index) 
     { 
      long lReturn=-1L; 
      if(m_yy_lexical_action) 
       lReturn=m_yy_lexical_action(id_rule,input_string, match_string, index); 
      return lReturn; 
     } 
    } 
}; 

Ahora la clase fasterlex_engine que ejecutar una gran cantidad de par patrón/acción:

public ref class fasterlex_engine 
{ 
private: 
    Dictionary<String^,ILexRule^> ^m_map_rules; 
public: 
    fasterlex_engine(); 
    fasterlex_engine(array<String ^,2>^defs); 
    Dictionary<String ^,Exception ^> ^load_definitions(array<String ^,2> ^defs); 
    void run(); 
}; 

Y dE ESTA bacalao para decorar TOPIC..some correo de mi cpp:

este código crea un invocador constructor por el signo del parámetro

inline Exception ^object::builder(ConstructorInfo ^target, array<Type^> ^args) 
{ 
try 
{ 
    DynamicMethod ^dm=gcnew DynamicMethod(
     "dyna_method_by_totem_motorist", 
     Object::typeid, 
     args, 
     target->DeclaringType); 
    ILGenerator ^il=dm->GetILGenerator(); 
    il->Emit(OpCodes::Ldarg_0); 
    il->Emit(OpCodes::Call,Object::typeid->GetConstructor(Type::EmptyTypes)); //invoca a constructor base 
    il->Emit(OpCodes::Ldarg_0); 
    il->Emit(OpCodes::Ldarg_1); 
    il->Emit(OpCodes::Newobj, target); //NewObj crea el objeto e invoca al constructor definido en target 
    il->Emit(OpCodes::Ret); 
    method_handler=(method_invoker ^) dm->CreateDelegate(method_invoker::typeid); 
} 
catch (Exception ^e) 
{ 
    return e; 
} 
return nullptr; 

}

Este código adjuntar un cualquier función de controlador (estática o no) para hacer frente a una devolución de llamada planteado haciendo coincidir de una cadena de entrada

Delegate ^connection_point::hook(String ^receiver_namespace,String ^receiver_class_name, String ^handler_name) 
{ 
Delegate ^d=nullptr; 
if(connection_point::waitfor_hook<=m_state) // si es 0,1,2 o mas => intenta hookear 
{ 
    try 
    { 
     Type ^tmp=meta::_class(receiver_namespace+"."+receiver_class_name); 
     m_handler=tmp->GetMethod(handler_name); 
     m_receiver_object=Activator::CreateInstance(tmp,false); 

     d=m_handler->IsStatic? 
      Delegate::CreateDelegate(m_tdelegate,m_handler): 
      Delegate::CreateDelegate(m_tdelegate,m_receiver_object,m_handler); 

     m_add_handler=m_connection_point->GetAddMethod(); 
     array<Object^> ^add_handler_args={d}; 
     m_add_handler->Invoke(m_publisher_object, add_handler_args); 
     ++m_state; 
     m_exception_flag=false; 
    } 
    catch(Exception ^e) 
    { 
     m_exception_flag=true; 
     throw gcnew Exception(e->ToString()) ; 
    } 
} 
return d;  
} 

, finalmente, el código que llama al motor de léxico:

array<String ^,2> ^defs=gcnew array<String^,2> {/* shortID pattern   namespc clase   fun*/ 
                {"LETRAS", "[A-Za-z]+"  ,"prueba", "manejador", "procesa_directriz"}, 
                {"INTS", "[0-9]+"  ,"prueba", "manejador", "procesa_comentario"}, 
                {"REM",  "--[^\\n]*"  ,"prueba", "manejador", "nullptr"} 
               }; //[3,5] 

//USO EL IDENTIFICADOR ESPECIAL "nullptr" para que el sistema asigne el proceso del evento a un default que realice nada 
fasterlex_engine ^lex=gcnew fasterlex_engine(); 
Dictionary<String ^,Exception ^> ^map_error_list=lex->load_definitions(defs); 
lex->run(); 
0

El problema no tiene nada que ver con las expresiones regulares: tendrías el mismo problema con un diccionario con teclas como funciones de lambdas. Entonces, el problema al que se enfrenta es imaginar que hay una forma de clasificar sus funciones para calcular cuál será verdadera o no y eso no es un problema de búsqueda porque f (x) no se conoce en general de antemano.

La programación distribuida o los conjuntos de respuestas de caché suponiendo que hay valores comunes de x pueden ayudar.

- DM

3

Aquí es una manera eficiente de hacerlo mediante la combinación de las teclas en una sola expresión regular compilada, y por lo que no requiere ningún bucle sobre patrones clave. Abusa del lastindex para averiguar qué clave coincide. (Es una pena que las bibliotecas regexp no le permitan etiquetar el estado terminal del DFA en el que se compila una expresión regular, o esto sería menos un hack).

La expresión se compila una vez y producirá un rápido matcher que no tiene que buscar secuencialmente. Los prefijos comunes se compilan juntos en el DFA, por lo que cada carácter de la clave se combina una vez, no muchas veces, a diferencia de algunas de las otras soluciones sugeridas. Está compilando efectivamente un mini lexer para su espacio de claves.

Este mapa no es extensible (no se pueden definir nuevas claves) sin recompilar la expresión regular, pero puede ser útil para algunas situaciones.

# Regular expression map 
# Abuses match.lastindex to figure out which key was matched 
# (i.e. to emulate extracting the terminal state of the DFA of the regexp engine) 
# Mostly for amusement. 
# Richard Brooksby, Ravenbrook Limited, 2013-06-01 

import re 

class ReMap(object): 

    def __init__(self, items): 
     if not items: 
      items = [(r'epsilon^', None)] # Match nothing 
     key_patterns = [] 
     self.lookup = {} 
     index = 1 
     for key, value in items: 
      # Ensure there are no capturing parens in the key, because 
      # that would mess up match.lastindex 
      key_patterns.append('(' + re.sub(r'\((?!\?:)', '(?:', key) + ')') 
      self.lookup[index] = value 
      index += 1 
     self.keys_re = re.compile('|'.join(key_patterns)) 

    def __getitem__(self, key): 
     m = self.keys_re.match(key) 
     if m: 
      return self.lookup[m.lastindex] 
     raise KeyError(key) 

if __name__ == '__main__': 
    remap = ReMap([(r'foo.', 12), (r'FileN.*', 35)]) 
    print remap['food'] 
    print remap['foot in my mouth'] 
    print remap['FileNotFoundException: file.x does not exist'] 
2

@ rptb1 no tiene que evitar la captura de grupos, porque puede usar re.groups para contarlos. De esta manera:

# Regular expression map 
# Abuses match.lastindex to figure out which key was matched 
# (i.e. to emulate extracting the terminal state of the DFA of the regexp engine) 
# Mostly for amusement. 
# Richard Brooksby, Ravenbrook Limited, 2013-06-01 

import re 

class ReMap(object): 
    def __init__(self, items): 
     if not items: 
      items = [(r'epsilon^', None)] # Match nothing 
     self.re = re.compile('|'.join('('+k+')' for (k,v) in items)) 
     self.lookup = {} 
     index = 1 
     for key, value in items: 
      self.lookup[index] = value 
      index += re.compile(key).groups + 1 

    def __getitem__(self, key): 
     m = self.re.match(key) 
     if m: 
      return self.lookup[m.lastindex] 
     raise KeyError(key) 

def test(): 
    remap = ReMap([(r'foo.', 12), 
        (r'.*([0-9]+)', 99), 
        (r'FileN.*', 35), 
        ]) 
    print remap['food'] 
    print remap['foot in my mouth'] 
    print remap['FileNotFoundException: file.x does not exist'] 
    print remap['there were 99 trombones'] 
    print remap['food costs $18'] 
    print remap['bar'] 

if __name__ == '__main__': 
    test() 

Lamentablemente muy pocos motores RE realidad compilar las expresiones regulares a código de máquina, aunque no es especialmente difícil de hacer. Sospecho que hay una mejora en el rendimiento del orden de magnitud esperando a que alguien haga una buena biblioteca RE JIT.

+0

Creo que es mejor eliminar los parens capturados cuando se construye la expresión regular, por dos razones: 1. el comparador no tiene que almacenar información inútil, y 2. el conjunto de claves en el diccionario sigue siendo denso, y estoy esperando que esté optimizado. – rptb1

+0

@ rptb1: "Espero que esté optimizado": los diccionarios en Python no tienen un tratamiento especial de conjuntos densos de enteros pequeños. Ver ['dictobject.c'] (http://hg.python.org/cpython/file/a3f6e5920881/Objects/dictobject.c). –

Cuestiones relacionadas