[elke taal] 2 strings tot n chars gelijk

[Juup]

Voor het inzicht ben ik bezig een natural sort functie te maken.
Een deelprobleem daarvan is het bepalen tot welk punt 2 strings aan elkaar gelijk zijn.
Wat is de snelste manier om dat punt te vinden?

voorbeeld:
string a = 'aabbcc';
string b = 'aabbaa';

Deze strings hebben de eerste 4 karakters gemeen.

Optie 1:
vanaf eerste karakter de karakters vergelijken. (schaalt lineair met stringlengte)

Optie 2:
met een 'binary search': strings op de helft afknippen, vergelijken en met 1e of 2e helften verdergaan. (schaalt met log(stringlengte))

Er moet toch een simpelere of snellere methode zijn om te kijken tot welk punt ze gelijk zijn?

[Alarmnummer]

Als je het vaak gaat doen zou je ook een hashcode ofzo kunnen bepalen voor een string, en kan je hashcodes met elkaar controleren. Zijn de hashcodes hetzelfde dan doe je een inhoudelijke vergelijking. De vraag is dus of je vaak een string moet controleren.

Trouwens strings copieren is ook een dure grap, je kan beter met offsets ofzo gaan werken.

[edit]
hmmzz.. ik was ff iets te snel met mijn reply.. en ik heb vandaag nog helemaal geen koffie gehad, dus vergeet mijn antwoord maar ff

[edit2]
Volgens mij is toch wel het meest handige om toch aan het begin te beginnen, want je kan eigelijk geen uitspraken doen als je halverwege ergens in gaat knippen.


Verder zou het misschien een idee zijn om de 1e paar chars om te zetten tot een int als je vaak moet checken?
aab
112

aaa
111

aangezien 111<112 weet je dus dat de 1e kleiner is.

Hierbij kan je al een kleine performance winst maken. Maar dit is alleen handig als je dus 1 string vaak moet checken.

[Juup]

Ik gebruik steeds 2 'nieuwe' strings. Met offsets bedoel je dat je de substring vanaf 0 tot offset vergelijkt en de offset steeds 1 ophoogt?

[Juup]

Eigenlijk wil je het 'verschil' weten van de twee strings (aangenomen dat ze dezelfde lengte hebben)

[Alarmnummer]

Ik heb ff een reply erbij geplaatst.

jaja.. mag niet.. foei alarmnummer

[Alarmnummer]

Juup schreef op 16 augustus 2002 @ 00:49:
Ik gebruik steeds 2 'nieuwe' strings. Met offsets bedoel je dat je de substring vanaf 0 tot offset vergelijkt en de offset steeds 1 ophoogt?

Ik bedoel dat je met een offset kan verhinderen dat je onnodig strings loopt te copieren. Je kan dan gewoon de orginele string houden, en als je dan een substring wilt hebben dan zou je bv met een offset kunnen werken (en eventueel een nieuwe lengte)

aaaabbba
12345678

nu zou je bbb kunnen schrijven als 5..7 van die string, zonder dat je hem copieerd.

[Juup]

code:

my $string = 'baaa';
print unpack("l", $string) . "\n";
$string = 'aaaa';
print unpack("l", $string);

levert:
1633771874
1633771873

Nu kan ik die twee getallen van elkaar afhalen

[Alarmnummer]

het probleem is dat je niet iedere string in een int of een long kan plaatsen, dus jouw aanpak gaat niet werken. Wat je wel zou kunnen doen is bij een string dan een array van longs kunnen plaatsen voor het extra snelle checkwerk. Maar volgens mij gaat je dus ook wel een stukje performance kosten. Waarom moet het eigelijk snel zijn?

[Juup]

Alarmnummer schreef op 16 augustus 2002 @ 01:15:
het probleem is dat je niet iedere string in een int of een long kan plaatsen, dus jouw aanpak gaat niet werken.

nee. tenzij je flink rommelt

Wat je wel zou kunnen doen is bij een string dan een array van longs kunnen plaatsen voor het extra snelle checkwerk. Maar volgens mij gaat je dus ook wel een stukje performance kosten.

Ja precies. Ik moet dan ook logaritmen nemen enzo. is vast niet snel.

Waarom moet het eigelijk snel zijn?

Hoeft niet, alleen ik vond het zo dom om per char te kijken of ze gelijk zijn maar misschien is dat toch wel de beste manier.
Bedankt voor je meedenken & tips Alarmnummer.

[Alarmnummer]

2 tips:
1) KISS
2) ga pas optimaliseren als het nodig is. De (onnodig) toegevoegde snelheid weegt meestal niet op tegen de complexiteit die ontstaat.

[Juup]

Misschien is het leuk als ik hier werkende (niet geoptimaliseerde code) neerzet.
De input is 2 strings en er komt -1, 0 of 1 uit.
als string1 < string2 komt er -1 uit,
als string1 == string2 komt er 0 uit,
als string1 > string2 komt er 1 uit.

Het heet natural sort omdat als je hiermee een heel array sorteert, het op een voor de mens natuurlijke manier gebeurt. Mensen vinden 'a2' < 'a13' maar in een gewone sort wordt de '2' met de '1' (dus 1 karakter tegelijk) en niet met het hele getal '13' vergeleken.

code:

