Fastest way to look for an array of char?

[Simon]

Hi,

If I have a string, (variable len), and I am looking for the first position
of one char in array starting from position 'x'

For example,

// the 'haystack'
$string = "PHP is great, php is ok";
// the needles
$char[] = 'P';
$char[] = 'r';
$char[] = 'k';

I would search the $string for the first $char starting from 3 and it would
return 7, (for 'g').

I could use many strpos(...) but that does not sound very efficient.
So what would be the fastest way to get the first position?

And, I am using PHP 4.x, not 5, (otherwise I guess I would use strpos(...)).

Many thanks in advance.

Simon

[John Bokma]

Re: Fastest way to look for an array of char?

Simon wrote:
[color=blue]
> Hi,
>
> If I have a string, (variable len), and I am looking for the first
> position of one char in array starting from position 'x'
>
> For example,
>
> // the 'haystack'
> $string = "PHP is great, php is ok";
> // the needles
> $char[] = 'P';
> $char[] = 'r';
> $char[] = 'k';
>
> I would search the $string for the first $char starting from 3 and it
> would return 7, (for 'g').[/color]

Based on what?
[color=blue]
> I could use many strpos(...) but that does not sound very efficient.
> So what would be the fastest way to get the first position?[/color]

If you mean that you want for all characters in char find the minimal
position in $string?

Hash each unique character, with it's position, e.g:

P => 0
H => 1
=> 3
i => 4
s => 5
g => 7
r => 8
e => 9
a => 10
t => 11
, => 12
p => 13
h => 14
o => 20
k => 21

(if I made no mistakes). Then you can do something like:

assign the position of the first item in char to $min
and keep the char in $firstchar;
for the next item in char up until and including the last one:
if the position of this item < $min:
$min = postion
$firstchar = item

It depends also on exactly what you want to do, it's quite possible that
doing just the n searches over the string is faster than the above hash
table stuff.


--
John MexIT: http://johnbokma.com/mexit/
personal page: http://johnbokma.com/
Experienced programmer available: http://castleamber.com/
Happy Customers: http://castleamber.com/testimonials.html

[Simon]

Re: Fastest way to look for an array of char?

> Hi,[color=blue]
>
> If I have a string, (variable len), and I am looking for the first
> position of one char in array starting from position 'x'
>
> For example,
>
> // the 'haystack'
> $string = "PHP is great, php is ok";
> // the needles
> $char[] = 'P';
> $char[] = 'r';
> $char[] = 'k';
>
> I would search the $string for the first $char starting from 3 and it
> would return 7, (for 'g').[/color]
^^^^^^^^^^^^^^^ sorry that should be "return 8 (for 'r')", because i am
looking for 'P', 'r' and 'k', not 'g'.

Simon

[Simon]

Re: Fastest way to look for an array of char?

>[color=blue][color=green]
>> Hi,
>>
>> If I have a string, (variable len), and I am looking for the first
>> position of one char in array starting from position 'x'
>>
>> For example,
>>
>> // the 'haystack'
>> $string = "PHP is great, php is ok";
>> // the needles
>> $char[] = 'P';
>> $char[] = 'r';
>> $char[] = 'k';
>>
>> I would search the $string for the first $char starting from 3 and it
>> would return 7, (for 'g').[/color]
>
> Based on what?[/color]

Sorry I made a typo, it should have been ...
"I would search the $string for the first $char starting from 3 and it would
return 8, (for 'r')."

'r' been one of the char I looking for.
[color=blue]
>[color=green]
>> I could use many strpos(...) but that does not sound very efficient.
>> So what would be the fastest way to get the first position?[/color]
>
> If you mean that you want for all characters in char find the minimal
> position in $string?
>[/color]

Sorry the typo made the whole thing unclear.
I want the fastest way to find the position of one of many characters in a
string.

Like look for the first of 'P' , 'r', 'k' in $string.

Simon

[John Bokma]

Re: Fastest way to look for an array of char?

