Adding a unique user name in a file

[sam]

Hi,

Is there any perl module I can use to read in a list of user names from
a file and do a binary search on the list base on the user name, if the
user name is not found, add this user name to the file?

Thanks
Sam

 

[Joe Smith]

Is there any perl module I can use to read in a list of user names from
a file and do a binary search on the list base on the user name, if the
user name is not found, add this user name to the file?

Why do a binary search? You can accomplish the same thing by
tying a hash to a file. Then use ordinary hash operations to test
for the existance of a given key. Or use
$file_based_hash_of_names{$username} = 1;
unconditionally to add it to the list.

-Joe

 

[Jürgen Exner]

Is there any perl module I can use to read in a list of user names
from a file and do a binary search on the list base on the user name,
if the user name is not found, add this user name to the file?

You don't need a module for this. It's probably 15-20 lines of code only.

Also, why do a binary search? If you read the user names into a hash then
you get an O(1) access instead of a O(log(n)) as with a binary search.

jue

 

[Josef Moellers]

You don't need a module for this. It's probably 15-20 lines of code only.

Also, why do a binary search? If you read the user names into a hash then
you get an O(1) access instead of a O(log(n)) as with a binary search.

Why the repeated reference to a hash? If I was given a user name to look
up in a file, I'd step through the file entry-by-entry. If I find the
user, I'll process his entry, close the file and be done with it. If I
didn't find him/her, I'll have reached the end of file and, given the
proper open mode, append a record for the (new) user. No hash, no fancy
legwork, just plain coding.

 

[sam]

Why the repeated reference to a hash? If I was given a user name to look
up in a file, I'd step through the file entry-by-entry. If I find the
user, I'll process his entry, close the file and be done with it. If I
didn't find him/her, I'll have reached the end of file and, given the
proper open mode, append a record for the (new) user. No hash, no fancy
legwork, just plain coding.

Right, this is for small number of users.
To deal with large number of users, one would need to load all user
records into memory when the system/server start up, and use hash/tree
to speed up the search rather than using linear search.

Sam.

 

[Josef Moellers]

Right, this is for small number of users.
To deal with large number of users, one would need to load all user
records into memory when the system/server start up, and use hash/tree
to speed up the search rather than using linear search.

You asked to "search on the list base on _the_user_name_", so I deduced
that you were having a go at the database with a single user name (e.g.
when adding a user to a system). If you need to batch-process several
user names in one go, then, obviously, a hash would be a suitable data
structure.

The size of the database would also play a role: loading a huge database
into memory would require a lot of memory (which is cheap these days),
reading one record at a time would not, so that would involve a
classical time/space-tradeoff.

The next step, then, would be to consider converting your list of user
names into a database (eg using the DBM modules) and then working on
that rather than the more unstructured list of names.

 

[Jürgen Exner]

Why the repeated reference to a hash? If I was given a user name to
look up in a file, I'd step through the file entry-by-entry. If I
find the user, I'll process his entry, close the file and be done
with it. If I didn't find him/her, I'll have reached the end of file
and, given the proper open mode, append a record for the (new) user.
No hash, no fancy legwork, just plain coding.

True! Sometimes the simplest methods are the best.
Thanks for reminding us that you have to read the file completely anyway.
Then you can just as well do the search at the same time.

jue

 

[Jürgen Exner]

sam wrote:

Is there any perl module I can use to read in a list of user names
from a file and do a binary search on the list base on the user
name, if the user name is not found, add this user name to the
file?

[Just check for the name while reading the file]

Right, this is for small number of users.
To deal with large number of users, one would need to load all user
records into memory when the system/server start up, and use hash/tree
to speed up the search rather than using linear search.

You realize that the second description is a totally different problem then
the first, do you?

jue

 

[Anno Siegel]

sam wrote:

Is there any perl module I can use to read in a list of user names
from a file and do a binary search on the list base on the user
name, if the user name is not found, add this user name to the
file?

[Just check for the name while reading the file]

Right, this is for small number of users.
To deal with large number of users, one would need to load all user
records into memory when the system/server start up, and use hash/tree
to speed up the search rather than using linear search.

You realize that the second description is a totally different problem then
the first, do you?

Well, OP didn't specify the number of *which* users is going to be small
or large. If it's a large number of users being *added*, slurping the
existing users into a hash looks reasonable. If it's adding *to* a large
base of existing users, building the hash for each new user would be a
waste of time.

The little remark about loading things into memory "when the system
starts up" seems to suggest running the process as a server. That
would indeed be an entirely different problem and open up a whole
slew of questions. I'm not going there for now.

Anno

 

[Jürgen Exner]

sam wrote:

Is there any perl module I can use to read in a list of user
names from a file and do a binary search on the list base on the
user name, if the user name is not found, add this user name to
the file?

[Just check for the name while reading the file]

Right, this is for small number of users.
To deal with large number of users, one would need to load all user
records into memory when the system/server start up, and use
hash/tree to speed up the search rather than using linear search.

You realize that the second description is a totally different
problem then the first, do you?

Well, OP didn't specify the number of *which* users is going to be
small or large. If it's a large number of users being *added*,
slurping the existing users into a hash looks reasonable.
If it's
adding *to* a large base of existing users, building the hash for
each new user would be a waste of time.

True, but I have a gut feeling this is not the culprit

The little remark about loading things into memory "when the system
starts up" seems to suggest running the process as a server. That
would indeed be an entirely different problem and open up a whole
slew of questions. I'm not going there for now.

That's what I was alluding at.

jue