CODEWITHSUNDEEP
php
Tiago Castro
Tiago Castro

Reputation: 7

Read in text file in binary search with PHP without using ram memory

I need to make script that reads a file delimite by pipes "|" in with binary search without using memory ram. How can I do it?

I tried:

$handle = fopen("myfile.txt", "r");
if ($handle) {
    while (($line = fgets($handle)) !== false) {
       // while reads line make binary search
    }

    fclose($handle);
} else {
   // error opening the file.
}

myfile.txt

  Name|Title|Andrew|TheBook1|July|TheChest|Carol|OneTime

Upvotes: 0

Views: 430

Answers (2)

Patrick
Patrick

Reputation: 213

Since its homework, I ll give you some tips/steps, you figure out how to implement them :)

  1. The binary search algorithm divides the the search into blocks. On each step, it chops the block which contains the element into half. That's why initially it aproximates very fast.
  2. For that matter you need your data ordered alphabetically. The exercise says you have to implement a binary search without using memory. Doesn't say you can't use memory to order your data. So explode that string by "|", order it alphabetically and implode it again. There you have you ordered string.
  3. For the actual algorithm you can't use memory, so you'll have to work with the filesystem only.
  4. You need to know where the block your're searching in starts and finnishes.
  5. I don't know if you are allowed to use variables in memory. If not, you'll have to write your variables to a file as well.
  6. In that case, write functions like getBlockStart(), getBlockEnd(), setBlockStart, setBlockEnd() which read/write the values from a file.
  7. Start the algorithm with blockStart = <first element>, blockEnd = <lastELement>
  8. Chop in 2 parts and look in which part your element is based on the alphabetical order.
  9. To check out the 10th, just read 10 elements of the file. That way you reach it.
  10. Repeat until you find the element you looking for.

Upvotes: 1

Federkun
Federkun

Reputation: 36964

You can use stream_get_line to use pipelines as delimiters.

while (($name = stream_get_line($handle, 0, '|')) !== false) {
   // if ($name == 'Carol') { ...
}

Upvotes: 1

Related Questions