Simon wrote:
[color=blue][color=green]
>>[color=darkred]
>>> Hi,
>>>
>>> If I have a string, (variable len), and I am looking for the first
>>> position of one char in array starting from position 'x'
>>>
>>> For example,
>>>
>>> // the 'haystack'
>>> $string = "PHP is great, php is ok";
>>> // the needles
>>> $char[] = 'P';
>>> $char[] = 'r';
>>> $char[] = 'k';
>>>
>>> I would search the $string for the first $char starting from 3 and
>>> it would return 7, (for 'g').[/color]
>>
>> Based on what?[/color]
>
> Sorry I made a typo, it should have been ...
> "I would search the $string for the first $char starting from 3 and it
> would return 8, (for 'r')."
>
> 'r' been one of the char I looking for.
>[color=green]
>>[color=darkred]
>>> I could use many strpos(...) but that does not sound very efficient.
>>> So what would be the fastest way to get the first position?[/color]
>>
>> If you mean that you want for all characters in char find the minimal
>> position in $string?
>>[/color]
>
> Sorry the typo made the whole thing unclear.
> I want the fastest way to find the position of one of many characters
> in a string.
>
> Like look for the first of 'P' , 'r', 'k' in $string.[/color]

Fastest way most likely is, just look it up.

If $char is very big, and $string very long (and some characters appear
at the very end for the first time) the hash table trick might be
faster.


--
John MexIT: http://johnbokma.com/mexit/
personal page: http://johnbokma.com/
Experienced programmer available: http://castleamber.com/
Happy Customers: http://castleamber.com/testimonials.html

[Simon]

Re: Fastest way to look for an array of char?

>[color=blue]
> Fastest way most likely is, just look it up.
>
> If $char is very big, and $string very long (and some characters appear
> at the very end for the first time) the hash table trick might be
> faster.
>
>[/color]

$char and $string are never really big, $char is up to 5 chars and $string
at most up to 1024.
I guess I am been overzealous.

I just think that looking for the possible position of 5 chars and returning
the lowest position seems like the long way around.

Simon

[John Bokma]

Re: Fastest way to look for an array of char?

Simon wrote:
[color=blue][color=green]
>>
>> Fastest way most likely is, just look it up.
>>
>> If $char is very big, and $string very long (and some characters
>> appear at the very end for the first time) the hash table trick might
>> be faster.[/color]
>
> $char and $string are never really big, $char is up to 5 chars and
> $string at most up to 1024.
> I guess I am been overzealous.[/color]

So worst case means: 5 x 1024 steps. You can speed this up by going over
the array once, and store the position of each character in a hash, e.g.

for each character in the string:
if character not in hash, use character as key
and position as value.

This means you can now almost in one step (the hash can have some
overhead) look up the position for each item in $char, and hence find
the lowest one:
[color=blue]
> I just think that looking for the possible position of 5 chars and
> returning the lowest position seems like the long way around.[/color]

See above. It depends a bit on the overhead of building the hash table,
which technically is just 1024 steps, but it's possible that doing the 5
lookups is faster.

In CS terms, building the hash is O( n ), doing each look up is O( 1 )
so in total the time is O( n ).

Doing 5 look ups in the entire string is 5 x O( n ), and hence total
time is O( n ) too.

Which one is the fastest depends on how PHP does things. Just a loop
like:

minpos = length $string; ( which is always an invalid position)
for i = 0 .. max:
find position of char[ i ]in $string;
if found, and position < minpos:
keep position
keep character

Might be more readable then the possible faster hash approach.

--
John MexIT: http://johnbokma.com/mexit/
personal page: http://johnbokma.com/
Experienced programmer available: http://castleamber.com/
Happy Customers: http://castleamber.com/testimonials.html

[Chung Leong]

Re: Fastest way to look for an array of char?

"Simon" <spambucket@myo ddweb.com> wrote in message
news:38t5q4F5tk 3riU1@individua l.net...[color=blue]
> Hi,
>
> If I have a string, (variable len), and I am looking for the first[/color]
position[color=blue]
> of one char in array starting from position 'x'[/color]

What exactly are you trying to do? I suspect regular expression is the
solution here.

[Simon]

Re: Fastest way to look for an array of char?

>> Hi,[color=blue][color=green]
>>
>> If I have a string, (variable len), and I am looking for the first[/color]
> position[color=green]
>> of one char in array starting from position 'x'[/color]
>
> What exactly are you trying to do? I suspect regular expression is the
> solution here.
>[/color]

If I wanted to find the pos of a char in a string I would use strpos(...).
But what I want to do is find one of many char in a string.

So ...
// the 'haystack'
$string = "PHP is great, php is ok";
// the needles, (the array of chars I am looking for)
$char[] = 'P';
$char[] = 'r';
$char[] = 'k'

And then I would look for the position of the first possible char in the
string...