sub NatSort($$)
{
  my $a = shift;
  my $b = shift;
  my $offset = -1;
  for (my $i = 1; $i <= length($a); $i++)
  {
    unless (substr($a, 0, $i) eq substr($b, 0, $i))
    {
      $offset = $i - 1;
      last;
    }
  }
  if ($offset == -1)
  {
    return 0;
  }
  else
  {
    if (substr($a, $offset) =~ m/^ *([0-9]+)/)
    {
      my $numbera = $1;
      if (substr($b, $offset) =~ m/^ *([0-9]+)/)
      {
        my $numberb = $1;
        return $numbera <=> $numberb;
      }
      else
      {
        return $a cmp $b;
      }
    }
    else
    {
      return $a cmp $b;
    }
  }
}

print NatSort('a2', 'a13');

Dit resulteert in -1 want 2 < 13.

[Verwijderd]

Gewoon KISS, zoals Alarmnummer 't zegt. Je kan op elke manier zoeken, maar als je wilt weten tot welke nummer ze gelijk zijn, zul je altijd de eerste char ook moet checken. Ergens middenin beginnen wertkg ewoon niet.

Voorbeeld:
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
Als ik nu halverwege begin, dan moet ik helemaal terug om uit te vinden dat er 0 chars gelijk zijn.
En van string naar int gaan lijkt me ook nogal hopeloos. Hash-codes levert alleen maar meer overhead, denk ik. Simpelweg chars vergelijken lijkt me 't snelst en simpelst hier.

[Verwijderd]

leuk topic k ben hier zelf ook een poosje met aan t kloten geweest en een echt ideale oplossing had ik toentertijd niet gevonden, want stel nou dat je het volgende hebt:

code:

string1 = aafghijzzz
string2 = aazzfghijz

zoals je ziet, 2 strings die niet gelijk zijn. Het letter voor letter gaan vergelijken:

code:

aafghijzzz
aazzfghijz
11000001 (1 = match, 0 = geen match)

zou de uitkomst aangeven dat t twee flink van elkaar verschillende strings zijn, terwijl sommige stukken in de strings wel met elkaar overeenkomen.

u snapt t probleem?
ik zal s kijken of ik de code die ik toen s verzonnen heb, nog ergens heb liggen

[Alarmnummer]

Hashcode`s is alleen handig als je snel wil checken of je gelijke strings hebt. Maar dit is alleen handig als je een string meerdere keren moet vergelijken omdat de 1e keer een hashcode wel wat overhead kost (daarna wordt ie gecached).

En verder kan zo`n lange int waarin dus meerdere chars in 1 slag gecontroleerd kunnen worden, wel een performance winst, als je veel strings hebt (en dus veel strings die pas na een x aantal chars verschillen).

En nog even over het halverwege kijken.
Als je een kilometerteller hebt, dan heeft het geen nut om het meter wiel te gaan vergelijken omdat dit niets zegt over de wielen voor hem (decameter,hectometer,kilometer)

[Verwijderd]

als je string geimplementeerd is als array dan hoef je toch geen strings door midden te knippen?

Want dan zal je binary search versie O(log n) (met n de lengte van de string) zijn in worst-case. Dat wordt overigens bereikt wanneer de twee strings gelijk zijn of wanneer de eerste karakter al niet matcht.
Als je wel gaat knippen, dan is het afhankelijk van wat je onder knippen verstaat of er een pointer verandert wordt of een gedeelten van een string gekopiert. In het laatste geval zal je dan toch minstens in worst-case een algoritme hebben in de orde van de lengte van de string (als n de lengte van de string is moet je n/2 karakters kopieren).

Verder hangt het ook nog af van hoe de lengte van de string bepaald wordt. Als je dat 'in' je algorithme doet door zoals in c je string af te lopen naar een termination character, dan heb je alsnog een algorithme in de orde van de lengte van de string.

In worst-case is je binary search algoritme dus efficienter. Maar een recht-toe-recht-aan algoritme kan nog best eens (verwacht) efficienter zijn als de strings een kleine maximum lengte hebben of de strings over het algemeen al snel of juist laat verschillen vertonen.

Interessanter algoritme is het bekijken of een string substring is van een andere string. Een simpele implementatie met een loopje en elke keer strings vergelijken levert een O(n*m) algoritme (met n en m de lengten van de betrokken strings). Slimmere implementaties kunnen dat in O(n+m).

[Crazy D]

Verwijderd schreef op 16 augustus 2002 @ 09:55:
zoals je ziet, 2 strings die niet gelijk zijn. Het letter voor letter gaan vergelijken:

code:

aafghijzzz
aazzfghijz
11000001 (1 = match, 0 = geen match)

zou de uitkomst aangeven dat t twee flink van elkaar verschillende strings zijn, terwijl sommige stukken in de strings wel met elkaar overeenkomen.

Dat maakt voor sorteren toch niet uit?
aafghijzzz en aazzfghijz "horen" in die volgorde omdat aa gelijk is, en de f die daarna komt is kleiner dan de z. Dus hoort ie ervoor te staan.

[Verwijderd]

Ik las overigens dat je een natural sort wilt doen op een stapel strings?
Dat kan je doen met radix sort i.c.m. stable bucket sort in O(n*m) met m de maximum lengte van de strings en n het aantal strings.

Met jouw huidige aanpak+binary search voor het zoeken op de plaats waarin de strings verschillen, doe je dat in O(n * log(n) * log(m)).
Of met die andere aanpak in O(n*m*log(n)).

Overigens, twee willekeurige strings (geimplemeneerd door een array) vergelijking heeft als ondergrens in de orde van de lengte van de string. Omdat kanstechnisch ieder karakter verschillend kan zijn, moet je minstens alle karakters bekeken hebben. Een logaritmisch algoritme zal dus karakters overslaan en daarom voor een bepaalde input incorrect werken.

[ Voor 0% gewijzigd door Verwijderd op 16-08-2002 19:32 . Reden: tja... ]