parallele

[bleicher]

Grüße,
ich zerbreche mir den kopf weiter, vllt kann mir aber jemand der mehr Ahnung hat ein Rat geben^^

problem - gegeben sind N bereiche - als array
definiert durch zahlen - sagen wir 701-905, 805-1125, 124-2000 etc
gesucht ist die maximale anzahl der nebeneinander existierenden bereiche

versuch war für jeden element den array durchzulaufen, und falls element I den aktuellen überlappt zähler erhöhen, das scheitert aber brutal an einem langen bereich, nebene dem mehrere kleinere vorliegen

=  ==  ====

• de facto sind es max 2 parallel, der ansatz liefert aber 4 parallele, was kann man noch machen?
  MFG
  bleicher

[Encoder]

Tut mir leid, aber ich hab nicht so wirklich den Plan von was du da redest.
Wann ist ein Bereich parallel?
Beschreibs mal etwas ausführlicher, deine Sätze krieg ich grad nicht so ganz zusammen wie du es wahrscheinlich möchtest.

[bleicher]

Grüße,
gegeben sind viele Zahlenpaare, jedes Zahlenpaar definiert einen geschlossenen Bereich auf dem Zahlenstrahl
gefragt ist die für jeden bereich maximale anzahl an sich überlappenden beriechen

oder stell es dir wie fernsehesendungen vor - du hast einige kanäle und eine liste mit sendungen und dazugehörigen sendezeiten, dich interessiert für jede sendung, wie viele videorekorder du brauchst um nix zu verspassen^^

beispielanordnung:

zeit->

10---12    14----16   17---18
   11---13            17-----------20
                           18---19
     ^-hier 2            auch hier jeweils 2

MFG
bleicher

[Otto]

Hi bleicher,

beispielanordnung:

zeit->

10---12    14----16   17---18
   11---13            17-----------20
                           18---19
     ^-hier 2            auch hier jeweils 2

MFG
bleicher

Wenn du zwei Zeit-Objekte vergleichst dann muss doch gelten.
   b.start() >= a.start()
&& b.start() <  a.ende()

Hoffe ich mach jetzt keinen Gedankenfehler.

MfG
Otto

[bleicher]

Grüße,
das ist was ich habe, und das ist nicht ausreichend (das problem ist im urpost beschrieben)

  
  