In PHP5 you can use strpos(...) with arrays, but what about PHP4?

Speed been important I was wondering what the fastest way might be to look
for one of many char in a string.

I also suspect that RegEx might help, but I am not too good at it.
And what about if I want to start looking from position X rather than search
the whole string?

Simon

[Chung Leong]

Re: Fastest way to look for an array of char?

"Simon" <spambucket@myo ddweb.com> wrote in message
news:38vv5tF5tp sorU1@individua l.net...[color=blue]
> If I wanted to find the pos of a char in a string I would use strpos(...).
> But what I want to do is find one of many char in a string.
>
> So ...
> // the 'haystack'
> $string = "PHP is great, php is ok";
> // the needles, (the array of chars I am looking for)
> $char[] = 'P';
> $char[] = 'r';
> $char[] = 'k'
>
> And then I would look for the position of the first possible char in the
> string...[/color]

Surely you'll use the index some where down the line to extract a sub-string
from the text? An index to a string really doesn't have much other use other
than that.
[color=blue]
> I also suspect that RegEx might help, but I am not too good at it.
> And what about if I want to start looking from position X rather than[/color]
search[color=blue]
> the whole string?[/color]

You can obtain the index of the match by passing the PREG_OFFSET_CAP TURE
flag. To start from a particular position, just specify in the pattern that
the match should have any least x number of any character first:

/(?<=.{8})[Prk]/

[Simon]

Re: Fastest way to look for an array of char?

>>[color=blue][color=green]
>> And then I would look for the position of the first possible char in the
>> string...[/color]
>
> Surely you'll use the index some where down the line to extract a
> sub-string
> from the text? An index to a string really doesn't have much other use
> other
> than that.[/color]

Yes, but I use the string for editing the actual string.
So knowing the position of the char is more useful than the string.

But getting PREG_OFFSET_CAP TURE might give me the best of both worlds.
[color=blue]
>[color=green]
>> I also suspect that RegEx might help, but I am not too good at it.
>> And what about if I want to start looking from position X rather than[/color]
> search[color=green]
>> the whole string?[/color]
>
> You can obtain the index of the match by passing the PREG_OFFSET_CAP TURE
> flag. To start from a particular position, just specify in the pattern
> that
> the match should have any least x number of any character first:
>
> /(?<=.{8})[Prk]/[/color]

sorry i am not sure i follow,

Are you saying that i should do.

preg_match( " /(?<=.{8})[Prk]/", $string, $match, PREG_OFFSET_CAP TURE );

Does "(?<=.{8}") mark the starting posision 8? and [Prk] mean any one char
what if one of the char is a special char like "[" or "{" and so on.

Simon

[Chung Leong]

Re: Fastest way to look for an array of char?


"Simon" <spambucket@myo ddweb.com> wrote in message
news:393rlqF5u0 dupU1@individua l.net...[color=blue][color=green][color=darkred]
> >>
> >> And then I would look for the position of the first possible char in[/color][/color][/color]
the[color=blue][color=green][color=darkred]
> >> string...[/color]
> >
> > Surely you'll use the index some where down the line to extract a
> > sub-string
> > from the text? An index to a string really doesn't have much other use
> > other
> > than that.[/color]
>
> Yes, but I use the string for editing the actual string.
> So knowing the position of the char is more useful than the string.
>
> But getting PREG_OFFSET_CAP TURE might give me the best of both worlds.
>[color=green]
> >[color=darkred]
> >> I also suspect that RegEx might help, but I am not too good at it.
> >> And what about if I want to start looking from position X rather than[/color]
> > search[color=darkred]
> >> the whole string?[/color]
> >
> > You can obtain the index of the match by passing the PREG_OFFSET_CAP TURE
> > flag. To start from a particular position, just specify in the pattern
> > that
> > the match should have any least x number of any character first:
> >
> > /(?<=.{8})[Prk]/[/color]
>
> sorry i am not sure i follow,
>
> Are you saying that i should do.
>
> preg_match( " /(?<=.{8})[Prk]/", $string, $match, PREG_OFFSET_CAP TURE );
>
> Does "(?<=.{8}") mark the starting posision 8? and [Prk] mean any one char
> what if one of the char is a special char like "[" or "{" and so on.[/color]

(?<= ) means a lookbehind assertion, meaning a condition that needs to be
fulfilled previously. In this case we have a condition of .{8}. The dot
means any character. {8} means exactly 8 characters.