[RETO] + Funcion Extraer Numeros de Cadenas! [Cpp/C]

Iniciado por x64core, 4 Enero 2012, 22:41 PM

0 Miembros y 4 Visitantes están viendo este tema.

x64core

Buenas gente bueno recordando hace meses me gustaria hacer un reto y espero que participemos todos :)
bien calentemos primeros :D

RETO: Funcion Extraer Valores Numericos de Cadenas
Ejemplo:
Input: ewiuc3dskhd8nkd62ndsnk9
Ouput: 38629

Teneis hasta 08/01/2012 ese dia se hara el Testing de nuestras funciones , gana la funcion mas optimizada, la mas veloz de todas!
como testear la velocidad de nuestras funciones?
Con la Cabecera: Time.h: http://es.wikipedia.org/wiki/Time.h

Vamos Participemos todos! ;D




edit: edito más reglas un poco tarde viendo las espectativas de algunos codigos :P

* NO VALE ASM INLINE ( sera para el proximo reto, pronto :D )

* la funcion debe de devolver el valor en una variable o como retorno de funcion




Cadena para la prueba de velocidad:


"sdh!w2 28 :-)  9ndk#1@b______dy0--hveybd@  # qism083  s'kl...: su2b7h ++bjsnbvxj77ygv1hiiiioms90nms sjbah b#!1!  --R-E-D--0+-w++ONE***WWW."

RETURN:
"228910083277719010"

BlackZeroX

#1


#include <stdio.h>
#include <stdlib.h>

unsigned int getNumbers(char* szIn, char* szBuffer, size_t sizeBuffer);

int main()
{
    char szCadena[] = {"ewiuc3dskhd8nkd62ndsnk9"};
    char* szBuffer = NULL;
    size_t size = getNumbers(szCadena, NULL, 0); // Cuantos numeros hay?...

    if (size > 0)
    {
        szBuffer = (char*)malloc(size + 1);
        printf("%d\n", getNumbers(szCadena, szBuffer, size));
        printf("%s\n", szBuffer);
        free(szBuffer);
    }
    getchar();

    return EXIT_SUCCESS;
}

unsigned int getNumbers(char* szIn, char* szOut, size_t sizeBuffer)
{
    unsigned int iRet = 0;

    while(*szIn)
    {
        if (sizeBuffer == 0 && szOut)
            break;

        if ((*szIn) >= '0' && '9' >= (*szIn) )
        {
            if (szOut)
            {
                (*szOut++) = (*szIn);
                --sizeBuffer;
            }
            iRet++;
        }
        szIn++;
    }

    if (szOut)
        *szOut = (char)0x0;

    return iRet;
}





#include <stdio.h>
#include <stdlib.h>

unsigned int getNumbers(char* szIn, char* szBuffer, size_t sizeBuffer);

int main()
{
    char szCadena[] = {"ewiuc3dskhd8nkd62ndsnk9"};
    char* szBuffer = NULL;
    size_t size = getNumbers(szCadena, NULL, 0); // Cuantos numeros hay?...

    if (size > 0)
    {
        szBuffer = (char*)malloc(size + 1 - 3);
        printf("Se extrayeron: %d de %d\n", getNumbers(szCadena, szBuffer, size - 3), size);
        printf("%s\n", szBuffer);
        free(szBuffer);
    }
    getchar();

    return EXIT_SUCCESS;
}



Dulces Lunas!¡.
The Dark Shadow is my passion.

Khronos14

Bueno ahí va mi versión, la de BlackZeroX la veo poco superable así que se me ocurrió ir guardando los números en un unsigned long ya que puede ser más práctico.


#include <stdio.h>
#include <stdlib.h>

unsigned int parseNumbers(char * szStr, unsigned long * uintOut)
{
unsigned int result = 0;

if (!(szStr && uintOut))
return result;

for (*uintOut = 0; *szStr != 0; szStr++)
if ((*szStr) >= '0' && (*szStr) <= '9')
{
*uintOut = (*uintOut * 10) + (*szStr) - 48;
result++;
}

return result;
}

int main()
{
char * szCadena = "ewiuc3dskhd8nkd62ndsnk9";
unsigned long numbers = 0;

printf("Cantidad de numeros: %d\n", parseNumbers(szCadena, &numbers));
printf("Numbers: %d\n", numbers);

getchar();

return 0;
}


