Ich möchte Anfragen aus einem Stream so schnell wie möglich abgleichen

Question

Ich verwende eine Karte, um eingehende Anfragen zu erfüllen. Ich möchte diese Anfragen mit ihrem Paar abgleichen, sobald ich sie bekomme. Ordnung ist wichtig, weil es zuerst kommt, zuerst, um zusammenzupassen. Vermeiden von unnötigen Vorgängen ist eine Voraussetzung. Mein Verständnis ist, dass Hash-Maps schneller als Array-Iterationen sind und Maps die Reihenfolge beibehalten. Was ist die beste Implementierung für die Zuordnung von Streaming-Objekten mit wenig oder gar keiner räumlichen oder zeitlichen Komplexität? Die Datenstruktur ist nicht in Stein gemeißelt, sie kann modifiziert und in jedem beliebigen Format optimiert werden, solange die Information nicht verloren geht. Nach meinem Verständnis ist das Beste, was erreicht werden kann, O (n). Ein anderes Problem, mit dem ich beim Hashing konfrontiert bin, ist das Überschreiben von Duplikaten in der Warteschlange. Das habe ich.

function* match(items, identity, remaining = new Map()) { 
 
    for (let item of items) { 
 
    let id = identity(item); 
 
    let pair = x =>({type:x.type==="passenger"? "driver": "passenger", direction:x.direction,   time:x.time}) 
 
    let key = item=> item.type + item.direction + item.time; 
 
    let candidate = remaining.get(key(pair(id))); 
 
    if (candidate) { 
 
     remaining.delete(key(pair(id))); 
 
     yield [item, candidate]; 
 
    } else { 
 
     remaining.set(key(id), item); 
 
    } 
 
    } 
 
} 
 
// Example: 
 
let items = [{ 
 
    type: 'driver', 
 
    direction: 'east', 
 
    time: '9:15', 
 
    name:['Archibald Trump'] 
 
    },{ 
 
    type: 'passenger', 
 
    direction: 'east', 
 
    time: '9:15', 
 
    name:['Bacon Eater'] 
 
    },{ 
 
    type: 'passenger', 
 
    direction: 'east', 
 
    time: '9:15', 
 
    name:['Banjo Barney'] 
 
    },{ 
 
    type: 'passenger', 
 
    direction: 'east', 
 
    time: '9:15', 
 
    name:['Flimsy Stick'] 
 
    }, { 
 
    type: 'passenger', 
 
    direction: 'west', 
 
    time: '9:30', 
 
    name:['Big Red'] 
 
    },{ 
 
    type: 'passenger', 
 
    direction: 'west', 
 
    time: '9:35', 
 
    name:['Hathaway Anne'] 
 
    }]; 
 
let remaining = new Map(); 
 
let pairs = match(items, item => item, remaining); 
 
console.log('pairs',...pairs); 
 
console.log('remaining',...remaining.values());

Answer 1

Encapsulation & Raum Komplexität:

Ihre Nutzung von Set ist angemessen, aber der Code kann durch Einkapseln der passende Funktionalität und das Loswerden von Globals verbessert werden. Ich schlage vor, einen Generator, der wie folgt passende Paare ergibt mit reduzierter Speicherkomplexität:

// Match items with first equal match: 
 
function* match(items, equals, remaining = new Set()) { 
 
    items: 
 
    for (let item of items) { 
 
    for (let candidate of remaining) { 
 
     if (equals(item, candidate)) { 
 
     remaining.delete(candidate); 
 
     yield [item, candidate]; 
 
     continue items; 
 
     } 
 
    } 
 
    remaining.add(item); 
 
    } 
 
} 
 

 
// Example: 
 
let items = [1, 2, 5, 3, 3, 4, 2, 1, 4]; 
 
let remaining = new Set(); 
 
let pairs = match(items, (a, b) => a == b, remaining); 
 

 
console.log(...pairs); 
 
console.log(...remaining);

auf Ihre Artikel Je würden Sie brauchen einen passenden equals Rückruf zu liefern. In Ihrem Fall:

let pairs = match(
    items, 
    (a, b) => 
    a.type !== b.type && 
    a.direction === b.direction && 
    a.time === b.time, 
    remaining 
); 

Optimierung:

Wenn Sie Anfragen an primitiven Identitätswerte abbilden könnten, könnten Sie die for (let i of memo) { ... } Schleife mit einem einfachen Karte Lookup ersetzen. Die Zeitkomplexität für die Paarung von n Elementen reduziert sich dann auf O(n).

Da jedoch keine identischen Artikel, sondern Artikel mit entgegengesetzter type-Eigenschaft übereinstimmen, ist diese Optimierung nicht direkt anwendbar. Sie müssen einen weiteren Rückruf hinzufügen, der uns die erwartete ID eines passenden Artikels liefert.

Auch, weil Sie mehrere Anfrage mit identischen Identität auftreten können, müssen Sie ein multimap:

// Multimap insertion: 
 
function insert(map, key, value) { 
 
    let values = map.get(key); 
 
    if (values) values.push(value); 
 
    else map.set(key, [value]); 
 
} 
 

 
// Multimap retrieval: 
 
function retrieve(map, key) { 
 
    let values = map.get(key); 
 
    if (values) { 
 
    let value = values.pop(); 
 
    if (values.length === 0) map.delete(key); 
 
    return value; 
 
    } 
 
} 
 

 
// Match items with first identical match: 
 
function* match(items, identity, match, remaining) { 
 
    for (let item of items) { 
 
    let candidate = retrieve(remaining, match(item)); 
 
    if (candidate) yield [item, candidate]; 
 
    else insert(remaining, identity(item), item); 
 
    } 
 
} 
 

 
// Example: 
 
let items = [{ 
 
    type: 'driver', 
 
    direction: 'east', 
 
    time: '9:15', 
 
    name: ['Archibald Trump'] 
 
}, { 
 
    type: 'passenger', 
 
    direction: 'east', 
 
    time: '9:15', 
 
    name: ['Bacon Eater'] 
 
}, { 
 
    type: 'passenger', 
 
    direction: 'east', 
 
    time: '9:15', 
 
    name: ['Banjo Barney'] 
 
}, { 
 
    type: 'passenger', 
 
    direction: 'east', 
 
    time: '9:15', 
 
    name: ['Flimsy Stick'] 
 
}, { 
 
    type: 'passenger', 
 
    direction: 'west', 
 
    time: '9:30', 
 
    name: ['Big Red'] 
 
}, { 
 
    type: 'passenger', 
 
    direction: 'west', 
 
    time: '9:35', 
 
    name: ['Hathaway Anne'] 
 
}]; 
 

 
let remaining = new Map(); 
 
let pairs = match(
 
    items, 
 
    item => '' + (item.type == 'driver') + item.direction + item.time, 
 
    item => '' + (item.type == 'passenger') + item.direction + item.time, 
 
    remaining 
 
); 
 

 
console.log(...pairs); 
 
console.log(...remaining.values());

Die Laufzeitkomplexität der obigen Implementierung ist nicht leicht zu bestimmen, wie es auf der Laufzeit hängt Komplexität von Array.shift() und Array.push(). Wenn wir jedoch davon ausgehen, dass solche Schlüsselkollisionen selten sind oder davon ausgehen, dass die JavaScript-Engine beide Methoden in amortisierter konstanter Zeit ausgeführt hat, könnten wir immer noch eine O (n) Laufzeitkomplexität für n Elemente erwarten.

Answer 2

Karten sind schneller als Arrays. Sie können viel schneller auf einen Map-Schlüssel zugreifen, als jedes Mal ein Array durchlaufen zu müssen. Hier ist Ihr Beispiel mit einer Karte.

var pairs = []; 
 
var memo = {}; 
 

 
function pair(item) { 
 
    var key = item.type.toString() + item.direction + item.time; 
 
    if(memo[key]) { 
 
     pairs.push(item); 
 
     delete memo[key]; 
 
    } else { 
 
     memo[key] = item; 
 
    } 
 
} 
 

 
var ar = [{ 
 
    type: true, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: false, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: true, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: false, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: true, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: false, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: true, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: false, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: true, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: false, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: true, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: false, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: false, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: false, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: false, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: false, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: false, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: false, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: false, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: false, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: false, 
 
    direction: false, 
 
    time: '9:00' 
 
}, { 
 
    type: false, 
 
    direction: false, 
 
    time: '9:00' 
 
}]; 
 

 
for (let it of ar) { 
 
    pair(it); 
 
} 
 

 
console.log('matching pairs: ', pairs); 
 
console.log('left over nonmatching pairs:', Object.values(memo));