Geringste Zahlendifferenz zwischen meheren Zahlenarrays?

[Hawkster]

Hallo allesamt,

bin sicher soetwas gibt es schon irgendwo, nur weiß ich net wie man das nennt. Ich möchste zwischen meheren Arrays die geringste Zahlendifferenz suchen

BSP:

$speed = array();
$speed[] = array(54898, 27454, 18306, 13732, 10988, 9158, 7851, 6871, 6109, 5499);
$speed[] = array(70144, 35077, 23388, 17543, 14037, 11699, 10029, 8777, 7803, 7023);

In dem Beispiel liegen die Zahlen 7803 und 7851 am nähesten Zusammen (glaub ich) ^^ Und nun soll er mir die jeweiligen Zahlen ausgeben, welche am nähesten zusammenliegen.
Problem ist, es müssen mehr als 2 Arrays unterstützt werden... hat jemand ne Idee wie ich das realisieren soll!?

Mit freundlichen Grüßen,
Hawkster

 

[Yaslaw]

SInd in den unterarrays immer gleich viele Einträge?

Also count($speed[0])= = count($speed[1])= = count($speed[x]) ?

 

[Hawkster]

In unserem Falle ja, muss aber nicht.

 

[Yaslaw]

egal.
Du musst alle Kombinationen finden, die differenzen innerhalb der Kombinationen erstellen und dann das minimum auswählen.

 

[Yaslaw]

Hast du die Daten nur als Array oder sindsie in einer DB?

 

[Hawkster]

Nur als Array, da es "errechnete" Zahlen sind.

 

[rd4eva]

Ich weiss zwar nicht ob es schon irgendetwas gibt aber ich hab mal schnell was hingekritzelt.
Es geht vermutlich noch wesentlich besser aber als Denkanstoss solltes es genügen.

$speed = array();
$speed[] = array(54898, 27454, 18306, 13732, 10988, 9158, 7851, 6871, 6109, 5499);
$speed[] = array(70144, 35077, 23388, 17543, 14037, 11699, 10029, 8777, 7803, 7023);  

$min = Array();
$bestMin = 0;
foreach ($speed as $key => $arr){
	foreach($arr as $val){
		for ( $i = $key+1; $i < count($speed);$i++){
			for ($j = 0; $j < count($speed[$i]);$j++){
				$curMin = $val - $speed[$i][$j];
				if ($bestMin == 0){ $bestMin = ($curMin < 0) ? $curMin*-1 : $curMin; }
				else {
					$curMin *= ($curMin < 0) ? -1 : 1;
					if ($curMin < $bestMin ){
						$bestMin = $curMin;
						$min[0] = $val;
						$min[1] = $speed[$i][$j];
					}
				}		
			}
		}
	}
}

print_r($min);
/*
Array ( [0] => 7851 [1] => 7803 ) 
*/

 

[Yaslaw]

Da SQL die Berechnung relativ einfach abnimmt, bin ich trotz fehlender Tabelle mal beim SQL-Ansatz geblieben.

#Ein Beispiel für 3 Arrays. Die Werte kann man mittels UNION zu einer Art Tabelle zusammensetzen
# $speed[] = array(123, 456, 789);
# $speed[] = array(135, 246, 543);
# $speed[] = array(196, 374, 532);
SELECT 
    v1, v2, v3,
    abs(v1-v2) + abs(v1-v3) + abs(v2-v3) AS diff    # Berechnung der Abweichung. Ev. ist eine andere Formael von nöten
FROM 
    (SELECT 123 AS v1 UNION SELECT 456 AS v1 UNION SELECT 789 AS v1) t1,
    (SELECT 135 AS v2 UNION SELECT 246 AS v2 UNION SELECT 543 AS v2) t2,
    (SELECT 196 AS v3 UNION SELECT 374 AS v3 UNION SELECT 532 AS v3) t3
ORDER BY diff