for(i=0;i<termine.length;i++){  
parallele=1;  
//von und bis gehören zum termin[i] ("aktuelles" der äußeren schleife)  
  
for(q=0;q<termine.length;q++){  
					sta=// start des termin[q]  
					sto=// ende des termins[q]  
					  
					if(i!=q && ((sta>=von && sta<bis) || (sto>von && sto<=bis)|| (sta<von && sto>bis))){  
						parallele++;  
					}  
				}  

MFG
bleicher

[Encoder]

Ein paar Gedanken dazu

Für die Anzahl der Überlappungen stell ich mir das so wie in deinem Beispiel  vor, wie jeder Zahlenbereich auf dem Zahlenstrahl liegt und man zählt für jede Zahl auf dem Strahl, wie viele Bereiche zu ihr gehören.
Dazu würde es helfen, wenn du die Bereiche nach der Startzahl sortierst. Dann gehst du alle Zahlen auf dem Strahl durch (also ne Schleife mit i++) und zählst alle Bereiche die

• an der aktuellen Zahl anfangen
• vorher schon angefangen haben und immer noch gültig sind
  Ein Bereich aus der Liste "vorher schon angefangen" wird gelöscht, wenn er die aktuelle Zahl nicht mehr enthält. Ein gerade begonnener Bereich kommt in die Liste. Das dürfte die Anzahl der Suchvorgänge ziemlich niedrig halten.

Optimierungen:
Wenn du in der Schleife feststellst dass zum aktuellen i kein Bereich mehr passt, kannst du bei der Startzahl des nächsten Bereichs in der sortierten Liste weitermachen.

Vielleicht bringt dich das schon mal gedanklich weiter.

[bleicher]

Grüße,

1. das problem 1 langer, mehrere kleinere nacheinander" bleibt
2. ich habe leider mit 4stelligen zahlen zu tun - die ienzeln durchzugehen ist mir bisshen unoptimal^^

ich brech mir den kopf über eine rekursive betrahctung - denn -

kein bereich kann mehr parallele haben, als max unter seinen parallelen ereignisse

MFG
bleicher

[Encoder]

1. das problem 1 langer, mehrere kleinere nacheinander" bleibt

So wie ich das dachte aber nicht. Du hast dann für jede Zahl im Bereich nur jeweils den Zähler "zwei".

2. ich habe leider mit 4stelligen zahlen zu tun - die ienzeln durchzugehen ist mir bisshen unoptimal^^

Vierstellige Zahlen in einer Schleife sind ja noch nicht so das Performanceproblem.
Du könntest evtl. noch optimieren, wenn du von den aktuell betrachteten Bereichen (also die in der Liste von der ich spreche) nicht die Zahlen einzeln durchgehst, sondern gleich bis dahin, wo alle Bereiche noch gelten. Sprich bis zur kleinsten Endezahl der Bereiche
also

3-----6
  2---------7
1-------------8
    3-----------9

du bist bei 3, dann stellst du fest dass hier zwei Bereiche anfangen und die aktuellen vier Bereiche bis zu 6 gleich sind. Dann brauchst du nicht mehr bis 6 hochzählen und kannst direkt da hin springen.
Das lohnt sich bei relativ wenigen, dafür aber großen Bereichen.

[Sven Rautenberg]

Moin!

Vierstellige Zahlen in einer Schleife sind ja noch nicht so das Performanceproblem.
Du könntest evtl. noch optimieren, wenn du von den aktuell betrachteten Bereichen (also die in der Liste von der ich spreche) nicht die Zahlen einzeln durchgehst, sondern gleich bis dahin, wo alle Bereiche noch gelten. Sprich bis zur kleinsten Endezahl der Bereiche

Es ist relativ einfach:

Alle Zahlenwerte, also Start wie Endwerte, werden aufsteigend sortiert. Startwerte werden mit "+1" gezählt, Endwerte mit "-1". Jetzt geht man nacheinander alle sortierten Werte durch, addiert den Wert (Start/Ende) und ermittelt das Maximum.

Randbedingung: Das Minimum darf nicht kleiner als 0 werden, am Ende muss 0 wieder genau erreicht werden, und das Maximum kann nicht größer als die Gesamtzahl aller Bereiche sein.

Sicherlich kann man das ganze auch noch grafischer lösen, indem man sich einen Baum erstellt und dessen Tiefe ermittelt.

- Sven Rautenberg

[bleicher]

Grüße,| Moin!

Alle Zahlenwerte, also Start wie Endwerte, werden aufsteigend sortiert. Startwerte werden mit "+1" gezählt, Endwerte mit "-1". Jetzt geht man nacheinander alle sortierten Werte durch, addiert den Wert (Start/Ende) und ermittelt das Maximum.

wie soll ich das mit einem array an Objekten die Eigenschaften von/bis haben anstellen?
MFG
bleicher

[Gunnar Bittersmann]

@@bleicher:

nuqneH

Alle Zahlenwerte, also Start wie Endwerte, werden aufsteigend sortiert. Startwerte werden mit "+1" gezählt, Endwerte mit "-1". Jetzt geht man nacheinander alle sortierten Werte durch, addiert den Wert (Start/Ende) und ermittelt das Maximum.

wie soll ich das mit einem array an Objekten die Eigenschaften von/bis haben anstellen?

Wo genau hapert’s denn?

In JavaScript könnte das so aussehen: Array aus Objekten mit 'von'- und 'bis'-Eigenschaften mit deinen Beispielwerten:

var bereiche = [  
	{von: 10, bis: 12},  
	{von: 11, bis: 13},  
	{von: 14, bis: 16},  
	{von: 17, bis: 18},  
	{von: 17, bis: 20},  
	{von: 18, bis: 19}  
];

Daraus http://de.selfhtml.org/javascript/objekte/array.htm#push@title=erstellst du ein Array von Bereichsgrenzen. Da du dir auch merken musst, ob die jeweilige Bereichsgrenze Anfangs- odr Endwert ist, sind die Einträge des Arrays auch wieder Arrays aus dem Wert und dem Typen (zur Vereinfachung des späteren Rechnens 1 für Anfangswert, -1 für Endwert):

var bereichsgrenzen = [];  
  
for (var i = 0; i < bereiche.length; i++) bereichsgrenzen.push([bereiche[i].von, 1], [bereiche[i].bis, -1]);

Das Array wird nun http://de.selfhtml.org/javascript/objekte/array.htm#sort@title=sortiert. Dazu brauchst du eine Vergleichsfunktion für die Werte (d.h. die nullten Elemente der Unterarrays), analog zum Beispiel in SELFHTML wäre das 'return a[0] - b[0];'.

Das berücksichtigt aber nicht, dass du bei Gleichheit der Werte (bei deinen Beispielwerten die 18) erst die Endwerte, dann die Startwerte haben willst. (Willst du doch, oder?) Bei Gleichheit der Werte musst du auch noch die Typen (d.h. die ersten Elemente der Unterarrays) vergleichen:

bereichsgrenzen.sort(function (a, b) { return a[0] - b[0] ? a[0] - b[0] : a[1] - b[1]; });

(Willst du erst die Startwerte, dann die Endwerte, hieße es hinten 'b[1] - a[1]'.)

Jetzt gehst du das geordnete Array durch und inkrementierst einen Zähler bei einem Startwert und dekrementierst bei einem Endwert, d.h. du addierst den Wert des jeweiligen ersten Elements der Unterarrays (welches ja den Wert 1 bzw. -1 hat), und merkst dir dabei den Maximalwert dieses Zählers:

var maxOpen = 0;  
  
for (var i = 0, currentOpen = 0; i < bereichsgrenzen.length; i++)  
{  
	currentOpen += bereichsgrenzen[i][1];  
	maxOpen = Math.max(maxOpen, currentOpen);  
}  
  
alert(maxOpen);

Qapla'

[bleicher]

Grüße,

danke - ich habs ähnlich versucht aber einiges nicht bedacht :)

