top - ¿Por qué este programa es más rápido en Python que en Objective-C?

statistics stack overflow

Question

Me interesé en este pequeño ejemplo de algoritmo en Python para recorrer una gran lista de palabras. Estoy escribiendo algunas "herramientas" que me permitirán cortar una cadena o matriz de Objective-C de manera similar a Python.

Específicamente, esta solución elegante me llamó la atención por la ejecución muy rápida y utiliza un segmento de cadena como elemento clave del algoritmo. ¡Intenta resolver esto sin una rebanada!

He reproducido mi versión local utilizando la lista de palabras de Moby a continuación. Puede usar /usr/share/dict/words si no tiene ganas de descargar Moby. La fuente es solo una gran lista de palabras únicas similar a un diccionario.

#!/usr/bin/env python

count=0
words = set(line.strip() for line in   
           open("/Users/andrew/Downloads/Moby/mwords/354984si.ngl"))
for w in words:
    even, odd = w[::2], w[1::2]
    if even in words and odd in words:
        count+=1

print count      

Este script a) será interpretado por Python; b) leer el archivo del diccionario Moby de 4,1 MB, 354,983 palabras; c) tira las líneas; d) colocar las líneas en un conjunto, y; e) y encuentre todas las combinaciones donde los vértices y las probabilidades de una palabra dada también sean palabras. Esto se ejecuta en aproximadamente 0,73 segundos en un MacBook Pro.

Intenté reescribir el mismo programa en Objective-C. Soy un principiante en este idioma, así que vaya fácil, por favor, señale los errores.

#import <Foundation/Foundation.h>

NSString *sliceString(NSString *inString, NSUInteger start, NSUInteger stop, 
        NSUInteger step){
    NSUInteger strLength = [inString length];

    if(stop > strLength) {
        stop = strLength;
    }

    if(start > strLength) {
        start = strLength;
    }

    NSUInteger capacity = (stop-start)/step;
    NSMutableString *rtr=[NSMutableString stringWithCapacity:capacity];    

    for(NSUInteger i=start; i < stop; i+=step){
        [rtr appendFormat:@"%c",[inString characterAtIndex:i]];
    }
    return rtr;
}

NSSet * getDictWords(NSString *path){

    NSError *error = nil;
    NSString *words = [[NSString alloc] initWithContentsOfFile:path
                         encoding:NSUTF8StringEncoding error:&error];
    NSCharacterSet *sep=[NSCharacterSet newlineCharacterSet];
    NSPredicate *noEmptyStrings = 
                     [NSPredicate predicateWithFormat:@"SELF != ''''"];

    if (words == nil) {
        // deal with error ...
    }
    // ...

    NSArray *temp=[words componentsSeparatedByCharactersInSet:sep];
    NSArray *lines = 
        [temp filteredArrayUsingPredicate:noEmptyStrings];

    NSSet *rtr=[NSSet setWithArray:lines];

    NSLog(@"lines: %lul, word set: %lul",[lines count],[rtr count]);
    [words release];

    return rtr;    
}

int main (int argc, const char * argv[])
{
    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];

    int count=0;

    NSSet *dict = 
       getDictWords(@"/Users/andrew/Downloads/Moby/mwords/354984si.ngl");

    NSLog(@"Start");

    for(NSString *element in dict){
        NSString *odd_char=sliceString(element, 1,[element length], 2);
        NSString *even_char=sliceString(element, 0, [element length], 2);
        if([dict member:even_char] && [dict member:odd_char]){
            count++;
        }

    }    
    NSLog(@"count=%i",count);

    [pool drain];
    return 0;
}

La versión de Objective-C produce el mismo resultado, (13,341 palabras), pero toma casi 3 segundos para hacerlo. Debo estar haciendo algo atrozmente incorrecto para que un lenguaje compilado sea más de 3X más lento que un lenguaje con guión, pero seré maldito si puedo ver por qué.

El algoritmo básico es el mismo: lee las líneas, quítalas y colócalas en un conjunto.

Mi conjetura de lo que es lento es el procesamiento de los elementos NSString, pero no conozco una alternativa.

Editar

Edité el Python para ser esto:

#!/usr/bin/env python
import codecs
count=0
words = set(line.strip() for line in 
     codecs.open("/Users/andrew/Downloads/Moby/mwords/354984si.ngl",
          encoding=''utf-8''))
for w in words:
    if w[::2] in words and w[1::2] in words:
        count+=1

print count 

Para que el utf-8 esté en el mismo plano que el utf-8 NSString. Esto redujo la velocidad del Python a 1.9 segundos.

