C Programm arbeitet genauso langsam wie im Java (brauche Hilfe)...

SeppJ

o4kareg schrieb:

Nein dies ist kein Benchmark, ich will einfach dies moeglichst schnell laufen zu kriegen und ueberrascht war das die Ergebnisse so sind.

Dann: STOPP!

Wie TyRoXx und ich schon angedeutet haben, der Code ist derzeit eher ... suboptimal.

Erklär mal ganz genau, was dein Code machen soll, am besten mit Beispielen. Dann kann man gemeinsam was gutes ausarbeiten. Und muss es C sein oder darf es auch C++ sein?

Dumme Compileroptionen?

Ja jetzt kommen wir vllt. zum wahres Grund , was fuer Optionen besser sind in dem Fall?

Na, irgendwelche. Du musst deine Werkzeuge schon selber beherrschen. Anleitung findest du bei Google und beim Compiler dabei (und der erste Treffer bei Google wird wahrscheinlich nochmals genau jene Anleitung sein)

Dies wuerde den noch verlangsamen, aus bestimmten gruenden ist mir Arbeistpeicher erst ...egal

Nein, es ist nicht egal. Wer schlampig programmiert der denkt auch erfahrungsgemäß schlampig. Schlampige Algorithmen schlampig programmiert sind langsam, fehleranfällig und schwer zu warten. ^[*]

^[*]: Jetzt wo ich das geschrieben habe, komme ich nicht drumrum anzumerken, dass dies deinen oben gezeigten Code recht gut beschreibt.

Mal was anderes:
Wenn du mit

dummy = ((47<chr) && (chr<58));

dummy = (('0'<=chr) && (chr<='9'));

meinst, dann kannst du das auch schreiben.
Oder besser

dummy = isdigit(chr);

Und in Zeile 69:

};//end of if ($lim<4)

Nur gibt es dieses if nirgends.

Wenn du möchtest, das dir jemand hilft, räum deinen Code auf. Auch optisch.

TyRoXx

o4kareg schrieb:

Die Listen gefallen mir auch nicht so wirklich, aber wie soll man ohne dies es zu loesen.

Mit einem Array, das alle 2^n Elemente mit realloc vergrößert wird.

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

typedef struct address
{
	//wird nie länger als 16
	char str[16];
} address;

typedef struct address_vector
{
	address *elements;
	size_t used;
	size_t allocated;
} address_vector;

void init_address_vector(address_vector *v)
{
	v->elements = 0;
	v->used = 0;
	v->allocated = 0;
}

void free_address_vector(address_vector *v)
{
	free(v->elements);
}

void add_address(address_vector *v, const address *element)
{
	if (v->allocated == v->used)
	{
		if (v->allocated == 0)
		{
			v->allocated = 4;
		}
		else
		{
			v->allocated *= 2;
		}

		v->elements = realloc(v->elements, sizeof(*v->elements) * v->allocated);
	}

	v->elements[v->used] = *element;
	++(v->used);
}

int main()
{
	size_t i;
	address_vector v;
	address a = {{"8.8.8.8"}};

	init_address_vector(&v);
	add_address(&v, &a);

	for (i = 0; i < v.used; ++i)
	{
		printf("%s\n", v.elements[i].str);
	}

	free_address_vector(&v);
	return 0;
}

o4kareg schrieb:

Dumme Compileroptionen?

Ja jetzt kommen wir vllt. zum wahres Grund , was fuer Optionen besser sind in dem Fall?

Aber klar, immer sind die anderen Schuld..

Zeus

Java Code aufräumen ganz einfach:

// Performance Trick for Speed Up
    private static Pattern pattern = Pattern.compile("[0-9]{1,3}+\\.[0-9]{1,3}+\\.[0-9]{1,3}+\\.[0-9]{1,3}+");

    public static List<String> findip4(String text){
        List<String> ret = new ArrayList<>();
        Matcher matcher = pattern.matcher(text);
        while(matcher.find()) {
            ret.add(matcher.group());
        }

        return ret;
    }

Ergebnis ist korrekter anscheinend, aber (bei mir) auch langsamer.

123.198.77.001
245.223.54.345
555.666.777.888
444.444.44.44
1.1.1.1
1.1.1.1
1.1.1.1
2.2.2.2
45.45.45.45

anstelle von

