Page 1 of 1
Number array to range string
Posted: Sun Sep 23, 2007 8:16 pm
by pbcomm
feyd | Please use Code: Select all
and [syntax="..."] tags where appropriate when posting code. Your post has been edited to reflect how we'd like it posted. Please read: [url=http://forums.devnetwork.net/viewtopic.php?t=21171]Posting Code in the Forums[/url] to learn how to do it too.[/color]
Hello,
I have a little function that I wrote to convert an array of numbers (array(1,2,3,5,7,8,9)) to a string range (1-3,5,7-9) similar to what is used by the crontab. What i wanted is to see if anyone has a better version for this or any optimizations to my code that could be made.
Code: Select all
<?php
function array_to_range($arr) {
$result = array();
$v1 = $v2 = $arr[0];
for ($i = 1; $i < count($arr); $i++) {
if ($arr[$i] == ($v2 + 1)) {
$v2 = $arr[$i];
} else {
$result[] = ($v2 > $v1) ? $v1 . '-' . $v2 : $v2;
$v1 = $v2 = $arr[$i];
}
}
$result[] = ($v2 > $v1) ? $v1 . '-' . $v2 : $v2;
return implode(',', $result);
}
$array = array(
1,2,3,5,6,7,9
);
# prints '1-3,5-7,9'
echo array_to_range($array);
?>
feyd | Please use Code: Select all
and [syntax="..."] tags where appropriate when posting code. Your post has been edited to reflect how we'd like it posted. Please read: [url=http://forums.devnetwork.net/viewtopic.php?t=21171]Posting Code in the Forums[/url] to learn how to do it too.[/color]
Posted: Sun Sep 23, 2007 8:26 pm
by Zoxive
This belongs in Coding Critique, but anyways.
With a quick glance over, the first thing i would do is take the count() out of the Loop so it doesn't get called each pass.
And if the output is a string, then i would just use the Concatenation-Operand (.=)
Posted: Sun Sep 23, 2007 8:41 pm
by pbcomm
Hey,
Sorry about mis-posting. I'll change the count(). The output is a string, however, it's a comma separated string, i think it's easier done with implode.
Posted: Sun Sep 23, 2007 11:21 pm
by Zoxive
If you change your loop to be Less then or Equal to, you can remove the line that sets the array outside of the loop.
And the implode is slightly easier, but also slightly slower. (You asked for Optimizations : p)
All you need is 1 more line for the if statment.
Something what i would of wrote it like
Code: Select all
function array2Range(array $Array){
$Result = '';
$V1 = $V2 = $Array[0];
$Cnt = count($Array);
for($i=1;$i<=$Cnt;$i++){
if($Array[$i] === ($V2 + 1)){
$V2++; // Slightly Faster then $V2 = $Array[$i]
}else{
$Result .= $V2 > $V1? $V1 . '-' . $V2 : $V2;
if($i!==$Cnt) $Result.= ',';
$V1 = $V2 = $Array[$i];
}
}
return $Result;
}
Posted: Sun Sep 23, 2007 11:33 pm
by John Cartwright
Just so you know, both of your functions will not take into account duplicate values, nor will it work as expected without a sorted array. Try adding 2 twice into your array or values not in order and see what happens
Anyways, I'm bored.. heres is my version
Code: Select all
function array_to_range(array $array)
{
sort($array);
$chunks = array_chunk(array_unique($array), 3);
$range = array();
foreach ($chunks as $chunk) {
$range[] = min($chunk) . (count($chunk) > 1 ? '-'. max($chunk) : '');
}
return implode(', ', $range);
}
Posted: Mon Sep 24, 2007 7:42 am
by VladSun
@JCart

try with "1,2,3,5,6,7,8,10,11"
I'm writing now my solution ... will post it later.
This topic should be moved to "Coding critique"

Posted: Mon Sep 24, 2007 7:44 am
by John Cartwright
VladSun wrote:@JCart

try with "1,2,3,5,6,7,8,10,11"
I'm writing now my solution ... will post it later.
This topic should be moved to "Coding critique"

