|
|
 | Hurtigste måde at finde ud af om en
Fra : Morten |
Dato : 22-04-02 20:05 |
|
Hej. Sidder og spekulerer over hvordan man hurtigst finder
ud af, om en streng består af ASCII tegn.
Naivt forslag:
String eval = ...
for(int i=0; i<eval.length(); i++) {
char c = eval.charAt(i);
if(c > 'Z' || c < 'a') {
throw new Exception("...");
}
}
Den kan selvf. pudses lidt af med checks i området ]z;A[,
men det er ikke lige det jeg tænker på. Kan man ikke lave
noget smart med bit operationer der tester strengen frem
for at skulle iterere over den og teste hver enkelt karakter?
Morten
| |
 Brian Matzon (22-04-2002)
| Kommentar
Fra : Brian Matzon |
Dato : 22-04-02 21:52 |
|
"Morten" <morten@kikobu.com> wrote in message news:3CC45EC9.8010002@kikobu.com...
>
> Hej. Sidder og spekulerer over hvordan man hurtigst finder
> ud af, om en streng består af ASCII tegn.
>
> Naivt forslag:
>
> String eval = ...
>
> for(int i=0; i<eval.length(); i++) {
>
> char c = eval.charAt(i);
>
> if(c > 'Z' || c < 'a') {
> throw new Exception("...");
> }
> }
Hvad er der nu galt med æøå ?
eller tænker du kun på 7 bit ascii?
Men nej, jeg kender ikke nogen god måde...
men i sidste ende vil en switch så ikke være bedre
performance mæssigt (pis at kode - fylder af H til)?
/Brian Matzon
| |
Morten (23-04-2002)
| Kommentar
Fra : Morten |
Dato : 23-04-02 08:45 |
|
Brian Matzon wrote:
> "Morten" <morten@kikobu.com> wrote in message news:3CC45EC9.8010002@kikobu.com...
>
>>Hej. Sidder og spekulerer over hvordan man hurtigst finder
>>ud af, om en streng består af ASCII tegn.
>>
>>Naivt forslag:
>>
>>String eval = ...
>>
>>for(int i=0; i<eval.length(); i++) {
>>
>> char c = eval.charAt(i);
>>
>> if(c > 'Z' || c < 'a') {
>> throw new Exception("...");
>> }
>>}
>
> Hvad er der nu galt med æøå ?
> eller tænker du kun på 7 bit ascii?
Ikke nødvendigvis.. Jeg har brugt lidt tid på at se på sourcen
til java.lang.Character - isLetter, det ser spændende ud, men
jeg undrede mig over om man kunne validere en hel streng frem
for eet tegn af gangen.
> Men nej, jeg kender ikke nogen god måde...
> men i sidste ende vil en switch så ikke være bedre
> performance mæssigt (pis at kode - fylder af H til)?
Jeg ved ikke hvordan en switch er implementeret, men det er vel
O(n) (n er antal cases) sammenligninger, hvor ovenstående eksempel
er O(1). Dertil kommer strengens længde.
Jeg prøver at forhøre mig i en comp.text gruppe :)
Mvh Morten
| |
Bertel Lund Hansen (23-04-2002)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 23-04-02 09:35 |
|
Brian Matzon skrev:
>Men nej, jeg kender ikke nogen god måde...
>men i sidste ende vil en switch så ikke være bedre
>performance mæssigt (pis at kode - fylder af H til)?
Det er mere overskueligt at lave det sådan her:
String alfabet =
"aábcdeéëfghiíïjklmnoópqrstuúvwxyýüzæäøöåAÁBCDEÉËFGHIÍÏJKLMNOÓPQRSTUÚVWXYÝÜZÆÄØÖÅ";
....
if (alfabet.indexOf(ch)>-1) { succes! }
Den metode bruger jeg ofte, bl.a. fordi det er let at vælge de
tegn der skal med. Man kan også bruge rækkefølgen i en
sorteringsalgoritme.
--
Bertel
http://lundhansen.dk/bertel/ FIDUSO: http://fiduso.dk/
| |
 Dennis Thrysøe (23-04-2002)