123.198.77.001
245.223.54.345
666.777.888.999
444.444.44.44
1.1.1.1
1.1.1.1
1.1.1.1
2.2.2.2
45.45.45.45

TyRoXx schrieb:

v->elements = realloc(v->elements, sizeof(*v->elements) * v->allocated);

Recht übel, realloc kann auch NULL liefern -> Speicherleck und alle Daten pfutsch. Excception-verwöhnt?

TyRoXx

Thorgrim schrieb:

TyRoXx schrieb:
v->elements = realloc(v->elements, sizeof(*v->elements) * v->allocated);
Recht übel, realloc kann auch NULL liefern -> Speicherleck und alle Daten pfutsch. Excception-verwöhnt?

Ja, das habe ich ganz vergessen.

So besser?

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

typedef struct address
{
	//wird nie länger als 16
	char str[16];
} address;

typedef struct address_vector
{
	address *elements;
	size_t used;
	size_t allocated;
} address_vector;

void init_address_vector(address_vector *v)
{
	v->elements = 0;
	v->used = 0;
	v->allocated = 0;
}

void free_address_vector(address_vector *v)
{
	free(v->elements);
}

int add_address(address_vector *v, const address *element)
{
	if (v->allocated == v->used)
	{
		address *new_elements;
		size_t reallocated;

		if (v->allocated == 0)
		{
			reallocated = 4;
		}
		else
		{
			reallocated = (v->allocated * 2);
		}

		new_elements = realloc(v->elements, sizeof(*v->elements) * reallocated);
		if (!new_elements)
		{
			return 0;
		}

		v->elements = new_elements;
		v->allocated = reallocated;
	}

	v->elements[v->used] = *element;
	++(v->used);
	return 1;
}

int main()
{
	size_t i;
	address_vector v;
	address a = {{"8.8.8.8"}};

	init_address_vector(&v);

	for (i = 0; i < 10; ++i)
	{
		if (!add_address(&v, &a))
		{
			fprintf(stderr, "Allocation failed\n");
			free_address_vector(&v);
			return 1;
		}
	}

	for (i = 0; i < v.used; ++i)
	{
		printf("%s\n", v.elements[i].str);
	}

	free_address_vector(&v);
	return 0;
}

o4kareg

Danke Leute, also hauptsache liegt es nur in Allocationen. Oder in dem Vergleich?
Ist isdigit() schneller?

Der Ratschlag

Mit einem Array, das alle 2^n Elemente mit realloc vergrößert wird.

klingt gut, bzw. koennte man sogar. mit zwei (grossen) statischen Array auskommen, und als einer voll wird mit anderem Thread die IPs in Text-File zu speichern.

Danke auch fuer Java- code (ich kannte nicht die Methode) aber selbstverstaendlich wurde dieser Aufruf langsamer sein.

Wenn es nur darum geht, die IPs aus dem Text rauszugreppen und in eine Datei zu speichern, kannst du dir die Kopiererei von vorneherein sparen und das alles in einem Rutsch machen. Dann entfällt auch die Speicherverwaltung vollständig.

Was den Algorithmus und seine Optimierung angeht, hängen die Details von den erwarteten Eingabedaten ab. Erwartest du eine Menge Text, in dem ein paar IP-Adressen stehen, oder eine Liste von IP-Adressen mit ein paar Zeichen hier und da dazwischen?

Außerdem: Aus "1.2.3.4.5" lässt sich sowohl "1.2.3.4" als auch "2.3.4.5" herauslesen, und aus "12.34.56.78" auch "2.34.56.78", "12.34.56.7" und "2.34.56.7". Außerdem ist es mit Zahlen allein nicht getan, denn "1.2.3.456" ist keine gültige IP-Adresse (obwohl man da "1.2.3.45" herausparsen könnte). Wie soll mit dieser Problematik umgegangen werden?

Nachtrag: Ich denke mir das etwa so:

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