También cambio la prueba de corte al tipo de cortocircuito como se suggested para las versiones Python y obj-c. Ahora están cerca de la misma velocidad. También intenté usar matrices C en lugar de NSStrings, y esto fue mucho más rápido, pero no tan fácil. También pierdes el soporte de utf-8 haciendo eso.

Python es realmente genial ...

Editar 2

Encontré un cuello de botella que aceleró las cosas considerablemente. En lugar de usar el [rtr appendFormat:@"%c",[inString characterAtIndex:i]]; método para añadir un carácter a la cadena de retorno, usé esto:

for(NSUInteger i=start; i < stop; i+=step){
    buf[0]=[inString characterAtIndex:i];
    [rtr appendString:[NSString stringWithCharacters:buf length:1]];
}

Ahora finalmente puedo afirmar que la versión de Objective-C es más rápida que la versión de Python, pero no mucho.

Answer 1

En AMBOS códigos usted construye los segmentos pares e impares y luego los compara con las palabras. Sería mejor si construyera la división impar solo después de que la división par tenga éxito.

Código de Python actual:

even, odd = w[::2], w[1::2]
if even in words and odd in words:

Mejor:

# even, odd = w[::2], w[1::2]
if w[::2] in words and w[1::2] in words:

Por cierto, una métrica que no mencionaste: ¿Cuánto tiempo te llevó ESCRIBIR cada código?

Answer 2

En primer lugar, la biblioteca de CPython está escrita en C y está altamente optimizada, por lo que no es sorprendente que un programa que aprovecha la biblioteca se ejecute más rápido que el Objective C no optimizado.

El resultado sería diferente si tradujera línea a línea el programa Objective C en Python.

Sospecho que gran parte del resultado se debe al hecho de que el contador no se incrementa con mucha frecuencia y que Python es muy eficiente para decidir que un objeto NO está en el conjunto. Después de todo, si toma cada segunda letra de una palabra, parece bastante improbable que termine con una palabra válida en inglés, y mucho menos una en el mismo texto de origen.

Answer 3

Su código de Python se ejecuta principalmente en estructuras de datos integradas, que se implementan en C. Python contiene optimizaciones increíblemente sofisticadas para esos tipos de datos. Busque conversaciones de Raymond Hettinger para más detalles. Se trata principalmente de un hashing de objetos muy eficiente, el uso de esos hashes para búsquedas, estrategias especiales de asignación de memoria, ...

Había implementado una búsqueda de red en python solo para realizar pruebas y nunca pudimos acelerarla en C ++, C # o un lenguaje similar. ¡No siendo principiantes en C ++ o C #! ;-)

Answer 4

Tenga en cuenta que la versión de Python se ha escrito para mover gran parte del levantamiento pesado a un código C altamente optimizado cuando se ejecuta en CPython (especialmente el búfer de entrada de archivos, el corte de cadenas y las búsquedas de tablas de hash para verificar si están odd e odd ) words ).

Dicho esto, parece que estás decodificando el archivo como UTF-8 en tu código de Objective-C, pero dejando el archivo en binario en tu código de Python. Usar Unicode NSString en la versión de Objective-C, pero las cadenas de bytes de 8 bits en la versión de Python no es realmente una comparación justa: esperaría que el rendimiento de la versión de Python se codecs.open() notablemente si utilizara codecs.open() para abrir el archivo con una codificación declarada de "utf-8" .

También estás haciendo una segunda pasada completa para eliminar las líneas vacías en tu Objective-C, mientras que ese paso no está presente en el código de Python.

Answer 5

http://developer.apple.com/library/mac/#documentation/Cocoa/Reference/Foundation/Classes/NSSet_Class/Reference/Reference.html sugiere que es posible que desee sustituir NSSet con CFSet, que puede mejorar el rendimiento.

No pude encontrar con una búsqueda rápida en Google la implementación utilizada para NSSet / CFSet: si usan una implementación basada en árbol (igual que el tipo de conjunto stdc ++), entonces la búsqueda y verificación son O (registro (N)) mientras que la búsqueda de conjunto de Python O ( 1), esto podría explicar la diferencia de velocidad.

[editar] ncoghlan señaló en una observación a continuación que los conjuntos en el objetivo C usan una tabla hash para que también obtengas una búsqueda constante en el tiempo. Así que esto se reduce a cuán eficiente es la implementación de conjuntos en Python vs en Objective C. Como otros lo señalaron, los conjuntos y diccionarios de Python están muy optimizados, especialmente. cuando las cadenas se utilizan como claves (los diccionarios de Python se utilizan para implementar los espacios de nombres y deben ser muy rápidos).