| Kommentar
Fra : Dennis Thrysøe |
Dato : 23-04-02 10:15 |
|
Men den metode er så lidt mere tidskompleks end større end/mindre end.
-dennis
Bertel Lund Hansen wrote:
> Brian Matzon skrev:
>
>
>>Men nej, jeg kender ikke nogen god måde...
>>men i sidste ende vil en switch så ikke være bedre
>>performance mæssigt (pis at kode - fylder af H til)?
>
>
> Det er mere overskueligt at lave det sådan her:
>
> String alfabet =
> "aábcdeéëfghiíïjklmnoópqrstuúvwxyýüzæäøöåAÁBCDEÉËFGHIÍÏJKLMNOÓPQRSTUÚVWXYÝÜZÆÄØÖÅ";
>
> ...
> if (alfabet.indexOf(ch)>-1) { succes! }
>
> Den metode bruger jeg ofte, bl.a. fordi det er let at vælge de
> tegn der skal med. Man kan også bruge rækkefølgen i en
> sorteringsalgoritme.
| |
Bertel Lund Hansen (23-04-2002)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 23-04-02 11:23 |
|
Dennis Thrysøe skrev:
>Men den metode er så lidt mere tidskompleks end større end/mindre end.
Nej, faktisk ikke. Den tager måske lidt længere tid, men det er
noget andet. Og større/mindre skal jo laves i flere omgange for
at få alle mulighederne med, så jeg er ikke sikker på hvad der er
hurtigst. Og min metode er fleksibel.
Tidskompleksiteten af begge metoder er O(1) (husk at
O(1)*<konstant> stadig er O(1)).
--
Bertel
http://lundhansen.dk/bertel/ FIDUSO: http://fiduso.dk/
| |
Dennis Thrysøe (23-04-2002)
| Kommentar
Fra : Dennis Thrysøe |
Dato : 23-04-02 13:20 |
|
To iterationer inden i hinanden er vel O(n i anden) og en iteration O(n)?
(Her antager jeg, at String.indexOf() er implementeret som et gennemløb).
-dennis
Bertel Lund Hansen wrote:
> Dennis Thrysøe skrev:
>
>
>>Men den metode er så lidt mere tidskompleks end større end/mindre end.
>
>
> Nej, faktisk ikke. Den tager måske lidt længere tid, men det er
> noget andet. Og større/mindre skal jo laves i flere omgange for
> at få alle mulighederne med, så jeg er ikke sikker på hvad der er
> hurtigst. Og min metode er fleksibel.
>
> Tidskompleksiteten af begge metoder er O(1) (husk at
> O(1)*<konstant> stadig er O(1)).
>
| |
Bertel Lund Hansen (23-04-2002)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 23-04-02 15:36 |
|
Dennis Thrysøe skrev:
>To iterationer inden i hinanden er vel O(n i anden) og en iteration O(n)?
Njej. En iteration gennem et array af fast størrelse er O(1),
uanset hvor stort det er. En iteration over et array af variabel
størrelse er O(n).
Jeg glemte at der er to iteraioner indeni hinanden, men det
betyder blot at den samlede tidskompleksitet er O(n) hvor n er
længden af strengen. Det samme er tilfældet ved
større-mindre-metoden.
>(Her antager jeg, at String.indexOf() er implementeret som et gennemløb).
Ditto.
--
Bertel Læst i en debatgruppe:
Jeg fik en regning fra Telia på 180 kr, men jeg har aldrig været kunde
hos dem. Da jeg ringede og gjorde påmærksom på fejlen, sagde en meget
venlig stemme: "Vi krediterer den bare til en anden."
| |
Thorbjørn Ravn Ander~ (23-04-2002)
| Kommentar
Fra : Thorbjørn Ravn Ander~ |
Dato : 23-04-02 10:50 |
|
Bertel Lund Hansen <nospam@lundhansen.dk> writes:
> Det er mere overskueligt at lave det sådan her:
>
> String alfabet =
> "aábcdeéëfghiíïjklmnoópqrstuúvwxyýüzæäøöåAÁBCDEÉËFGHIÍÏJKLMNOÓPQRSTUÚVWXYÝÜZÆÄØÖÅ";
>
> ...
> if (alfabet.indexOf(ch)>-1) { succes! }
>
> Den metode bruger jeg ofte, bl.a. fordi det er let at vælge de
> tegn der skal med. Man kan også bruge rækkefølgen i en
> sorteringsalgoritme.
Har du overvejet hvordan du vil implementere sortering så "aa" kommer
sammen med "å"?
--
Thorbjørn Ravn Andersen
http://homepage.mac.com/ravn
| |
Bertel Lund Hansen (23-04-2002)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 23-04-02 11:20 |
|
Thorbjørn Ravn Andersen skrev:
>Har du overvejet hvordan du vil implementere sortering så "aa" kommer
>sammen med "å"?
Ja, det har jeg faktisk lavet en implementation af, omend den
ikke er perfekt: Jeg opretter en buffer som en kopi af (in casu)
navnet og udskifter alle forekomster af "aa" med å. Man kan så
sætte et flag for at huske at det var "aa" som skal alfabetiseres
efter "å". Det har jeg dog ikke lavet i min implementation.
Det giver fejl ved f.eks. "kraal", men den slags kan vel kun
fanges ved at man laver en ordliste med undtagelser? Det har jeg
ikke gjort i mit program fordi det kun håndterer personnavne.
--
Bertel
http://lundhansen.dk/bertel/ FIDUSO: http://fiduso.dk/
| |
Thorbjørn Ravn Ander~ (23-04-2002)
| Kommentar
Fra : Thorbjørn Ravn Ander~ |
Dato : 23-04-02 12:18 |
|
Bertel Lund Hansen <nospam@lundhansen.dk> writes:
> >Har du overvejet hvordan du vil implementere sortering så "aa" kommer
> >sammen med "å"?
>
> Ja, det har jeg faktisk lavet en implementation af, omend den
> ikke er perfekt: Jeg opretter en buffer som en kopi af (in casu)
> navnet og udskifter alle forekomster af "aa" med å. Man kan så
> sætte et flag for at huske at det var "aa" som skal alfabetiseres
> efter "å". Det har jeg dog ikke lavet i min implementation.
Så er det godt Sun har.
http://java.sun.com/docs/books/tutorial/i18n/text/locale.html
> Det giver fejl ved f.eks. "kraal", men den slags kan vel kun
> fanges ved at man laver en ordliste med undtagelser? Det har jeg
> ikke gjort i mit program fordi det kun håndterer personnavne.
Så vidt vides, ja.
--
Thorbjørn Ravn Andersen
http://homepage.mac.com/ravn
| |
Bertel Lund Hansen (23-04-2002)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 23-04-02 15:38 |
|
Thorbjørn Ravn Andersen skrev:
>> >Har du overvejet hvordan du vil implementere sortering så "aa" kommer
>> >sammen med "å"?
>> ...
>Så er det godt Sun har.
Glimrende. Min implementation er desværre bare i C.
--
Bertel Læst i en debatgruppe:
Jeg fik en regning fra Telia på 180 kr, men jeg har aldrig været kunde
hos dem. Da jeg ringede og gjorde påmærksom på fejlen, sagde en meget
venlig stemme: "Vi krediterer den bare til en anden."
| |
Thorbjørn Ravn Ander~ (23-04-2002)
| Kommentar
Fra : Thorbjørn Ravn Ander~ |
Dato : 23-04-02 15:55 |
|
Bertel Lund Hansen <nospam@lundhansen.dk> writes:
> >> >Har du overvejet hvordan du vil implementere sortering så "aa" kommer
> >> >sammen med "å"?
>
> >> ...
>
> >Så er det godt Sun har.
>
> Glimrende. Min implementation er desværre bare i C.
Overvej at reimplementere det i det sprog denne gruppe omhandler.
--
Thorbjørn Ravn Andersen
http://homepage.mac.com/ravn
| |
Christian Holm (26-04-2002)
| Kommentar
Fra : Christian Holm |
Dato : 26-04-02 12:18 |
|
"Morten" <morten@kikobu.com> wrote in message
news:3CC45EC9.8010002@kikobu.com...
>
> Hej. Sidder og spekulerer over hvordan man hurtigst finder
> ud af, om en streng består af ASCII tegn.
Med 1.4 kan du bruge:
import java.util.regex.*;
....
Pattern p = Pattern.compile("[^a-zA-Z]");
Matcher m = p.matcher(....input...);
if (m.find())
{
throw new ....
}
Christian Holm
| |
|
|