473,687 Members | 3,417 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Fastest way to look for an array of char?

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
Jul 17 '05 #1
11 2537
Simon wrote:
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').
Based on what?
I could use many strpos(...) but that does not sound very efficient.
So what would be the fastest way to get the first position?


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
Jul 17 '05 #2
> 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').

^^^^^^^^^^^^^^^ sorry that should be "return 8 (for 'r')", because i am
looking for 'P', 'r' and 'k', not 'g'.

Simon
Jul 17 '05 #3
>
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').
Based on what?


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.
I could use many strpos(...) but that does not sound very efficient.
So what would be the fastest way to get the first position?


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


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
Jul 17 '05 #4
Simon wrote:
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').


Based on what?


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.
I could use many strpos(...) but that does not sound very efficient.
So what would be the fastest way to get the first position?


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


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.


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
Jul 17 '05 #5
>
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.


$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
Jul 17 '05 #6
Simon wrote:

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.
$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.


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:
I just think that looking for the possible position of 5 chars and
returning the lowest position seems like the long way around.


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
Jul 17 '05 #7
"Simon" <sp********@myo ddweb.com> wrote in message
news:38******** *****@individua l.net...
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'


What exactly are you trying to do? I suspect regular expression is the
solution here.
Jul 17 '05 #8
>> 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'


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


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
Jul 17 '05 #9
"Simon" <sp********@myo ddweb.com> wrote in message
news:38******** *****@individua l.net...
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...
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.
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?


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]/

Jul 17 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

17
2314
by: DraguVaso | last post by:
Hi, I need to find the FASTEST way to get a string in a Loop, that goes from "a" to "ZZZZZZZZZZZZZZZZZ". So it has to go like this: a b .... z
354
15814
by: Montrose... | last post by:
After working in c# for a year, the only conclusion I can come to is that I wish I knew c. All I need is Linux, the gnu c compiler and I can do anything. Web services are just open sockets hooked up to interfaces. The Gtk is more than enough gui.
7
4542
by: bluekite2000 | last post by:
new/delete, std::allocator, pool_allocator or mt_allocator??? What r the pros and cons if each method? PS: I m designing a matrix/tensor/vector lib, all of which call base_constructor of class Array.
11
2109
by: Ignacio X. Domínguez | last post by:
Hi. I'm developing a desktop application that needs to store some data in a local file. Let's say for example that I want to have an address book with names and phone numbers in a file. I would like to be able to retrieve the name by searching for a given phone number the fastest I can. I have considered the posibility of using XmlTextReader with something like: <list> <item number="1234567"> <name>John Doe</name>
14
23226
by: mesterak | last post by:
I want to very quickly count the number of lines in text files without having to read each line and increment a counter. I am working in VB.NET and C#. Does anyone have a very fast example on how to do this? Thanks, Matt
9
6815
by: sshock | last post by:
Hi all, I want to read from a file into a vector<unsigned char>. Right now my code looks like this: FILE* f = fopen( "datafile", "rb" ); enum { SIZE = 100 }; vector<unsigned char> buf(SIZE); fread(&buf, 1, SIZE, f);
24
2287
by: ThunderMusic | last post by:
Hi, The subject says it all... I want to use a byte and use it as byte* so I can increment the pointer to iterate through it. What is the fastest way of doing so in C#? Thanks ThunderMusic
19
29248
by: Eugeny Myunster | last post by:
I know, only simple one: #include <stdio.h> int main() { int min=0,max=0,i,arr; for(i=0;i<12;i++) arr=rand()%31-10; for(i=0;i<12;i++)
0
8590
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9066
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
1
8779
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
8783
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
7617
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
6450
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
4321
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
4541
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
3
1947
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.