currentOpen += bereichsgrenzen[i][1];
maxOpen = Math.max(maxOpen, currentOpen);

ähnlich habe ich es gestern gegen 2 noch hingebogen , allerdings kam ich dann noch auf Math.abs() - denn falls die parallelen berieche neben dem aktuellen nur "enden" würde der zähler nur "runter gehen" :)
MFG
bleicher

[Gunnar Bittersmann]

@@bleicher:

nuqneH

allerdings kam ich dann noch auf Math.abs() - denn falls die parallelen berieche neben dem aktuellen nur "enden" würde der zähler nur "runter gehen" :)

Hä?? Wie meinen?

Qapla'

[bleicher]

Grüße,

Hä?? Wie meinen?

[das ist der betrachtet bereich]
[----------------]
  [--------------------]
      [-------]

so eine anordung würde mit 3 "enden" den currentOpen auf -3 bringen, sodass
maxOPen mit startwert 0 bei null bleibt?
MFG
bleicher

[Gunnar Bittersmann]

@@bleicher:

nuqneH

[das ist der betrachtet bereich]
[----------------]
  [--------------------]
      [-------]

Ah, verstehe, was du meinst.

AFAIS musst du den Bereich von Anfang an betrachten; du kannst nicht mittendrin einsteigen, da du dann nicht weißt, wie viele Dinger schon offen sind. Man kann allerdings schon am Ende des für einen interessanten Bereichs aufhören.

Die Ermittlung des Maximalwerts beginnt erst am Anfang des für einen interessanten Bereichs:

var  maxOpen = 0;  
  
for (var i = 0, currentOpen = 0; i < bereichsgrenzen.length && bereichsgrenzen[i][0] <= endeBereich; i++)  
{  
        currentOpen += bereichsgrenzen[i][1];  
        if (bereichsgrenzen[i][0] >= anfangBereich) maxOpen = Math.max(maxOpen, currentOpen);  
}  
  
alert(maxOpen);

Qapla'

[Gunnar Bittersmann]

@@bleicher:

nuqneH

10---12    14----16   17---18
   11---13            17-----------20
                           18---19
     ^-hier 2            auch hier jeweils 2

Ich hätte 3 gesagt (bei geschlossenen Intervallen im Punkt 18).

Du solltest genauer angeben, ob du geschlossene oder (halb)offene Intervalle meinst.

Qapla'