pl: Algorithmus zu einer Suchfunktion

io,

ich habe eine Liste mit Zahlenpaaren, jedes Pärchen verkörpert zwei untertägige Uhrzeiten-von/bis. Assoziiert mit jedem Paar ist ein bestimmter Wert (z.B. On, Off, 30%, 26°C, 5kW oder sowas).

Nun kommt mein Programm mit einer bestimmten Uhrzeit daher und will den dazugehörigen Wert wissen. Gibts da nicht auch irgendwas von Ratio* -- einen schlaufuchsigen blitzgescheiten Algorithmus vielleicht!?

MfG

  1. Hallo pl,

    Nun kommt mein Programm mit einer bestimmten Uhrzeit daher und will den dazugehörigen Wert wissen. Gibts da nicht auch irgendwas von Ratio* -- einen schlaufuchsigen blitzgescheiten Algorithmus vielleicht!?

    Die Suchalgorithmen sind gesicherte mathematische Erkenntnis.

    Bis demnächst
    Matthias

    --
    Dieses Forum nutzt Markdown. Im Wiki erhalten Sie Hilfe bei der Formatierung Ihrer Beiträge.
    1. Hallo Matthias Apsel,

      Die Suchalgorithmen sind gesicherte mathematische Erkenntnis.

      Die vielleicht auch, aber ich hatte grade die Sortieralgorithmen im Hinterkopf - sorry.

      Bis demnächst
      Matthias

      --
      Dieses Forum nutzt Markdown. Im Wiki erhalten Sie Hilfe bei der Formatierung Ihrer Beiträge.
      1. Hallo Matthias Apsel,

        Die Suchalgorithmen sind gesicherte mathematische Erkenntnis.

        Die vielleicht auch, aber ich hatte grade die Sortieralgorithmen im Hinterkopf - sorry.

        Jahah! Sortieren ist eine gute Idee ;)

        Denn damit ist das Prüfkriterium nur noch halb so groß.

        MfG

  2. Hallo und guten Tag,

    ich habe eine Liste mit Zahlenpaaren, jedes Pärchen verkörpert zwei untertägige Uhrzeiten-von/bis. Assoziiert mit jedem Paar ist ein bestimmter Wert (z.B. On, Off, 30%, 26°C, 5kW oder sowas).

    Nun kommt mein Programm mit einer bestimmten Uhrzeit daher und will den dazugehörigen Wert wissen. Gibts da nicht auch irgendwas von Ratio* -- einen schlaufuchsigen blitzgescheiten Algorithmus vielleicht!?

    Gibt es Überlappungen? Wie ist da zu entscheiden?

    Sonst haben wir dazu schon Lösungen im Archiv, Thema: Buchungsdatenbank Hotelzimmer. Da darf es keine Überlappungen geben, es sei denn, man betreibt eine Partnervermittlung ;-P

    Grüße
    TS

    --
    es wachse der Freifunk
    http://freifunk-oberharz.de
    1. Servus!

      Thema: [...] Hotelzimmer. Da darf es keine Überlappungen geben, es sei denn, man betreibt eine Partnervermittlung ;-P

      YMMD

      Passt zum Thema Befruchtung

      Herzliche Grüße

      Matthias Scharwies

      --
      Es gibt viel zu tun: ToDo-Liste
    2. Hallo und guten Tag,

      ich habe eine Liste mit Zahlenpaaren, jedes Pärchen verkörpert zwei untertägige Uhrzeiten-von/bis. Assoziiert mit jedem Paar ist ein bestimmter Wert (z.B. On, Off, 30%, 26°C, 5kW oder sowas).

      Nun kommt mein Programm mit einer bestimmten Uhrzeit daher und will den dazugehörigen Wert wissen. Gibts da nicht auch irgendwas von Ratio* -- einen schlaufuchsigen blitzgescheiten Algorithmus vielleicht!?

      Gibt es Überlappungen? Wie ist da zu entscheiden?

      Möglich -- Zu programmieren ist praktisch eine Schaltuhr.

      Sonst haben wir dazu schon Lösungen im Archiv, Thema: Buchungsdatenbank Hotelzimmer. Da darf es keine Überlappungen geben, es sei denn, man betreibt eine Partnervermittlung ;-P

      Bei mir gehts um Geräte ;)

      Überlappungen sind nicht dramatisch, für jedes Gerät gibt es einen Default. Für Geräte die nur den OnOff-Modus kennen ist der Default Off.

      Der Algorithmus wird also entweder einen Eintrag im Zeitplan finden oder auf den Default zurückfallen.

      MfG

      1. Hallo und guten Tag,

        Gibt es Überlappungen? Wie ist da zu entscheiden?

        Möglich -- Zu programmieren ist praktisch eine Schaltuhr.

        Und wie ist da zu entscheiden? Welcher Zustand soll gelten? Der alte oder der neue?
        Ich war ja mal aktiv in der Bühnen(beleuchtugns)technik. Da hieß es immer: "der letzte Zustand gilt". Und dann kam der Wechsel von AMX auf DMX und von DMX auf CSMA/CD und schlussendlich TCP/IP. Da musste man dann Vorherbestimmungen machen und konnte nicht mehr von Echtzeitauswertung ausgehen. Was sollte dann also gelten? Es wurde dann ein recht komplexes Expertensystem daraus, durch das niemand mehr durchstieg. Die weltgrößte Fachfirma ging portionsweise in Insolvenz und/oder wurde liquidiert.

        Also bitte erspare dir diese Entwiklung und bleib auf dem Teppich. Nenne uns deine wichtigsten Prämissen!

        Bisschen mehr Input sorgt dann vielleicht auch für brauchbaren Output.

        Grüße
        TS

        --
        es wachse der Freifunk
        http://freifunk-oberharz.de
        1. Hallo und guten Tag,

          Gibt es Überlappungen? Wie ist da zu entscheiden?

          Möglich -- Zu programmieren ist praktisch eine Schaltuhr.

          Und wie ist da zu entscheiden? Welcher Zustand soll gelten? Der alte oder der neue?

          Der Default (übersetzt heißt Default ja auch Fehlwert).

          Ich war ja mal aktiv in der Bühnen(beleuchtugns)technik. Da hieß es immer: "der letzte Zustand gilt". Und dann kam der Wechsel von AMX auf DMX und von DMX auf CSMA/CD und schlussendlich TCP/IP. Da musste man dann Vorherbestimmungen machen und konnte nicht mehr von Echtzeitauswertung ausgehen. Was sollte dann also gelten? Es wurde dann ein recht komplexes Expertensystem daraus, durch das niemand mehr durchstieg. Die weltgrößte Fachfirma ging portionsweise in Insolvenz und/oder wurde liquidiert.

          Hättet Ihr mal lieber einen Default gesetzt ;)

          Also bitte erspare dir diese Entwiklung und bleib auf dem Teppich. Nenne uns deine wichtigsten Prämissen!

          Bisschen mehr Input sorgt dann vielleicht auch für brauchbaren Output.

          Wieso? Ich hab doch die Lösung schon. Die Liste wird sortiert und damit wird die Prüfung ein einfacher Vergleich anstelle zweier Vergleiche. D.h., ein zweiter Vergleich muss nur noch einmal gemacht werden, nämlich dann wenn der erste Vergleich erfolgreich war.

          Fertig.

          1. Hallo und guten Tag,

            Gibt es Überlappungen? Wie ist da zu entscheiden?

            Möglich -- Zu programmieren ist praktisch eine Schaltuhr.

            Und wie ist da zu entscheiden? Welcher Zustand soll gelten? Der alte oder der neue?

            Der Default (übersetzt heißt Default ja auch Fehlwert).

            Ich war ja mal aktiv in der Bühnen(beleuchtugns)technik. Da hieß es immer: "der letzte Zustand gilt". Und dann kam der Wechsel von AMX auf DMX und von DMX auf CSMA/CD und schlussendlich TCP/IP. Da musste man dann Vorherbestimmungen machen und konnte nicht mehr von Echtzeitauswertung ausgehen. Was sollte dann also gelten? Es wurde dann ein recht komplexes Expertensystem daraus, durch das niemand mehr durchstieg. Die weltgrößte Fachfirma ging portionsweise in Insolvenz und/oder wurde liquidiert.

            Hättet Ihr mal lieber einen Default gesetzt ;)

            Gerade hierzu habe ich neulich auch was dazugelernt: Anhand meiner neuen Regelung für die Heizung. Wenn die Regelstrecke ausfällt wäre ein Rückfall auf den letzten Wert nämlich fatal. Im günstigsten Fall würde die Heizung off bleiben, schlimmer jedoch wäre es, wenn sie on bleiben würde.

            Genau deswegen hat der Hersteller festgelegt: Bei einem Ausfall der Regelstrecke (weder Ist- noch Sollwert verfügbar) wird die Heizung mit einem Tastverhältnis 1:3 getaktet, d.h., sie läuft effektiv auf rund 30% ihrer Gesamtleistung (PWM).

            Also bitte erspare dir diese Entwiklung und bleib auf dem Teppich. Nenne uns deine wichtigsten Prämissen!

            Bisschen mehr Input sorgt dann vielleicht auch für brauchbaren Output.

            Wieso? Ich hab doch die Lösung schon. Die Liste wird sortiert

            Noch besser: Beim Durchlaufen der Liste wird für einen gegeben Zeitpunkt nicht nach der On-Zeitangabe sondern nach der Off-Zeitangabe gesucht. Fälle:

            1. Zur gefundenen Off-Zeit gibt es eine On-Zeit => Suche beendet, es gilt der dazugehörige Wert
            2. Zur gefundenen Off-Zeit gibt es keine On-Zeit => weitersuchen bis Fall (1) erreicht wird

            Wird (1) bis zum Ende der Planliste nicht erreicht, gilt der Default.

            Hierzu muss die Planliste nicht sortiert werden.

            Ferig ;)

            1. Hallo pl

              Wie kann's denn eine off Zeit ohne eine on Zeit geben, wenn du doch eine Liste von Zeitpaaren als gegeben nimmst?

              Rolf

              1. Hallo pl

                Wie kann's denn eine off Zeit ohne eine on Zeit geben, wenn du doch eine Liste von Zeitpaaren als gegeben nimmst?

                Keine On-Zeit zur Off-Zeit gefunden heißt: Beide Zeitangaben liegen in der Zukunft.

                Wobei: On-Zeit im Sinne des Zeitplans heißt nicht dass das Gerät den Status On bekommt sondern heißt dass ein Zeit-Interval beginnt ;)

                1. Ok.

                  Schlaufuxige, blitzgescheite Algorithmen dazu gibt's sicher mengenweise, frag Donald, Robert oder Niklaus. Roberts Buch habe ich noch aus Ausbildungzeiten hier stehen, Donald und Niklaus mal irgendwann aus der Bibliothek geliehen gehabt.

                  Problem bei den dreien ist nur, dass deren Algorithmen gerne auf geringe Komplexität optimieren, aber dafür Sockelaufwand mitbringen. Du bekommst dann einen blitzgescheiten Suchalgorithmus, und einen seitenlangen informationstheoretischen Beweis, dass seine Laufzeitkomplexität $$O(\log{(n-3,51)})$$ beträgt. Deine naive Suche dackelt dagegen mit $$O(n)$$ daher, hat aber den Vorteil, längst fertig zu sein, bis das Obergenie sich seine Strategie zurechtgelegt hat. Dafür ist das Obergenie dann bei Datenmengen mit 10000 Einträgen unglaublich fix. Beeindruckend, aber im konkreten Fall nutzlos.

                  Oder anders formuliert: Ich kaufe kein Sägewerk, um ein Stück von einer Dachlatte abzuschneiden. Für kleine zu durchsuchende Listen wird deine naive Suche immer hinreichend sein. Um sie zu optimieren, muss man aber Rahmenbedingungen kennen, sonst geht die Optimierung fehl. Selbst eine Trivialität wie "Sortiere nach Beginnzeit und führe statt einer sequenziellen Suche eine binäre Suche aus" bringt nur was, wenn Du Einschränkungen für überlappende Intervalle machst. Andernfalls kann dir irgendein ewig langes Intervall aus frühen Morgenstunden böse den Abend verderben.

                  Rolf

                  1. Moin,

                    Oder anders formuliert: Ich kaufe kein Sägewerk, um ein Stück von einer Dachlatte abzuschneiden. Für kleine zu durchsuchende Listen wird deine naive Suche immer hinreichend sein. Um sie zu optimieren, muss man aber Rahmenbedingungen kennen, sonst geht die Optimierung fehl. Selbst eine Trivialität wie "Sortiere nach Beginnzeit und führe statt einer sequenziellen Suche eine binäre Suche aus" bringt nur was, wenn Du Einschränkungen für überlappende Intervalle machst. Andernfalls kann dir irgendein ewig langes Intervall aus frühen Morgenstunden böse den Abend verderben.

                    Diese Rahmenbedingungen sind: Ein zweckmäßiger Default und ein darauf ausgerichtes Fallback. Und der Fall, dass es Geräte geben kann für die es gar keinen Zeitplan gibt, macht den Sinn eines Defaults ja nun besonders deutlich ;)

                    Btw., anstelle Uhrzeiten ist es auch möglich, Funktionen wie sunrise(), sunset() oder bestimmte Event-Listener einzusetzen.

                    MfG

  3. Über² -lappungen (*) habt ihr ja schon gesprochen. Hinzuzufügen wäre noch, aufpassen wenn die Anfangszeit größer als die Endzeit ist. Kommt bei Dingen vor wie 23.00 Uhr bis 1.20 Uhr.

    (*) Es gab schon länger kein Matherätsel mehr im Forum

    1. Hallo encoder,

      Es gab schon länger kein Matherätsel mehr im Forum

      Bitteschön.

      Bis demnächst
      Matthias

      --
      Dieses Forum nutzt Markdown. Im Wiki erhalten Sie Hilfe bei der Formatierung Ihrer Beiträge.
    2. Über² -lappungen (*) habt ihr ja schon gesprochen. Hinzuzufügen wäre noch, aufpassen wenn die Anfangszeit größer als die Endzeit ist. Kommt bei Dingen vor wie 23.00 Uhr bis 1.20 Uhr.

      Hier auch für das erste Interval:

      my $CFG = {
          'Hoflicht' => {
              type    => 'onoff',
              default => 'off',
              times   => ['sunset','sunrise','on','14','14:35','on'], 
              #             16:10    8:30
          },
      

      Und das heißt für die Engine, dass dieses Interval über die Nacht gilt (als eine Frage der Vereinbarung die natürlich kommuniziert werden muss).

  4. io!

    So siehts aus, wer Lust hat, kann sich ja mal am Eintragen einer Planliste testen ;)

    Viele Grüße!