Wie berechnet man die absolute Mindestanzahl von Änderungen, um einen Sortierreihenfolge in eine andere umzuwandeln?

Question

Wie berechnet man die absolute Mindestanzahl von Änderungen, um einen Sortierreihenfolge in eine andere umzuwandeln?

8

Ziel

Wie kann man die Daten kodieren, die beschreiben, wie man eine statische Liste von einer Bestellung in eine andere bestellen kann, indem man die minimale Anzahl von möglichen Bytes verwendet?

Ursprüngliche Motivation

Ursprünglich entstand dieses Problem während der Arbeit an einem Problem, bei dem Sensordaten mittels teurer Satellitenkommunikation weitergeleitet wurden. Ein Gerät hatte eine Liste von etwa 1.000 Sensoren, die überwacht wurden. Die Sensorliste konnte nicht geändert werden. Jeder Sensor hatte eine eindeutige ID. Alle Daten wurden intern für eine spätere Analyse protokolliert. Das einzige, was Endbenutzer täglich benötigten, war, welcher Sensor in welcher Reihenfolge ausgelöst wurde.

Das gesamte Projekt wurde verschrottet, aber dieses Problem scheint zu interessant zu sein, um ignoriert zu werden. Auch vorher habe ich über "Swaps" gesprochen, weil ich an den Sortieralgorithmus gedacht habe, aber eigentlich ist es die Gesamtordnung, die wichtig ist, die Schritte, die erforderlich sind, um zu dieser Reihenfolge zu gelangen, wären wahrscheinlich egal.

Wie die Daten bestellt wurden

In SQL-Begriffen könnte man sich das so vorstellen.

%Vor%

Annahmen

Die Startliste und die Endliste bestehen aus genau dem gleichen Satz von Elementen
Jeder Sensor hat eine eindeutige ID (32-Bit-Ganzzahl)
Die Größe der Liste beträgt ungefähr 1.000 Elemente
Jeder Sensor kann mehrmals pro Minute oder gar nicht tagelang ausgelöst werden
Nur die Änderung der ID-Sortierreihenfolge muss weitergeleitet werden.
Rechenressourcen zur Ermittlung optimaler Lösungen sind billig / unbegrenzt
Datenkosten sind teuer, ungefähr ein Dollar pro Kilobyte.
Daten konnten nur als Ganzbyte (Oktett) Inkremente
Die Reihenfolge von Tag 0 ist dem Sender und Empfänger bekannt, mit dem
Nehmen Sie jetzt an, das System funktioniert einwandfrei und es ist keine Fehlerprüfung erforderlich

Wie gesagt, das Projekt / die Hardware ist nicht mehr so, das ist jetzt nur ein akademisches Problem.

Die Herausforderung!

Definieren Sie einen Encoder

Gegeben A. Tag N Sortierreihenfolge
Gegebene B. Tag N + 1 Sortierreihenfolge
Liefert C eine Sammlung von Bytes, die beschreiben, wie man A in B umwandelt, indem man die kleinste mögliche Anzahl von Bytes verwendet

Definieren Sie einen Decoder

Gegeben A. Tag N Sortierreihenfolge
Gegeben B. eine Sammlung von Bytes
Zurückgeben C. Tag N + 1 Sortierreihenfolge

Viel Spaß mit allen.

algorithm optimization computer-science sorting

Great Turtle 15.01.2010, 21:27

quelle

1 Antwort

Tags und Links algorithm optimization computer-science sorting

Django: Verwenden von Annotate, Count und Distinct in einem Queryset WebRequest.GetResponse dauert sehr lange, es sei denn, DefaultWebProxy wird auf Null gesetzt

score 1 · Answer 1

Als akademisches Problem wäre ein Ansatz, den Algorithmus P Abschnitt 3.3.2 von Band II von Knuths Kunst der Computerprogrammierung zu betrachten, der jede Permutation von N Objekten in eine ganze Zahl zwischen 0 und N! -1 abbildet. Wenn jede mögliche Permutation zu jeder Zeit gleich wahrscheinlich ist, dann ist das Beste, was Sie tun können, diese (Vielpräzisions-) Ganzzahl zu berechnen und zu übertragen. In der Praxis geben Sie jedem Sensor eine 10-Bit-Zahl und verpacken diese 10-Bit-Zahlen dann, so dass Sie z.B. 4 Zahlen, die in jeden Block von 5 Bytes gepackt wurden, würden fast genauso gut funktionieren.

Schemata, die auf Diff- oder Off-Shelf-Komprimierung basieren, nutzen das Wissen, dass nicht alle Permutationen gleich wahrscheinlich sind. Je nachdem, welches Gerät Sie verwenden, können Sie davon Kenntnis haben, oder Sie können anhand der vorherigen Daten sehen, ob dies der Fall ist. Gut, wenn es funktioniert. In einigen Fällen mit Sensoren und Satelliten könnten Sie sich über seltene Ausnahmen Gedanken machen, bei denen Sie im schlimmsten Fall das Verhalten Ihres Komprimierungsschemas bekommen und plötzlich mehr Daten übertragen werden, als Sie erwartet haben.