Auswählen eines eindeutigen Bezeichners in C für eine eingebettete Anwendung

Question

Ich versuche derzeit, einen Algorithmus zur Auswahl eines eindeutigen (16-Bit) Bezeichners zu implementieren. Die Herausforderung besteht darin, dies so schnell zu tun, dass nicht zu viel Speicher verbraucht. Die Liste der aktuell verwendeten Kennungen wird ermittelt, indem ein externes Flash-Gerät über eine Sequenz von SPI-Transaktionen abgetastet wird und somit ein relativ langsamer Prozess ist. Auch der Algorithmus wird auf einem kleinen ish-Mikrocontroller laufen, so kann ich nicht wirklich nur alle Einträge in RAM lesen und sie dort verarbeiten.

Die Gedanken, die ich bisher gehabt haben, sind:

1. eine Reihe Auswahl, dann die Liste scannen und sehen, wenn es verwendet wird. Spülen und wiederholen. Lässt davon ab, ziemlich langsam zu sein (besonders wenn dort viele Dateien sind).
2. Wie oben, aber wählen Sie die Nummer mit einem Pseudozufallszahlengenerator mit einem geeigneten Saatgut. Dies hat den Vorteil, dass es weniger wahrscheinlich ist, dass es so viele Iterationen geben wird.
3. Durchsuchen Sie die Liste und füllen Sie ein Array mit allen Einträgen gefunden. Sortieren Sie es und dann wird es trivial. Dies könnte eine enorme Menge an Speicher verwenden.
4. Verwenden Sie eine enorme (okay, lächerlich enorme) Bitmaske. Nicht wirklich praktisch.
5. Akzeptieren, dass die Lebensdauer des Tools ist so dass es weggeschleudert oder "formatiert" lange bevor es 65534 Dateien in den Flash geschrieben hat, so speichern Sie einfach den höchsten Wert bisher im Flash oder Backup-Speicher und halten inkrementieren. Um ehrlich zu sein, würde dies wahrscheinlich sehr gut für diese spezielle Anwendung funktionieren.

Im Moment bin ich grenzend auf entweder die zweite oder die fünfte, aber ich würde mich interessieren jemand zu wissen, ob irgendwelche anderen Gedanken hat. Ich würde gerne denken, dass es einen Algorithmus ähnlich in der Form zu einem CRC, der jede Reihe der Reihe nach verarbeitet werden könnte und geben Sie eine gute Idee von einer Nummer, die nicht verwendet wurde, aber ich habe keine Ahnung wie das funktionieren könnte.

Answer 1

Ich denke, Sie haben hier einige Optionen, aber eine weitere in Betracht zu ziehen ist ein Bloom Filter. Dies hat die Möglichkeit von Fehlalarmen (d. H., Sie können eine ID als bereits verwendet ausschließen, obwohl dies nicht der Fall war), aber Sie können den genauen Speicherplatz auswählen, den Sie diesen Daten zuweisen können.

Answer 2

Ich werde mit 2 gehen. Sei aber vorsichtig, wie Sie den Generator und das Saatgut auswählen. Alle Pseudo-Zahlenfolgen wiederholen sich nach einer gewissen Anzahl von Iterationen. Also müssen Sie Ihre testen, dass es sich nicht zu früh wiederholt.

Answer 3

Ich vermute, dass das FLASH-Gerät aufgrund der Erwähnung von SPI nicht entfernbar ist, aber IIRC-SD-Karten haben einen SPI-Zugriffsmodus, so dass dies möglicherweise nicht wahr ist.

Wenn der FLASH permanent ist und Sie einen robusten, nichtflüchtigen Platz haben, um sich an die letzte ausgegebene ID zu erinnern, dann ist das wahrscheinlich die beste Lösung. Es ist sicherlich schnell und wenig Speicher zur Laufzeit. Es sollte leicht zu erklären, zu implementieren und zu testen sein.

