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

Question

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

read with generators (yield), see here. Yielding lines have a low memory footprint. — Xorifelse
– Xorifelse, Commented Nov 12, 2016 at 17:50
@Xorifelse, how yield can be useful here? The $line is overwritten in each iteration. — Ruslan Osmanov
– Ruslan Osmanov, Commented Nov 12, 2016 at 17:53
What do you mean by a binary search. What are you searching. Are you searching within the line read or the whole file? — RiggsFolly
– RiggsFolly, Commented Nov 12, 2016 at 17:54
What kind of strange use case is this? Homework? Why not simply explode by "|" and search? The binary search requires the imput to be ordered, so you ll have to load it into memory anyway to order it... — Patrick
– Patrick, Commented Nov 12, 2016 at 17:58
@Patrick its for homework. I need to make it without using memory ram, I cant figure out an way to do this. — Tiago Castro
– Tiago Castro, Commented Nov 12, 2016 at 18:01

Patrick · Accepted Answer · 2016-11-12 18:24:50Z

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

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.
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.
For the actual algorithm you can't use memory, so you'll have to work with the filesystem only.
You need to know where the block your're searching in starts and finnishes.
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.
In that case, write functions like getBlockStart(), getBlockEnd(), setBlockStart, setBlockEnd() which read/write the values from a file.
Start the algorithm with blockStart = <first element>, blockEnd = <lastELement>
Chop in 2 parts and look in which part your element is based on the alphabetical order.
To check out the 10th, just read 10 elements of the file. That way you reach it.
Repeat until you find the element you looking for.

Federkun · Accepted Answer · 2016-11-12 18:00:51Z

1

You can use stream_get_line to use pipelines as delimiters.

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

answered Nov 12, 2016 at 18:00

Federkun

37.2k8 gold badges82 silver badges93 bronze badges

1 Comment

Tiago Castro Over a year ago

But I still need to use the binary search algorithm

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related