Video: Wie Algorithmen Obst sortieren 2024
Stellen Sie sich vor, Sie versuchen ein Element in einer Liste zu finden, ohne es zuerst zu sortieren. Jede Suche wird zu einer zeitaufwendigen sequentiellen Suche. Aber es kann ein Fall dafür gemacht werden, dass Daten für Algorithmen nicht sortiert werden. Schließlich sind die Daten auch dann noch zugänglich, wenn Sie sie nicht sortieren - und das Sortieren braucht Zeit.
Natürlich ist das Problem mit unsortierten Daten das gleiche Problem wie die Junk-Schublade in Ihrer Küche (oder wo auch immer Sie Ihre Junk-Schublade haben - vorausgesetzt, Sie finden sie überhaupt). Suchen Sie nach etwas in der Junk-Schublade ist zeitaufwendig, weil Sie nicht einmal anfangen können, zu erraten, wo etwas zu finden. Anstatt nur nach innen zu greifen und zu nehmen, was Sie wollen, müssen Sie unzählige andere Dinge herausnehmen, die Sie nicht wollen, um den einen Artikel zu finden, den Sie brauchen. Leider ist der Gegenstand, den Sie benötigen, möglicherweise nicht in der Junk-Schublade - Sie haben ihn vielleicht weggeworfen oder in eine andere Schublade gesteckt.
Die Junk-Schublade in Ihrem Heim ist genau wie unsortierte Daten auf Ihrem System. Wenn die Daten unsortiert sind, müssen Sie jeweils nur ein Element durchsuchen, und Sie wissen nicht einmal, ob Sie das finden, was Sie benötigen, ohne zuerst jedes Element im Datensatz zu durchsuchen. Es ist eine frustrierende Art, mit Daten zu arbeiten.
Natürlich genügt es nicht, die Daten einfach zu sortieren. Wenn Sie eine Mitarbeiterdatenbank haben, die nach dem Nachnamen sortiert ist und dennoch einen Mitarbeiter nach dem Geburtsdatum suchen muss, ist die Sortierung nicht sinnvoll. (Angenommen, Sie möchten alle Mitarbeiter finden, die an einem bestimmten Tag Geburtstag haben.) Um das Geburtsdatum zu ermitteln, das Sie benötigen, müssen Sie immer noch den gesamten Datensatz einzeln durchsuchen. Folglich muss sich die Sortierung auf einen bestimmten Bedarf konzentrieren. Ja, Sie haben die Mitarbeiterdatenbank an einer Stelle nach Nachnamen und nach Nachnamen zu einem anderen Zeitpunkt sortiert, aber jetzt müssen Sie sie nach dem Geburtsdatum sortieren, um die Datenmenge effektiv nutzen zu können.
Die Notwendigkeit, mehrere sortierte Aufträge für dieselben Daten zu verwalten, ist der Grund dafür, dass Entwickler Indizes erstellt haben. Das Sortieren eines kleinen Index ist schneller als das Sortieren des gesamten Datasets. Der Index behält eine spezifische Datenreihenfolge bei und zeigt auf das vollständige Dataset, so dass Sie schnell finden können, was Sie benötigen. Indem Sie für jede Sortieranforderung einen Index pflegen, können Sie die Datenzugriffszeit effektiv verkürzen und mehreren Personen erlauben, gleichzeitig auf die Daten in der Reihenfolge zuzugreifen, in der sie darauf zugreifen müssen.
Es gibt viele Möglichkeiten Sortieralgorithmen zu kategorisieren. Einer dieser Wege ist die Geschwindigkeit der Sorte. Bei der Betrachtung der Effektivität eines bestimmten Sortieralgorithmus beim Anordnen der Daten berücksichtigen Timing-Benchmarks in der Regel zwei Faktoren:
- Vergleiche: Um Daten von einem Speicherort eines Datasets zu einem anderen zu verschieben, müssen Sie wissen, wohin der Speicherort verschoben werden soll. Dies bedeutet, dass die Zieldaten mit anderen Daten im Dataset verglichen werden.Weniger Vergleiche bedeuten eine bessere Leistung.
- Austäusche: Abhängig davon, wie Sie einen Algorithmus schreiben, können die Daten beim ersten Versuch nicht an ihren endgültigen Speicherort im Datensatz gelangen. Die Daten könnten sich tatsächlich mehrmals bewegen. Die Anzahl der Austauschvorgänge beeinflusst die Geschwindigkeit beträchtlich, da Sie jetzt tatsächlich Daten von einem Speicherort zu einem anderen im Speicher verschieben. Weniger und kleinere Börsen (wie bei Indizes) bedeuten eine bessere Performance.