Wenn der FLASH entfernbar ist, dann ist die Verwendung eines Pseudozufallszahlengenerators und das Testen auf Kollisionen wahrscheinlich der richtige Weg. Vorausgesetzt, Ihre Zahlen sind gut verteilt, sind Ihre Chancen auf eine Kollision leicht aus dem Gesamteinsatz vorherzusagen. Wählen Sie einfach einen Generator mit einem anständig langen Wiederholungsintervall. Es kann eine gute Idee sein, dies in einer Simulation als Akzeptanztest für den ausgewählten Algorithmus nachzubilden.

Answer 4

Ich würde versuchen, eine Variante von 3. Anstatt eine sortierte Reihe von Werten zu speichern, würde ich eine sortierte Reihe von Bereichen speichern.

Answer 5

Ich frage mich, warum Sie nicht einfach die letzte ID speichern und erhöhen. Gibt es einen Grund, warum Sie zögern? Du gibst keinen zu deiner Frage, nur eine allgemeine Unruhe.

Wenn die ID aus Sicherheitsgründen etwas zufällig sein soll, verwenden Sie einen Zufallsgenerator und speichern Sie die aktuellen Registerwerte des Generators im Flash-Speicher. Auf diese Weise können Sie sie für die nächste ID laden, die sicherstellt, dass Sie die volle Zykluslänge ohne Wiederholungen erhalten, wenn Sie Ihren Algorithmus sorgfältig auswählen.

[EDIT] Da es sich um Kollisionen handelt, müssen einige Daten vorhanden sein, in denen die Kollision auftreten kann, z. B. in Dateinamen oder dergleichen. Wenn der naheliegende Ansatz (erstellen Sie einen Dateinamen und überprüfen Sie, ob es existiert) ist zu langsam und Sie haben große Lücken in der "Zuordnung", dann generieren Sie eine zufällige ID und damit zu überprüfen. Dies sollte Ihnen ermöglichen, eine ungenutzte ID mit nur wenigen Iterationen zu finden.

Answer 6

Wie viel RAM haben Sie? Es ist ein bisschen schwer zu sagen, "Embedded" kann heutzutage so viel bedeuten. :) Eine Bitmap benötigt 8192 Bytes für die Dauer der Generierung und garantiert jedes Mal perfekte Ergebnisse.

Ich habe auch eine Art "spärliche" Bitmap betrachtet, aber ich kenne keine passende Datenstruktur, aber es lohnt sich, sie zu untersuchen.

Answer 7

Wenn nicht genügend RAM vorhanden ist, um eine Bitmap zu erstellen, die groß genug für 64K Einträge ist, kann die Anzahl der Scans durch FLASH zur Suche nach einer ungenutzten ID reduziert werden, indem für jeden Scan eine kleinere, temporäre Bitmap verwendet wird. Eine 16-Byte-Bitmap könnte gefundene IDs im Bereich von 0 bis 255 im ersten Durchgang, 256 bis 511 im zweiten Scan usw. am Ende jedes Scanvorgangs aufzeichnen, wenn mindestens ein nicht markiertes Bit in der Bitmap vorhanden ist. Wieder getan. Ich glaube, das würde in Kombination mit der Verwendung eines zufälligen Startbereichs gut funktionieren.

Auf der anderen Seite, wenn ich hohes Vertrauen in Option 5 hätte, könnte ich einfach damit gehen.

Answer 8

Halten Sie eine laufende Zählung eine sequentielle ID.
Führen Sie die ID über MD5.
Verwenden Sie die niedrigsten 16-Bit.

Die Theorie ist, dass MD5 einen anderen Hash für jede Eingabe erstellt. Die niedrigsten 16 Bits sollten genauso "zufällig" wie der gesamte Hash sein.

Answer 9

Wenn Sie größere IDs verwenden könnten, wäre 5 ein Kinderspiel.

Answer 10

