Solved

Accessing directory or file very fast

Posted on 2004-09-29
21
215 Views
Last Modified: 2010-04-15
Hello All,

This question is related to C algorithm and not to any OS as such.

My structure is something like this

Typedef struct file_or_directory
{
      void    **handle;
      char       file_or_Directory_name[256];
      int       date_of_creation;
      int      date_of_modification;
      long      size_in_bytes;
      long      size_in_sector;
      byte      access_proviledges;
      byte      type_of_file;
};

I create new directories or files in my application. Now user will access for file by name and need to access it very fast. How would one do?

Forget about, how file is created? How file is accessed? And all that.

My first question is how would you access it fast?
I will ask next question after this.

Thanks,
M
0
Comment
Question by:Mamata_gd
  • 7
  • 6
  • 2
  • +3
21 Comments
 
LVL 55

Expert Comment

by:Jaime Olivares
Comment Utility
Consider this first:
The first member of struct is 'handle', besides the OS you are using, you cannot open much file handles at a time.

Its is difficult to separate OS from file manipulation because faster methods are specific OS related, I think there is not a "universal" formula to do it.
'portability' sometimes compromise 'high performance'
0
 

Author Comment

by:Mamata_gd
Comment Utility
Please forget about OS. I will have to change the question itself.

I have database of student.
typedef struct student
{
      int      student_id;
      char       name[256];
      int      age;
      char      address[1024]
      int       date_of_creation;
      int      date_of_modification;
      int      maths_marks;
      int      physic_marks;
      int      chemistry_marks;
};

If I want to access the student with id, then I should have fast access. Student Ids are not contiguous as Ids are generated by accounts dept as per their convenience, so do not think of 'array of structure'.

0
 
LVL 22

Expert Comment

by:grg99
Comment Utility
There's not much you can do to speed up opening the file for access.  Most OS's have like ONE "open me this file" call.  Very rarely is there a faster alternative.

There are some things you can do to speed up the code though:

(1)  Depending on the OS, you may be allowed to keep 10 to 1000 files open at once.   So if your user is likely to use a file more than once, leave the file open so you don't have to open it again the next time.  Saves 100% of the open time.  Do learn what the limit is on open files, it varies widely by OS and I/O library.

(2)  If you know roughly what path the user is exploring, like they're browsing thru the file system tree, it helps to pre-touch the directories on the next level down.  This loads them into the OS's disk cache, so when you do go to one of those directories, the info will tend to be already in memory.

(3)  If the files are not too large, you could have a separate thread that reads them into memory before the user has even started picking files.  That eliminates 100% of the file opening/reading delay.

0
 

Author Comment

by:Mamata_gd
Comment Utility
I repeat,

"This question is related to C algorithm and not to any OS as such"

M
0
 
LVL 55

Expert Comment

by:Jaime Olivares
Comment Utility
OK, I guess filename was not the best example.
According to your needs, you have a list of data in tabular format, which is identified by a unique_id field.
Data is fixed lenght and you want to access it randomly.
I will assume all the information will kept in memory, but will be valid for file too.

I guess one of the best method is:
Store all your data in a contiguos array, with growing functionality.
Index all data in a new array of pointers, pointing to true data, and ordered by unique_id field.
Every time you want to add an element, just add **at the end** of the main array.
In case of index, add a new index element in the proper location of array to maintain order, according to new id.
Every time you want fast access to a record, use a binary search, knowing that array is ordered by index.

Hope to be a good starting point.
Jaime.
0
 
LVL 22

Accepted Solution

by:
grg99 earned 25 total points
Comment Utility
The traditional answer is to build an index, mapping student Ids to location in the database.

The index could be a simple linear array if there arent too many entries.  With memory going for 12 cents a megabyte, it's likely any list of student ID's will fit in $5 of memory.

Now you have to lookup the id in the array.  If you have just a hundred or so students, a simple linear search will be mighty fast.  if you have more students, ytou can sort the list and do a binary search, again mighty fast for up to thousands of students.  Or you could hash the student ID's into a prime-sized hash table.  That will be even faster in most cases.



0
 

Author Comment

by:Mamata_gd
Comment Utility
Let me tell you, what exactly, I need to do. If  I add new student it will have student ID greater than last added.

Now if I want to sort the list by highest marks obtained in Physics. Later I will say, sort the list with maths marks with least to highest. Later sort with date of modification.

If this is the case, what data structure is best and how do I achieve this?

Let me know…
M
0
 
LVL 84

Assisted Solution

by:ozo
ozo earned 25 total points
Comment Utility
Build an index mapping student_id to address of the structure
0
 

Author Comment

by:Mamata_gd
Comment Utility
Ozo,

Please explain...
0
What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
LVL 22

Assisted Solution

by:NovaDenizen
NovaDenizen earned 25 total points
Comment Utility
There are several traditional data structures that help you perform your task, all in the basic category of 'map'.  They all have different performance characteristics and strengths.  You can use a binary tree, a hash table, a perfect hash table, a B-tree, a skiplist, a balanced binary tree, or use a sorted list with binary search.
0
 

Author Comment

by:Mamata_gd
Comment Utility
Say I use binary tree and added the student as per there Ids created.  

Now, somebody asks for a student who has obtained highest marks in chemistry.  
Later, somebody asks who is youngest in this school.

How do I sort the binary tree. DO I break the tree and reconstruct. How  do I go about this?

M
0
 
LVL 55

Expert Comment

by:Jaime Olivares
Comment Utility
Binary tree is not efficient for multiple-index.
Just have to make many index arrays as I have suggested.
0
 

Author Comment

by:Mamata_gd
Comment Utility
Requirement is, I should be able to be able to add and delete students. And at the same time, sort with any of the key.
0
 
LVL 55

Expert Comment

by:Jaime Olivares
Comment Utility
The add/delete operation is very frequent, then you need a linked list, but still a index array is a good idea for it.
0
 

Expert Comment

by:oxblood
Comment Utility

I'm not answering your question but rather curious on why you don't want to use an already existing DB? I too am not familiar with any algorithm for multi-indexing but it seems like any data structure that has been proposed needs to be reconstructed for every particular query unless you want to have bunch of data structures for each field open.
0
 
LVL 55

Expert Comment

by:Jaime Olivares
Comment Utility
if you **HAVE** to process in memory, then may justify, but if you want to process in file, is really unnecessary.
If you explain your motifs maybe we can help you better.
0
 

Author Comment

by:Mamata_gd
Comment Utility
Sorry I am responding to your questions bit late.

I want to build system where I can add and delete the student structure. I do not want to store or retieve these stucture into any secondary media at this moment. It is plain application, creates the sudent as unser enters data.

But I want to sort them and access these structres efficiently with the different keys. How do I do that?

Jamie, was telling to build the mapping table with help of array. But can not build this mapping table until and unless I know the number of students.


Please let me know...

0
 
LVL 55

Assisted Solution

by:Jaime Olivares
Jaime Olivares earned 25 total points
Comment Utility
>Jamie, was telling to build the mapping table with help of array. But can not build this mapping table until and unless I know the number of students
Why? you can grow index array dinamically, there are several methods, grow it one by one, a bit inefficient by low memory comsuming, or grow 10 by 10 or 100 by 100, far more efficient, and just a few memory comsuming because each index element has only 4 bytes (a pointer size)
0

Featured Post

What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

728 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

9 Experts available now in Live!

Get 1:1 Help Now