Number array to range string

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
pbcomm
Forum Newbie
Posts: 5
Joined: Sun Sep 23, 2007 8:05 pm

Number array to range string

Post by pbcomm »

feyd | Please use

Code: Select all

,

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

,

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]
User avatar
Zoxive
Forum Regular
Posts: 974
Joined: Fri Apr 01, 2005 4:37 pm
Location: Bay City, Michigan

Post 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 (.=)
pbcomm
Forum Newbie
Posts: 5
Joined: Sun Sep 23, 2007 8:05 pm

Post 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.
User avatar
Zoxive
Forum Regular
Posts: 974
Joined: Fri Apr 01, 2005 4:37 pm
Location: Bay City, Michigan

Post 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;
}
User avatar
John Cartwright
Site Admin
Posts: 11470
Joined: Tue Dec 23, 2003 2:10 am
Location: Toronto
Contact:

Post 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 :wink:

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);
}
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Post 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" :)
There are 10 types of people in this world, those who understand binary and those who don't
User avatar
John Cartwright
Site Admin
Posts: 11470
Joined: Tue Dec 23, 2003 2:10 am
Location: Toronto
Contact:

Post 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.
pbcomm
Forum Newbie
Posts: 5
Joined: Sun Sep 23, 2007 8:05 pm

Post 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.
User avatar
Zoxive
Forum Regular
Posts: 974
Joined: Fri Apr 01, 2005 4:37 pm
Location: Bay City, Michigan

Post 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 ^ :lol:
pbcomm
Forum Newbie
Posts: 5
Joined: Sun Sep 23, 2007 8:05 pm

Post 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;
	}
User avatar
Zoxive
Forum Regular
Posts: 974
Joined: Fri Apr 01, 2005 4:37 pm
Location: Bay City, Michigan

Post 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;
}
Last edited by Zoxive on Mon Sep 24, 2007 6:03 pm, edited 2 times in total.
pbcomm
Forum Newbie
Posts: 5
Joined: Sun Sep 23, 2007 8:05 pm

Post by pbcomm »

I saw your last post, and if you turn error_reporting E_ALL you will see what notices i'am talking about.
User avatar
Zoxive
Forum Regular
Posts: 974
Joined: Fri Apr 01, 2005 4:37 pm
Location: Bay City, Michigan

Post 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
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Post 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 :)
There are 10 types of people in this world, those who understand binary and those who don't
Post Reply