über Ihre CRC ähnlichen Algorithmus Interesse ...

Es scheint, dass Sie für einen Algorithmus suchen, der nicht durch eine zufällige Liste von weniger als 64 KB 16-Bit-Zahlen und erzeugen eine neue 16-Bit-Zahl laufen schon in der Liste; vorzugsweise tun Sie dies in einem einzigen Durchgang durch die angegebene Liste.

Wenn die Reihenfolge, in der IDs freigegeben werden, keine Beziehung zu der Reihenfolge hat, in der sie zugewiesen sind (wie ich denke, ist Ihr Fall), können Sie nichts mit der Generierung oder Zuweisung der IDs für Ihren Algorithmus tun.

Die beste Wette scheint dann 5 von Ihrer Liste zu sein.

Wenn Sie abenteuerlich sind ...

und können, wenn Sie wieder Nummer Ihre IDs (dh eine zugeordnete ID an einen anderen nicht zugeordneten ID ändern), können Sie einmal eine ‚defrag‘ Art von Iteration laufen konnte in eine Weile, um alle zugewiesenen IDs auf niedrigere Werte zu verschieben und die höchste freie ID-Nummer für die nächste Zuweisung zu finden. Es würde helfen, sich an die Gesamtzahl der Zuteilungen und Freigaben zu erinnern, die seit dem letzten derartigen "Defrag" -Lauf durchgeführt wurden. Ordnen Sie das Inkrementieren fortlaufend beginnend mit 0 zu.

Auf diese Weise müssen Sie sich nur 3 unsigned short Ganzzahlen im Speicher merken. Und ja, nehmen Sie von Zeit zu Zeit eine etwas kostspielige Neuzuordnungs-Iteration basierend auf ihren Werten.

Answer 11

Eine andere Option wäre, eine Datei mit gültigen IDs auf dem Flash-Laufwerk zu behalten. Auf diese Weise werden nicht jedes Mal alle Möglichkeiten abgefragt. Wenn Sie zufällige IDs wünschen, dann randomisieren Sie die Datei. Speichern Sie den Offset als letzten Wert in der Datei. Wenn Sie einen benötigen, entfernen Sie den letzten aus der Datei, und wenn Sie einen löschen, fügen Sie ihn zurück zur Datei hinzu. Mit dem Offset und einem Flash-Laufwerk sollte es eine nahezu konstante Operation sein, unabhängig von der Anzahl der verbleibenden IDs. Als Bonus wird Ihnen der Offset zu Beginn sagen, wie viele IDs Sie noch haben, wenn Sie das an irgendeinem Punkt wissen müssen. Der Nachteil wäre, dass Sie für jede ID auf den Flash-Speicher zugreifen müssen (konstante Zeit, aber immer noch ein Zugriff), und wie der Fall behandelt wird, wenn die Datei nicht vorhanden ist.

Answer 12

Verwenden Sie eine Maximal Linear Feedback Shift Register und speichern Sie den zuletzt ausgegebenen Wert. Ein LFSR gibt Ihnen bei einem bestimmten Startpunkt (ohne Null) alle Zahlen in der Reihenfolge 1..2^n in einer Pseudozufallsreihenfolge. Wenn Sie mit dem Element kth beginnen, erhalten Sie immer das gleiche k + 1-te Element. Die Implementierung ist winzig:

if (IsEven(sequence)) { 
    sequence /= 2; 
} 
else { 
    sequence = (sequence/2)^feedback; 
} 

wo Feedback ein Bitmuster aus einer Tabelle der maximalen Feedbacks für die Anzahl der Bits, die Sie generieren möchten. Das heißt, um die nächste Nummer zu generieren, lesen Sie die letzte ausgegebene Nummer, führen Sie sie durch den obigen Code und verwenden Sie sie dann.

Abwechselnd, warum zählen Sie nicht gerade und speichern die letzte ausgegebene Nummer?