Entwerfen Sie die Datenstruktur eines Echtzeit-Handelssystems mit STL

Question

Mein Design für dieses Problem ist am unteren Rand. Jede es einfacher zu machen, schlägt vor, schneller willkommen

Problem:

Ein System sammelt gebrauchtes Auto kaufen/verkaufen Raten in Echtzeit. Entwerfen Sie eine Datenstruktur mit STL, um in Echtzeit die besten verfügbaren Angebote zu analysieren.

Zitat Format:

timestamp | model | dealer | buy rate | sell rate 

• Timestamp: eine ganze Zahl einen eindeutigen Zeitstempel für jedes Zitat darstellt
• Model: eine Zeichenfolge, die Automodell
• Dealer darstellt: ein String, der den Namen des Händlers darstellt
• Buy rate: eine Gleitkommazahl, bei der der Händler diese c kaufen möchte ar Modell
• Sell rate: eine Gleitkommazahl, bei der der Händler dieses Automodell verkaufen möchte
• Angenommen, die Zahlen von Händler und Automodell liegen beide in der Größenordnung von 100; Zitat

ist in der Größenordnung von mehreren hundert Millionen jeden Tag.

Beschreibung:

Entwerfen Sie eine Datenstruktur, die einen Strom von Zitaten nimmt und den besten Kauf und das beste Verkaufsangebot für ein bestimmtes Automodell bei jedem neuen Angebote.

Der beste Kauf ist der Händler, der den größten Kaufwert anbietet, während der beste Verkauf der Händler ist, der den niedrigsten Verkaufswert bietet.

Hier sind einige Beispiele:

1. Eingang:

1| Model1 | Dealer1 | 1.1 | 1.2 

Ausgang:

Best Model1 Buy = 1.1 from Dealer1 

Best Model1 Sell = 1.2 from Dealer1 

2.

Eingang:

1| Model1 | Dealer1 | 1.1 | 1.2 

2| Model1 | Dealer2 | 1.1 | 1.15 

Output:

Best Model1 Buy = 1.1 from Dealer1 

Best Model1 Sell = 1.2 from Dealer1 

Best Model1 Buy = 1.1 from Dealer1 //stay with old dealer if price is the same 

Best Model1 Sell = 1.15 from Dealer2 

3.

Input:

1| Model1 | Dealer1 | 1.1 | 1.2 

2| Model1 | Dealer2 | 1.1 | 1.15 

3| Model1 | Dealer3 | 1.15 | 1.2 

Output:

Best Model1 Buy = 1.1 from Dealer1 

Best Model1 Sell = 1.2 from Dealer1 

Best Model1 Buy = 1.1 from Dealer1 

Best Model1 Sell = 1.15 from Dealer2 

Best Model1 Buy = 1.15 from Dealer3 // Dealer 3 offers highest buy rate 

Best Model1 Sell = 1.15 from Dealer2 

4.

Input:

1| Model1 | Dealer1 | 1.1 | 1.2 

2| Model1 | Dealer1 | 1.0 | 1.3 

Output:

Best Model1 Buy = 1.1 from Dealer1 

Best Model1 Sell = 1.2 from Dealer1 

Best Model1 Buy = 1.1 from Dealer1 //New quote will invalidate old quote 

Best Model1 Sell = 1.3 from Dealer1 

5.

Input:

1| Model1 | Dealer1 | 1.1 | 1.2 

2| Model1 | Dealer2 | 1.05 | 1.25 

3| Model1 | Dealer1 | 1.0 | 1.3 

Output:

---

Hier ist mein Design

struct Maps 

{ 

unordered_map<string /*Dealer Name*/, Quote> Dealer; 

multimap< int /* Buy rate*10 */, Quote> Buy; 

multimap< int /* Sell rate*10 */, Quote> Sell; 

} 

1. unordered_map< string /* car model */, Maps > CarModelHashMap //Main hashmap

2. unordered_map<string /*Dealer Name*/, Quote> Dealer; //Each time we get a new quote, update this hashmap

3. multimap< int /* Buy rate*10 */, Quote> Buy; //In ascending order, fast lookup for largest buy rate, //Each time Dealer map is updated, update this Buy map as well.

4. multimap< int /* Sell rate*10 */, Quote> Sell; //In descending order, fast lookup for smallest sell rate, //Each time Dealer map is updated, update this sell map as well.

Gedanken:

HashMap bietet konstante Lookup-Zeit. Multimap hält die Reihenfolge aufrecht und bietet eine konstante Nachschlagezeit für den maximalen/minimalen Wert und log (n) für das Einfügen.

Doch jede Karte behält ihre eigene Kopie von Zitat, die Art von Verschwendung von Speicher ist. Auch jedes Mal, wenn wir das Angebot in Dealer hashmap einfügen/aktualisieren, müssen wir das alte Angebot anhand seiner Kauf-/Verkaufsrate in der Buy/Sell-Multimap suchen und entsprechend aktualisieren, um es mit Händler hashmap zu synchronisieren.

Ich frage mich, ob es ein besseres/einfacheres Design gibt, um Speicher zu sparen und die Synchronisierung verschiedener Karten zu vermeiden?

Dank

Answer 1

In Ihrem Fall ein optimaler Lösung Speicher Abfälle.

Eine optimale Lösung besteht darin, alle Datensätze in eine std::vector, wörtlich zu setzen.

Erstellen Sie als nächstes Indextabellen von {Schlüssel, Zeiger auf Element in Vektor}. Eine Tabelle für jeden Suchschlüssel. Normalerweise funktioniert ein std::map gut als eine Indextabelle.

Die Regel ist, dass Sie die Indextabelle mit einem Schlüssel suchen. Wenn ein Datensatz in der Indextabelle gefunden wird, extrahieren Sie den Zeiger. Verwenden Sie den Zeiger, um auf den Datensatz zu verweisen.