static char const *const text =
  "abd\n\n\tc\r123.198.77.001fddfsd245.223.54.345  546.345.234..543gd"
  "asdadfsdfgdfgdfgdg1233.4444.5555.666.777.888.999.dfgadfgkajhdfogiuadf"
  "oiguahdfgjandlfgadfgaldfjkgaldkfjghaldkfjghalkdjfghakljdfhgklajdfhgkljd"
  "fhlgkjadf444.444.44.44.1.1.1.1.1.1.1.1.1.1.1.1.2.2.2.2.dfgdfgdfgdfdfgdfgdf"
  "sdfgjksfhgisudfhgjnwe.e,rrmnw.e,rndk;fjgnd;kfjgnw.,rmn;kjdfs;kdjgndfg"
  "#$%#$%.@$@#$2.qweqwr.2#$@#4.wer.er.e.e.r4f.5g.3d.34.df.45.45.45.45g"
  "abd\n";

int main(void) {
  char const *p = text;
  char const *p_vorn = p;

  while((p_vorn = p = strpbrk(p, "123456789"))) {
    int octet_count;

    for(octet_count = 0; octet_count < 4; ++octet_count, ++p) {
      int digits;
      for(digits = 0; digits < 3 && isdigit(*p); ++digits, ++p) { }
      if(digits == 0 || (*p != '.' && octet_count != 3)) break;
    }

    if(octet_count == 4) {
      /* Hier dann halt statt stdout deine Datei */
      fwrite(p_vorn, sizeof(char), p - p_vorn - 1, stdout);
      putchar('\n');
    }
  }

  return 0;
}

Ob die Verwendung von strpbrk in dieser Form sich lohnt, sollte anhand typischer Eingabedaten ausgemessen werden; es dürfte vor allem dann der Fall sein, wenn längere Textstellen ohne Ziffern vorkommen, also viel auf einmal übersprungen wird. Andernfalls kann der strpbrk-Aufruf durch die Funktion

char const *skip_nondigits_and_zeroes(char const *str) {
  for(; *str && (*str < '1' || *str > '9'); ++str)
    ;

  return *str ? str : NULL;
}

oder so ersetzt werden.

Merke: 1233.4444.5555.666.777.888.999 wird von diesem Algorithmus nur mäßig sinnvoll behandelt.

knivil

alle IPv4- aenliche Substrings (d.h. "nnn.nnn.nnn.nnn")

Definiere das mal richtig, so dass eine check-Funktion geschrieben werden kann, die true/false zurueckgibt, wenn der uebergebene String deine Kriterien entspricht/nicht entspricht.

Wutz

o4kareg schrieb:

das bloede dabei ist dass die C und Java Kode fast dasselbe Zeit brauchen

Das halte ich bei diesen Aufgabenstellungen für unhaltbar.

o4kareg schrieb:

(21 sek Java vergl. 19 sek C) und ich habe keine Ahnung wie man dies in C noch optimisieren soll:

Jedenfalls nicht mit verketteten Listen, verkettete Listen und Performanz schließen sich gegenseitig aus.

char **ipv4(const char *s)
{
  int n,n0,n1,n2,n3;
  char *r=calloc(2,strlen(s)),**p=r,*c=r+strlen(s)/2;
  while( EOF!=sscanf(s,"%*[^0-9]%n",&n) )
    if( n0=n1=n2=n3=0,sscanf(s+=n,"%*3[0-9]%n.%*3[0-9]%n.%*3[0-9]%n.%*3[0-9]%n",&n0,&n1,&n2,&n3), n3 )
    {
      memcpy(c,s,n3);
      *p++=c+=n3+1;
      s+=n3;
    }
    else
      s+=n2?n2:n1?n1:n0;
  return r;
}

int main()
{
  char **p=ipv4("abd\n\n\tc\r123.198.77.001fddfsd245.223.54.345  546.345.234..543gd"
                "asdadfsdfgdfgdfgdg1233.4444.5555.666.777.888.999.dfgadfgkajhdfogiuadf"
                "oiguahdfgjandlfgadfgaldfjkgaldkfjghaldkfjghalkdjfghakljdfhgklajdfhgkljd"
                "fhlgkjadf444.444.44.44.1.1.1.1.1.1.1.1.1.1.1.1.2.2.2.2.dfgdfgdfgdfdfgdfgdf"
                "sdfgjksfhgisudfhgjnwe.e,rrmnw.e,rndk;fjgnd;kfjgnw.,rmn;kjdfs;kdjgndfg"
                "#$%#$%.@$@#$2.qweqwr.2#$@#4.wer.er.e.e.r4f.5g.3d.34.df.45.45.45.45g"
                "abd\n"),*r=p;
  while( *p )
    puts(*p++);
  free(r);
  return 0;
}