El algoritmo no tiene mucha ciencia, en cada instancia del bucle que encuentra un número voy multiplicando por 10 y sumándole el nuevo número. El nuevo número lo calculo restándole 48 a su número ASCII.

Se me ocurrió una forma de superar el algoritmo de BlackZeroX, igual mañana la pongo en práctica. Sería recorrer el bucle hasta la mitad e ir comprobando los números por delante y por detrás de la cadena, el problema sería juntar los números de las dos mitades pero en cadenas muy muy largas sería más eficiente.

Saludos.

BlackZeroX

#3
Cita de: Khronos14 en  5 Enero 2012, 00:17 AM

Se me ocurrió una forma de superar el algoritmo de BlackZeroX, igual mañana la pongo en práctica. Sería recorrer el bucle hasta la mitad e ir comprobando los números por delante y por detrás de la cadena, el problema sería juntar los números de las dos mitades pero en cadenas muy muy largas sería más eficiente.

Saludos.

Al leerte se me ocurrieron 2 formas mas... al rato las pongo en practica xP, igual son lentas en cadenas cortas, pero en cadenas largas uff.

Nota: Modifique mi codigo...

Dulces Lunas!¡.
The Dark Shadow is my passion.

Eternal Idol

C++, solo para ver que tal le va a la STL del compilador que usen para probar  :laugh:

Código (cpp) [Seleccionar]
#include <string>
#include <algorithm>
#include <iostream>

using namespace std;

bool no_es_numero(char c)
{
  return !isdigit(c);
}

string &extraer(string &str)
{
  str.resize(remove_if(str.begin(), str.end(), no_es_numero) - str.begin());
  return str;
}

void main()
{
  string s = "ewiuc3dskhd8nkd62ndsnk9";
  cout << extraer(s);
}
La economía nunca ha sido libre: o la controla el Estado en beneficio del Pueblo o lo hacen los grandes consorcios en perjuicio de éste.
Juan Domingo Perón

ace332

#5
Bueno estoy suponiendo que no hay más de 9 digitos en la cadena (por que sino no caverán en un int)

#include <stdio.h>
#include <ctype.h>

int extraernum(const char *s);

int main()
{
 printf("%d\n",extraernum("ewiuc3dskhd8nkd62ndsnk9"));
 return 0;
}

int extraernum(const char *s)
{
 const char *p=s;
 int n=0;
 while(*p)
 {
   if(isdigit(*p)) n=10*n+((*p)-'0');
   p++;
 }
 return n;
}