Dabei berechne ich alle differnezen zwieschen allen Kombinationen und zähle die Differenzen zusammen. Diese sortiere sie aufsteigend.
Es kann vorkommen, dass mehrere Kombinationen die gleiche Differenz aufweisen

in meinem PHP-Code mache ich nix anderes als ein solches SQL zusammenzubauen und mit der DB berechnen zu lassen

<?php 
//Connection zur DB herstellen
include_once('connect.php');

//Testdaten
$speed[] = array(54898, 27454, 18306, 13732, 10988, 9158, 7851, 6871, 6109, 5499);
$speed[] = array(70144, 35077, 23388, 17543, 14037, 11699, 10029, 8777, 7803, 7023);  

//UNION-Selects zusammenstellen
foreach($speed as $i => $set){
    array_walk($set, create_function('&$item, $key, $i', '$item = "SELECT {$item} AS v{$i}";'), $i);
    $source = implode(' UNION ', $set);
    $sources[] = "\n    ({$source}) t{$i}";
    $fields[] = "v{$i}";
}

//Formael für Differenz (diff) erstellen.
for($i = 0; $i < count($speed); $i++) {
    for($u = $i+1; $u < count($speed); $u++) {
        $diffs[] = "abs(v{$i}-v{$u})";
    }
}
$fields[] = "\n    " .implode('+', $diffs) . ' AS diff';

//Das Select zusammensetzen
$fromS = implode(",", $sources);
$fieldsS = implode(', ', $fields);
$sql = "SELECT {$fieldsS} \nFROM {$fromS} \nOrder BY diff";

//SQL ausführen
$result = mysql_query($sql);

//Es kann vorkommen, dass mehrere Kobinationen gleich gut sind
while($fields = mysql_fetch_assoc($result)){
    var_dump($fields);
    if($diff != $fields['diff']) break;
    $diff = $fields['diff'];
}
?>

Ausgabe:

array(3) {
  ["v0"]=>
  string(4) "7851"
  ["v1"]=>
  string(4) "7803"
  ["diff"]=>
  string(2) "48"
}

 

[bn]

Nette Lösung aber mit Kanonen auf Spatzen geschossen

Unter Berücksichtigung, dass nur 2 Wertereihen mit geringer Anzahl an Werten verglichen werden, schlage ich folgende Lösung vor:

<?php
  $speed    = array ();
  $speed [] = array (54898, 27454, 18306, 13732, 10988, 9158, 7851, 6871, 6109, 5499);
  $speed [] = array (70144, 35077, 23388, 17543, 14037, 11699, 10029, 8777, 7803, 7023);
  
  $valuePair = array ($speed [0][0], $speed [1][0]);
  $gap 	  = abs ($valuePair [0] - $valuePair [1]);
  
  for ($x=0; $x<count ($speed [0]); $x++)
  {
	$val1 = $speed [0][$x];
	
	for ($y=0; $y<count ($speed [1]); $y++)
	{
	  $val2  = $speed [1][$y];
	  $gap_x = abs ($val1 - $val2);
	  
	  // unter Umständen anstelle von > auch >= um das zuerst gefundene
	  // Paar nicht zu überschreiben. Grundsätzlich können nämlich
	  // mehrere Wertepaare ein identisches Gap aufweisen.
	  if ($gap_x > $gap)
		continue;
	  
	  $valuePair = array ($val1, $val2);
	  $gap 	  = $gap_x;
	}
  }
  
  echo $valuePair [0] . " - " . $valuePair [1];
  echo "\n";
?>

Sind die Wertereihen länger, lohnt sich unter Umständen die Sortierung der einzelnen Wertereihen und ein anschließender Vergleich des Gaps ohne Absolution zum vorzeitigen Ausbrechen aus der inneren oder äußeren Schleife.

EDIT:
Ich habe im Eröffnungstopic überlesen, dass mehr als 2 Wertereihen unterstützt werden müssen. Mein Ansatz ist daher nicht brauchbar.

Grüße BN

 

[Cromon]

Gem. Threadersteller müssen mehr als 2 Wertereihen unterstützt werden.