My output is 1-3, 5-7, 8-11
What's wrong with that?
EDIT | Okay I guess I misread the intention of the snipplet.
Posted: Mon Sep 24, 2007 8:38 am
by pbcomm
Thank you all.
Zoxive, your version seems to be the fastest one. Even thou this function does not get a lot of traffic, its nice to know it could be made faster.
One thing:
you can remove the line that sets the array outside of the loop
gives 2 "undefined offset notices. I think its just better t keep the line outside the loop.
JCart,
This function will always get the unique and sorted list, but it is still a good idea to have all the bases covered. Thanks.
Once again sorry for the mis-posting.
Posted: Mon Sep 24, 2007 8:44 am
by Zoxive
pbcomm wrote: gives 2 "undefined offset notices. I think its just better t keep the line outside the loop.
I was referring to
Code: Select all
$result[] = ($v2 > $v1) ? $v1 . '-' . $v2 : $v2;
If you changed your loop to <= instead of <
Sorry for not being clear.
pbcomm wrote:Once again sorry for the mis-posting.
This keeps getting brought up because one of the mods is right up there ^

Posted: Mon Sep 24, 2007 3:21 pm
by pbcomm
So i got it nailed to this, which is the fastest version with no notices.
Code: Select all
function array2range(array $array) {
$array = array_unique($array);
sort($array);
$result = '';
$start = $end = $array[0];
$count = count($array);
for ($i = 1; $i < count($array); $i++) {
if ($array[$i] == ($end + 1)) {
$end++;
} else {
$result .= ($end > $start) ? $start . '-' . $end : $end;
if ($i !== $count) $result .= ',';
$start = $end = $array[$i];
}
}
$result .= ($end > $start) ? $start . '-' . $end : $end;
return $result;
}
Posted: Mon Sep 24, 2007 3:57 pm
by Zoxive
[s]Did you read my last post?[/s]
Code: Select all
function array2Range(array $Array){
$Result = '';
$V1 = $V2 = $Array[0];
$Cnt = count($Array);
for($i=1;$i<=$Cnt;$i++){
if(isset($Array[$i]) && $Array[$i] === ($V2 + 1)){
$V2++;
}else{
$Result .= $V2 > $V1? $V1 . '-' . $V2 : $V2;
if($i!==$Cnt) $Result.= ',';
if(!isset($Array[$i])) break;
$V1 = $V2 = $Array[$i];
}
}
return $Result;
}
Posted: Mon Sep 24, 2007 4:20 pm
by pbcomm
I saw your last post, and if you turn error_reporting E_ALL you will see what notices i'am talking about.
Posted: Mon Sep 24, 2007 6:02 pm
by Zoxive
pbcomm wrote:I saw your last post, and if you turn error_reporting E_ALL you will see what notices i'am talking about.
My Bad.. i forgot at work my stupid boss has notices, so error_reporting isn't at all on default.
I fixed it with a 2 empty checks. But Doesn't matter that much, you have what you want : p
Posted: Tue Sep 25, 2007 1:46 pm
by VladSun
Here is my mighty array2ranges function
Code: Select all
<?php
$array = array(1,2,3,4,5,6,8,10,11,13,14,15,16,17,);
function array2ranges($array)
{
$result = "";
$pad_min_arr = array($array[0] - 2);
$pad_max_arr = array($array[count($array)-1] + 2);
$padded_array = array_merge($pad_min_arr, $array, $pad_max_arr);
$low = 1;
$high = count($array);
while ( ($range = binary_search($padded_array, $low, $high)) > 0)
{
$result .= ($range == $low) ? $padded_array[$low] : $padded_array[$low]."-".$padded_array[$range];
$result .= ($range == $high) ? '':',';
$low = $range + 1;
}
return $result;
}
function binary_search($array, $low, $high)
{
if( $low > $high ) // termination case
{
return -1;
}
$middle = intval( ( $low+$high )/2 ); // gets the middle of the array
if ( ($middle - $low == $array[$middle] - $array[$low]) && ($array[$middle + 1] - $array[$middle] > 1) ) // if the middle is our range
{
return $middle;
}
if ( $middle - $low < $array[$middle] - $array[$low] ) // our range is in the left sub-array
{
return binary_search( $array, $low, $middle-1 );
}
return binary_search( $array, $middle+1, $high ); // our range is in the right sub-array
}
echo array2ranges($array);
?>
It is based on binary search algorithm with modified compare function

[s]Should be much faster on bigger arrays than by using linear search.[/s]
I'm using padded array, so I don't need range checks inside my search function.
EDIT: In fact it has complexity > O(n) ... so I don't think it will be always faster