EDIT: No habia leído los códigos de más arriba antes de hacer este post  :-[. En este uso básicamente es el MISMO ALGORITMO que utilizó Kronos14.

rir3760

#6
Una forma ligeramente distinta en C estándar, utilizando la función strpbrk (prototipo en <string.h>) es:
#include <stdio.h>
#include <string.h>

int get_num(char const *s)
{
   int num = 0;
   
   while (s = strpbrk(s, "01234567890"))
      num = num * 10 + *s++ - '0';
   
   return num;
}

int main(void)
{
   printf("%d\n", get_num("ewiuc3dskhd8nkd62ndsnk9"));

   return 0;
}


Editado: el proceso ahora esta en una funcion.

Un saludo
C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language

x64core

Bueno codes gente! ;D




Cita de: GarbageCollector en  5 Enero 2012, 01:20 AM
Bueno estoy suponiendo que no hay más de 9 digitos en la cadena (por que sino no caverán en un int)

#include <stdio.h>
#include <ctype.h>

int extraernum(const char *s);

int main()
{
 printf("%d\n",extraernum("ewiuc3dskhd8nkd62ndsnk9"));
 return 0;
}

int extraernum(const char *s)
{
 const char *p=s;
 int n=0;
 while(*p)
 {
   if(isdigit(*p)) n=10*n+((*p)-'0');
   p++;
 }
 return n;
}



Lo siento la función debe de aceptar cualquier longitud de cadena, no debe ser fija ( no lo puse en la reglas, perdon)




la mia:
Código (cpp) [Seleccionar]

#include "stdio.h"

void getnumbers(char* Str, int &v)
{
int c=0;
do{
if((Str[c] >= 0x30) && (Str[c] <= 0x39)){
Str[v]=Str[c];
v++;
}
Str[c]=NULL;
c++;
}while(!(Str[c] == NULL));
}

int main()
{
char rSTR[] = {"ewiuc3dskhd8nkd62ndsnk9"};
int nVals = 0x0;

getnumbers(rSTR,nVals);
printf("%s\n",rSTR);
printf("%i\n",nVals);

return 0;
}




ace332

No hay cuidado  ;D Ahora el code sí cumple con las especificaciones del problema:


#include <stdio.h>
#include <ctype.h>

#define MAX_DIGITOS 1000

int extraernum(const char *s, char *n);

int main()
{
 char n[MAX_DIGITOS];
 int cdig;
 cdig=extraernum("ewiuc3dskhd8nkd62ndsnk9",n);
 printf("%s\n%d\n",n,cdig);
 return 0;
}

int extraernum(const char *s, char *n)
{
 const char *p=s;
 int cdig=0;
 while(*p)
 {
   if(isdigit(*p)) n[cdig++]=*p;
   p++;
 }
 n[cdig]='\0';
 return cdig;
}

BlackZeroX

#9
@GarbageCollecter
Tu codigo tiene una declaración que es absurda... mas en espesifico const char *p...

Dulces Lunas!¡.

EI: juntando mensajes.

mmm se me ocurre hacer esto (es demasiado CODIGO)...

* Tiene un Bug respecto a la ordenación de los elementos...
* Tiene la ventaja de que deberia de ser el doble de rapido que mi algoritmo normal (Solo si se cuenta con minimos 2 nucleos esto es plena teoria)...

linkear a: libpthread o como se llame en su PC...

Esta funcion el 1er hilo recorre el 0 y numeros PARES, el segundo hilo solo Numeros IMPARES...


#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

typedef struct _config
{
    char* szIn;
    char* szOut;
    size_t size;
    size_t start;
    unsigned int* lpPosOut;
    pthread_mutex_t* lpMutex;
}
CONFIG, *LPCONFIG;

void* divideYVenceras(void* arg);
unsigned int getNumbers(char* szIn, char* szOut, size_t size);

int main()
{
    char szCadena[] = {"ewiuc3dskhd8nkd62ndsnk9"};
    char* szBuffer = NULL;
    size_t size = getNumbers(szCadena, NULL, 0); // Cuantos numeros hay?...

    if (size > 0)
    {
        szBuffer = (char*)malloc(size + 1);
        printf("Se extrayeron: %d de %d\n", getNumbers(szCadena, szBuffer, size ), size);
        printf("%s\n", szBuffer);
        free(szBuffer);
    }

    getchar();

    return EXIT_SUCCESS;
}

void*
divideYVenceras(void* arg)
{
    LPCONFIG lpConfig = (LPCONFIG)arg;
    unsigned int iRet = 0;
    unsigned int i = lpConfig->start;

    while(lpConfig->szIn[i])
    {
        if (i > 0 && !lpConfig->szIn[i - 1])
            break;

        if (lpConfig->size < (*lpConfig->lpPosOut) && lpConfig->szOut)
            break;

        if (lpConfig->szIn[i] >= '0' && '9' >= lpConfig->szIn[i] )
        {
            if (lpConfig->szOut)
            {
                pthread_mutex_lock(lpConfig->lpMutex);
                lpConfig->szOut[(*lpConfig->lpPosOut)++] = lpConfig->szIn[i];
                pthread_mutex_unlock(lpConfig->lpMutex);
            }
            iRet++;
        }
        i += 2;
    }

    pthread_exit((void*)iRet);

    //return iRet;  //  No tendria caso...
}

unsigned int
getNumbers(char* szIn, char* szOut, size_t size)
{
    pthread_t pthHilos[2];
CONFIG udtConfig[2];
unsigned int i = 0;
unsigned int lpiRet = 0;
unsigned int iRet = 0;
pthread_mutex_t mutex;

    pthread_mutex_init(&mutex, NULL);

udtConfig[0].szIn = udtConfig[1].szIn = szIn;
udtConfig[0].size = udtConfig[1].size = size;
udtConfig[0].szOut = udtConfig[1].szOut = szOut;
udtConfig[0].start = 0;
udtConfig[1].start = 1;
udtConfig[0].lpPosOut = udtConfig[1].lpPosOut = &i;
udtConfig[0].lpMutex = udtConfig[1].lpMutex = &mutex;

pthread_create(&pthHilos[0], NULL, divideYVenceras, &udtConfig[0]);
pthread_create(&pthHilos[1], NULL, divideYVenceras, &udtConfig[1]);

    pthread_join(pthHilos[0], (void**)&lpiRet);
    iRet = (int)lpiRet;
    pthread_join(pthHilos[1], (void**)&lpiRet);
    iRet += (int)lpiRet;

    pthread_mutex_destroy(&mutex);

    if (szOut)
        szOut[iRet + 1] = (char)0x0;

    return iRet;
}



Codigo Actualizado...

El primer Hilo recorre el 1er trozo de la cadena y el segundo hilo el trozo faltante... se pueden agrenar N hilos si asi se requieren... es RAPIDO con Cadenas LARGAS...



#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

typedef struct _config
{
    char* szIn;
    size_t sizeIn;
    char* szOut;
    size_t sizeOut;
    unsigned int* lpPosOut;
    pthread_mutex_t* lpMutex;
}
CONFIG, *LPCONFIG;

void* divideYVenceras(void* arg);
unsigned int getNumbers(char* szIn, size_t sizeIn, char* szOut, size_t sizeOut);

int main()
{
    char szCadena[] = {"ewiuc3dskhd8nkd62ndsnk9"};
    char* szBuffer = NULL;
    size_t size = getNumbers(szCadena, strlen(szCadena), NULL, 0); // Cuantos numeros hay?...

    if (size > 0)
    {
        szBuffer = (char*)malloc(size + 1);
        printf("Se extrayeron: %d de %d\n", getNumbers(szCadena, strlen(szCadena), szBuffer, size ), size);
        printf("%s\n", szBuffer);
        free(szBuffer);
    }

    getchar();

    return EXIT_SUCCESS;
}

void*
divideYVenceras(void* arg)
{
    LPCONFIG lpConfig = (LPCONFIG)arg;
    unsigned int iRet = 0;

    if (lpConfig->szIn)
    {
        while(lpConfig->sizeIn-- && *lpConfig->szIn)
        {
            if (lpConfig->sizeOut < (*lpConfig->lpPosOut) && lpConfig->szOut)
                break;

            if ((*lpConfig->szIn) >= '0' && '9' >= (*lpConfig->szIn) )
            {
                if (lpConfig->szOut)
                {
                    pthread_mutex_lock(lpConfig->lpMutex);
                    lpConfig->szOut[(*lpConfig->lpPosOut)++] = *lpConfig->szIn;
                    pthread_mutex_unlock(lpConfig->lpMutex);
                }
                iRet++;
            }
            lpConfig->szIn++;
        }
    }

    pthread_exit((void*)iRet);

    //return iRet;  //  No tendria caso...
}

unsigned int
getNumbers(char* szIn, size_t sizeIn, char* szOut, size_t sizeOut)
{
    pthread_t pthHilos[2];
    CONFIG udtConfig[2];
    unsigned int i = 0;
    unsigned int iRet = 0;
    unsigned int iAdd = 0;
    pthread_mutex_t mutex;

    pthread_mutex_init(&mutex, NULL);

udtConfig[0].szIn = szIn;
udtConfig[0].sizeIn = (sizeIn >> 1);
udtConfig[0].szOut = udtConfig[1].szOut = szOut;
udtConfig[0].sizeOut = udtConfig[1].sizeOut = sizeOut;
udtConfig[0].lpPosOut = udtConfig[1].lpPosOut = &i;
udtConfig[0].lpMutex = udtConfig[1].lpMutex = &mutex;
udtConfig[1].sizeIn = ((udtConfig[0].sizeIn) + (sizeIn & 0x1));
udtConfig[1].szIn = &szIn[(udtConfig[0].sizeIn)];

pthread_create(&pthHilos[0], NULL, divideYVenceras, &udtConfig[0]);
pthread_create(&pthHilos[1], NULL, divideYVenceras, &udtConfig[1]);

    pthread_join(pthHilos[0], (void**)&iAdd);
    iRet = (int)iAdd;
    pthread_join(pthHilos[1], (void**)&iAdd);
    iRet += (int)iAdd;

    pthread_mutex_destroy(&mutex);

    if (szOut)
        szOut[iRet + 1] = (char)0x0;

    return iRet;
}



Dulces Lunas!¡.
The Dark Shadow is my passion.