1

I have a file with consisted of int;int values in each line. Both columns are ascending, row by row. I plan to load that file into an array with following code:

while( ! feof($f) ) {
    $line = fgets( $f, 32 );
    $tmp = explode( ";", $line );
    $elements[] = array( $tmp[0] => $tmp[1] );
}

I intend to use this array to do a binary search based on the key $tmp[0]. Array will have 1000 elements, but the search will be applied for 10.000 different values. Should I simply define a 2x1000 matrix and load elements into it?

Thx

hummingBird
  • 2,495
  • 3
  • 23
  • 43

1 Answers1

2

You can use file to get the entire contents of a file as an array of lines. Assuming that the first int in each pair is unique, you can use it as the key for the array:

foreach (file('ints.txt') as $line) {
  list($key, $value) = explode(';', $line);
  $elements[$key] = $value;
}

Looking up values by their keys in $elements will be O(n) but really close to O(1); this might be fast enough for your purposes.

Community
  • 1
  • 1
user229044
  • 232,980
  • 40
  • 330
  • 338
  • 3
    array in php are maps with access time O(1) (constant), not O(log(n)) (logarithmic, binary search) – knittl Oct 30 '10 at 14:40
  • @knittl Really! I always assumed PHP's arrays were implemented with a balanced tree. – user229044 Oct 30 '10 at 14:42
  • thx very much. they are all unique, so that won't be a problem. also, good to know about internal representation! – hummingBird Oct 30 '10 at 14:45
  • @meagar: see [how-is-the-php-array-implemented-on-the-c-level](http://stackoverflow.com/questions/2350361/how-is-the-php-array-implemented-on-the-c-level), arrays are HashTales (access time `O(1)`) – binary trees would still only provide logarithmic access time – knittl Oct 30 '10 at 14:49
  • @playcat Note that I've updated my answer: PHP arrays are associative, but lookups are O(1) not O(log(n)) as I erroneously assumed. – user229044 Oct 30 '10 at 14:51
  • thx meagar, it's noted. i tend to carefully watch for changes on / in my questions. but, would it be more efficient to use n x 2 map? – hummingBird Oct 30 '10 at 15:10